MP Grid Pathfinding - How To make Enemies Avoid Each Other?

N

Necromedes

Guest
I understand that this is a long lived issue but I haven't been able to find a proper solution.

I am using an mp_grid for my enemy pathfinding and need a means of collision between different enemies, instead of allowing them to seemingly merge into one spot.

I have tried x and yprevious, move_towards_point with a negative speed value to essentially move away from the other enemies. I have tried using move_bounce (it kind of works but is really buggy and jerky,) I have tried so many different things.
I have even tried to add obj_enemy to the list of instances for them to avoid on the grid but since they consider themselves something to avoid, they just sit there.

Someone gave me a code a long time ago with only a few lines of could that essentially let the enemies slide around each other but I no longer have access to said code. If someone could give me a similar code or something that will solve my issue in some other manner, then please let me know.

Thanks in advance.
 

NightFrost

Member
Combining mp grid pathfinding (that is, A star pathfinding) and avoiding enemy overlap is something I've been trying to figure out for a good while, too. By which I mean the enemies should also be capable of moving around others to reach the player; and because walls are on the mp grid they are not created as objects, and cannot be detected with collision checking. While grid walls and enemy overlap can be solved with a routine that combines data from both the grid and collisions, it doesn't solve the routing towards player problem. They just queue up dumbly and await their turn as player kills their friends.

