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:
After that each wall object runs the following code in the create event, to fill this array:
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:
And now comes the real pathfinding algorithm:
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.
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
}
}
Code:
global.blocked[x/global.size,y/global.size] = true
Code:
scr_apathfinding(0,0,floor(mouse_x/global.size)*global.size,floor(mouse_y/global.size)*global.size
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
}
}
}
}
}
}
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.