Pathfinding Tutorial

(Download the project files to work along the tutorial for GMS2 -- and a working version in GMS1) 

In this tutorial series we are going to create a pathing controller that will map the obstacles in the world and generate paths. We will then use those paths to create a custom path following system so we can more easily manage collisions and non-mapped obstacles. (Note: using Game Maker 2023.6.0.89 will result in random crashes when using paths. It is recommended you use a different version)

Part 1: Collision Manager

Lets start by creating a script called scr_initCollisionGrid and place the following code inside:

function scr_initCollisionGrid(){
    /// auto run this script at game startup
    gml_pragma("global", "scr_initCollisionGrid()");
    
    #macro GRID_MARGIN    32    // Add padding to the grid so there is space around room edges
    #macro GRID_DIVS    32    // Grid square size
    
    /// create collision manager
    global.collisionManager = {};
    
}

Adding gml_pragma("global", "scr_initCollisionGrid")  will call the script function before the first room of the game is run. Now, lets add the following code to the global.collisionManager object brackets.

grid: -1,
position: {x: -GRID_MARGIN, y: -GRID_MARGIN, w: room_width+GRID_MARGIN,h: room_height+GRID_MARGIN, dx: GRID_DIVS, dy: GRID_DIVS},

reset: function(collObjectsArray){
    if(grid != -1){
        mp_grid_destroy(grid);    
    }
    position.w = room_width+GRID_MARGIN*2;
    position.h = room_height+GRID_MARGIN*2;
    var wcount = position.w/position.dx;
    var vcount = position.h/position.dy;
    if(debug_mode) show_debug_message($"Created new grid of size x: {wcount}, y: {vcount}");
    grid = mp_grid_create(position.x,position.y,wcount,vcount,position.dx,position.dy);
    mp_grid_clear_all(grid);
    addObjects(collObjectsArray);
},

addObjects: function(collObjectsArray){
    if(!is_array(collObjectsArray)) collObjectsArray = [collObjectsArray];
    for(var i = 0; i < array_length(collObjectsArray); i++){
        mp_grid_add_instances(grid,collObjectsArray[i],1);
    }
},

clearGrid: function(){
    mp_grid_clear_all(grid);
},

setPath: function(path, xto, yto){
    var pathCreated = mp_grid_path(grid, path, other.x, other.y, xto, yto, 1);
    return(pathCreated);
},

setPathFrom: function(path, xfrom, yfrom, xto, yto){
    var pathCreated = mp_grid_path(grid, path, xfrom, yfrom, xto, yto, 1);
    return(pathCreated);
},

positionFree: function(xx, yy){
    var _xto = (xx - position.x) div position.dx;
    var _yto = (yy - position.y) div position.dy;
    var _hitX = mp_grid_get_cell(grid, _xto, _yto) == 0;
    return(_hitX);
},

moveTo: function(xto, yto){
    if(positionFree(other.x+xto,other.y)){
        other.x += xto;    
    }
    if(positionFree(other.x,other.y+yto)){
        other.y += yto;    
    }
}

Here's a breakdown of what the code does:

1. The code defines a global object called `collisionManager` to manage collisions and pathfinding.

2. The `collisionManager` object has various properties and methods:

   - `grid`: Holds the reference to the grid used for collision and pathfinding. It is initialized with a value of `-1`.

   - `position`: Defines the position and size of the grid. It includes properties like `x`, `y`, `w`, `h`, `dx`, and `dy`.

   - `reset`: A method to reset the collision manager. It destroys the old grid, adjusts the size of the grid to match the room size, creates a new grid, and adds objects to it.

   - `addObjects`: A method to add obstacles to the collision grid. It accepts either a single object or an array of objects and adds them to the grid.

   - `clearGrid`: A method to remove all collisions from the grid.

   - `setPath`: A method to calculate a path from the calling object's position to the specified destination (`xto`, `yto`) and store it in the provided `path` variable.

   - `setPathFrom`: A method to calculate a path from the specified starting position (`xfrom`, `yfrom`) to the destination (`xto`, `yto`) and store it in the provided `path` variable.

   - `positionFree`: A method to check if a specified position (`xx`, `yy`) is free of obstacles in the grid. It returns `true` if the position is free and `false` otherwise.

   - `moveTo`: A method to move an object towards a specified position (`xto`, `yto`) using the grid to avoid obstacles. It checks if the desired movement in the X and Y directions is free of obstacles and updates the object's position accordingly.

3. The code initializes the `collisionManager` object by assigning it to the global variable `global.collisionManager`.

Overall, this code provides a framework for managing collisions and implementing pathfinding using a grid-based approach.

Now that we have some code to manage the collision system, lets create an object that called oStartCollisions and modify it to be persistent, and create a variable definition of type Asset called obstacle. Create a wall object and add it under the obstacle variable.

