GameMaker Platformer Pathfinding. Tutorial

S

Skull_k

Guest
GM Version: Game Maker Studio 2
Target Platform: All
Download: NA
Links: https://www.youtube.com/channel/UCQ02JtC2Kbu_PnMPaxBDQEQ

Summary:
This tutorial deals with platform pathfinding. I made 3 vidéos on Youtube to explain how we can implement pathfinding for a 2D platformer in game maker studio 2.
This tutorial is split in 3 parts :

- Fill the grid (Part 1)
- Build a path (Part 2)
- Follow the path (Part 3)

Tutorial:


The aim of this to tutorial is to show the theory and how I managed the pathfinding in game maker. For sure, it is not the only solution to implement pathfinding, but I think it is a base to go further and to improve the code.
So this code is just a base and have to be adapted to your own game, it is very important, you cannot copy these codes and expect that it will work for your own game. You have to adapt it. Anyway, I hope it will be useful for some people. Please find below all the code shown in Youtube Tutorial.

In create event of the player :
Code:
// Initialization of variable player's movement
max_speed = 4;
game_gravity = 1;
acceleration = 0.3;
game_friction = 0.2;
jump_height = -11;
speed_v = 0 ;
speed_h = 0 ;
In step event of the player
Code:
//Input of the player. Horrizontal mouvement
var player_input = keyboard_check(vk_right) - keyboard_check(vk_left) ;
if player_input != 0
    {
        speed_h += player_input * acceleration;
        speed_h = clamp(speed_h, -max_speed, max_speed);
    }
        else
        {
            speed_h = lerp(speed_h, 0, game_friction);
        }

//Jump input of the player. Vertical mouvement
if !place_meeting (x, y+1, O_Collision)
    {
        speed_v = speed_v + game_gravity ;
    }
    else    {
                if keyboard_check(vk_space)
                {
                    speed_v = jump_height ;
                }
            }
    
// Check if there is collision
scr_collision();
The collision script : scr_collision
Code:
//Collision horizontal with object Collision
if place_meeting(x+speed_h, y, O_Collision) {
    while !place_meeting(x+sign(speed_h), y, O_Collision) {
        x += sign(speed_h);
    }
    speed_h = 0;
}
x += speed_h;

// Collision vertical with object Collision
if place_meeting(x, y+speed_v, O_Collision) {
    while !place_meeting(x, y+sign(speed_v), O_Collision) {
        y += sign(speed_v);
    }
    speed_v = 0;
}
y += speed_v;
In create event of the enemy
Code:
/// Initialize the color
draw_set_color (c_black) ;

/// initialize variables in order to draw grid and the path
ds_gridpathfinding = noone ;
path_building = noone ;

/// Initialize variables for ennemy movement
max_speed = 4;
game_gravity = 1;
acceleration = 0.3;
game_friction = 0.1;
jump_height = -10;
speed_v = 0 ;
speed_h = 0 ;

/// Intialialize variables for follow the path
action = 0 ;
path_point = 0 ;
jump_action = 0 ;
In step event of the enemy :
Code:
if keyboard_check(ord("S"))
{
     /// Reset all variable when we build a new path because enemy might be in path when we press S
     speed_h = 0;
     speed_v = 0;
     if path_exists(path_building) {
         path_delete (path_building);
     }
     path_point = 0 ;
     action = 0 ;
     jump_action = 0 ;

    scr_fill_the_grid(floor(x/O_Grid.cell_width), floor(y/O_Grid.cell_height), floor(O_Player.x/O_Grid.cell_width), floor(O_Player.y/O_Grid.cell_height));
}

// Follow the path if path exists
if path_exists(path_building)
{
    scr_follow_the_path(path_building);
}


// Apply gravity
if !place_meeting (x, y+1, O_Collision)
    {
        speed_v = speed_v + game_gravity ;
    }

// Check if there is a collsiion
scr_collision () ;
In draw_gui of the enemy :

