Help with A*-Pathfinding

S

Simulacron

Guest
Hello everyone,
I'm trying to implement a simple a*-pathfinding algorithm in my game, but I have problems with it. I don't get any error messages, but the script doesn't seem to work. Here's the code i'm using so far:
In the create event of an control object the following code runs, that initializes an array that stores which parts of the room are blocked:
Code:
global.size = 32

for(var i = 0; i < room_width/global.size; i++){
    for(var j = 0; j < room_height/global.size; j++){
        global.blocked[i,j] = false
    }
}
After that each wall object runs the following code in the create event, to fill this array:
Code:
global.blocked[x/global.size,y/global.size] = true
Until here everything works, but when the pathfinding somes the poblems start. I have a script, that inputs the coordinates that get connected by the path. For simplicity I used for the starting points the coordinates 0,0 and for the goal coordinates my mouse_x/y when I click. The following code is in the global left pressed event:
Code:
scr_apathfinding(0,0,floor(mouse_x/global.size)*global.size,floor(mouse_y/global.size)*global.size
And now comes the real pathfinding algorithm:
Code:
var sx = argument[0]/global.size //Start x
var sy = argument[1]/global.size //Start y
var gx = argument[2]/global.size //End x
var gy = argument[3]/global.size //End y
var cx = sx//Current x
var cy = sy//Current y
var gw = room_width/global.size //grid witdh
var gh = room_height/global.size //grid height

//Initialize Arrays & Ds_grids
f_cost = ds_grid_create(gw,gh) //create grid for f_cost
g_cost = ds_grid_create(gw,gh) //create grid for g_cost
ds_grid_set_region(f_cost,0,0,gw,gh,10000000) //set all f_costs and g_costs to very high numbers they will never reach
ds_grid_set_region(g_cost,0,0,gw,gh,10000000)

for(var i = 0; i < gw; i++){ //initialize all arrays
    for(var j = 0; j < gh; j++){
        open[i,j] = false //open-list
        closed[i,j] = false //closed-list
        parentx[i,j] = 0 //parentx and parent y save the position of the position the new node originated from to retrace the path
        parenty[i,j] = 0
    }
}

ds_grid_set(g_cost,cx,cy,0) //set g_cost of the start node to 0
ds_grid_set(f_cost,cx,cy,abs(cx-gx)+abs(cy-gy) + ds_grid_get(g_cost,cx,cy)); //calculate f_cost out of g_cost and the absolute distance to the goal nodes
open[cx,cy] = true //add start node to open-list

//loop to find path
while(true){
    var val = ds_grid_get_min(f_cost,0,0,gw,gh) //find lowest f_cost
    cx = ds_grid_value_x(f_cost,0,0,gw,gh,val) //find x/y of node with lowest f_cost
    cy = ds_grid_value_y(f_cost,0,0,gw,gh,val);
    open[cx,cy] = false //remove current node from open
    closed[cx,cy] = true //add current node to closed
    
    if (cx = gx) and (cy = gy){ //if current node is goal node
        //retrace path
        while((cx != sx) and (cy != sy)){ //while we are not at the start node
            instance_create(parentx[cx,cy],parenty[cx,cy],obj_test) //create a test object to indicate path (will be replaced with an array that gets returned)
            var savex = cx //save cx/cy to get correct new cx/cy
            var savey = cy
            cx = parentx[savex,savey] //go to next cx/cy on the path
            cy = parenty[savex,savey]
        }
        ds_grid_destroy(g_cost) //Destroy ds_grids after path has been found
        ds_grid_destroy(f_cost)
        
        break //break the while loop when finished
        
        
    }else{
        //Check each neigbour
        
        //Right
        if cx + 1 <= gw{ //if the node is in the grid
            if (global.blocked[cx+1,cy] = false) and (closed[cx+1,cy] = false){ //if the neigbour-node is is not in the closed-list or the neigbour-node is not traversable
                if (open[cx+1,cy] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx+1-gx)+abs(cy-gy) < ds_grid_get(f_cost,cx+1,cy)){ //if the neigbour-nod eis not in the iopen list or the new path to the node is shorter
                    ds_grid_set(g_cost,cx+1,cy,ds_grid_get(g_cost,cx,cy)+1) //set new g_cost and f_cost
                    ds_grid_set(f_cost,cx+1,cy,ds_grid_get(g_cost,cx+1,cy) + abs(cx+1-gx)+abs(cy-gy))
                    parentx[cx+1,cy] = cx //save the x and y from the node the neigbour node "came" from
                    parenty[cx+1,cy] = cy
                    if open[cx+1,cy] = false{ //Add neigbour to open list if he isn't in it
                        open[cx+1,cy] = true
                    }
                }
            }
        }
        
        //Left
        if cx - 1 >= 0{
            if (global.blocked[cx-1,cy] = false) and (closed[cx-1,cy] = false){
                if (open[cx-1,cy] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx-1-gx)+abs(cy-gy) < ds_grid_get(f_cost,cx-1,cy)){
                    ds_grid_set(g_cost,cx-1,cy,ds_grid_get(g_cost,cx,cy)+1)
                    ds_grid_set(f_cost,cx-1,cy,ds_grid_get(g_cost,cx-1,cy) + abs(cx-1-gx)+abs(cy-gy))
                    parentx[cx-1,cy] = cx
                    parenty[cx-1,cy] = cy
                    if open[cx-1,cy] = false{
                        open[cx-1,cy] = true
                    }
                }
            }
        }
        
        //Up
        if cy - 1 >= 0{
            if (global.blocked[cx,cy-1] = false) and (closed[cx,cy-1] = false){
                if (open[cx,cy-1] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx-gx)+abs(cy-1-gy) < ds_grid_get(f_cost,cx,cy-1)){
                    ds_grid_set(g_cost,cx,cy-1,ds_grid_get(g_cost,cx,cy)+1)
                    ds_grid_set(f_cost,cx,cy-1,ds_grid_get(g_cost,cx,cy-1) + abs(cx-gx)+abs(cy-1-gy))
                    parentx[cx,cy-1] = cx
                    parenty[cx,cy-1] = cy
                    if open[cx,cy-1] = false{
                        open[cx,cy-1] = true
                    }
                }
            }
        }
        
        //Down
        if cy + 1 <= gh{
            if (global.blocked[cx,cy+1] = false) and (closed[cx,cy+1] = false){
                if (open[cx,cy+1] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx-gx)+abs(cy+1-gy) < ds_grid_get(f_cost,cx,cy+1)){
                    ds_grid_set(g_cost,cx,cy+1,ds_grid_get(g_cost,cx,cy)+1)
                    ds_grid_set(f_cost,cx,cy+1,ds_grid_get(g_cost,cx,cy+1) + abs(cx-gx)+abs(cy+1-gy))
                    parentx[cx,cy+1] = cx
                    parenty[cx,cy+1] = cy
                    if open[cx,cy+1] = false{
                        open[cx,cy+1] = true
                    }
                }
            }
        }
    } 
}
I made this algorithm after the the structure from this video (timestamp: 7:45)

