GML Keeping Enemies from Touching

O

OneExalted

Guest
Hi everyone!
I'm making my first game right now (a top-down zombie survival) and it's going pretty good but I have an issue noone can seem to answer.

My zombies will clump together in one small space and it makes it far too easy for the player to kill them.

Their movement code is very simple

/// Zombie Movement

image_angle = direction
speed = 3



if instance_exists(oPlayer) {
direction = point_direction(x,y,oPlayer.x,oPlayer.y)
}
else {
direction = point_direction(x,y,oCorpse.x,oCorpse.y)
}


What I specifically want them to do is to always move towards the player but not overlap. People have suggested doing a collision event with xprevious and yprevious. But that makes them stop and I want them to just move around eachother to almost form a big wave around the player.

Does gml have an easy way to do this? People have also suggested place_free but I don't really understand how to use it to achieve what I want. Any help would be great. Thanks!
 
There is no simple way to do this. It's a complicated topic within AI and a lot of research time has been devoted to finding quick, accurate dynamic pathfinding algorithms. You could look into steering behaviours combined with A* (or another pathfinding algorithm), but unfortunately there is no real effective "Get enemies to move smoothly and avoid other dynamic objects accurately" GML preset.
 
O

OneExalted

Guest
There is no simple way to do this. It's a complicated topic within AI and a lot of research time has been devoted to finding quick, accurate dynamic pathfinding algorithms. You could look into steering behaviours combined with A* (or another pathfinding algorithm), but unfortunately there is no real effective "Get enemies to move smoothly and avoid other dynamic objects accurately" GML preset.
Thanks for the reply!
Yeah it seems like this is more complex than I realized. I might table this game and work on something a bit easier until I'm more familiar with the language. I'm also trying to create a wave system using an equation I came up for wave size increase and that's proving to be a towering endeavor. Just glad to know I wasn't missing an easy solution that I should have figured out. Thanks again.
 

Yal

🐧 *penguin noises*
GMC Elder
The problem is that all zombies move to the same point, clustering up like that is a natural consequence of it.

The easiest way to solve this is to give zombies separate deltax and deltay variables that are set to random values when zombies are created, and once every 3-5 seconds or something using an alarm. Instead of moving to the player's position, move to its position plus these delta coordinates. Now zombies will still move in the player's general direction, but surround the player better since they're evenly spread over a square around the player.

(It can get obvious zombies aren't targetting the player directly if the player stops and observes the zombies, so you MIGHT want to make zombies go straight for the player if they're too close, but for big hordes this should work sufficiently)
 
The problem is that all zombies move to the same point, clustering up like that is a natural consequence of it.

The easiest way to solve this is to give zombies separate deltax and deltay variables that are set to random values when zombies are created, and once every 3-5 seconds or something using an alarm. Instead of moving to the player's position, move to its position plus these delta coordinates. Now zombies will still move in the player's general direction, but surround the player better since they're evenly spread over a square around the player.

(It can get obvious zombies aren't targetting the player directly if the player stops and observes the zombies, so you MIGHT want to make zombies go straight for the player if they're too close, but for big hordes this should work sufficiently)
But that wouldn't stop the zombies from overlapping would it Yal? It would simply make it so they don't overlap as much, right?
 

Yal

🐧 *penguin noises*
GMC Elder
It would do nothing to stop them from overlapping, but it'd stop them from clustering up in a single line if the player just backsteps for a while. (This is one of the major complaints with Strafe, it mechanically promotes doing this to enemies rather than playing the game as intended)

(Enemies going single file is an ancient AI problem; the ghosts in the original Pac-Man uses different AI to ensure they wouldn't do this, because it'd make the game too easy.)
 
O

OneExalted

Guest
Is there a way to make them actually solid, like a wall? So they would just collide and continue to push against each other while still moving towards the player. Or would doing that cause them to collide and then stop?
 
O

OneExalted

Guest
I did get some random success with move_outside but it only let's you move them in a set direction and usually they just back themselves up against the side of the room.
 
You can use GM's inbuilt pathfinding options (I think it's mp_potential_step or something like that), but as I said above, it won't work perfectly. It can give some ok movement, but things will still group together and get stuck if a solid object rotates onto them and stuff like that. It's a frustrating problem to try to fix.
 

Yal

🐧 *penguin noises*
GMC Elder
What's important to realize here is that "make zombies don't queue up in a single line" and "make zombies not overlap each other" is two different problems (behavioral and physics). It's probably possible to solve both with the same solution, but it's generally easier to solve two small problems than one big.

