Saturday 5 May 2012

Easy Motion planning

Original post

Hey mate! I forgot your name from G+.. Here's what you wanted..
Zombie game fixed 
Hopefully you've re-downloaded it.. (If your downloaded version has a constant val, then it's the correct one)..
 I've changed it a bit..
I've defined a constant val to tweak the values ... Change its value to tweak the performance .. 40 (default) is pretty fine..
It's working pretty good ... Just the way I planned .. Without real motion planning...

Detailed post

Prologue

James Clerk  on Google+ asked me:

" As for my problem, it's based around Step Towards Point being removed from the D&D options. Turns out all MP (Motion Planning) functions were removed, so my game can't port to HTML5 properly.
What I wanted was for object A (A zombie) to move towards object B (The player), and if it came in contact with a solid object, he would move around it and continue to the player.
However, while the functions can be called in Studio/HTML5, they only do linear paths, and the zombies get caught on solid objects still."

This was in reference to his online zombie game here.

As he is going to edit his game, I will be hosting it on my dropbox account soon..

So, he asked me if I could help him solve it and there was a big bonus for completing this task .....

I'll get my first subscriber for this blog...

 My reply was:

Oh.. I checked your zombie game.. Is that the problem?.. 
Yup, I remember your zombies (your zombies.. :D) getting stuck at RIP stones.. 
If that is the problem, I can give you some easy solutions but specific only to that game...

I promised him that I will post a solution within 6 hours but in my count, I took about 30 minutes more though...

You can find the file .GMK file above ...

(As this post is GM-specific and doesn't use any pro-only function, so I am doing away with the .EXE version)

So, here I'll try to break up how the solution works
(even though it's far less advanced than motion planning, it works quite fine)...

James told that he will be looking forward to it and so here's the detailed explanation  of the solution...

Basic Theoretical Concept 

 

The main concept is  whenever the zombie is stuck because the straight line path to the player is blocked, give the zombie a local goal (which is the closest possible position from where it can make a straight motion to the player) and when the zombie reaches that local goal, change it's goal to the x and y-position of the player..

What is this goal thing you're telling??

The goal is a point on the current room of the game towards which the zombie will try to move in a straight line path ..

Please define the term "try" ??

"Try" here refers to a simple linear movement from one position to another unless it is obstructed by a RIP stone (i.e. a solid obstacle), in which case it will simply stop...

Is it this simple? Or, can you explain the concept in more details?

I have to break the truth.. It isn't that simple..
Even if the theoretical concept sounded perfect, here are some complexities..
I'll try to add  real-life examples to describe the problems easily..

Problem 1:

In defining "try" , I told that it is a simple movement which will stop if its straight path towards the goal is obstructed by an obstacle. But we don't want the zombie to stop (don't we? :D  Nope.. atleast in the game we are going to make those dumb zombies a little bit intelligent..) simply because it's path is obstructed by a solid obstacle .. We want them to move on..

Real-life example 1  and solution (Well, not so real...)

Consider it like hide and seek game.. 
You are the zombie who can walk only in straight lines... You want to find that damn intelligent human..
But as the human is intelligent, he tries to get your view (of him) obstructed by obstacles..
So, here you decide your strategy..
You'll scan your nearby places (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)...
Now, you find one such place from where you view of the player is unobstructed and you can move in a straight line path towards him.. 

But there can arise this problem:

You can't move towards that nearby place you thought will be perfect because the straight line path to that point is obstructed.. So, you need to know if you can reach that point in a linear path or not..

If not, continue searching for the next closest best place according to your strategy.. 
(This closest best point has been referred to as ' local goal' or 'goal' previously...)

And, if yes, move to that place and continue the chase..

Problem 2 (Based on example..)

Though this problem may sound similar, it's a bit different....
Actually, this problem lies in problem1 too..
So, problem to both these solutions needs to be merged in the end..

So, that instrument tells you whether you can see the human from another point or not..
It doesn't really imply that you can move towards the human from that point or not.. Because your body 
(the body is equivalent to sprite of the zombie and the vision is equivalent to the line joining the center of the sprites of the zombie and the human) has dimensions and it may get obstructed even if you vision isn't..

Solution 2:

We'll need a bit of geometry now and also we need to focus on the game more now...

We'll need a basic assumption (which will make the complex geometrical problem easy) and my game also stands on this..
So, unfortunately this is a must requirement and in some minor way, limitation for the game...

Both the zombie and the player needs to have sprites of same dimensions and the precise collision (in GM) must be turned off for both the sprites

which is equivalent to

Both the sprites must have same size of bounding box used for collision

Look at this illustration:
The rectangles represent bounding box of the sprites, which are of same dimensions


Please note that this is a 2-D diagram though it may appear to be 3-D..

The line joining the center of both the sprites doesn't get obstructed by the RIP stone ...
But the two line joining the left-top and left-bottom end of the two sprites gets obstructed by the stone. So, the zombie can't move towards the human in linear motion without getting obstructed...

So, to make sure that the whole sprite can pass through, we need to do some more checking

We need to check if the line joining all the four corresponding ends of the two bounding box collides with the obstacle or not...

If not, then only that point can be considered as a local goal...

What still needs to be done?

James, at first wanted to know if I can re-write those MP (motion planning) functions and in the end, I can see that I've finally come up with a primitive and this game-specific version of it.....
Though I have always referred to it as a trick...
So, why not make it still better?

There is this one problem:
  • The zombies tend to overlap each other to a high extent such that after few minutes many of them becomes recognizably one... 
          I knew this was to come, and I do have a solution in my head..
         So, this will probably not be a problem in the future...
 Also, my approach can be highly optimized, I know that...
So, I'll make a new post on this optimization part... 
Hopefully, I'll be posting it tomorrow .....
Still then, hang on....

You may avoid this part (Unless you are James Clerk ) ...

Note: This part is GM-specific...

Q:James asked me why  I haven't used the solid property present for all objects in GM..

A:  Well, the truth is you would have yourself stopped using it after some days..
  It can be easily re-created with the place_meeting(x,y,obj) function..
  Just check if the next position will be collision free 
  from the other objects you consider solid and you're done...
  As an added benefit,you'll have full control over your objects..
  The solid property is somewhat mysterious and added in the help file 
  without much details...
  So, everyone tries to avoid it...
  From what I've experienced, I can tell this:
  1.It works only when two objects are colliding due to their speed variables
    (hspeed and vspeed)
  2.If you use like x=5 and y=22 to move an instance of an object to (5,22) and 
    there is already a solid object at (5,22) it doesn't give a error.. 
    i.e. both of them exists at that point in harmony.. but the problem starts
    if you want to move any of those instances using the speed variables they 
    get stuck...
  So, it is like your unrecognizable pain-in-the-ass feature...

 Don't use it at all....

2 comments:

  1. I noticed you don't use the solid setting on objects, and you have place_meeting code. I was wondering if -maybe in a later post- you could explain in basic terms why it is you do this? I'm not too clever and have always just used the "solid" setting on objects.

    ReplyDelete
    Replies
    1. I have already replied to it within the blog post.

      Delete