Can anyone see what my mistake is? Thanks in advanced for your help!
If you have any questions regarding my code feel free to ask.
 

jo-thijs

Member
Hello everyone,
I'm trying to implement a simple a*-pathfinding algorithm in my game, but I have problems with it. I don't get any error messages, but the script doesn't seem to work. Here's the code i'm using so far:
In the create event of an control object the following code runs, that initializes an array that stores which parts of the room are blocked:
Code:
global.size = 32

for(var i = 0; i < room_width/global.size; i++){
    for(var j = 0; j < room_height/global.size; j++){
        global.blocked[i,j] = false
    }
}
After that each wall object runs the following code in the create event, to fill this array:
Code:
global.blocked[x/global.size,y/global.size] = true
Until here everything works, but when the pathfinding somes the poblems start. I have a script, that inputs the coordinates that get connected by the path. For simplicity I used for the starting points the coordinates 0,0 and for the goal coordinates my mouse_x/y when I click. The following code is in the global left pressed event:
Code:
scr_apathfinding(0,0,floor(mouse_x/global.size)*global.size,floor(mouse_y/global.size)*global.size
And now comes the real pathfinding algorithm:
Code:
var sx = argument[0]/global.size //Start x
var sy = argument[1]/global.size //Start y
var gx = argument[2]/global.size //End x
var gy = argument[3]/global.size //End y
var cx = sx//Current x
var cy = sy//Current y
var gw = room_width/global.size //grid witdh
var gh = room_height/global.size //grid height

//Initialize Arrays & Ds_grids
f_cost = ds_grid_create(gw,gh) //create grid for f_cost
g_cost = ds_grid_create(gw,gh) //create grid for g_cost
ds_grid_set_region(f_cost,0,0,gw,gh,10000000) //set all f_costs and g_costs to very high numbers they will never reach
ds_grid_set_region(g_cost,0,0,gw,gh,10000000)

for(var i = 0; i < gw; i++){ //initialize all arrays
    for(var j = 0; j < gh; j++){
        open[i,j] = false //open-list
        closed[i,j] = false //closed-list
        parentx[i,j] = 0 //parentx and parent y save the position of the position the new node originated from to retrace the path
        parenty[i,j] = 0
    }
}

ds_grid_set(g_cost,cx,cy,0) //set g_cost of the start node to 0
ds_grid_set(f_cost,cx,cy,abs(cx-gx)+abs(cy-gy) + ds_grid_get(g_cost,cx,cy)); //calculate f_cost out of g_cost and the absolute distance to the goal nodes
open[cx,cy] = true //add start node to open-list

//loop to find path
while(true){
    var val = ds_grid_get_min(f_cost,0,0,gw,gh) //find lowest f_cost
    cx = ds_grid_value_x(f_cost,0,0,gw,gh,val) //find x/y of node with lowest f_cost
    cy = ds_grid_value_y(f_cost,0,0,gw,gh,val);
    open[cx,cy] = false //remove current node from open
    closed[cx,cy] = true //add current node to closed
   
    if (cx = gx) and (cy = gy){ //if current node is goal node
        //retrace path
        while((cx != sx) and (cy != sy)){ //while we are not at the start node
            instance_create(parentx[cx,cy],parenty[cx,cy],obj_test) //create a test object to indicate path (will be replaced with an array that gets returned)
            var savex = cx //save cx/cy to get correct new cx/cy
            var savey = cy
            cx = parentx[savex,savey] //go to next cx/cy on the path
            cy = parenty[savex,savey]
        }
        ds_grid_destroy(g_cost) //Destroy ds_grids after path has been found
        ds_grid_destroy(f_cost)
       
        break //break the while loop when finished
       
       
    }else{
        //Check each neigbour
       
        //Right
        if cx + 1 <= gw{ //if the node is in the grid
            if (global.blocked[cx+1,cy] = false) and (closed[cx+1,cy] = false){ //if the neigbour-node is is not in the closed-list or the neigbour-node is not traversable
                if (open[cx+1,cy] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx+1-gx)+abs(cy-gy) < ds_grid_get(f_cost,cx+1,cy)){ //if the neigbour-nod eis not in the iopen list or the new path to the node is shorter
                    ds_grid_set(g_cost,cx+1,cy,ds_grid_get(g_cost,cx,cy)+1) //set new g_cost and f_cost
                    ds_grid_set(f_cost,cx+1,cy,ds_grid_get(g_cost,cx+1,cy) + abs(cx+1-gx)+abs(cy-gy))
                    parentx[cx+1,cy] = cx //save the x and y from the node the neigbour node "came" from
                    parenty[cx+1,cy] = cy
                    if open[cx+1,cy] = false{ //Add neigbour to open list if he isn't in it
                        open[cx+1,cy] = true
                    }
                }
            }
        }
       
        //Left
        if cx - 1 >= 0{
            if (global.blocked[cx-1,cy] = false) and (closed[cx-1,cy] = false){
                if (open[cx-1,cy] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx-1-gx)+abs(cy-gy) < ds_grid_get(f_cost,cx-1,cy)){
                    ds_grid_set(g_cost,cx-1,cy,ds_grid_get(g_cost,cx,cy)+1)
                    ds_grid_set(f_cost,cx-1,cy,ds_grid_get(g_cost,cx-1,cy) + abs(cx-1-gx)+abs(cy-gy))
                    parentx[cx-1,cy] = cx
                    parenty[cx-1,cy] = cy
                    if open[cx-1,cy] = false{
                        open[cx-1,cy] = true
                    }
                }
            }
        }
       
        //Up
        if cy - 1 >= 0{
            if (global.blocked[cx,cy-1] = false) and (closed[cx,cy-1] = false){
                if (open[cx,cy-1] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx-gx)+abs(cy-1-gy) < ds_grid_get(f_cost,cx,cy-1)){
                    ds_grid_set(g_cost,cx,cy-1,ds_grid_get(g_cost,cx,cy)+1)
                    ds_grid_set(f_cost,cx,cy-1,ds_grid_get(g_cost,cx,cy-1) + abs(cx-gx)+abs(cy-1-gy))
                    parentx[cx,cy-1] = cx
                    parenty[cx,cy-1] = cy
                    if open[cx,cy-1] = false{
                        open[cx,cy-1] = true
                    }
                }
            }
        }
       
        //Down
        if cy + 1 <= gh{
            if (global.blocked[cx,cy+1] = false) and (closed[cx,cy+1] = false){
                if (open[cx,cy+1] = false) or (ds_grid_get(g_cost,cx,cy) + 1 + abs(cx-gx)+abs(cy+1-gy) < ds_grid_get(f_cost,cx,cy+1)){
                    ds_grid_set(g_cost,cx,cy+1,ds_grid_get(g_cost,cx,cy)+1)
                    ds_grid_set(f_cost,cx,cy+1,ds_grid_get(g_cost,cx,cy+1) + abs(cx-gx)+abs(cy+1-gy))
                    parentx[cx,cy+1] = cx
                    parenty[cx,cy+1] = cy
                    if open[cx,cy+1] = false{
                        open[cx,cy+1] = true
                    }
                }
            }
        }
    }
}
I made this algorithm after the the structure from this video (timestamp: 7:45)

