Motion planning

Motion planning helps you to move certain instances from a given location to a different location while avoiding collisions with certain other instances (e.g. walls). Motion planning is a difficult problem. It is impossible to give general functions that will work properly in all situations. Also, computing collision free motions is a time-consuming operation. So you have be careful how and when you apply it. Please keep these remarks in mind when you use any of the following functions.

Different forms of motion planning are provided by GameMaker. The simplest form lets an instance take a step towards a particular goal position, trying to go straight if possible but taking a different direction if required. These functions should be used in the step event of an instance. They correspond to the motion planning actions that are also available:

mp_linear_step(x,y,stepsize,checkall) This function lets the instance take a step straight towards the indicated position (x,y). The size of the step is indicated by the stepsize. If the instance is already at the position it will not move any further. If checkall is true the instance will stop when it hits an instance of any object. If it is false it only stops when hitting a solid instance. Note that this function does not try to make detours if it meets an obstacle. It simply fails in that case. The function returns whether or not the goal position was reached.
mp_linear_step_object(x,y,stepsize,obj) Same as the function above but this time only instances of obj are considered as obstacles. obj can be an object or an instance id.
mp_potential_step(x,y,stepsize,checkall) Like the previous function, this function lets the instance take a step towards a particular position. But in this case it tries to avoid obstacles. When the instance would run into a solid instance (or any instance when checkall is true) it will change the direction of motion to try to avoid the instance and move around it. The approach is not guaranteed to work but in most easy cases it will effectively move the instance towards the goal. The function returns whether or not the goal was reached.
mp_potential_step_object(x,y,stepsize,obj) Same as the function above but this time only instances of obj are considered as obstacles. obj can be an object or an instance id.
mp_potential_settings(maxrot,rotstep,ahead,onspot) The previous function does its work using a number of parameters that can be changed using this function. Globally the method works as follows. It first tries to move straight towards the goal. It looks a number of steps ahead which can be set with the parameter ahead (default 3). Reducing this value means that the instance will start changing direction later. Increasing it means it will start changing direction earlier. If this check leads to a collision it starts looking at directions more to the left and to the right of the best direction. It does this in steps of size rotstep (default 10). Reducing this gives the instance more movement possibilities but will be slower. The parameter maxrot is a bit more difficult to explain. The instance has a current direction. maxrot (default 30) indicates how much it is allowed to change its current direction in a step. So even if it can move e.g. straight to the goal it will only do so if it does not violate this maximal change of direction. If you make maxrot large the instance can change a lot in each step. This will make it easier to find a short path but the path will be uglier. If you make the value smaller the path will be smoother but it might take longer detours (and sometimes even fail to find the goal). When no step can be made the behavior depends on the value of the parameter onspot. If onspot is true (the default value), the instance will rotate on its spot by the amount indicated with maxrot. If it is false it will not move at all. Setting it to false is useful for e.g. cars but reduces the chance of finding a path.

Please note that the potential approach uses only local information. So it will only find a path if this local information is enough to determine the right direction of motion. For example, it will fail to find a path out of a maze (most of the time).

The second kind of functions computes a collision-free path for the instance. Once this path has been computed you can assign it to the instance to move towards the goal. The computation of the path will take some time but after that the execution of the path will be fast. Of course this is only valid if the situation has not changed in the meantime. For example, if obstacles change you possibly will need to recompute the path. Again notice that these functions might fail. These functions are only available in the Standard Edition of GameMaker.

The first two functions use the linear motion and potential field approach that were also used for the step functions.