Code:
// Draw the grid
if ds_exists(ds_gridpathfinding,ds_type_grid) {
    for (var i=0; i<ds_grid_width(ds_gridpathfinding); i+=1)
    {
        for (var j=0; j<ds_grid_height(ds_gridpathfinding); j+=1)
        {
            var value = ds_grid_get(ds_gridpathfinding,i,j);
            
            draw_text_transformed(i*O_Grid.cell_width + 8, j*O_Grid.cell_height + 8,string(value), 1, 1,0);
        }
    }
}

/// Draw the path
if path_exists(path_building)
{
    draw_path(path_building,floor(x/O_Grid.cell_width), floor(y/O_Grid.cell_height),true) ;
}
In create event of O_Grid :
Code:
/// initialize dimesion variables for the grid
cell_width = 32 ;
cell_height = 32 ;
In room start event of O_Grid :
Code:
//Fill the grid to see if there is a collision object
var hcells = ceil (room_width/cell_width) ;
var vcells = ceil (room_height/cell_height);
global.ds_grid_pathfinding = ds_grid_create(hcells, vcells);
    for (var i=0; i<hcells; i+=1)
    {
        for (var j=0; j<vcells; j+=1)
        {
            if place_meeting(i*cell_width,j*cell_height,O_Collision){
            ds_grid_add(global.ds_grid_pathfinding,i,j,-2)
            }
            else {
            ds_grid_add(global.ds_grid_pathfinding,i,j,-1)
            }
        }
    }
Script scr_fill_the_grid :
Code:
var ax = argument0;   // Start X position
var ay = argument1;    // Start Y position
var xgoal = argument2;   // X Position where we want to go
var ygoal = argument3 ;  // Y Position where we want to go
var path_found ;      // A way was found
var n ;  // Variable when you fall
var a ; // Variable when you fall
path_found = 0;  // 0 means that the path is not found

/// Copy the global pathfinding
ds_gridpathfinding = ds_grid_create(ds_grid_width(global.ds_grid_pathfinding), ds_grid_height(global.ds_grid_pathfinding)) ;
ds_grid_copy (ds_gridpathfinding, global.ds_grid_pathfinding);

/// Add the first point into the list
var point_list = ds_list_create() ;
ds_list_add (point_list, ax);
ds_list_add (point_list, ay);
ds_grid_set(ds_gridpathfinding,ax,ay,0);

