GMS 2 Platformer Pathfinding. Tutorial

Discussion in 'Tutorials' started by Skull_k, Feb 19, 2018.

  1. Skull_k

    Skull_k Member

    Joined:
    Sep 21, 2017
    Posts:
    10
    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 ;
                }
        }
    
    
     
  2. heirey

    heirey Member

    Joined:
    Jun 27, 2016
    Posts:
    8
    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 !!!
     
  3. Ryno

    Ryno Member

    Joined:
    Mar 24, 2019
    Posts:
    1
    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!
     
  4. Bentley

    Bentley Member

    Joined:
    Jun 18, 2017
    Posts:
    790
    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: Jun 7, 2019
    elithejew likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice