Dynamic MP Grids


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...

Skeletons Going To 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_* function to create a unique path resource that will try to go around those squares flagged as "occupied" and go through those ones that are not. You then assign this path resource to an instance and it will look to the player like the instance is displaying "intelligence" as it neatly avoids obstacles while following the path. For full details, please see the manual.


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 scope variable - we use global variables since we only need one single path and one grid for all instances to use in this project. In general, it's good practice when using MP grids to only ever create one and have all instances access that, since creating and using MP grids is a fairly processor intensive task.

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. Now copy the following code into it:

/// @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(). This function will calculate a path between the two given points and returns true if one is found (ie: no obstacles flagged in the grid block it) or it will return false if none is found. Note that if the function returns true, it also creates the path for you and assigns it to the path resource that you use as the second argument (in this case the global path we defined at the start).

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.

Mp Grid debug overview

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() as you may expect. No, instead we are going to have it go from point to point on the path without actually using the path itself. Let me explain...

When the mp_grid_path function creates the path, the path is comprised of a number of points, and each point has an x/y position in the room. Now, if we have the enemy instance follow the path exactly, when the path changes (as you add wall objects) the enemy instances will "jump" to a new position and it will all look very bugged as they change position in the room to keep on the path. Obviously this is not a behavior that we want!

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 and y_goto variables in the create event, remember?) and if the position has been reached, we increment the position counter variable (pos) and then use that to determine what to do next.

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 and y_goto variables again.

The last two lines are where the magic happens! We use the function mp_potential_step() to move our instance towards the path point that is defined as the current position to go to. This function on its own is a very basic AI as it tells an instance to move towards a point while avoiding obstacles. However it is not powerful enough to cross a whole room of obstacles, which is why we are using the MP grid. But it is powerful enough to avoid one or two obstacles and get to the defined path point, which is close by and easy to reach.

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.

Debug final 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!



Written by Mark Alexander

Mark Alexander is the former GameMaker technical writer. He’s moved on to pastures new, but still hangs around as admin on the GameMaker Community forum and makes his own indie games as Nocturne Games.