I'd say the best way to handle zombie overlaps would be to have them be "soft"... try to avoid zombies moving into each other when pathfinding, but don't be too harsh about moving them out again when there IS an overlap (unlike walls that should have them out ASAP), and only move them out gradually so there's not too many random jittering occurencies.
 

Tsa05

Member
Just do the high school prom approach; put a yardstick between them and don't let them kiss.

Ok, ok. but code-wise, something very much like what Yal is suggestion about timing.
Suppose you have a "zombie wave controller" object, which spawns zombies.
Let's give it a *second* job, too. Command the zombiesssss.
Every N number of steps or seconds, the zombie object controller could look at things like the player's position, and could choose new "target destinations" for each zombie.

If the controller object has a list of zombies that've been made, this gets easy. Whenever the timing event fires:
1) Make a list of target coordinates for the zombies. The list is empty.
2) Loop through the list of zombies, checking their location, point_direction, and point_distance to the target (player?).
3) Decide where you want the zombie to go--is it towards the player?
4) Check the list of already determined target coordinates. Is this new, intended target coordinate too close to an existing one? (too close would be within 1/2 of the size of a zombie sprite, for example)
5 A) If the intended coord is too close to an existing coord, move the target coord until it's ok.
5 B) Add the intended coordinate to the list of target coordinates, and tell the zombie to start moving towards that.

Ofc, "move the target coord until it's ok" is the tricky bit--well, not really, but it's up to how you want to adjust behaviours.
Maybe you try moving the coordinate in an arc around the player, up to a certain degree, and then, if no suitable coordinate can be found, move the coordinate backwards along the point_direction line? Depends.

Anyhow, the end result of the 5 steps above is that every N amount of time, all of the zombies are given a coordinate to aim for that is near the player, but a little distance from each other.
 

samspade

Member
Hi everyone!
I'm making my first game right now (a top-down zombie survival) and it's going pretty good but I have an issue noone can seem to answer.

My zombies will clump together in one small space and it makes it far too easy for the player to kill them.

Their movement code is very simple

/// Zombie Movement

image_angle = direction
speed = 3



if instance_exists(oPlayer) {
direction = point_direction(x,y,oPlayer.x,oPlayer.y)
}
else {
direction = point_direction(x,y,oCorpse.x,oCorpse.y)
}


What I specifically want them to do is to always move towards the player but not overlap. People have suggested doing a collision event with xprevious and yprevious. But that makes them stop and I want them to just move around eachother to almost form a big wave around the player.

Does gml have an easy way to do this? People have also suggested place_free but I don't really understand how to use it to achieve what I want. Any help would be great. Thanks!
As other people have noted this is a moderately difficult problem to deal with which is why a lot of games don't actually (it's surprising how many games allow enemies to overlap each other once you start looking for it). Steering behaviors do this really naturally but are unfortunately not natively supported in game maker so you either have to learn how to do them from scratch or find some scripts made by other people. Both somewhat complicated processes. If you don't care too much about how it looks though, just try this:

Code:
/// Zombie Create Event

speed = 3;

/// Zombie Step Event

//find nearest zombie that isn't this one
var xx = x;
x -= 10000;
var nearest_zombie = instance_nearest(xx, y, object_index);
x += 10000;

if (nearest_zombie != id) {
     if (distance_to_object(nearest_zombie) < 50) {
           direction = point_direction(nearest_zombie.x, nearest_zombie.y, x, y)
     } else if (instance_exists(oPlayer)) {
           direction = point_direction(x,y,oPlayer.x,oPlayer.y)
     } else {
          direction = point_direction(x,y,oCorpse.x,oCorpse.y)
     }
} else if (instance_exists(oPlayer)) {
    direction = point_direction(x,y,oPlayer.x,oPlayer.y)
} else {
    direction = point_direction(x,y,oCorpse.x,oCorpse.y)
}

image_angle = direction;
Or something like this. Depending upon a variety of other factors it could look pretty bad or it might be fine. Basically what it does is it checks to see if there is another zombie. If there is, it checks to see whether or not that zombie is close enough. If it is, it moves away from that zombie rather than towards the player. Otherwise it moves towards the player. If there are no other zombies, it acts the way your original code did. Using point_direction and direction is really unsophisticated movement and will likely cause your zombies objects to stutter if they are close to other zombies. However, you can fix this to some extent by making more sophisticated movement patters but using the same movement priorities (first move away from other zombies, then move towards player). For example, you could average the various point directions together and move in that new direction creating a sort of fake steering behavior look.
 
O

OneExalted

