SOLVED Enemies walk through/into each other

Zuurix

Member
Hey all,

I'm making an RPG with real-time combat. I use built-in motion planning grid functions (mp_grid_) to make enemies move and the problem is that enemies don't consider each other solid objects, so this often happens when fighting against multiple enemies:



Has anyone solved this problem in your games or got any suggestions on how to fix it?
 

NightFrost

Member
Yes, I think it is generally called as avoidance. This is something beyond capabilities of mp_grid, because it uses A* pathfinding. While you might be seeing the game world as 32x32 (or such) pixel grid, A* sees it as points connected to each other throuh 4 or 8 lines (whether your diagonal pathing is off or on) which obviously cannot cater for avoidance. In avoidance systems A* might still serve as basis of routes, but more to figure out which general heading is shortest path to player, not as path to stick to. One common avoidance system is Steering Behaviors. In dungeon-like maps like yours appears to be, it will still need help from A* style pathfinding to figure a way around complex obstacles and to player while the Steering Behavior takes care of local avoidance.
 

Nocturne

Friendly Tyrant
Forum Staff
Admin
The general rule for things like this is to not make your enemies follow the path using path_start(). Instead, get the first path point position and use something else to move towards that point, then check to see if it's been reached, and if it has, get the next point on the path and move towards that until you reach the end of the path. Using this method, you can then add extra code in to avoid objects or simply move out of collision with them. For an example of what I mean, see this article on the helpdesk (it's for a tower defense game and for GMS 1.4, but the principle and code is almost exactly the same as what you're asking about and should work fine in GMS2): https://help.yoyogames.com/hc/en-us/articles/216755858--GMS-S-Using-Mp-grids-To-Create-AI

PS: I like the visual direction of the game!!!
 

Zuurix

Member


I've set enemies to solid and somehow they are avoiding each other. Okay... (Didn't bother to create a path for each of the spawners, still works!)

Assuming I want to do this in my game, I would need to come up with mp_potential_step for tile collisions - I don't use objects for my collisions, figured out a way to add tiles to motion planning grid via mp_grid_add_rectangle.
Well, both for tiles and objects that need to be avoided.

This isn't great, so I'm not sure.
 

NightFrost

Member
Each enemy should be doing their own decisions regarding best approach route towards player, instead of using a common path. A path is only good from its starting position, and when only one is used then as happens in your image enemies from elsewhere in the room first seek to path start, only then to player. Sticking to path will also lead to erratic behavior in crowded / narrow spaces and the enemies will still exhibit the behavior of wanting to form an orderly queue to attack the player.

An alternative to A* is using a flow field. Basically, a breadth-first search radiates out of player's current grid cell and assigns to each cell a distance value from player. Then, any enemy can take distance values of its current cell's neighbours and calculate a 2d vector (left - right, up - down) and the result is direction that takes it closer to player's current cell. (But on large maps this too can become expensive...)

EDIT - oh, also, when the enemy has direct line of sight to player, it is best to drop all the expensive pathfinding as it is unnecessary, and directly proceed towards player using some avoidance technique (like Steering Behaviors) to avoid other enemies and walls.
 
Last edited:

Zuurix

Member
Yeah, every enemy would have its own path in my game, I just wanted to see what mp_potential_step can do.

Maybe I should just make enemies move to a random spot whenever distance to the nearest character is very low. Since there doesn't seem to be a good solution for my skill level.
 

Yal

🐧 *penguin noises*
GMC Elder
Another fun thing to consider is adding a "approach angle" parameter, which is a random angle between 0 and 360 [optionally: changes every few seconds]. Instead of enemies approaching the player directly, they first approach a point some distance away from them in the approach_angle direction. THEN they approach the player directly. The result of this is that enemies won't just form a conga line after the player, they attack from all sides.
 

Zuurix

Member
Yeah, I think I need something hacky like that. I probably won't have fights with over 5 enemies.
 

NightFrost

