Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more

Tech

Using Motion Planning

Posted by Mark Alexander on 29 August 2014

In today’s article we are going to go over the motion planning functions in GameMaker: Studio. If you are not familiar with them, they are a set of functions that use different methods to get an instance from point A to point B, and they can be configured in different ways to make this movement more complex. You can get an overview of the functions from the GameMaker manual here: Motion Planning Functions.

The motion planning functions are split into three groups, with each type offering different pros and cons, as well as levels of sophistication. Which functions you use will depend largely upon the game you are making and the uses you want to put them to, but it is important to note that the functions themselves are not mutually exclusive and they are most powerful when combined. Together they can create very powerful artificial intelligence (AI) for your games! However, before getting to that level, let's just quickly run through each type and how it works.

Mp_linear Functions

Arguably the "weakest" of the motion planning function, the mp_linear functions are only capable of calculating straight-line movement from one point to another. There are two types of linear functions, one that steps towards its goal, and one that generates a path to the goal.

Linear stepping will simply move the instance from point A to point B in a straight line, stopping if it meets any other instance (which can be flagged as solid or normal) or any given instance or object if you use the _object version. This behaves almost the same as the move_towards_point() function, only it automatically detects collisions along the way and will stop if it encounters one. This can be very useful for things like (for example) moving platforms that you want to stop if an enemy or other instance is blocking them, but move again if they are not.

Linear pathing will take a pre-made path, clear it, and then add in the path point for point A before "stepping" along the line to point B checking for collisions along the way either with any instance (which can be flagged as solid or not) or with a specific instance or object if you use the _object version. If no collision is found the end point of the path is set to point B and the function returns true, but if there is a collision, then the pathing function will return false and the path will be cut short. This does not mean that the path hasn't been generated, as it has! All it means is that the path did not reach point B, but has been created up to the point that it met the collision. When the path has been generated, you will then need to call path_start() to set the instance moving. This function can be useful for bullet objects, or instances that need to follow another one closely.

When using the pathing functions be aware that you must have created the path previously with path_add(). Normally you would do this in the Create Event and then just re-assign the path when required using the mp functions. It is very important to note that the path must be deleted at the end of the room or when the instance is destroyed to prevent memory leaks! This advice goes for all the functions that use paths in this article.

When using these functions, you should note that the collisions will be checked against the current sprite index or sprite mask that the instance running the code has, so if there is no sprite or mask assigned there will be no collisions detected. The detection is also carried out over the step sizes, and with the step functions, the instance will not move into collision, but stop if the current direction plus "stepsize" meets anything. The path functions are similar, in that the last path point will be generated at the last good position before the collision was detected.

Mp_potential Functions

As with the linear functions, the potential functions have step and path versions, but unlike the linear functions, these ones will actively try to avoid instances. This makes them quite powerful for creating instance behaviours and simulating basic AI.

These functions work on potential steps, which basically means that the instance will do checks every step (or along the path when it is generated) for any instances, or solids, or a given object or instance. These checks take into consideration the current rotation of the instance, and in the case of the step function the functions will rotate the instance by a given amount each step and re-check the new direction for a collision and move if it can. The step functions are ideal for things like "zombie" AI or as a compliment to other motion planning functions.

The path versions of the potential functions are slightly more complicated. They take the start position and orientation of the instance then start to create a straight-line path to the goal position, checking along the way in "chunks" for collisions. If a collision is found, then the path is re-factored and advanced a bit more. To prevent infinite loops, you can set the factor value, with a larger factor requiring more processing and time to resolve, while a lower factor will be faster, but more likely to fail. Like the linear path functions, even if the function fails, a path is still generated and can be used, but it will not reach the goal position (unless the instance is completly blocked in which the function will fail and no path will be generated). This can be very useful even in sophisticated AI as it creates a natural "search" path.

You can control the behaviour of these functions using mp_potential_step_settings(), which permits you to change the number of degrees that an instance will rotate while checking for a collision, the maximum degrees of rotation permitted each step, the distance (in pixels) ahead that the collision check should be performed, and finally the ability to rotate on the spot when in a collision. Note that switching off the on-spot rotation will greatly reduce the ability for the instance to negotiate obstacles. These settings will also affect the way the pathing functions search out a path through any obstacles.

