Jump to content
  • Advertisement
Sign in to follow this  
Norman Barrows

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

This topic is 793 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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....

Edited by Norman Barrows

Share this post


Link to post
Share on other sites
Advertisement

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?

Share this post


Link to post
Share on other sites

Properly-implemented A* won't 're-open' a closed node. The whole premise of A* is that you are examining candidate solutions in ascending order of optimistically-assessed cost. If you ever re-open a node, that implies that the first time you examined it wasn't the shortest route to it after all - which means your algorithm is broken somewhere. Unfortunately there are a bunch of bastardised implementations that conflate physical locations with state space nodes and perform various tricks to treat the 2 graphs as equivalent, meaning various juggling tricks when it comes to node 'opening' and 'closing'.

 

The closed set is basically "state spaces I have already examined, and therefore do not need to examine again". How you represent that is up to you, but those nodes should not be candidates for further examination if you are implementing A* properly.

 

"node 6's parent is node 7, and 7's parent is 6" - one of those nodes should have been added to the closed list when you pulled it off the open list. It shouldn't have been a candidate neighbour for any subsequent node.

 

e.g.

We start with an open list of just node 7.

Find the neighbours - nodes 6, 123, 456, and 999. Add those to the open list, each with a parent of 7, ordered by f=g+h, as specified. H must never be an overestimate. G must never be less than its parent's G score. If these conditions aren't met, then you're not doing A*.

Now add node 7 to the closed list - we can't possibly reach here by a quicker route because we were already here.

Next iteration - our open list is 6, 123, 456, and 999. Assume they're in that order.

The node to examine is 6. Find the neighbours - you'd discount 7 because it's on the closed list. You wouldn't discount 123, 456, or 999 if encountered, and they can replace the corresponding existing nodes on the open list if somehow this would be a quicker route to them. But discounting 7 means you can't get that loop.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

If the heuristic is inadmissible then your algorithm is no longer A*. But we'll set that aside, because Amit is right in saying that inadmissible heuristics can be useful.

 

Your problem appears to be that you keep hitting "if neighbor in CLOSED and cost less than g(neighbor)". Node 6 is pulled off Open, added to Closed. It sees Node 7 as a neighbour, adds it to Open. Then later, Node 7 sees Node 6 in Closed and thinks it costs no more to get back there than it did to reach it in the first place. 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.

 

To word it another way, somehow G(Start -> ... -> 6 -> 7 -> 6) < G(Start -> ... -> 6). This isn't allowed, because G, for each extra node added to a path, must grow monotonically. (Proof: if somehow a path can get shorter by doubling back, then you'd just keep circling for an infinitely short path, so the algorithm will never terminate.)

Edited by Kylotan

Share this post


Link to post
Share on other sites
So THAT's where that implementation came from. I recently fixed an implementation at work that was written that way.

I write the inner portion of the loop like this instead:
 
if (neighbor.openClosedState == CLOSED) continue // all possibly cheaper ingress paths to this node have been evaluated already

newCost = generate cost

if (neighbor.openClosedState == OPEN and newCost >= neighbor.existingCost) continue // not better than existing path

// if no condition above has continued the neighbor loop yet, the new path is better

update neighbor cost and parent

if (neighbor.openClosedState == OPEN)
{
  Fix neighbor location in the priority queue (since the cost modification may have invalidated the heap ordering)
}
else
{
  put neighbor in priority_queue
  neighbor.openClosedState = OPEN
}
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. Edited by Nypyren

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

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.


I agree, it would be helpful to find out. I would put remove-from-closed back in and have a breakpoint on it, and examine what the various cost values are and double check that they're valid. It may reveal other issues.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!