Next, in the Room Start event of oStartCollisions we need to add the code:

global.collisionManager.reset(obstacle);

Part 2: Path Management

Lets first start by defining all the variables we want to use to manage the path. We are going to store all the path points in an array so we can let the garbage collector manage the removal and it has a very low overhead performance-wise. Lets create a script called scr_init_path:

function scr_init_path(_step_size = 8){
    path_pos = 0;                        
    path_ready = false;                    
    path_length = 0;                    
    path_current_location = {x:x,y:y};    
    path_position_list = [];            
    path_step_size = _step_size;        
    path_node_range = 16;                
    path_end_position = [x,y];            
    path_end_range = 48;                
    path_distance = 1;                    
}

Here's a breakdown of what the code does:

1. The code initializes several variables used for pathfinding:

   - `path_pos`: Represents the current position in the path array.

   - `path_ready`: A boolean flag that indicates whether the path is ready or not. It is initially set to `false`.

   - `path_length`: Stores the length of the path array.

   - `path_current_location`: Represents the current position of the node. It is initially set to the values of `x` and `y`.

   - `path_position_list`: An empty array that will hold all the nodes in the path.

   - `path_step_size`: Specifies the distance between each node in the path. It is set to the value of `_step_size`.

   - `path_node_range`: Represents the margin or proximity around each node. It is set to 16.

   - `path_end_position`: Stores the last position in the path array. It is initially set to the values of `x` and `y`.

   - `path_end_range`: Specifies the range within which the path is considered to have reached its end. It is set to 48.

   - `path_distance`: Keeps track of the length of the path. It is initially set to 1.

2. The code sets up the initial state for pathfinding, initializing the variables to their respective starting values.

The function `scr_init_path` is called at the beginning to set up the necessary variables for pathfinding calculations.

Next, we want to write a script that moves the player on the path. Lets create a function called scr_update_path_pos:

function scr_update_path_pos(_spd, _wallObj){
    if(path_ready){
        // do stuff
    }
}

In the if statement (where "do stuff" is) place the following code:

/// get location
var _px = path_position_list[path_pos].x;
var _py = path_position_list[path_pos].y;
var _dist = path_node_range;
path_current_location.x = lerp(path_current_location.x, _px, 0.9);
path_current_location.y = lerp(path_current_location.y, _py, 0.9);
if(is_nan(_px) || is_nan(_py)){
    show_debug_message("broken path");
    path_ready = false;
    return;
}
/// last point, we want to get close
if (path_pos == path_length-1) {
    _dist = path_end_range;
}
var _next = point_in_circle(_px, _py, x, y, _dist);
/// keep from getting stuck
var _leave = 5;
while(_next && _leave-- > 0){
    /// increment path position when in range
    path_pos++;
    /// exit path when finished
    if(path_pos >= path_length){
        path_pos = 0;
        path_ready = false;
    }
    
    /// move node away from player
    var _px = path_position_list[path_pos].x;
    var _py = path_position_list[path_pos].y;
    _next = point_in_circle(_px, _py, x, y, _dist);
    
}
    
/// keep moving toward next path position
var _dir = point_direction(
    x,y,
    path_current_location.x,
    path_current_location.y
);
var _dx = lengthdir_x(_spd, _dir);
var _dy = lengthdir_y(_spd, _dir);
    
x += _dx;
y += _dy;

Here's a breakdown of what the code does:

1. The function checks if the path is ready (`path_ready` is `true`).

2. If the path is ready, the function performs the following steps:

   - It retrieves the x and y coordinates of the current node from the `path_position_list` at the current position (`path_pos`).

   - It uses linear interpolation (`lerp`) to gradually update the current location (`path_current_location`) towards the target node's coordinates.

   - It checks if the target node's coordinates (`_px` and `_py`) are not NaN (not-a-number). If they are NaN, it indicates a broken path, and the function sets `path_ready` to `false` and returns.

   - If the current position (`path_pos`) is at the last point of the path (path_length-1), it sets the distance (`_dist`) to the path_end_range.

   - It checks if the player's position (x, y) is within a certain range of the target node's coordinates (using `point_in_circle` function). If it is, the function enters a loop to increment the path position and find the next target node. It moves to the next node until the player is outside the specified distance range from the target node or until a certain number of iterations (`_leave`) is reached.

   - After finding the next node, the function calculates the direction (`_dir`) from the player's current position (x, y) to the target node's coordinates (path_current_location.x, path_current_location.y) using `point_direction`.

   - It calculates the change in x and y coordinates (`_dx` and `_dy`) based on the speed (`_spd`) and direction (`_dir`) using `lengthdir_x` and `lengthdir_y`.

   - It updates the player's position (x, y) by adding the calculated change in x and y coordinates.

