Monday, 7 May 2012

A bit more advanced motion planning ... Revenge of the zombies

Some words on the blog  (You can ignore this)...

Before I start this post, I am taking these opportunity to write something about the blog itself..

No one will like to read this, so let's keep it short..
 
In short, I made a banner for my blog using GIMP which you can see on the top instead of the text.. 
You can download the banner here if you wish and use anywhere, but don't remove the blog link..

Actually this is a stripped down-version of this image I made today using free GIMP brushes and fonts...
If you didn't notice, this image has a secret word hidden in the title itself !! Did you get it?
 You can get it here and also you can share it freely...
That's all about it, the real post starts here...

The post starts here...

FYI, this post is a continuation of the previous post on Easy Motion Planning made yesterday..

You must read the previous post, if you already haven't, to understand the context of this post..

I told something about optimization on the last post, but instead what I came up with is an algorithm for finding shorter route (compared to the previous one)...

But, unfortunately, this shorter route comes with a lot of sacrifice in terms of memory usage ..

I have always sticked to my philosophy of adding one example game to every theoretical concept offered in this blog and this one isn't a exception too, but, as I already said the game can slowdown a lot, specially if you move away from the zombies to a greater distance in a condition where there are numerous obstacles in between...

The example game is present here in .gmk format and here in .exe format..

Theoretical Concept (A better zombie arrives in the scene..)

 The main concept is a bit more detailed this time and so, it needs to be elaborated from the start...

Remember the previous zombie-human hide-and-seek game ??

Well, they unfortunately couldn't take down the lonely human that time because they weren't intelligent enough ....
So, they decide to learn from a human-vs-human hide-and-seek game and learn their strategy..

Zombies learn a thing or two :

They notice a few wonderful things :

  • Humans don't change their direction of motion only when they hit an obstacle..
       They become aware of the obstacle from a distance and plan their motion before-hand before hitting an 
       obstacle and are usually able to avoid it...

       So, in a hide-and-seek game with obstacles, they are planning their motion virtually at every moment..
  • Humans move in curved paths..
          They were confused how humans can move in curved paths !!
 
          After all, till now, they could move only in straight line...
 
          But in the end a wise zombie came up with this:
 
          Why not make small linear movements such that it appears curved as a whole??
 
           They already knew linear motion and so it wasn't hard for them to grasp the concept...
  • Humans are ugly (What!! I am serious!) 
          After all, the zombies saw only their male counterparts :D

Learn and evolve:

As soon as they noticed how humans perform well in Hide-and-Seek game, 
they were bent on imitating all those good things to better their performance ....

A better strategy:

The zombies change their strategy for good and here's what they come up with:

1. If there's a linear motion possible towards the human from your current position, always take that route...
    (After all, those fancy curved motion ain't the least-distance paths in this case)

2. If there's no linear path available,
    A. At first, you'll scan your nearby places (like the previous strategy)
       starting from closest places and gradually moving to far away places with the help of a (hypothetical) 
       instrument which can tell you if you'll be able to see that human if you move to a certain point or not 
       (without  physically moving to that place) and also check if the path to that point is obstruction-free
    B. Now, if you don't find such a point, you just hope that some other zombie will find him...
        But, as in most cases, you'll find one, which is your "local goal".
        So, when you have that point, you just don't start moving towards that point and stop when you reach 
        it...
        Instead you take only a single step towards it and reanalyze the situation starting from point 1.

So, what's the big deal?

Well, you have to do a lot of analysis for sure, because you decide your next step wisely in every instant..

But, as a reward, you get all this:

1. You'll always know the position of your enemy, and you don't follow any obsolete "local goal" 
   (As the player is usually always in motion, your local goal is bound to change every instant..
     There was this problem with the previous approach that you continue to move towards your "local goal"
     even when it isn't the best motion possible, as the player changes position...)
2. You don't ever collide against a obstruction 
    (unless moving along the perimeter of the obstruction is the best possible route... 
     even in that case it isn't technically a collision...)
3. You move along a shorter path
   ( As your strategy is decided in real time, you don't move through longer path wasting some time...
      This is a direct impact of  the absence of "obsolete goals")
4. And can you believe this !!!
    Your motion, in some cases, appear to be curved in nature....

Verdict

What verdict!! 

Don't ask me if the zombies won or lost.... They don't PM me so often...
In case, they ever decide to, I'll surely share it with you ....

Ok, enough is enough !!

In a more serious tone, though, I think this more advanced Motion Planning has its own advantages and disadvantages...
It follows a much shorter path, for sure, but it isn't practical to  make the basic zombies this advanced because, of course,
a) it'll waste a lot of processing power 
(as it has to plan its next step every instant whereas the basic motion planning required such decisions only when it collided against an obstacle)
b) it'll make the game harder for the player...

So, it is usually better to use this motion planning algorithm only in case of "Boss zombies" or a army of "elite zombies"...
Whatever it is, in the end, always remember to keep the number of such zombies as low as possible....


The END ??

So, here ends my second post on Motion Planning 
And as I can feel, I will have a "overdose of motion planning" if I continue to post on this topic...
To be true, I don't have any more views to offer on this topic at the moment...

Though if I ever come across any fresh idea on this topic, I'll be sure to post theme here ..

So, there will be a change of taste in the next blog post:

The next post is going to be on one of those platforming tutorials I mentioned here ...

So, still tomorrow, good bye...

1 comment:

  1. Guess Who !7 May 2012 23:55

    You can make the zombies utilize the A* algorithm, which will be slightly more complicated than this, but will also have a better chance of the zombie succeeding (good for harder difficulty levels)..

    ReplyDelete