I've been learning and trying to make A* pathfinding for a 50x50 grid with 'virtual' tiles. Everything is numbers.
The first 4 attempts I failed. Now , the fifth I started again from scratch. I created every single function separately testing it and everything worked until I started using them together to find a path.
I've added while space == 0 wait , while space == 1 wait to see what exactly happened each time the 'current_node' changed and the pathfinding function was setting current_node to absolutely diffrent nodes than the ones it should.
I've tested with X2,Y2 to X4,Y3 , or 52 to 153 node It sets 52 as the current node , next it sets 51 but it should set 53 or 102 as current. And next (51 is Y = 1) when it reaches the border of the grid Y = 0 it sets current as 0 and I get a crash when trying to set the adjacent node (current_node - 1).
This sounds like something is wrong with the evaluation of the F value but I looked hundreds of times at it and everything looks fine. Here it is :
Code:
function calc_h_value(current,goal)
{
var tmp1[2];
var tmp2[2];
tile_to_pos(current);
vec_set(tmp1,ttp);
tile_to_pos(goal);
vec_set(tmp2,ttp);
if(tmp1.x >= tmp2.x) { tmp1.x = tmp1.x - tmp2.x; }
else { tmp1.x = tmp2.x - tmp1.x; }
if(tmp1.y >= tmp2.y) { tmp1.y = tmp1.y - tmp2.y; }
else { tmp1.y = tmp2.y - tmp1.y; }
tmp1.x = (tmp1.x + tmp1.y) * 10;
h_value[current] = tmp1.x;
return(tmp1.x);
}
function calc_g_value(current)
{
var tmpg;
if(parent_list[current] != 0)
{
tmpg = g_value[parent_list[current]] + 10;
g_value[current] = tmpg;
return(tmpg);
}
return(-1);
}
function calc_f_value(current,goal)
{
var tmpf1;
var tmpf2;
tmpf1 = calc_h_value(current,goal);
tmpf2 = calc_g_value(current);
tmpf1 = tmpf1 + tmpf2;
f_value[current] = tmpf1;
return(tmpf1);
}
function compare_f_values(current,goal)
{
var tmp1;
while(tmp1 < 4)
{
f_val[tmp1] = calc_f_value(adj_node[tmp1],goal);
tmp1 += 1;
}
var i = 0;
var j;
var tmp;
while(i<4)
{
j=0;
while(j<i) // "<" or ">" for asc./desc. sort
{
if(f_val[testvar3[i]] < f_val[testvar3[j]])
{
tmp=testvar3[j];
testvar3[j]=testvar3[i];
testvar3[i]=tmp;
}
j+=1;
}
i+=1;
}
tmp = 0;
while(tmp < 4)
{
if(node_list[testvar3[tmp]] == 0)
{
return(testvar3[tmp]);
}
tmp += 1;
}
}
The only thing I'm not shure about is the sorting of f_val array , I took the script from here (bubble sorting) and it worked fine when I tested it alone.
Here's the PathFind function:
Code:
function pathfind(snode,gnode)
{
current_node = snode;
goal_node = gnode;
add_open_list(current_node);
while(open_list[0] != 0 || current_node != gnode)
{
set_adj_nodes(current_node);
var counter1;
while(counter1 < 4)
{
if(search_closed_list(adj_node[counter1]) == 0)
{
if(search_open_list(adj_node[counter1]) == 0)
{
add_open_list(adj_node[counter1]);
make_parent(adj_node[counter1],current_node);
}
}
counter1 += 1;
}
tmpstore1 = compare_f_values(current_node,goal_node);
add_closed_list(current_node);
current_node = adj_node[tmpstore1];
}
}
PS.: I tought I should have a deadline for this one,just to see if I can make it,but I guess I cant learn it and do it in 10 hours