for (var i=1; i<200; i+=1)
{
    if path_found == 1 {
    ds_list_destroy(point_list); // We don't need the list anymore because we find a path.
    ///ds_grid_destroy(ds_gridpathfinding); /// Grid has to be delete. We keep it only for debuger purposes
    return path_found ;
    break ;
    }

var size_list = ds_list_size(point_list) ;  // Update the size of the list. It is for delete all the previous points.

if size_list == 0 {    // When size list is zero, it means that, we check all the positions where the enemy could go, and no one is the goal position
ds_list_destroy(point_list);   // Destroy the list because it takes up memory and we don't need it anymore.
ds_grid_destroy(ds_gridpathfinding); // // Destroy the grid because it takes up memory.
return path_found ;  /// It will return 0, so if script returns 0, it means that no path was found to reach the goal.
break ;
}


for (var j=0; j<size_list; j+=2){
        ax = ds_list_find_value(point_list,j)
        ay = ds_list_find_value(point_list,j+1)

        if ax==xgoal && ay==ygoal {
        path_found = 1 ;
        scr_build_the_path(xgoal,ygoal);
        break ;
        }

n=1 ; /// Variable for the Fall

/// Check if the enemy can go to the right
if ds_grid_get(ds_gridpathfinding,ax+1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax+1,ay+1)==-2 {
ds_grid_set(ds_gridpathfinding,ax+1,ay,i);
ds_list_add (point_list, ax + 1);
ds_list_add (point_list, ay);
}

else{   /// If the enemy can go to the right, the other movement will be impossible. So we can put a else to skip all the following code

/// Check if we can go jump one block vertically (right side)
if (ds_grid_get(ds_gridpathfinding,ax+1,ay)==-2 && ds_grid_get(ds_gridpathfinding,ax+1,ay-1)==-1)
            {
            ds_grid_set(ds_gridpathfinding,ax+1,ay-1,i);
            ds_list_add (point_list, ax + 1);
            ds_list_add (point_list, ay-1);
            }
else {  /// If the ennemy can go jump one block horizontally, the others movement will be impossible. So we can put a else to skip all the following code

/// Check if the enemy can do a diagonal jump (Big Jump). (Right side);
if ds_grid_get(ds_gridpathfinding,ax+1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax+2,ay)==-2 && ds_grid_get(ds_gridpathfinding,ax+2,ay-1)==-1
        {
        ds_grid_set(ds_gridpathfinding,ax+2,ay-1,i);
        ds_list_add (point_list, ax + 2);
        ds_list_add (point_list, ay-1);
        }

///Check if the enemy can jump horizontally (jump over a void). (Right side)
if ds_grid_get(ds_gridpathfinding,ax+1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax+2,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax+2,ay+1)==-2
        {
        ds_grid_set(ds_gridpathfinding,ax+2,ay,i);
        ds_list_add (point_list, ax + 2);
        ds_list_add (point_list, ay);
        }

/// Check if the enemy can fall (Right side).
if ds_grid_get(ds_gridpathfinding,ax+1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax+1,ay+1)==-1
            {
                    {
                    do
                       {
                       n=n+1 ;
                       a = ds_grid_get(ds_gridpathfinding,ax+1,ay+n);
                       }
                    until (a==-2) ||  (ay+n == ds_grid_height(ds_gridpathfinding)) }
                    
        if ds_grid_get(ds_gridpathfinding,ax+1,ay+n-1)==-1 && ds_grid_get(ds_gridpathfinding,ax+1,ay+n)== -2
            {
            ds_grid_set(ds_gridpathfinding,ax+1,ay+n-1,i);
            ds_list_add (point_list, ax + 1);
            ds_list_add (point_list, ay+n-1);
            }
        }
    }
}


n=1 ; /// Re-initialize variable for the Fall (left side)

/// Check if the enemy can go to the left
if ds_grid_get(ds_gridpathfinding,ax-1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax-1,ay+1)==-2 {
ds_grid_set(ds_gridpathfinding,ax-1,ay,i);
ds_list_add (point_list, ax -1);
ds_list_add (point_list, ay);
}
else{

/// Check if we can go jump one block vertically (left side)
if ds_grid_get(ds_gridpathfinding,ax-1,ay)==-2 && ds_grid_get(ds_gridpathfinding,ax-1,ay-1)==-1{
ds_grid_set(ds_gridpathfinding,ax-1,ay-1,i);
ds_list_add (point_list, ax-1);
ds_list_add (point_list, ay-1);
}
else {

/// Check if the enemy can do a diagonal jump (Big Jump). (left side);
if ds_grid_get(ds_gridpathfinding,ax-1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax-2,ay)==-2 && ds_grid_get(ds_gridpathfinding,ax-2,ay-1)==-1{
ds_grid_set(ds_gridpathfinding,ax-2,ay-1,i);
ds_list_add (point_list, ax-2);
ds_list_add (point_list, ay-1);
}

///Check if the enemy can jump horizontally (over a void). (left side)
if ds_grid_get(ds_gridpathfinding,ax-1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax-2,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax-2,ay+1)==-2{
ds_grid_set(ds_gridpathfinding,ax-2,ay,i);
ds_list_add (point_list, ax-2);
ds_list_add (point_list, ay);
}

/// Check if the enemy can fall (left side).
if ds_grid_get(ds_gridpathfinding,ax-1,ay)==-1 && ds_grid_get(ds_gridpathfinding,ax-1,ay+1)==-1
            {
                {
                do
                   {
                   n=n+1 ;
                   a = ds_grid_get(ds_gridpathfinding,ax-1,ay+n);
                   }
                until (a=-2) || (ay+n==ds_grid_height(ds_gridpathfinding))}   
                    if ds_grid_get(ds_gridpathfinding,ax-1,ay+n-1)==-1 && ds_grid_get(ds_gridpathfinding,ax-1,ay+n)== -2
                    {
                    ds_grid_set(ds_gridpathfinding,ax-1,ay+n-1,i);
                    ds_list_add (point_list, ax-1);
                    ds_list_add (point_list, ay+n-1);
                    }
            }
        }
    }
}
/// Delete all the previous points
for (var k=0; k< size_list; k+=1)
    {
    ds_list_delete (point_list, 0);
    }
}
In script scr_build_the_path :
Code:
var xgoal = argument0;   /// X coordinates where we want to go
var ygoal = argument1;  /// Y coordinate where we want to go
path_building = path_add(); /// Create a path where we will add all the points
var value;   /// Value in the enemy grid
var x_previous ; /// Coordinate of X previous
var a = -1 ;  /// Use when enemy falls. We will store data from grid_pathfinding
var b = -1 ;  /// Use when enemy falls. We will store data from grid_pathfinding
var n = 0 ;  /// Use when enemy falls.