Member
Yeah, pathfinding and avoidance are complex subjects. I've been experimenting on and off with various methods for a long time now. I am able to create a system that gets an enemy to player with local avoidance included in movement, but there's a number of edge cases creating really ugly behavior that I haven't been able to solve in satisfactory manner. (They relate to local avoidance in larger groups, and I won't bore people by going off on a tanget about them.)
 

Yal

🐧 *penguin noises*
GMC Elder
There's a thing called "soft collision" that some engines use, where collision and obstacle status is more of a recommendation than absolute law, so things can partially overlap for a while if they need to, but get pushed out once there's enough free space. Having a system for that might fix some of the ugly behaviors in large clusters of enemies?
 

NightFrost

Member
The system I've been experimenting with lately is context steering. It assigns an interest value (interpolated) across sixteen main directions, highest to intended destination and neighbours with progressively less. Next avoidance is mapped to same directions with closer obstacles assigning higher values and those near enough blocking the direction completely. (Walls are line obstacles not points so they affect multiple directions.) When mapping is done, a nonblocked direction with lowest avoidance is picked; if multiple directions have same avoidance the one with highest interest is picked; if all directions are blocked no movement happens. (Incidentally, the interest pull comes from a flow field, so it will always pull the agent towards target even in a maze.)

In other words, when on open field with no obstacles the agent is pulled straight toward interest. If obstacles exists the lower interest values attempt to pull it around obstacles. A soft collision system would require a rethink of the mechanism.
 

Zuurix

Member
My solution:



(Sorry for corpse looting, haven't spent any time writing proper lines for the NPCs yet)

Every character checks the distance to the nearest character. If that distance is lower than X, the character picks a random point (yellow square in the GIF) in its range and moves to it.

Once the distance is greater than X, the character switches back to normal behavior. Works well with my melee attacking AI, which tells NPC to move to the nearest enemy until it reaches the melee range.

Still needs some bug fixing, I think my "pick a random point" code has a problem with leads to NPCs "freaking out", and there's an issue of both NPCs trying to avoid each other which makes them stuck. That can be solved with a code like "if nearest_character.id > id { engage evasive maneuvers } but not sure if "id" is the best way to determine which of NPCs should have priority when avoiding, plus, if player's instance id is lower, NPC won't avoid it.
 

NightFrost

Member
Well, instead of picking random point, you could pick a point that is in the opposite direction from the nearby character. And then act on all characters that are nearer than N, and consider each as vector pushing you. The length of the vector is the inverse of distance (closer they are, harder they push) and the location where you want to move is the sum of those vectors. Which basically is how in steering behaviors the avoidance behavior works.
 

Zuurix

Member
Well, instead of picking random point, you could pick a point that is in the opposite direction from the nearby character. And then act on all characters that are nearer than N, and consider each as vector pushing you. The length of the vector is the inverse of distance (closer they are, harder they push) and the location where you want to move is the sum of those vectors. Which basically is how in steering behaviors the avoidance behavior works.
It's already pretty bad performance-wise when all characters need to calculate their distance to the nearest character - I'll need to optimize that in some way.

I also need distance to nearest different faction character and nearest character with a bad reputation - these three calculations with 40 characters in an area slows down the game quite a bit IIRC.
It's because my game requires characters to be always active in large areas - so that the life of an area of the world wouldn't stop just because there are no players around =]
 

Yal

🐧 *penguin noises*
GMC Elder
It's already pretty bad performance-wise when all characters need to calculate their distance to the nearest character - I'll need to optimize that in some way.

I also need distance to nearest different faction character and nearest character with a bad reputation - these three calculations with 40 characters in an area slows down the game quite a bit IIRC.
It's because my game requires characters to be always active in large areas - so that the life of an area of the world wouldn't stop just because there are no players around =]
How often do you update this? If it's every step, I can definitely see potential for improvement... I would update the IDs about once per second, and when I say "about" once per second, I mean "add a bit of randomness to the alarm/countdown for load balancing"... i.e. every random_range(50,70) steps.
 
Top