Dynamic MP Grids
If you've ever had to make any type of enemy movement in a game (especially a top down game) the chances are that you've had a look at - or used - the Motion Planning Functions, specifically MP Grids. On the surface, MP grids may seem a great solution for finding a way through a predefined maze, but are too rigid to be used in other circumstances, since, as the name implies, they "lock" movement to a grid. Well, in today's tech blog, I'm here to tell you that that isn't true, and you can use MP grids to create complex-appearing and dynamic AI with just a few lines of code...
Before we continue, this tech-blog will take the form of a mini-tutorial and as such requires you to open a base file to build on in GameMaker Studio 2. You can get this file from the link below and once downloaded simply go to the File menu in GMS2 and select Import.
GETTING STARTED
Once you've imported the above YYZ file, take a moment to run the project and examine the objects and code they contain. At the moment it's not very inspiring and simply sends poor skeletons from one side of the room to the other, and their doom...
We need to spice things up a bit and have our enemy change direction and react dynamically to things that the player does, and in this case we are going to have it change direction and avoid walls that the player adds into the room while playing. Which is where the MP grid comes into play!
For those that maybe haven't dipped their toes into this water yet, an MP grid is a "motion planning grid", and all it does is section up a room into individual grid "squares", and each of these squares can then be flagged as "occupied" or not. This grid is then used by another
mp_*
CREATE THE GRID
To get started, we'll first need to create our MP grid resource, so open up the object "obj_Control" and open the Create Event code block now. Here, apart from creating our MP grid, we will also make a single path resource too. Both the grid and the path will have their unique ID's stored in a
global
With the Create event open, add the following code:
global.ai_grid = mp_grid_create(0, 0, room_width / 64, room_height / 64, 64, 64); global.ai_path = path_add(); mp_grid_add_instances(global.ai_grid, obj_wall, false); mp_grid_define_path(obj_Start.x, obj_Start.y, obj_Finish.x, obj_Finish.y);
With this code, we are creating a grid that is 16 x 12 cells in size (we divide the room width and height by 64 to get the number of cells since our "base" block size in the game is 64) and we are assigning its ID to a global variable. You should note here that since MP grids are quite resource heavy, you should never make the grid smaller than is absolutely necessary - the smaller the cell size, the more processing it requires and the more possible it is that your game will lag later.
We also make another global variable and assign a new dynamic path ID to that. We call this a dynamic path, since it is one that will be created dynamically and change throughout the game (unlike the pre-defined path resources that can be created in the GameMaker Studio 2 Path Editor).
After that we then add the wall instances into the MP grid. All this function does is loop through all instances of the object "obj_Wall" in the room, and then use their position to "flag" a cell in the MP grid. These "flagged" cells will be the ones that we want the enemy instances to avoid.
The final "function" in the code isn't a function at all, it's a script that we are going to write now to create the path between two points...
THE PATH SCRIPT
We need a script to create the path that the skeleton instances are going to follow, so make a new script resource and call it
mp_grid_define_path
/// @function mp_grid_define_path(start_x, start_y, finish_x, finish_y); /// @param {real} start_x The start X position for the path /// @param {real} start_y The start Y position for the path /// @param {real} finish_x The finish X position for the path /// @param {real} finish_y The finish Y position for the path /// @description Create a path between two points using the path and MP grid /// stored in global variables. var _sx = argument0; var _sy = argument1; var _fx = argument2; var _fy = argument3; if !mp_grid_path(global.ai_grid, global.ai_path, _sx, _sy, _fx, _fy, true) { show_debug_message("ERROR: mp_grid_define_path() - No path created"); return false; } else { path_set_kind(global.ai_path, 1); path_set_precision(global.ai_path, 8); return true; }
This code gets the start and finish coordinates for our path and then uses them in conjunction with the function mp_grid_path()
So, our code first tries to create a path through the MP grid, and if none is found, it tells us with a message in the Output Window (you would normally have some failsafe code in here to catch this problem and deal with it, but for our tech blog, a simple message is fine). However if a path is found, it sets the path type to 1 to make a "smooth" path, and it sets the path precision to 8 to make the path as smooth as possible. This step isn't really necessary, but I find that it gives the path a better "feel" later.
Our script returns true or false depending on the outcome of the path creation check, which we will use as an additional check later in our tech blog.
DEBUGGING THE GRID
When working with MP grids and paths, it is often important to be able to see exactly what cells have been flagged as occupied, as well as show the path that is being created. For that we have some special Draw functions, which we are now going to add into our controller object to give a visual clue as to what exactly is going on. This code can be removed later (and should be, as it is one of the slowest functions in GML, which is why it is only for debugging!).
In the object "obj_Control" add a Draw End Event now with the following code (we use the Draw End event so it will be drawn over everything else):
if keyboard_check(vk_f1) { draw_set_alpha(0.1); draw_set_colour(c_white); mp_grid_draw(global.ai_grid); for (var i = 0; i < room_width; i += 64;) { draw_line_width(i, 0, i, room_height, 3); } for (var j = 0; j < room_width; j += 64;) { draw_line_width(0, j, room_width, j, 3); } draw_set_alpha(1); draw_path(global.ai_path, x, y, true); }
This code simply draws each cell of the MP grid as either red (flagged as occupied) or green (flagged as open), then draws some lines to better define the grid, before finally drawing the path.
You can run the tutorial game again now, and while the behaviour of the enemy instance hasn't changed, you can press F1 and see the MP grid cells that the walls fall into have been flagged as occupied (red) and you can also see the path drawn from the start to the finish instances.
TIDYING UP
There is one very important thing to do to now - tidy up our MP grid and path! Whenever you create a dynamic resource like an MP grid or a path, it takes a chunk of system memory to store its information. If you do not delete these resources from your game when no longer required, then they can quickly take over more and more memory which will eventually cause your game to lag and finally crash. To prevent that we need to add a Clean Up Event to our object "obj_Control" with the following:
path_delete(global.ai_path); mp_grid_destroy(global.ai_grid);
This frees up the memory associated with these resources and you should always make sure that anything that you create dynamically in your games has the equivalent clean up code in the appropriate event (Room End, Instance Destroy, Clean Up, etc...).
PLACING WALLS
We have one final block of code to add into our controller object, and that's the code to create the wall objects that you can place into the room to change the MP grid path. For that we need to use the Global Right Mouse Button Pressed event, so add that now to the object.
The code we are going to add here will first get the "snapped" mouse coordinates, then check the position for an instance of the wall object. If one is found it destroys it, but if one isn't found it then goes ahead and creates it (in this way the RMB can be used to add and remove wall instances). After creating the wall, it is then added into the MP grid, and the script we created earlier is used to re-create the path that the enemy instances will follow. At this point, if the path creation has succeeded, we send some information to the object "obj_pathfinder" (our skeleton "enemy" object), otherwise we destroy the wall instance we have just created because it is blocking the path and we want the enemy instances to always have a path to the goal.
We will cover the "obj_pathfinder" instance in the next part of the tutorial, but for now simply copy the code into the Global RMB Pressed Event:
var _snapx = (mouse_x >> 6); var _snapy = (mouse_y >> 6); var _inst = instance_position(mouse_x, mouse_y, obj_wall); var _change = false; if instance_exists(_inst) { mp_grid_clear_cell(global.ai_grid, _snapx, _snapy); instance_destroy(_inst); } else { _inst = instance_create_layer(_snapx << 6, _snapy << 6, "Wall_Layer", obj_wall); with (_inst) { mp_grid_add_instances(global.ai_grid, id, false); } } if mp_grid_define_path(obj_start.x, obj_start.y, obj_finish.x, obj_finish.y) { with (obj_pathfinder) { x_goto = path_get_point_x(global.ai_path, pos); y_goto = path_get_point_y(global.ai_path, pos); } } else { mp_grid_clear_cell(global.ai_grid, _snapx, _snapy); instance_destroy(_inst); }
Before we move on to the pathfinder, take a moment to note the use of bitshifting here to snap the mouse coordinates to the 64x64 grid. This is a fast way to round any value to a power of two, and you can change the range simply by changing the number of bits to shift down or up, so if you want to snap to a 16x16 grid, for example, you'd shift by 4. You can find more information on this in the manual.
THE PATHFINDER
Our last task in this tech blog project is to have our skeleton object "obj_pathfinder" actually follow the new path that we've created. For that, open object now and then open the Create Event and remove the current code block before adding in the following:
image_speed = 01; pos = 1; x_goto = path_get_point_x(global.ai_path, pos); y_goto = path_get_point_y(global.ai_path, pos);
This code creates a variable to hold the current path position, as well as two more variables to hold the room coordinates of that position. You see, what we are going to do here is not start our instance along the path using
path_start()
When the
mp_grid_path
To overcome this, what we are going to do is use another of the more basic AI functions that GML has to move from point to point on the path in a more autonomous way. So, we need to know the current "go to" point and its coordinates - which when the AI is created is point 1.
But the instance isn't actually moving yet? Let's add in our final block of code to deal with that... Create a Step Event and open a code block, then add this code:
if point_distance(x, y, x_goto, y_goto) < 8 { if ++pos == path_get_number(global.ai_path) { instance_destroy(); } else { x_goto = path_get_point_x(global.ai_path, pos); y_goto = path_get_point_y(global.ai_path, pos); } } mp_potential_step(x_goto, y_goto, 3, false); var _dif = angle_difference(point_direction(x, y, x_goto, y_goto), image_angle); image_angle += clamp(-3, _dif, 3);
Believe it or not, this short code block is probably the most important in the whole project! This code will give our enemy instances a basic AI that actually avoids obstacles while constantly searching for the path to the finish instance location. How does it do this? Well, we are first of all checking to see if the instance has reached the assigned path position (we set the
x_goto
y_goto
We next check to see if pos is equal to the length of the path, because if we try to get a position that is not on the path - ie: we've reached the last point and we try to get the next one, which doesn't exist - then GameMaker Studio 2 will give an error, which we obviously don't want. If it hasn't reached the end of the path then the next path point position is used to set the
x_goto
y_goto
The last two lines are where the magic happens! We use the function
mp_potential_step()
It's this combination of the MP grid and the other motion planning functions that make this simple AI surprisingly versatile and powerful, so keep in mind that you can mix and match simple functions like this to achieve sophisticated effects when making your games.
SUMMARY
That's it for this tech blog! You can test your project now and use the RMB to place and remove wall objects. If you have done everything correctly, then if you press "F1" while adding and removing walls you should be able to see the path change (try making one right on top of the path and see what happens, or even try blocking the path altogether!). You should also see the enemy instances rushing to change course and avoid it the newly placed walls, all the while getting back to the main path.
Now, this AI is not foolproof, but hopefully you have a good enough grasp of the necessary functions to improve upon it. For example, you can "trap" an enemy instance in a loop of movement if the path point they have to go to means they have to go backwards around a wall... can you fix this? (I'll give you a hint - you can use an alarm in the enemy and count a variable down.)
Have fun playing with these functions and this demo project!