mp_linear_path(path,xg,yg,stepsize,checkall) This function computes a straight-line path for the instance from its current position to the position (xg,yg) using the indicated step size. It uses steps as in the function mp_linear_step(). The indicated path must already exist and will be overwritten by the new path. (See a later chapter on how to create and destroy paths.) The function will return whether a path was found. The function will stop and report failure if no straight path exists between start and goal. If it fails a path is still created that runs till the position where the instance was blocked.
mp_linear_path_object(path,xg,yg,stepsize,obj) Same as the function above but this time only instances of obj are considered as obstacles. obj can be an object or an instance id.
mp_potential_path(path,xg,yg,stepsize,factor,checkall) This function computes a path for the instance from its current position and orientation to the position (xg,yg) using the indicated step size trying to avoid collision with obstacles. It uses potential field steps, like in the function mp_potential_step() and also the parameters that can be set with mp_potential_settings(). The indicated path must already exist and will be overwritten by the new path. (See a later chapter on how to create and destroy paths.) The function will return whether a path was found. To avoid the function continuing to compute forever you need to provide a length factor larger than 1. The function will stop and report failure if it cannot find a path shorter than this factor times the distance between start and goal. A factor of 4 is normally good enough but if you expect long detours you might make it longer. If it fails a path is still created that runs in the direction of the goal but it will not reach it.
mp_potential_path_object(path,xg,yg,stepsize,factor,obj) Same as the function above but this time only instances of obj are considered as obstacles. obj can be an object or an instance id.

The other functions use a much more complex mechanism using a grid-based approach (sometimes called an A* algorithm). It will be more successful in finding paths (although it still might fail) and will find shorter paths but it required more work on your side. The global idea is as follows. First of all we put a grid on (the relevant part of) the room. You can choose to use a fine grid (which will be slower) or a coarse grid. Next, for all relevant objects we determine the grid cells they overlap (either using bounding boxes or precise checking) and mark these cells as being forbidden. So a cell will be marked totally forbidden, even if it only partially overlaps with an obstacle. Finally we specify a start and a goal position (which must lie in free cells) and the function computes the shortest path (actually close to the shortest) between these. The path will run between centers of 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. This path you can now give to an instance to follow.

The grid-based approach is very powerful (and is used in many professional games) but it requires that you do some careful thinking. You must determine which area and cell size are good enough for solving the game. Also you must determine which objects must be avoided and whether precise checking is important. All these parameters strongly influence the efficiency of the approach.

In particular the size of the cells is crucial. Remember that the cells must be large enough so that the moving object placed with its origin on the center of a cell must lie completely inside the cell. (Be careful about the position of the origin of the object. Also realize that you can shift the path if the origin of the object is not in its center!) On the other hand, the smaller the cells the more possible paths exist. If you make cells too large, openings between obstacles may get closed because all cells intersect an obstacle.

The actual functions for the grid-based approach are as follows:

mp_grid_create(left,top,hcells,vcells,cellwidth,cellheight) This function creates the grid. It returns an index that must be used in all other calls. You can create and maintain multiple grid structures at the same moment. left and top indicate the position of the top-left corner of the grid. hcells and vcells indicate the number of horizontal and vertical cells. Finally cellwidth and cellheight indicate the size of the cells.
mp_grid_destroy(id) Destroys the indicated grid structure and frees its memory. Don't forget to call this if you don't need the structure anymore.
mp_grid_clear_all(id) Mark all cells in the grid to be free.
mp_grid_clear_cell(id,h,v) Clears the indicated cell. Cell 0,0 is the top left cell.
mp_grid_clear_rectangle(id,left,top,right,bottom) Clears all cells that intersect the indicated rectangle (in room coordinates).
mp_grid_add_cell(id,h,v) Marks the indicated cell as being forbidden. Cell 0,0 is the top left cell.
mp_grid_add_rectangle(id,left,top,right,bottom) Marks all cells that intersect the indicated rectangle as being forbidden.
mp_grid_add_instances(id,obj,prec) Marks all cells that intersect an instance of the indicated object as being forbidden. You can also use an individual instance by making obj the id of the instance. Also you can use the keyword all to indicate all instances of all objects. prec indicates whether precise collision checking must be used (will only work if precise checking is enabled for the sprite used by the instance).
mp_grid_path(id,path,xstart,ystart,xgoal,ygoal,allowdiag) Computes a path through the grid. path must indicate an existing path that will be replaced by the computer path. xstart and ystart indicate the start of the path and xgoal and ygoal the goal. allowdiag indicates whether diagonal moves are allowed instead of just horizontal or vertical. The function returns whether it succeeded in finding a path. (Note that the path is independent of the current instance; It is a path through the g rid, not a path for a specific instance.)
mp_grid_draw(id) This function draws the grid with green cells being free and red cells being forbidden. This function is slow and only provided as a debug tool.