Windows Enemy AI

DarthTenebris

Definitely not a Sith Lord
Hello everybody,

I am currently trying to make my game's enemies, and I thought I'd start from the most basic enemy, a simple kamikaze enemy. Unfortunately it turns out it isn't as simple as I thought, particularly when it comes to their behavior.
upload_2019-6-19_14-9-4.png
The circles are the enemies, the box on the left is the spawner, and the box on the right is the target. The player is the tank. This grid is drawn by the function mp_grid_draw(), and it's making me wonder.

1. Why is the grid uneven? All objects are 64x64, center origin, while the grid is 32x32, to make sure a 64x64 can be placed a bit more freely instead of just on the center of a 64x64 grid.
Code:
grid = mp_grid_create(0, 0, room_width / 32, room_height / 32, 32, 32);
mp_grid_add_instances(grid, obj_wall, false);
path = path_add();
if (mp_grid_path(grid, path, x, y, obj_target.x, obj_target.y, true)) {
    path_start(path, 0, path_action_stop, false);
}
The code above is located in the create event of the enemy object.

2. The main problem is that the enemy can't pathfind through the gaps, even though it obviously fits. Why is that, and how would I fix that?

3. I've tried the other mp_* functions but the grid is the one that gave me the most progress. The manual says the grid is the most costly. Could I use the other mp_* functions to achieve my goal? I plan on adding "smarter" enemies, that could try to avoid the player, or instead rush past the player, etc. but for now a kamikaze enemy would do. The obstacles generally don't change, not planned for now at least.

Thank you for your time.
 
I just made a grid, and it showed up perfectly normal. Not sure why you're seeing something different.

As to the size of the grid cells: they have to be the size of the object that you want moving around. The way that the path finding works has nothing to do with the information of the object, and just looks at what cells are free. It does not actually consider whether the calling instance can fit. The cells size must be as large as the object for the path finding to work properly. That's just the nature of how it functions.