Can anyone see what my mistake is? Thanks in advanced for your help!
If you have any questions regarding my code feel free to ask.
You've got a couple of mistakes in that code, but the main mistake is the following.
You use ds_grid_get_min to get the value of the next node (or point) to visit.
Of course, the node with the minimal cost will be the one you just visited.
Because your arguments start in the top left corner, ds_grid_value_x and ds_grid_value_y will always set both cx and cy to 0, resulting in an infinite loop.
You have to exclude "closed nodes" or "visited nodes" from being able to be revisited.
The easiest way to do this given your code, is to set the value of f_cost at (cx, cy) to something rediculously high just after using ds_grid_get_min, ds_grid_value_x and ds_grid_value_y.

The second biggest mistake you've made is to check whether cx + 1 <= gw and cy + 1 <= gh instead of checking whether cx + 1 < gw and cy + 1 < gh.

The third biggest mistake is to use while((cx != sx) and (cy != sy)) instead of while cx != sx or cy != sy.

It is probably also a mistake to use instance_create with coordinates (parentx[cx, cy], parenty[cx, cy]) instead of (cx * global.size, cy * global.size).

Further mistakes are:
- Not using semicolons.
- Using = instead of == to compare values
- Using finite numbers to represent infinite values (in GM:S you can actually use infinite as a value):
Code:
var zero = 0;
var infinite = 1 / zero;
- Calculating the new cx and cy separately through ds_grid_value_*.
You know cx will point to the x coordinate of a cell with the lowest value.
You know cy will point to the y coordinate of a cell with the lowest value.
This does not mean that te cell with coordinates (cx, cy) will have the lowest value.
You should create your own algorithm for this.
- You assume in your algorithm that there will exist a path from (sx, sy) to (gx, gy) and never check if there are no visitable nodes left.
- You initialize parentx and parenty with the values 0 instead of -1 or undefined.
This will hide bugs of your algorithm as 0 is an actual valid cell coordinate, while -1 or undefined are not.
- You should initialize arrays in reverse order, it is more optimized (starting with highest index).
- You keep track of visited nodes and costs through grids where each cell represents a node, so you keep track of every possible node at any time.
You could alternatively only keep track of the visited nodes in a set (in GameMaker, sets are ds_maps of which the keys matter, but the values corresponding to the keys don't).
You could then also keep track of all the yet-to-visit (or open) nodes through a ds_priority_queue.
This will give a way more reliable and way more performant alternative to the ds_grid_* functions that you were using.
 
S

Simulacron

Guest
You've got a couple of mistakes in that code, but the main mistake is the following.
You use ds_grid_get_min to get the value of the next node (or point) to visit.
Of course, the node with the minimal cost will be the one you just visited.
Because your arguments start in the top left corner, ds_grid_value_x and ds_grid_value_y will always set both cx and cy to 0, resulting in an infinite loop.
You have to exclude "closed nodes" or "visited nodes" from being able to be revisited.
The easiest way to do this given your code, is to set the value of f_cost at (cx, cy) to something rediculously high just after using ds_grid_get_min, ds_grid_value_x and ds_grid_value_y.

The second biggest mistake you've made is to check whether cx + 1 <= gw and cy + 1 <= gh instead of checking whether cx + 1 < gw and cy + 1 < gh.

The third biggest mistake is to use while((cx != sx) and (cy != sy)) instead of while cx != sx or cy != sy.

It is probably also a mistake to use instance_create with coordinates (parentx[cx, cy], parenty[cx, cy]) instead of (cx * global.size, cy * global.size).

Further mistakes are:
- Not using semicolons.
- Using = instead of == to compare values
- Using finite numbers to represent infinite values (in GM:S you can actually use infinite as a value):
Code:
var zero = 0;
var infinite = 1 / zero;
- Calculating the new cx and cy separately through ds_grid_value_*.
You know cx will point to the x coordinate of a cell with the lowest value.
You know cy will point to the y coordinate of a cell with the lowest value.
This does not mean that te cell with coordinates (cx, cy) will have the lowest value.
You should create your own algorithm for this.
- You assume in your algorithm that there will exist a path from (sx, sy) to (gx, gy) and never check if there are no visitable nodes left.
- You initialize parentx and parenty with the values 0 instead of -1 or undefined.
This will hide bugs of your algorithm as 0 is an actual valid cell coordinate, while -1 or undefined are not.
- You should initialize arrays in reverse order, it is more optimized (starting with highest index).
- You keep track of visited nodes and costs through grids where each cell represents a node, so you keep track of every possible node at any time.
You could alternatively only keep track of the visited nodes in a set (in GameMaker, sets are ds_maps of which the keys matter, but the values corresponding to the keys don't).
You could then also keep track of all the yet-to-visit (or open) nodes through a ds_priority_queue.
This will give a way more reliable and way more performant alternative to the ds_grid_* functions that you were using.
Thanks for this list of problems, how to fix them and what else I need to do. I would never thought about all of those. I will start fixing those as soon as I can.
 
Top