path_add_point(path_building, xgoal*O_Grid.cell_width + (O_Grid.cell_width/2), ygoal*O_Grid.cell_height +(O_Grid.cell_height/2), 100); /// Initialize the first point of the path
value = ds_grid_get(ds_gridpathfinding,xgoal,ygoal) ; /// Value in grid pathfinding of the goal position

for (var i = value-1; i > 0 ; i -= 1)
{
    x_previous=xgoal ;  // We put in x previous the variable xgoal.
    n=0;
        if ds_grid_value_exists(ds_gridpathfinding, xgoal-1,ygoal, xgoal+1,ygoal+1, i)  /// Check if left / right, jump 1 block vertically left right
           {
           xgoal = ds_grid_value_x(ds_gridpathfinding, xgoal-1,ygoal, xgoal+1,ygoal+1,i);  // Store the X coordinate in xgoal
           ygoal = ds_grid_value_y(ds_gridpathfinding, x_previous-1,ygoal, x_previous+1,ygoal+1,i); // Store the Y coordinate in ygoal
           path_add_point(path_building, xgoal*O_Grid.cell_width + (O_Grid.cell_width/2), ygoal*O_Grid.cell_height +(O_Grid.cell_height/2), 100); // Add point in path
           }
                else   
                {
                    if ds_grid_value_exists(ds_gridpathfinding, xgoal-2,ygoal, xgoal+2,ygoal+1, i) /// Check if diagonal jump (big jump) or Horizontal jump (jump over a void)
                    {
                    xgoal = ds_grid_value_x(ds_gridpathfinding, xgoal-2,ygoal, xgoal+2,ygoal+1,i);
                        if ds_grid_get (ds_gridpathfinding, x_previous + sign(xgoal-x_previous), ygoal) == -1 /// Check if enemy could really jump
                        {
                        ygoal = ds_grid_value_y(ds_gridpathfinding, x_previous-2,ygoal, x_previous+2,ygoal+1,i);
                        path_add_point(path_building, xgoal*O_Grid.cell_width + (O_Grid.cell_width/2), ygoal*O_Grid.cell_height +(O_Grid.cell_height/2), 100);
                        }
                            else {      /// Case where he find a O_Collsiion, means that we cannot reach it. Means that we have to fall.
                                    {
                                    do
                                       {
                                       n=n+1 ;
                                       a= ds_grid_get(ds_gridpathfinding,x_previous-1,ygoal-n);
                                       b= ds_grid_get(ds_gridpathfinding,x_previous+1,ygoal-n);
                                       }
                                    until (a==i) || (b==i) || ((ygoal-n) < 0)
                                    }
                                            if ds_grid_value_exists(ds_gridpathfinding, x_previous-1,ygoal-n, x_previous+1,ygoal-n, i)
                                            {
                                               xgoal = ds_grid_value_x(ds_gridpathfinding, x_previous-1,ygoal-n, x_previous+1,ygoal,i);
                                               ygoal = ds_grid_value_y(ds_gridpathfinding, x_previous-1,ygoal-n, x_previous+1,ygoal,i);
                                               path_add_point(path_building, xgoal*O_Grid.cell_width + (O_Grid.cell_width/2), ygoal*O_Grid.cell_height +(O_Grid.cell_height/2), 100);
                                            }
                                }
                    }
                                    else{  /// When enemy fall
                                            {
                                            do
                                               {
                                               n=n+1 ;
                                               a= ds_grid_get(ds_gridpathfinding,x_previous-1,ygoal-n);
                                               b= ds_grid_get(ds_gridpathfinding,x_previous+1,ygoal-n);
                                               }
                                                until (a==i) || (b==i) || ((ygoal-n) < 0)
                                            }
                                                if ds_grid_value_exists(ds_gridpathfinding, x_previous-1,ygoal-n, x_previous+1,ygoal-n, i)
                                                {
                                                   xgoal = ds_grid_value_x(ds_gridpathfinding, x_previous-1,ygoal-n, x_previous+1,ygoal,i);
                                                   ygoal = ds_grid_value_y(ds_gridpathfinding, x_previous-1,ygoal-n, x_previous+1,ygoal,i);
                                                   path_add_point(path_building, xgoal*O_Grid.cell_width + (O_Grid.cell_width/2), ygoal*O_Grid.cell_height +(O_Grid.cell_height/2), 100);
                                                }

                                        }
                }
}


