astar: diagonal movement cost makes path end in loop not at goal

i'm somewhat stumped here.

i've been working on the bbox astar for Caveman. its regular astar, but you can pass it a bbox radius for determining if a tile is impassable. if any tile in a bbox radius around a given tile is impassable, the tile is considered impassable. this effectively creates a buffer of depth bbox_radius around all obstacles on the map. this keeps entities from clipping corners when moving diagonally around the corner of an obstacle. it also means you can use a single astar map for entities of different sizes! with a bbox radius of zero, it becomes normal astar.

so far everything has worked fine. limiting it to horizontal and vertical movement, i have perfect astar behavior. even with bboxes (it would seem - at least so far).

but at first, diagonal movement had a cost of 1, just like horizontal and vertical movement. as a result, the path would sometimes go out diagonally then come back in diagonally instead of going straight. my estimate to goal heuristic was bbox distance in tiles.

since the code used ints for cost, i decided to use a form of "fixed point", and make horiz and vert cost 10, diagonal 14, and make the heuristic bbox dist * 10.

but when i do this, the path will sometimes go part way, then end in a loop with the next node (the parent) pointing to the previous node. IE node 6's parent is node 7, and 7's parent is 6!

so on a path of length 10, it might get as far as node 7, then think that node 6 is the next node. when you extract the path by chasing the parents, it jumps back and forth between nodes 6 and 7 until you exceed MAX_PATH_LENGTH for an entity (currently set to 10000).

i thought the bbox_dist*10 heuristic might be overestimating the distance to goal, so i tried replacing the heuristic with true 2d distance * 10 converted to an int, but no difference.

i changed it back to cost =1 for everything and it works- even with the new true 2d distance heuristic, but the paths may be diagonal not straight. then i changed it back to cost = 10 or 14, and now it loops again, instead of reaching the goal. so its definitely the change in cost values that's causing the problem - somehow.

i guess using floats for cost is the next step.

anyone ever run into this kind of bug? i'm obviously doing something wrong. just haven't figured out what yet.

changing the heuristic to true diagonal distance (i forget the proper name) should only tighten the search area....

Regardless of any weird cost issues, you should never be able to have a node that goes back to any of its parents.

i know. : (

to test, i set all parent x's to -1, and made add_to_open() check to see if the parent had been set yet. it had. and yes, i'm using if in_closed_and_not_removed().

as i recall, that's required if the solution is not complete (closed set?). IE if it later finds a shorter path to a node.

so if i have a closed set, i don't need if in_closed_and_not_removed() ? all i need is get_lowest_open, add_to_closed, if in_open_and_not_removed, and add_to_open?

i used this as my primary reference:

http://theory.stanford.edu/~amitp/GameProgramming/

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): ?²?
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers
?²? This should never happen if you have an consistent admissible heuristic. However in games we often have inadmissible heuristics.

as you can see, they include "remove from closed" for the more general case algo where the heuristic can be inadmissible.

so you're saying i should keep the heuristic admissible, and just lose "remove from closed"?.

the heuristics i've been using (BBox dist or true 2D dist) are admissible, never over estimating the distance to the goal (right?). but diagonal should be more suited to my case.

NOTE: I use a state member (enum { UNVISITED, OPEN, CLOSED }) on the nodes themselves instead of actual sets to eliminate set.contains operations. I can't evaluate multiple paths at the same time, but this game doesn't need to. I have to reset the states after each pathfinding operation though. It's gross, but very fast.

Interesting....

I started with a similar system. Searches were blazingly fast, but setup time wasn't that great. This was for a 300x300 node map. Now I'm using a traditional two list system. Searches on a 300x300 node map are only slow if there is no path and no limit on the search. I'm limiting searches to a path length of 50 nodes max, and only chase the first two or three nodes before re-pathing.

If your cost to traverse nodes is positive and non-zero (hint: if not, the whole thing breaks, so it has to be - make sure movementcost(X, Y) never returns zero) then your calculation of G is wrong, somehow.