One solution I've managed to make work at acceptable level (still working on it though) is using Steering Behaviors combined with taking hints from mp grid (your desired velocity is the initial direction of the path, discard the rest). Anyone who's played around with them knows though that SBs do not guarantee collision avoidance. When you reach a critical group mass depending on parameters, the forces will overcome separation and make agents overlap with each other or the walls. Not a problem you see with simple flocking movement but you do see it when agents attempt to converge en masse on a single point - that is, attack the player. (SB is also based on vector math, and GM doesn't support that, so you have to work around.)

I've also seen a method that is based on steering across localized, temporary flow fields. I've not tried something like that yet and I feel the math may be too heavy to support large amounts of enemies.
 
N

Necromedes

Guest
I'm truly astounded that YoYo never took this into consideration for their grid system. I can achieve the desire results with mp_potential_step but the pathfinding is a lot less accurate and the enemies tend to get caught on the corners of walls quite a bit and even when they don't, the path's aren't very intelligent. For instance, if a player were to move back around a wall and the enemy instance is currently on a path to the player, they often don't go back the way they came to reach the player sooner.

Perhaps I can use mp_step to do this and find a way to improve their wall detection to avoid snags and may have to at this rate, since most of what you mentioned in your post went over my head for the most part.
 

lolslayer

Member
In the collision event with another enemy, put something like this:

Code:
var push = 1;
x -= lengthdir_x(push,point_direction(x,y,other.x,other.y));
y-= lengthdir_y(push,point_direction(x,y,other.x,other.y));
Now they'll push eachother aside
 
P

ph101

Guest
I'm truly astounded that YoYo never took this into consideration for their grid system.
Hmm no offense but it seems to me its more that you haven't taken in to consideration what you want your agents to do and how best to acheive it. This is not a problem with gamemaker - the a* algorthim and grid system works just fine out of the box. There is not really enough info in your post, but you could either update the grid to know the location of obstacles (probably not what you want, cpu heavy), or if you are using path_start for your movement, you could instead extract the points from the path once calculated (path_get_point_x, path_get_point_y) and move to wards them in sequence using mp_potential_step_object to avoid desired objects without a need to refill the grid and recalculate the path frequently (as you want to keep that to a minumum) and or/use pushing aside idea @lolslayer mentions.
 

NightFrost

Member
Perhaps I can use mp_step to do this and find a way to improve their wall detection to avoid snags and may have to at this rate, since most of what you mentioned in your post went over my head for the most part.
I mixed up the terminology bit too much there. An older pathfinding system I made that doesn't use wall objects worked like this. First the enemy would, according to its current state, create a certain direction it wants to move into (random wander, approach player, etc). Then it would check all eight surrounding grid spaces for walls. Not mp_grid, simply a grid that contained true/false for presence of obstacles. It would decrease movement speed accordingly so the movement direction would not take it inside any wall. After that, it collision detected for entities that might be in the way, and decreased speed even more if necessary so it wouldn't walk over them. There was some basic AI where the code attempted to steer the creature in 45 degree increments to get around other creatures, but just as often as it helped it would send them off into distance before attempting to approach the player again. So it didn't work in acceptable manner.

The approach I'm taking now uses the mp_grid. It lets the mp calculate a path from current position to player, then takes the direction towards first path node (or second, if first is inside same grid cell as the creature) and uses it as target for its desired velocity vector. This way, the creature "knows" where the path towards player is. Next, movement system known as Steering Behaviors is used to move the creature towards the point, which accomplishes wall and overlap avoidance. Once the creature has moved far enough, it calculates another mp_grid path and picks a node as explained above. All in all, this works very well for one or several creatures. But because SB is a forces system not a collision avoidance system, a large enough group of creatures in close proximity turns the separation force into a pushing force that overcomes separation at the center of the group, causing the creatures to push atop each other.

EDIT: mp_grid can't really be faulted for being unable to avoid instances. It is based on A star, which is a fast system designed find a path across a mesh, which is always a grid in GM. That's why it is fast. To mark down instance positions into the grid, you'd need to make it much more fine-grained (with maximum fidelity being one grid cell for each pixel) but that could slow down pathfinding quite a bit.
 
Last edited:
A

Ampersand

Guest
I think you need a larger node-based structure for your coarse pathfinding, and then you need to handle your short-term routing between nodes. This would probably be the simplest way, but it probably wouldn't be the easiest. It'll add work to your level design pipeline.
 
B

bojack29

Guest
Why not use the path generated from the A* as a guide and use a different method to handle collisions and avoidance? Simply move the character toward each point on the path.
 

NightFrost

Member
The challenge in node to node movement (for a group) is that it turns into a queue, and due to potential blocking events & crowding it becomes really difficult to reach the next node and much easier to reach the one after that. Detecting when this is the case and skipping a node becomes important, or the group of creatures is in danger of looking like bumbling fools.
 
The challenge in node to node movement (for a group) is that it turns into a queue, and due to potential blocking events & crowding it becomes really difficult to reach the next node and much easier to reach the one after that. Detecting when this is the case and skipping a node becomes important, or the group of creatures is in danger of looking like bumbling fools.
I replied to a similar thread a while ago with my method:

https://forum.yoyogames.com/index.p...ial-be-used-at-the-same-time.2254/#post-19722


In regards to the 'queue' effect that you speak of, it is pretty tough to deal with without adding a bunch of conditions for the units to keep track of, but it is possible to mitigate the worst instances of it with several modifications:

-make sure you have the all-important: 'if I am bumping into another unit and I am close enough to the node, forget about it and go to the next one' check. This will help a lot, but units can still look pretty bumbling with it.

-to help mitigate endless mp_potential loops of units against units, implement a simple 'wait' state for them. A simple way of doing this is for all units to check if they are within X distance of another unit, and to time how long they are close to them. If they are close to them for a long time, and their directions are not similar (i.e. they are trying to go around each other for too long), then make one of them wait for a couple seconds, going idle until the other passes. This can be achieved with a simple 'if(id>other.id){}' kind of code, whereby only one is chosen to wait while the other can just go on about their business.

and perhaps most importantly:
-design your maps accordingly to cope with the code you have!! I know this doesn't sound helpful at first glance, but pathfinding and local collision avoidance is never going to be perfect, or even close to perfect. You have to design your game with these limitations in mind. For a really good example of efficiency and working with what you have, see Warlocked for the GBC. It only uses an analog of mp_potential_step with no pathfinding at all, but works so well because the maps and game mechanics are made around this limitation.


Good luck!
 

NightFrost

Member
I dug up the resource I mentioned earlier, a method to use flow fields (and assorted tricks) to guide agents to their goals. It is a 17-page pdf that goes heavy on the math, but explains things well enough that the point comes across even without getting what all the letters and squigglies are about.
 
E

Enegris

Guest
In the collision event with another enemy, put something like this:

Code:
var push = 1;
x -= lengthdir_x(push,point_direction(x,y,other.x,other.y));
y-= lengthdir_y(push,point_direction(x,y,other.x,other.y));
Now they'll push eachother aside
thank you so much! i was reading through the forum because i had a similar problem to that of the op and stumbled upon your solution, and it works like a charm for me. exactly what i was looking for!
 

JackTurbo

Member
Personally I've found the normal mp_potential from path point to path point approach with the addition of a small bounce effect when enemies collide with one another, to be sufficient so far.
 

lolslayer

Member
thank you so much! i was reading through the forum because i had a similar problem to that of the op and stumbled upon your solution, and it works like a charm for me. exactly what i was looking for!
No problem man, I used this method for years, kinda makes me nostalgic now that you remind me of this post :)
 

KPJ

Member
lolslayer's method worked for me. Thanks a lot!
In the collision event with another enemy, put something like this:

Code:
var push = 1;
x -= lengthdir_x(push,point_direction(x,y,other.x,other.y));
y-= lengthdir_y(push,point_direction(x,y,other.x,other.y));
Now they'll push eachother aside
 

Evanski

Raccoon Lord
Forum Staff
Moderator
just make the enemys one of the objects that marked as a invalid spot to pathfind too
 
Top