path_add_point(path_building, floor(x/O_Grid.cell_width)*O_Grid.cell_width+(O_Grid.cell_width/2),floor(y/O_Grid.cell_height)*O_Grid.cell_height+(O_Grid.cell_height/2), 100);  /// We add the last point which is the point where there is the enemy.
path_set_closed (path_building,0); /// We didn't close the path because it is an open path. We don't to have loop in this path.
path_reverse (path_building);  // We reverse the path because we start from the end.
In script scr_follow_the_path :
Code:
var number_of_points = path_get_number(argument0);
var path_direction ;

path_direction = sign(path_get_point_x(argument0, path_point+1)-path_get_point_x(argument0, path_point)) ;

if action == 0
{
    /// Check if the next point is to move left or right
    if path_get_point_y(argument0, path_point) == path_get_point_y(argument0, path_point+1) && path_get_point_x(argument0, path_point) + O_Grid.cell_width*path_direction == path_get_point_x(argument0, path_point+1)
    {
    speed_h = max_speed * path_direction ;
    action = 1;
    }
     else {
            /// Check if the next point is horizontal jump / jump over a void.
            if path_get_point_y(argument0, path_point) == path_get_point_y(argument0, path_point+1) && path_get_point_x(argument0, path_point) + 2*O_Grid.cell_width*path_direction == path_get_point_x(argument0, path_point+1)
            {
            speed_h = max_speed * path_direction ;
            speed_v = jump_height *0.7 ;
            action = 1;
            }
                else {
                    /// Check if the next point is to fall
                    if path_get_point_y(argument0, path_point) < path_get_point_y(argument0, path_point+1)
                    {
                    speed_h = max_speed * path_direction ;
                        if x <= path_get_point_x(argument0, path_point+1) && path_get_point_x(argument0, path_point+1) <(x + speed_h*path_direction)
                        {
                        action = 1 ;
                        speed_h = 0 ;
                        x = path_get_point_x(argument0, path_point+1);
                        }
                    }
                        else {
                                /// Check if the next point is a diagonal jum /big jump
                                if path_get_point_x(argument0, path_point) == path_get_point_x(argument0, path_point+1)-O_Grid.cell_width*2*path_direction && path_get_point_y(argument0, path_point) == path_get_point_y(argument0, path_point+1)+O_Grid.cell_height
                                {
                                speed_h = max_speed * path_direction * 0.625 ;
                                speed_v = jump_height * 1.1 ;
                                action = 1;
                                }
                                    else {
                                            /// Check if the next point is a jump one block vertically
                                            if path_get_point_y(argument0, path_point) == path_get_point_y(argument0, path_point+1)+O_Grid.cell_height && path_get_point_x(argument0, path_point) + O_Grid.cell_width*path_direction == path_get_point_x(argument0, path_point+1)
                                            {
                                            speed_h = max_speed * path_direction / 2;
                                                if place_meeting(x, y+1, O_Collision) && jump_action == 0
                                                {
                                                speed_v = jump_height * 0.9 ;
                                                jump_action = 1 ;
                                                speed_h = max_speed * path_direction ;
                                                }
                                }
                            }
                        }
                    }
        }
}