Guest
As other people have noted this is a moderately difficult problem to deal with which is why a lot of games don't actually (it's surprising how many games allow enemies to overlap each other once you start looking for it). Steering behaviors do this really naturally but are unfortunately not natively supported in game maker so you either have to learn how to do them from scratch or find some scripts made by other people. Both somewhat complicated processes. If you don't care too much about how it looks though, just try this:

Code:
/// Zombie Create Event

speed = 3;

/// Zombie Step Event

//find nearest zombie that isn't this one
var xx = x;
x -= 10000;
var nearest_zombie = instance_nearest(xx, y, object_index);
x += 10000;

if (nearest_zombie != id) {
     if (distance_to_object(nearest_zombie) < 50) {
           direction = point_direction(nearest_zombie.x, nearest_zombie.y, x, y)
     } else if (instance_exists(oPlayer)) {
           direction = point_direction(x,y,oPlayer.x,oPlayer.y)
     } else {
          direction = point_direction(x,y,oCorpse.x,oCorpse.y)
     }
} else if (instance_exists(oPlayer)) {
    direction = point_direction(x,y,oPlayer.x,oPlayer.y)
} else {
    direction = point_direction(x,y,oCorpse.x,oCorpse.y)
}

image_angle = direction;
Or something like this. Depending upon a variety of other factors it could look pretty bad or it might be fine. Basically what it does is it checks to see if there is another zombie. If there is, it checks to see whether or not that zombie is close enough. If it is, it moves away from that zombie rather than towards the player. Otherwise it moves towards the player. If there are no other zombies, it acts the way your original code did. Using point_direction and direction is really unsophisticated movement and will likely cause your zombies objects to stutter if they are close to other zombies. However, you can fix this to some extent by making more sophisticated movement patters but using the same movement priorities (first move away from other zombies, then move towards player). For example, you could average the various point directions together and move in that new direction creating a sort of fake steering behavior look.
I can't wait to get home and try this! It's kind of amusing to me how I spent 10 hours straight accomplishing such easy things through trial and error, thinking I was a genius lol. I clearly have a lot to learn. Thanks for the responses everyone! I'll let you know if this ends up working decently.
 
O

OneExalted

Guest
As other people have noted this is a moderately difficult problem to deal with which is why a lot of games don't actually (it's surprising how many games allow enemies to overlap each other once you start looking for it). Steering behaviors do this really naturally but are unfortunately not natively supported in game maker so you either have to learn how to do them from scratch or find some scripts made by other people. Both somewhat complicated processes. If you don't care too much about how it looks though, just try this:

Code:
/// Zombie Create Event

speed = 3;

/// Zombie Step Event

//find nearest zombie that isn't this one
var xx = x;
x -= 10000;
var nearest_zombie = instance_nearest(xx, y, object_index);
x += 10000;

if (nearest_zombie != id) {
     if (distance_to_object(nearest_zombie) < 50) {
           direction = point_direction(nearest_zombie.x, nearest_zombie.y, x, y)
     } else if (instance_exists(oPlayer)) {
           direction = point_direction(x,y,oPlayer.x,oPlayer.y)
     } else {
          direction = point_direction(x,y,oCorpse.x,oCorpse.y)
     }
} else if (instance_exists(oPlayer)) {
    direction = point_direction(x,y,oPlayer.x,oPlayer.y)
} else {
    direction = point_direction(x,y,oCorpse.x,oCorpse.y)
}

image_angle = direction;
Or something like this. Depending upon a variety of other factors it could look pretty bad or it might be fine. Basically what it does is it checks to see if there is another zombie. If there is, it checks to see whether or not that zombie is close enough. If it is, it moves away from that zombie rather than towards the player. Otherwise it moves towards the player. If there are no other zombies, it acts the way your original code did. Using point_direction and direction is really unsophisticated movement and will likely cause your zombies objects to stutter if they are close to other zombies. However, you can fix this to some extent by making more sophisticated movement patters but using the same movement priorities (first move away from other zombies, then move towards player). For example, you could average the various point directions together and move in that new direction creating a sort of fake steering behavior look.
This is a GIANT step in the right direction. I have a question about it though. What is the x-=10000 and x+=10000 doing exactly? Is that like maximum distance? The only thing I ended up changing is the image angle (so that they face the player instead of direction), and I'm playing around with the distance to object to find what looks the smoothest. I also am increasing the Zombies speed to compensate for the times the have to move away from eachother. One thing I would love to add to this would be a way to only let them move sideways (relative to the current way they faceing) when moving away from eachother. Looking through the code though I can see how that might not be possible with this method considering they seem to move directly away from the other zombie. Thanks again!
 
O

OneExalted