hmm...

//  f is estimated total path length.  g is path length so far.
//  px,pz is the parent node
void add_to_open(int x,int z,int f,int g,int px,int pz)
{
/*
if (astarmap[x][z].px != -1)
    {
    msg("add to open: parent already set!");
    }
*/
olist.list[olist.num].x=x;
olist.list[olist.num].z=z;
olist.list[olist.num].f=f;
olist.list[olist.num].g=g;
olist.list[olist.num].id=z*ASTAR_MAPSIZE+x;
astarmap[x][z].px=px;
astarmap[x][z].pz=pz;
olist.num++;
if (olist.num > olist.peak)
    {
    olist.peak=olist.num;
    }
}







//  two list version
//  x,z is parent. x2,z2 is neighbor.
//  i = CM index
//  rad = radius of bbox check for impassable node.
void expand_neighbor(int x,int z,int x2,int z2,int goal_x,int goal_z,int i,int cost,int rad)
{
//  i in_open in_closed result
int result;
//  i g
//  skip if off map
if (x2 < 0)
    {
    return;
    }
if (x2 >= ASTAR_MAPSIZE/CM[i].scale)
    {
    return;
    }
if (z2 < 0)
    {
    return;
    }
if (z2 >= ASTAR_MAPSIZE/CM[i].scale)
    {
    return;
    }
if (bbox_is_impassable(x2,z2,i,rad) == 1)
    {
    return;
    }
/*
//  ==============  astar check for impassable tile! =================
if (CM[i].data[x2][z2] != CM_CLEAR)
    {
    return;
    }
//  ==============  astar check for impassable tile! =================
*/
//  = in_open 0
//  = in_closed 0
//  cr result in_closed_and_not_removed x2 z2 cost
result=in_closed(x2,z2);
if (result == 1)
    {
    return;
    }
//  at this point, node is not in closed
result=in_open_and_not_removed(x2,z2,cost);
if (result == 1)
    {
    return;
    }
//  at this point, node is  not in closed or open
add_to_open(x2,z2,astar_dist(x2,z2,goal_x,goal_z)+cost,cost,x,z);
}






void expand_neighbors(int x,int z,int goal_x,int goal_z,int i,int rad)
{
expand_neighbor(x,z,x-1,z-1,goal_x,goal_z,i,astarmap[x][z].g+14,rad);
expand_neighbor(x,z,x,z-1,goal_x,goal_z,i,astarmap[x][z].g+10,rad);
expand_neighbor(x,z,x+1,z-1,goal_x,goal_z,i,astarmap[x][z].g+14,rad);

expand_neighbor(x,z,x-1,z,goal_x,goal_z,i,astarmap[x][z].g+10,rad);
expand_neighbor(x,z,x+1,z,goal_x,goal_z,i,astarmap[x][z].g+10,rad);

expand_neighbor(x,z,x-1,z+1,goal_x,goal_z,i,astarmap[x][z].g+14,rad);
expand_neighbor(x,z,x,z+1,goal_x,goal_z,i,astarmap[x][z].g+10,rad);
expand_neighbor(x,z,x+1,z+1,goal_x,goal_z,i,astarmap[x][z].g+14,rad);
}

 

do you see anything wrong?

g for the new node = parent's g + 10 or 14.

f = g for new node + astar_dist()

NOTE: astar_dist = int (true_2D_dist * 10.0f)

This is why i'm stumped. I hate it when I don't understand WHY something doesn't work. I'm one of these people who always has to understand why something is the way it is, or in programming, why a bug was doing what it was doing. I mean technically, i just keep my heuristic admissible and don't use remove from closed, and its doesn't matter why.

BTW, getting rid of remove from closed fixed everything!

But the question of why exactly still remains.

The most dangerous fix is the one where you don't exactly know why it worked - or exactly what was wrong in the first place. Because then you don't really know if its fixed for sure or not.