3. If the path is not ready (`path_ready` is `false`), the function does nothing.

Once the last node is reached, the path is considered finished, and the function stops updating the player's position until a new path is ready.

Finally, we will create the script that generates the actual pathing data. Create a new script and call it scr_make_path:

function scr_make_path(xto, yto){
    /// create a path
}

Now lets fill the function with the following code:

var path = path_add();
path_ready = false;
/// generate path
var _setPath = global.collisionManager.setPath(path, xto, yto);
/// if path generated, grab the points on the path every 16 pixels
if(_setPath && path_exists(path)){
    path_pos = 0;
    path_distance = path_get_length(path);
    var path_step = path_step_size / path_get_length(path);
    path_position_list = [];
    
    try{
        /// start at 1, skip position right at path start
        for(var i = path_step; i <= 1; i+= path_step){
            
            var _ratio = floor(i * 1000) / 1000;
            var _px = path_get_x(path, _ratio);
            var _py = path_get_y(path, _ratio);
            array_push(path_position_list,{x: _px, y: _py});
        }
    } catch (e) {
        show_debug_message("failed to make path");
        path_delete(path);
        path_ready = false;    
        return;
    }
    
    /// set last position
    path_end_position = [xto, yto];
    
    path_ready = true;
    path_length = array_length(path_position_list);
}
path_delete(path);

Here's a breakdown of what the code does:

1. The function creates a new path using `path_add()` and assigns it to the variable `path`. It also sets the `path_ready` flag to `false`.

2. It calls the `setPath` method of the `global.collisionManager` object to generate a path from the current position (x, y) to the specified target position (`xto`, `yto`). The result is stored in the `_setPath` variable.

3. If the path was successfully generated (`_setPath` is true) and the path exists (using `path_exists`), the function continues with the following steps:

   - It sets the `path_pos` variable to 0, indicating the starting position in the path.

   - It calculates the total distance of the path using `path_get_length` and stores it in the `path_distance` variable.

   - It calculates the step size between each point in the path (`path_step`) by dividing `path_step_size` by the total length of the path.

   - It initializes an empty array `path_position_list` to store the positions of the nodes in the path.

   - It attempts to loop through the path from `path_step` to 1 (excluding 1) with a step size of `path_step`. Inside the loop, it calculates the x and y coordinates (`_px` and `_py`) for each point in the path using `path_get_x` and `path_get_y` functions, respectively. It adds an object with x and y coordinates to the `path_position_list` array using `array_push`.

   - If any error occurs during the loop, it indicates a failure to create the path. The function shows a debug message, deletes the path using `path_delete`, sets `path_ready` to `false`, and returns.

   - It sets the `path_end_position` variable to the target position (`xto`, `yto`).

   - It sets `path_ready` to `true` to indicate that the path is ready for use.

   - It sets `path_length` to the length of the `path_position_list` array.

4. Finally, it deletes the temporary `path` using `path_delete`.

This code generates a path from the current position to a specified target position using a collision manager. It calculates intermediate points along the path and stores them in an array for later use.

Part 3: Moving our game object

Now, to finish the implementation we just need to create a player object obj_player. In the create event of the player object add:

scr_init_path();

Next, add this to the step event:

scr_update_path_pos(3, obj_wall);

The wall object code doesn't do anything in this script, but is provided in case you want to use another built in pathing avoidance function or move_and_collide(..), (by replacing the code in scr_update_path_pos at the bottom of the script)

/// can be replaced with move_and_collide or other movement fcn
/// using obj_wall
x += _dx; 
y += _dy;

Now, lets add in a mouse event for global left pressed that will update the path end location and set the player in motion:

scr_make_path(mouse_x, mouse_y);

Conclusion:

This pathfinding tutorial has provided a comprehensive overview of implementing pathfinding in your game. We covered the essential concepts and techniques necessary for efficient and accurate navigation through complex environments using game makers built in A* path finding system.

Throughout the tutorial, we explored the creation of a collision manager that handles obstacles and grid-based pathfinding. We learned how to generate a grid, add obstacles to it, and calculate paths using A* algorithm. Additionally, we discussed methods to check for free positions, move along the path, and handle path updates.

By understanding these fundamental concepts, you now have the knowledge and tools to incorporate advanced pathfinding capabilities into your projects. Whether you're developing a game with intelligent NPCs or designing an autonomous system, pathfinding is a crucial aspect that greatly enhances the realism and interactivity of your application.

Remember, pathfinding involves a delicate balance between efficiency and accuracy. 

With the skills acquired in this tutorial, you are well-equipped to tackle pathfinding challenges and create immersive experiences that captivate your audience. So go ahead, experiment, and unleash the power of pathfinding in your projects!