MP_grid Functions

Now we come to the most powerful of all the motion planning functions... the motion planning grids. An mp_grid is similar to a ds_grid in that it is an area that is split into individual cells, and these cells can have a value to flag it as occupied or not. An occupied cell will be considered as "impassable" when you later calculate the path from point A to point B, and you can flag cells as occupied using the mp_grid_add_cell, _add_rectangle, or _add_instance functions. In this way you can create a "map" of where an instance can move and where it can't.

As you can see from the images above, when you add an instance to the mp_grid, you have to take into consideration the grid resolution, and the mask of the instance being used, as even if only 1 pixel overlaps a grid square it will be flagged as occupied and may cause the created path to be wrong or even fail completely.

How do you create a path? Well, you need to use the function mp_grid_path(), which will take a previously made path, clear it and attempt to re-create it to form a connection between point A and point B. the function will return true if the path is made, and false otherwise, but unlike the previous path functions, if it is false, then the path will not be populated and will instead be empty.

With the mp_grid functions, you can do things like create maze solving instances or have an enemy chase an instance through a room. However it is worth noting that these grids are very intensive and shouldn't be abused when using them.

Tips And Tricks

When working with the motion planning functions it is very important to keep some basic principles in mind, otherwise you can easily run into problems with memory and with performance. The first thing to note is that the pathing functions will require the instance using them to have made the path previously. This would normally be done in the Create Event of the instance, but you must not neglect to delete the path later when the instance is destroyed or the room ends otherwise you'll get a memory leak, which will, over time, slow down and crash your game. Below is an example code snippet for an instance using an mp path:

// CREATE EVENT
path = path_add();
go = true;

// STEP EVENT
if (go)
{
var p = mp_potential_path(path, obj_Player.x, obj_Player.y, 3, 4, 0);
if (p)
    {
    go = false;
    path_start(path, 3, 0, 0);
    }
}

// PATH END EVENT
go = true;

// ROOM END EVENT
path_delete(path);

// DESTROY EVENT
path_delete(path);

When working with mp grids, it becomes even more important to watch how you set them up, since they require more processing and memory. In general you'll want to create a global grid in some controller object at the start of the room, and then you would have the instances access that to create individual paths. In the case of a Tower Defense type game (for example) you could even make a global path and then have instances follow that. Typically a controller for an mp grid would be set up like this:

// CREATE EVENT
global.AI_Grid=mp_grid_create(0,0,room_width/32,room_height/32,32,32);
mp_grid_add_instances(global.AI_Grid,obj_Wall,false);
mp_grid_add_instances(global.AI_Grid,obj_Blocker,false);

// ROOM END
mp_grid_destroy(global.AI_grid);

Creating the path through the grid is also an intensive process, so it is recommended that you don't do it every step unless absolutely necessary. You can simply place it in a repeating alarm that is triggered every 5 steps or something, or have it only re-calculate if the instance or point to go to actually moves out of its current grid cell. Also note that if you have multiple instances pathing through the grid, it is a good idea to use staggered alarms (when you first set them use a random value) to help spread the load and prevent CPU spikes.

One thing that was mentioned at the start of this article was that mixing the mp functions is the way to create more powerful AI. A great example of this is when using mp_grids. The path that is create is a rigid thing and will only change when you re-generate it. this means that if you have multiple enemies and their paths over-lap then you will have issues, as the instance will try to progress along the path while dealing with collisions with other instances whose path coincides with the one its on. This will result in instances either "bunching up" or "jumping" from points on the path, which looks terrible.

To get around this, you can create a path through the grid but not set the instance along it. Instead you can use the mp_potential_step function to move from point to point along the path. This has the benefit of creating a more natural movement and also permitting the instances to interact and "wait" for the other instances around it to move out of the way before continuing. Here's an example image of some code which does this (the script "Define_Path" simply creates the path for the instance):

That image was taken from a tutorial on the YoYo Games Knowledge Base, so if you want to test out some of the things discussed in this article, you can check it out here: Using Mp_grids To Create AI.

This tech blog only scratches the surface of the motion planning functions, and we have discussed only a small sample of what you can do with them, but there are many more things that work well together so don't be afraid to experiment!

 

Back to Top