/// Check if enemy reached the next point
if x <= path_get_point_x(argument0, path_point+1) && path_get_point_x(argument0, path_point+1) <= x + speed_h*path_direction && path_get_point_y(argument0, path_point+1)== y - sprite_yoffset - (O_Grid.cell_height/2 - sprite_height)
    {
    path_point = path_point + 1 ;
    action = 0 ;
    jump_action = 0 ;
        if path_point == number_of_points -1  /// Check if it is the last point of the path
            {
            speed_h = 0;
            speed_v = 0;
            path_delete (argument0);
            path_point = 0 ;
            }
    }
 

heirey

Member
Hi !

I tried to use your script but when i launch the project, the paths are drawn only when the two objects are touching, is there a bug in your scripts?

Have you an archive version of the project to check where is the problem ?

Thanks !!!
 
R

Ryno

Guest
Hi !

I tried to use your script but when i launch the project, the paths are drawn only when the two objects are touching, is there a bug in your scripts?

Have you an archive version of the project to check where is the problem ?

Thanks !!!
I'm having the same issue. Also, the formatting has been kind of a pain to handle. It's a shame this is seemingly the only platformer AI guide on the internet because I can't translate it to my own works at all. Skull_K, get back here!
 

Bentley

Member
This looks pretty cool. Will check it out!

Edit: It's amazing that it all works. Some really cool things you subtly did:

1. At first glance, I thought a right then a left check would over-write cells.
For example, it's iteration 0 in the main loop.
The right check sets cell x + 1 to "i".
// Same iteration...
The lefts check (I thought would) set cell x - 1 to "i".

BUT, you can't set cell x -1 because it is effectively locked. It's locked because it has a value of 0. You can only change cells with values of -1 or -2 (empty or solid).

2. I thought that the drop would intersect with a previous path. But this check prevents that: if (pathfind[# cx + 1, cy + fall_count] == EMPTY) // -1

Lots of other stuff I really liked that I omitted. Great tutorial!
 
Last edited:
Hello there!

Just wanted to say thank you for this cool feature. Currently trying to adapt this to my own little project and while sometimes its hard to understand how things works (im kinda noob so its sbsolutely not your fault) im still advancing more and more - adding new things that i needed, based on your implementation. For example, my enemies taller than height of cell, so i had to add such condition in your scripts, able to jump over bigger areas and such.
Cannot stress enough how helping this tutorial is. Thank you very much.
 

Ghost546

Member
hi, it's very likely that I won't get an answer, but it doesn't hurt to ask. I'm working on a game that has larger sprites than your project and I was wondering how to make it work with different sizes. Thanks in advance and your code is great.
 
Top