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 :
In step event of the player
The collision script : scr_collision
In create event of the enemy
In step event of the enemy :
In draw_gui of the enemy :
In create event of O_Grid :
In room start event of O_Grid :
Script scr_fill_the_grid :
In script scr_build_the_path :
In script scr_follow_the_path :
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 ;
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();
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;
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 ;
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 () ;
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) ;
}
Code:
/// initialize dimesion variables for the grid
cell_width = 32 ;
cell_height = 32 ;
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)
}
}
}
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);
}
}
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.
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 ;
}
}