8 replies to this topic

[blazingcrash]

The title of this topic may make it sound like it belongs in the beginner's section, but please hear out my problem:

I'm making a top-down 8 directional game, in which enemies try to make contact with the player. I am handling this by using grid motion-planning, using 32x32 sized blocks, so that the enemies are capable of making their way through a maze. The problem I am facing is what to do when an enemy collides with another enemy: doing nothing results in the enemies eventually piling up on the same square, resulting in it looking like their is only one enemy. I am trying to figure out a way to keep them spread out, while still following their paths to the player.

So far the best workaround I have for this is, when an enemy collides with another, first destroy the path it is on, then check it's x position against the other, then move in one direction (example: northeast, east, or southeast)for two steps, while the other enemy moves in the other direction (northwest, west, southwest), then create have them both create paths again and continue.

Their paths are being updated every 20 steps, using a timer, but the motion planning grids do not take other enemies into account, only solid object (I am using tiles, and a generic solid object to handle everything). setting the enemies to move in a different direction for anything longer than two steps results in the possibility that enemies will go through the walls (if they are assigned to collide with walls too, they get stuck). I have tried making another grid during a collision with an enemy and adding the enemy object to this map, but when calculating the grid this sometimes results in no possible path to the player, in which case the enemy doesn't move, and enemies end up piling up. I have also tried to move an enemy backwards on their path to avoid the collision, but this also results in them getting stuck when their are multiple enemies around.