Guest
Alright I think I found what I'll stick with. Thanks again Samspade for your code. I ended up using that to make the enemies spread out when they're far from the player. Then they revert to my original movement when they get close. It actually plays decently for what it is. I think we can call this one solved! Here's the new code if you're interested.

Code:
/// Zombie Movement

var XX = x
x -= 10000
var NearestZombie = instance_nearest(XX,y,oZombie)
x += 10000



if instance_exists(oPlayer) {


    if (distance_to_object(oPlayer) >175) {


        if (NearestZombie != id) {
            if (distance_to_object(NearestZombie) <50) {
                    direction = point_direction(NearestZombie.x,NearestZombie.y,x,y)
                        }
            
            else {
                direction = point_direction(x,y,oPlayer.x,oPlayer.y)
                    }
        
                }
        
        else {
            direction = point_direction(x,y,oPlayer.x,oPlayer.y)
                }
    
    
        }

    else {
        direction = point_direction(x,y,oPlayer.x,oPlayer.y)
            }
    
            
    }

else {
    direction = point_direction(x,y,oCorpse.x,oCorpse.y)
        }
    
///Look Direction
    
if instance_exists(oPlayer)    {
    image_angle = point_direction(x,y,oPlayer.x,oPlayer.y)
        }
else {
    image_angle = point_direction(x,y,oCorpse.x,oCorpse.y)
        }
 

samspade

Member
This is a GIANT step in the right direction. I have a question about it though. What is the x-=10000 and x+=10000 doing exactly? Is that like maximum distance? The only thing I ended up changing is the image angle (so that they face the player instead of direction), and I'm playing around with the distance to object to find what looks the smoothest. I also am increasing the Zombies speed to compensate for the times the have to move away from eachother. One thing I would love to add to this would be a way to only let them move sideways (relative to the current way they faceing) when moving away from eachother. Looking through the code though I can see how that might not be possible with this method considering they seem to move directly away from the other zombie. Thanks again!
It sounds like you might have figured it out already but the x -= 10000 and x += 10000 is for the following reason - instance_nearest will find itself otherwise. In other words, if you use instance_nearest(x, y, object) it will return the closest instance of that object to those x and y coordinates. This is fine if the object using instance nearest is obj_player and is looking for obj_zombie. However, if obj_zombie is looking for obj_zombie then instance_nearest(x, y, obj_zombie) will find the closest obj_zombie which is itself. Generally, not very useful. What those three lines of code does is save the obj_zombie current x coordinate to xx and then change's it's current x coordinate to very far away. That way when instance_nearest looks for the nearest obj_zombie it won't find that one because it's x and y coordinates are now very different. The third line returns it to its original position.

One other thing you could try is this code for movement. I'd be curious to know if it works as I've never tried it myself. You would replace direction = point_direction(NearestZombie.x,NearestZombie.y,x,y) with it - whenever you wanted the zombies to move away from each other in other words. Basically, I think it might make the movement smoother.

Code:
var x_averaged = (-NearestZombie.x + oPlayer.x) / 2;
var y_averaged = (-NearestZombie.y + oPlayer.y) / 2;
direction = point_direction(x, y, x_averaged, y_averaged)
The idea of this code is that instead of telling the zombie to simply run directly away from the nearest zombie it creates a new x and y which is the a result of the averaged x and y of the player and nearest zombie and points in that direction. The end result is that the zombie now points in a direction which is an average between pointing directly away from the nearest zombie and directly towards the player meaning the zombie moves towards the player while still trying to avoid the other zombie. You could draw this out on a piece of paper to see what I mean. The reason NearestZombie.x and y are negative is that since you are trying to flee the nearest zombie you want to actually find the inverse of that zombie's location.

For example, zombie 1 is 0, 0 and zombie 2 is 10, 10. if zombie 1 wants to flee zombie 2 it needs to head towards -10, -10. If player is located at -10, 40 then (-10 + -10) / 2 is -10 and (-10 + 40) / 2 is 15 so the new point direction is -10, 15.

I'm not entirely sure this would work, as I haven't tried it myself.
 

Yal

🐧 *penguin noises*
GMC Elder
I'm not entirely sure this would work, as I haven't tried it myself.
I can see several potential problems...
  • All zombies just spreading out infinitely since the zombie coordinate is having an equal impact as the player coordinate no matter the distance
  • Jittering when whichever zombie is the nearest changes every step due to complex interactions
  • Zombies STILL moving into each other when there are big groups, because only the nearest impact decision-making and not other zombies that are very near but not AS near
It's definitely simple enough that it's worth trying, though - it might actually work decently enough anyway. :3
 
Top