sv3nxd
Member
Hello game-maker-community,
I've been working on a pathfinding-algorithm since yesterday morning. I didn't find any tutorials on how to implement it in GML nor what the most cost-effecient is.
This is really important to me, as pathfinding has been a problem for me for atleast half a year
(If not - then even longer)
I was wondering several things:
The first thing I was working on was: "Were could I store the information for all these nodes?" ... and nothing else made any sense for me but simple objects.
It just seems to be a waste. It just sounds too obvious to be right.
I made a grid and then initialized it with the instance-id of a node, so a grid-field directly correlates to a node.
( I was also wondering if that's the right thing to do here)
There are 3 objects really important to the pathfinding.
oDjikstra - Create Event
oColl - Has no events
There are 4 scripts really important to the pathfinding.
check_neighbours();
set_parent_as_path();
reassemble_nodes();
Thanks for everybody reading this, can't tell you how appreciated it is!
As an endnote: Thanks to @MishMash for inspiring me to try this
I've been working on a pathfinding-algorithm since yesterday morning. I didn't find any tutorials on how to implement it in GML nor what the most cost-effecient is.
This is really important to me, as pathfinding has been a problem for me for atleast half a year
(If not - then even longer)
I was wondering several things:
- Should nodes be objects?
- Can I have several grid's instead of object's?
- Could 1 grid come with a map,which would store the variables of the nodes instead?
- ... and several other questions that I couldn't answer.
The algorithm has no problems in a 640x640 room (Nodes being 32px).
But when having a room 1280x960 (Nodes being 32px), then the software freezes for circa 1 second.
But when having a room 1280x960 (Nodes being 32px), then the software freezes for circa 1 second.
The first thing I was working on was: "Were could I store the information for all these nodes?" ... and nothing else made any sense for me but simple objects.
It just seems to be a waste. It just sounds too obvious to be right.
I made a grid and then initialized it with the instance-id of a node, so a grid-field directly correlates to a node.
( I was also wondering if that's the right thing to do here)
There are 3 objects really important to the pathfinding.
- oNode
- oDjikstra
- oColl
oNode - Create Event
Code:
///Set up variables
parent = -1;
cost = -1;
checked = false;
path = false;
Code:
///Setup djikstra-algorithm
//variables for loop
stop = false;
all_cost = 0;
//Grid
SIZE = 32;
grid_w = room_width div SIZE;
grid_h = room_height div SIZE
//Grid erstellen
grid = ds_grid_create(grid_w, grid_h);
//Grid initialiseren - Auf 1'ern werden Nodes gespawnt
ds_grid_set_region(grid,0,0,grid_w - 1,grid_h - 1,-2);
//Kollisionen finden
reassemble_nodes();
//Craete nodes
for(var row = 0; row < grid_w; row++)
{
for(var col = 0; col < grid_h; col++)
{
if(grid[#row,col] == -2) grid[#row,col] = instance_create(row*SIZE,col*SIZE,oNode);
}
}
oColl - Has no events
There are 4 scripts really important to the pathfinding.
- find_path : End-user-function, that returns a path (or -1) and uses all other functions
- check_neighbours: Sets neighbours cost and set neighbours as childs
- set_parent_as_path: (Recursive) Backtracks the path and adds every point to path
- reassemble_nodes: If enviroment changes, this script is called to delete nodes or create them
Code:
///find_path(x1,y1,x2,y2)
//This is the function the user will be using in the end
//Arguments
x1 = argument0;
y1 = argument1;
x2 = argument2;
y2 = argument3;
with(oDjikstra)
{
//Variables
stop = false;
all_cost = 0;
//Startcoordinates
x1 = other.x1;
y1 = other.y1;
//Goalcoordinates
x2 = other.x2;
y2 = other.y2;
//In case a pathsearch has been done before, reset all nodes to create-state
if(instance_exists(oNode))
{
with(oNode)
{
cost = -1;
parent = -1;
checked = false;
path = false;
}
}
//Initialize variables with instance-ID's for easier use later
goal = grid[#other.x2 div SIZE, other.y2 div SIZE];
start = grid[#other.x1 div SIZE,other.y1 div SIZE];
//Set cost of startnode to 0 so the loop has a startingpoint
with(start) cost = 0;
while(stop == false)
{
//Set variables
val = 10000;
all_checked = true; //Check if there are nodes left
goal_reached = false; //Check if goal-node is reached
//Pathfinding-Loop
for(var i = 0; i < instance_number(oNode); i++)
{
var o = instance_find(oNode,i);
found = false; //Check for nodes that have not been visited yet
if(o.cost == all_cost) //Check if current node is equal to the current sum of costs of walked nodes
{
with(o)
{
if(!checked)
{
other.all_checked = false;
other.found = true;
checked = true; //Mark this note as visited
check_neighbours(x div oDjikstra.SIZE,y div oDjikstra.SIZE); //Set neighbours-cost and set them as childs
}
}
if(!found) //If a node has been found, reset 'i' so no node gets skipped
{
all_cost++;
i = 0;
}
}
}
if(all_checked == true) stop = true; //If no nodes are left, break the loop
}
//Create path
if(goal_reached)
{
djikstras_path = path_add();
with(goal)
{
path_add_point(oDjikstra.djikstras_path,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
set_parent_as_path();
}
path_reverse(djikstras_path);
return djikstras_path; //If a goal has been found return path
}
return -1; //If no goal has been found return -1
}
Code:
///check_neighbours(gridx,gridy)
var gridx = argument0;
var gridy = argument1;
//Stop when no solution or or goal reached
if(oDjikstra.stop) exit;
//Check left neighbour
if(gridx - 1 >= 0)
{
obj = oDjikstra.grid[#gridx - 1,gridy];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}
//Check right neighbour
if(gridx + 1 < oDjikstra.grid_w)
{
obj = oDjikstra.grid[#gridx + 1,gridy];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}
//Check top neighbour
if(gridy - 1 >= 0)
{
obj = oDjikstra.grid[#gridx,gridy - 1];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}
//Check bottom neighbour
if(gridy + 1 < oDjikstra.grid_h)
{
obj = oDjikstra.grid[#gridx,gridy + 1];
if(obj.cost == -1)
{
with(obj)
{
cost = other.cost + 1;
parent = other;
}
//Check if neighbour is goal-node
if(obj.id == oDjikstra.goal.id)
{
oDjikstra.stop = true;
oDjikstra.goal_reached = true;
show_debug_message("done");
exit;
}
}
}
Code:
//Recursive Function - Execute until there is no parent to be added
//This function backtracks the route and adds it to a predetermined path
if(parent == -1) exit;
with(parent)
{
path_add_point(oDjikstra.djikstras_path,x + oDjikstra.SIZE/2,y + oDjikstra.SIZE/2,100);
set_parent_as_path();
}
Code:
//If a wall gets placed or anything changes (also at startup), this script should be called so no collison-objects gets into the grid
//(Collisionobject should be the size of SIZExSIZ (32 in this case)
for(var i = 0; i < instance_number(oColl); i++)
{
var o = instance_find(oColl,i);
with(o)
{
SIZE = other.SIZE;
//lower left corner
if(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] != -2)
with(other.grid[#bbox_left div SIZE,bbox_bottom div SIZE]) instance_destroy();
other.grid[#bbox_left div SIZE,bbox_bottom div SIZE] = -1;
//upper left corner
if(other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_left div SIZE,bbox_top div SIZE] != -2)
with(other.grid[#bbox_left div SIZE,bbox_top div SIZE]) instance_destroy();
other.grid[#bbox_left div SIZE,bbox_top div SIZE] = -1;
//lower right corner
if(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] != -2)
with(other.grid[#bbox_right div SIZE,bbox_bottom div SIZE]) instance_destroy();
other.grid[#bbox_right div SIZE,bbox_bottom div SIZE] = -1;
//upper right corner
if(other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -1 and other.grid[#bbox_right div SIZE,bbox_top div SIZE] != -2)
with(other.grid[#bbox_right div SIZE,bbox_top div SIZE]) instance_destroy();
other.grid[#bbox_right div SIZE,bbox_top div SIZE] = -1;
}
}
As an endnote: Thanks to @MishMash for inspiring me to try this