My above solution results in all of the enemies sort of bouncing off of each other for awhile, before finally getting far enough away from each other to continue on their paths (which usually end up being pretty identical) without colliding again: it is okay, but temporary. My main question: how can I use an mp_grid function for an enemy(so far it is the only motion planning technique I've found that is complex enough to get the enemy to the player reliably), yet have them avoid one another, or resolve a collision in a decent manner? I guess the ideal solution would be when a collision occurs, to have the enemies figure out who is "in front" (i.e. who needs to move first given their direction) , and have the other enemy wait a moment while he moves first, then continue as well. However, since enemies don't have a direction while moving on a path, this makes it difficult.

any help is greatly appreciated,

BC

[paul23]

Well I haven't myself tried to figure a way to solve this problem yet.. However
this site may help you (though it doesn't really give much information)

1. Other Units (collision avoidance): If you happen to look closely at my example code, you will notice that it completely ignores other units on the screen. The units pass right through each other. Depending on the game, this may be acceptable or it may not. If you want to consider other units in the pathfinding algorithm and have them move around one another, I suggest that you only consider units that are either stopped or adjacent to the pathfinding unit at the time the path is calculated, treating their current locations as unwalkable. For adjacent units that are moving, you can discourage collisions by penalizing nodes that lie along their respective paths, thereby encouraging the pathfinding unit to find an alternate route (described more under #2).

If you choose to consider other units that are moving and not adjacent to the pathfinding unit, you will need to develop a method for predicting where they will be at any given point in time so that they can be dodged properly. Otherwise you will probably end up with strange paths where units zig-zag to avoid other units that aren't there anymore.

You will also, of course, need to develop some collision detection code because no matter how good the path is at the time it is calculated, things can change over time. When a collision occurs a unit must either calculate a new path or, if the other unit is moving and it is not a head-on collision, wait for the other unit to step out of the way before proceeding with the current path.

These tips are probably enough to get you started. If you want to learn more, here are some links that you might find helpful:

* Steering Behavior for Autonomous Characters: Craig Reynold's work on steering is a bit different from pathfinding, but it can be integrated with pathfinding to make a more complete movement and collision avoidance system.
* The Long and Short of Steering in Computer Games: An interesting survey of the literature on steering and pathfinding. This is a pdf file.
* Coordinated Unit Movement: First in a two-part series of articles on formation and group-based movement by Age of Empires designer Dave Pottinger.
* Implementing Coordinated Movement: Second in Dave Pottinger's two-part series.

The problem is that in gm's pathfinding routines you can't add a "cost" to that path: so penalizing nodes is out of the question.

What you could do is look (only for adjacent units) is to look at their next few (2-3) nodes, and then make those also unwalkable (unless it's the node the unit is currently on). I think this will prevent piling up too much.

Also when no path found it should keep it's original path, so you can keep checking the nodes..

Edited by paul23, 02 May 2008 - 09:41 AM.

[ragarnak]

However, since enemies don't have a direction while moving on a path, this makes it difficult.

Actually, they do (that is how you can get them to turn (their sprites) in the direction they are moving in).

As for "who's in front of me ?" problem ? Why don't you ask the Path what your next position is and check if there is allready someone there ? If so, simply stop moving/move back to your previous position on the path :

//end-step event
if place_meeting(path_get_x(path_index,path_position),path_get_y(path_index,path_position),object_index) then path_position=path_positionprevious

(Warning: Untested code)

Hope that helps/gives you an idea.

[blazingcrash]

However, since enemies don't have a direction while moving on a path, this makes it difficult.

Actually, they do (that is how you can get them to turn (their sprites) in the direction they are moving in).

As for "who's in front of me ?" problem ? Why don't you ask the Path what your next position is and check if there is allready someone there ? If so, simply stop moving/move back to your previous position on the path :

//end-step event
if place_meeting(path_get_x(path_index,path_position),path_get_y(path_index,path_position),object_index) then path_position=path_positionprevious

(Warning: Untested code)

Hope that helps/gives you an idea.

Thanks for the info ragarnak: I was unaware that you can get direction on a path for instances: I have been changing the sprite by saving the previous x position as a variable and then checking it against the x position in the next step, using a simple timeline (for some reason I cant get the "previous x" function in game maker to do this, hence saving the position in a variable). If you can tell me how to find the direction while on the path, it would be appreciated). As for checking the for a meeting on the path: can this work if the instances are on separate paths? I thought this only worked if they are on the same path, but if this is not the case, then I'll definitely check it out....

Paul23:

Thanks for your input too -- can you go a little more indepth about looking at the next few nodes and making them unwalkable, I'm not sure I follow you... Also, when using the mp_grid functions, is there a way to add a specific instance of an object as impassable, as opposed to all of the instances of a given object? I think simply adding the nearest instance to the grid as impassable may help clear up this problem as well...

anyway, thanks for all the help, any additional ideas would be greatly appreciated.

[ragarnak]

If you can tell me how to find the direction while on the path, it would be appreciated

I just noticed that I forgot to explicitily name it. But its simply the "direction" variables value of your instance that gets changed depending on in which direction the path makes it go. A simple "image_angle=direction" (for registered users) in the end-step event should be enough.

As for checking the for a meeting on the path: can this work if the instances are on separate paths?

The path only tells the object where to go. I merely showed a way to ask the path what the instances next position will be. After that its just a "if I (the instance) would be placed there, would I collide with someone ?" -check, which has got nothing to do with the path.

So yes, it will work even when both instances are using different paths.

Hope that helps.

[paul23]

Paul23:

Thanks for your input too -- can you go a little more indepth about looking at the next few nodes and making them unwalkable, I'm not sure I follow you... Also, when using the mp_grid functions, is there a way to add a specific instance of an object as impassable, as opposed to all of the instances of a given object? I think simply adding the nearest instance to the grid as impassable may help clear up this problem as well...

anyway, thanks for all the help, any additional ideas would be greatly appreciated.

mp_grid_add_instances(id,obj,prec) Marks all cells that intersect an instance of the indicated object as being forbidden. You can also use an individual instance by making obj the id of the instance. Also you can use the keyword all to indicate all instances of all objects. prec indicates whether precise collision checking must be used (will only work if precise checking is enabled for the sprite used by the instance).

So yes you can..

as for the other thing, Well it's to prevent objects from "walking" next to each other. Consider this case: objectA meets objectB head on. Let's say that A is at cell 5,4 and needs to go to cell 5,6. B is at 5,5 and needs to go to 5,3. So obviously a head on collision in the vertical direction.

A wants to move round B, and "decides" to go to the east, so the next nodes would be 6,4 -> 6,5 -> 6,6 -> 5,6
B wants to move round A, but also decides to go to the east, the next nodes would be: 6,5 -> 6,4 -> 6,3 -> 5,3

Now let's asume both have moved 1 node, so they're at 6,4 and 6,5. Now another collision occurs: and both now see that the shortest path is to go through the "5" column again (5,4 -> 5,5 -> 5,6 and 5,5 -> 5,4 -> 5,3).

And again are they lined up at 5,4 and 5,4 - and the first situation will happen again.

Now you're asking: why are they both deciding to go east. Well this is because that's the way A* pathfinding is mostly programmed, they don't use a random -since randoms add additional overhead and A* is already slow- and always have it "pre-programmed" (depending on how the sorting algorithm works) to choose either the eastern, or western node.
I'm not 100% sure GM works this way too: but it's the way most A* algorithms work.

Now consider if we make also the next node -unless it's the goal node or our current node- of the instance unwalkable: When the collision occurs first A makes up a new path... B's next node is A's current node so it's not added to the field as unwalkable: so it chooses the path: 6,4->6,5->6,6 ->5,6 again.
Then B decides to create a path. A's the one it collides with, and A's next node is "6,4", so it makes 5,4 and 6,4 unwalkable.. This means that the shortest path is to the left: 4,5 -> 4,4 -> 4,3 -5,3.. And now there won't be a a collision anymore.
(though better would be if B detects that it should simply wait 1 step: but that would require a 3d array to use pathfinding on - where the 3rd dimension is the time, and isn't really feasable in GM).

Now there is a slight problem in this approach: consider if 4,4 and 7,4 too: at this point they will keep "moving along" untill some external influence decides that 1 should stop and wait. - You could for example say that it uses the next 2 nodes to battle this problem, since it that case it would detect it couldn't move through this narrow path, and would move the long way around (through column 3). Sure it's stupid (it could just wait 1 time) but at least it would work.

The only main problem with this approach is that it reduces the chances to find a path by adding extra nodes..

[Ajw1995]

Would it help you to break your map up into basic large areas, (i.e. use a navigation mesh), do your pathfinding, and then use a collision avoidance system within each area? It would reduce the amount of pathfinding needed, and your units wouldn't collide. I recommend Paul T's big rant about navigation meshes, at www.ai-blog.net/archives/000152.html and Craig Reynold's papers, which comes with some limited source code examples, at www.red3d.com/cwr/steer/ and www.opensteer.sourceforge.net/

[Gamer3D]

Would it help you to break your map up into basic large areas, (i.e. use a navigation mesh), do your pathfinding, and then use a collision avoidance system within each area? It would reduce the amount of pathfinding needed, and your units wouldn't collide. I recommend Paul T's big rant about navigation meshes, at www.ai-blog.net/archives/000152.html and Craig Reynold's papers, which comes with some limited source code examples, at www.red3d.com/cwr/steer/ and www.opensteer.sourceforge.net/

"Posted 07 May 2008 - 02:01 AM"
If he hasn't solved it in more than 3 years, he's probably moved on.

[Ajw1995]

"Posted 07 May 2008 - 02:01 AM"
If he hasn't solved it in more than 3 years, he's probably moved on.
[/quote]

derp. I always forget to look at the dates.