Your cells are 32 by 32, so say that you had a wall one cell away from the edge of the grid. To the path finding that gap is a free cell (no questions asked - it's empty, end of story), but if your object is 64 by 64 it clearly isn't going to fit. A path will still be returned though, because it expects you to have tailored the grid cell size to the object.
 

Phil Strahl

Member
About the grid: It looks like there's some kind of down-scaling going on in your viewport that the grid doesn't show up at 100% size. This could be because you resized the game window or the port is smaller than the view, for example.
 

rIKmAN

Member
For the pathing not working, it's because your object is bigger than the grid size so it isn't seeing any "free" cells.

From the mp_grid docs:
The path will run between the centers of all free cells, so if the cells are large enough so that the instance placed at its center will lie completely inside it this will be successful.

You should realise how important cell size is for this as the cells must be large enough so that the moving object placed with its origin on the center of a cell will lie completely inside the cell. (Be careful about the position of the origin of the object.)
 

NightFrost

Member
On a more general level, it should be noted that your movement is not strictly grid aligned. Examples of games with such movement would be NetHack, Dungeon Crawl Stone Soup, tactical RPGs such as Disgaea series, Rimworld, even XCOM (old and new). Some of these are more realtime than others, but step or turn always ends and consequently starts grid-aligned. Your entities however move freely. Also the player is likely moving constantly, so it is nearly guaranteed that remembering most of the calculated path is unnecessary, because it becomes obsolete.

For these reasons, I would propose writing your movement differently. Instead of strictly moving along the path, treat it as direction of shortest path towards the player. After calculating the path, save its first point to other variables as your movement goal, then destroy the path. Have the enemy move towards this goal and upon reaching it, repeat the process by requesting a new path. The exception is when player's location on the grid changes, then you must immediately request a new path and handle it as before. Otherwise the enemy will react to player movement with lag.

This'll also be helpful when you start wondering how to make the enemies not overlap. The answer is, that can't be done with mp grid. You'll ditch it but still have an enemy movement system that can take destinations from some other pathfinder system.
 

Rob

Member
On a more general level, it should be noted that your movement is not strictly grid aligned. Examples of games with such movement would be NetHack, Dungeon Crawl Stone Soup, tactical RPGs such as Disgaea series, Rimworld, even XCOM (old and new). Some of these are more realtime than others, but step or turn always ends and consequently starts grid-aligned. Your entities however move freely. Also the player is likely moving constantly, so it is nearly guaranteed that remembering most of the calculated path is unnecessary, because it becomes obsolete.

For these reasons, I would propose writing your movement differently. Instead of strictly moving along the path, treat it as direction of shortest path towards the player. After calculating the path, save its first point to other variables as your movement goal, then destroy the path. Have the enemy move towards this goal and upon reaching it, repeat the process by requesting a new path. The exception is when player's location on the grid changes, then you must immediately request a new path and handle it as before. Otherwise the enemy will react to player movement with lag.

This'll also be helpful when you start wondering how to make the enemies not overlap. The answer is, that can't be done with mp grid. You'll ditch it but still have an enemy movement system that can take destinations from some other pathfinder system.
You're right but I think he wants his balls to go towards the stationary target rather than the player in this instance.
 

NightFrost

Member
You're right but I think he wants his balls to go towards the stationary target rather than the player in this instance.
So it is, in which case mp-gridding the path is sufficient as long as OP doesn't mind enemies overlapping each other. If that is undesirable, then methods such as steering behaviors have to be considered.
 

DarthTenebris

Definitely not a Sith Lord
I just made a grid, and it showed up perfectly normal. Not sure why you're seeing something different.

As to the size of the grid cells: they have to be the size of the object that you want moving around. The way that the path finding works has nothing to do with the information of the object, and just looks at what cells are free. It does not actually consider whether the calling instance can fit. The cells size must be as large as the object for the path finding to work properly. That's just the nature of how it functions.

Your cells are 32 by 32, so say that you had a wall one cell away from the edge of the grid. To the path finding that gap is a free cell (no questions asked - it's empty, end of story), but if your object is 64 by 64 it clearly isn't going to fit. A path will still be returned though, because it expects you to have tailored the grid cell size to the object.
For the pathing not working, it's because your object is bigger than the grid size so it isn't seeing any "free" cells.

From the mp_grid docs:
The relevant objects are 64x64, however the reason my grid is 32x32 is because the center origin messes up placing in the room editor, therefore I have it snapped at 32x32 there, and as a side effect, allows half-object sized holes to exist. Am I still to keep my grid 64x64?
EDIT: I changed the grid to 64x64, and it now works most of the time, but occasionally the enemy collides into the edges of the wall. How can I fix that?

About the grid: It looks like there's some kind of down-scaling going on in your viewport that the grid doesn't show up at 100% size. This could be because you resized the game window or the port is smaller than the view, for example.
My laptop is pretty ancient by now, running only a 1366x768 display, however the room is set to be 1920x1024 for a perfect alignment of 64x64, but also a window size of 1920x1080 to fill the more common 1080p monitor. Is that causing the weird issues on my screen?

On a more general level, it should be noted that your movement is not strictly grid aligned. Examples of games with such movement would be NetHack, Dungeon Crawl Stone Soup, tactical RPGs such as Disgaea series, Rimworld, even XCOM (old and new). Some of these are more realtime than others, but step or turn always ends and consequently starts grid-aligned. Your entities however move freely. Also the player is likely moving constantly, so it is nearly guaranteed that remembering most of the calculated path is unnecessary, because it becomes obsolete.

For these reasons, I would propose writing your movement differently. Instead of strictly moving along the path, treat it as direction of shortest path towards the player. After calculating the path, save its first point to other variables as your movement goal, then destroy the path. Have the enemy move towards this goal and upon reaching it, repeat the process by requesting a new path. The exception is when player's location on the grid changes, then you must immediately request a new path and handle it as before. Otherwise the enemy will react to player movement with lag.

This'll also be helpful when you start wondering how to make the enemies not overlap. The answer is, that can't be done with mp grid. You'll ditch it but still have an enemy movement system that can take destinations from some other pathfinder system.
If I'm understanding correctly... Create a path, follow the path for a while, save the location, and make a new path to take into account environment changes?
EDIT 2: I set it to recalculate the path every 3 seconds, doesn't seem to help. Any ideas?

So it is, in which case mp-gridding the path is sufficient as long as OP doesn't mind enemies overlapping each other. If that is undesirable, then methods such as steering behaviors have to be considered.
I think I'll ignore enemy overlap for now, but thanks for the consideration.

Thank you everybody for your time :)
 
Last edited:

NightFrost

Member
To figure when target has moved to a different grid cell and enemies need to recalculate paths, you need to track its grid position. You do this by calculating the position every step and comparing it to previous grid position. For example, in this manner:
Code:
// CREATE EVENT of the moving target.
Grid_X = 0;
Grid_Y = 0;
Moved = false;

// STEP EVENT, after movement has been handled.
Moved = false;
// Let's say your grid is 32 by 32 pixels, so we'll divide position by grid size and floor away fractions to get grid position.
var New_X = floor(x / 32);
var New_Y = floor(y / 32);
// If current position is not equal to previous position, mark this as moved.
if(Grid_X != New_X || Grid_Y != New_Y){
    Moved = true;
    Grid_X = New_X;
    Grid_Y = New_Y;
}
Optimally you'd have your grid size in some global variable so you can reference it everywhere instead of having to write numbers all around your code. Now that your target has updated its movement status, every enemy can check it:
Code:
// Assuming current pathing target is saved in "Target" variable.
if(instance_exists(Target)){
    if(Target.Moved == true){
        // Calculate new path to target.
    }
}
 

Phil Strahl

Member
My laptop is pretty ancient by now, running only a 1366x768 display, however the room is set to be 1920x1024 for a perfect alignment of 64x64, but also a window size of 1920x1080 to fill the more common 1080p monitor. Is that causing the weird issues on my screen?
Yes, I'd say that that's the issue. If you want to be 100% certain you could build the game with the grid and try it on a computer capable of displaying its resolution natively.
 

rIKmAN

Member
The relevant objects are 64x64, however the reason my grid is 32x32 is because the center origin messes up placing in the room editor, therefore I have it snapped at 32x32 there, and as a side effect, allows half-object sized holes to exist. Am I still to keep my grid 64x64?
EDIT: I changed the grid to 64x64, and it now works most of the time, but occasionally the enemy collides into the edges of the wall. How can I fix that?
Like the manual says, for pathing to work correctly the object needs to fit fully inside the the cells of the grid if the object is at the centre of the cell (taking into account the origin), so you can either make your grid larger or make the objects smaller (sprite / bounding box or both - you'd have to check this as I can't remember the exact wording of the manual).

One method I've used in thepast is to have a small 8x8, 16x16 etc object which does the pathing, and then simply setting my actual object (character etc) to the x/y of the pathing object so it appears like the character is pathing, when really it's just being attached to the invisible smaller pathing object.

Whether that would work for you or not depends on your game as it might visually look wrong if the characters are popping through walls or looking like they shouldn't fit through gaps and corridors but are doing.
 

DarthTenebris

Definitely not a Sith Lord
Like the manual says, for pathing to work correctly the object needs to fit fully inside the the cells of the grid if the object is at the centre of the cell (taking into account the origin), so you can either make your grid larger or make the objects smaller (sprite / bounding box or both - you'd have to check this as I can't remember the exact wording of the manual).

One method I've used in thepast is to have a small 8x8, 16x16 etc object which does the pathing, and then simply setting my actual object (character etc) to the x/y of the pathing object so it appears like the character is pathing, when really it's just being attached to the invisible smaller pathing object.

Whether that would work for you or not depends on your game as it might visually look wrong if the characters are popping through walls or looking like they shouldn't fit through gaps and corridors but are doing.
I prefer modifying code rather than sprites, so that's what I went with. However, neither enlarging nor shrinking the grid size helped, I tried 32, 64, and 128, all of then had a problem. 32 and 64 aren't too different, the objects collide into walls, while 128 made the walls too large on the grid.
ezgif.com-resize.gif
I mean... I guess I can sell it off saying "the kamikaze pilots aren't very great at flying either", but a part of me still wants to try to fix this problem (the gif above is the grid at 64x64).

Code:
Create Event:
grid = mp_grid_create(0, 0, room_width / 64, room_height / 64, 64, 64);
mp_grid_add_instances(grid, obj_wall, false);
path = path_add();
if (mp_grid_path(grid, path, x, y, obj_target.x, obj_target.y, true)) {
    path_start(path, 4, path_action_stop, false);
}
alarm[0] = room_speed * 3;

Alarm0 Event:
mp_grid_destroy(grid);
path_delete(path);

grid = mp_grid_create(0, 0, room_width / 64, room_height / 64, 64, 64);
mp_grid_add_instances(grid, obj_wall, false);
path = path_add();
if (mp_grid_path(grid, path, x, y, obj_target.x, obj_target.y, true)) {
    path_start(path, 4, path_action_stop, false);
}
alarm[0] = room_speed * 3;
Thank you for your time.
 
Top