Pathfinding implementation not working the way I want it to.

[mike3]

Hi.

I just wrote up some code to do the A* pathfinding algorithm for digging tunnels in a dungeon generator for a Roguelike game, and I'm getting some odd results. When I use it to dig a tunnel through free space between two points, I got this:

Code: [Select]

################################################################################
################################################################################
################################################################################
################################################################################
####.###########################################################################
#####.##########################################################################
######.#########################################################################
#######.########################################################################
########.#######################################################################
#########.######################################################################
##########.########################.############################################
###########.######################.#############################################
############.##################...##############################################
#############.##############...#################################################
##############.########.....####################################################
###############.##.....#########################################################
################..##############################################################

But that doesn't look good. I'd like to have it look like a straightish diagonal line between the two points, something sort of like what would come out of Bresenham's algorithm. Why is it goofy like that? I use a rounded-down Euclidean H-function (with sqrt), a same-cost G-function (i.e. move to any neighbor including diagonals is the same cost), and the open list priority queue is implemented via binary heap with supplementary tiebreaking key to enforce LIFO tie behavior (so it's more of a "stack" than a "queue" when it comes to ties) among nodes/tiles with equal F-cost. Neighbors are checked in a clockwise pattern starting at the upper-left.

If I switch the heap over to FIFO behavior (like a proper "queue"), I get this:

Code: [Select]

################################################################################
################################################################################
################################################################################
####.......#####################################################################
###########.......##############################################################
##################.....#########################################################
#######################.....####################################################
############################...#################################################
###############################...##############################################
##################################.#############################################
###################################.############################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################

which looks a bit better, but the algorithm also seems to explore many more squares. And it's still got that "curve" which doesn't look too good. (Strange; it reminds me of the graph of the square root function. Is there something significant about that?) Both tunnels seem to have the same length (32 squares). I presume it has something to do with how it handles the multiple existent shortest paths between the points, but how do I get it to give me "nice" ones?

The code (C++) for the G, H functions is this:

Code: [Select]

float GCostFuncs_Flat(u16 y1, u16 x1, u16 y2, u16 x2)
{
  return(BASE_COST);
}

float HCostFuncs_Euclidean(u16 y1, u16 x1, u16 y2, u16 x2)
{
  double ydist(y2), xdist(x2);

  ydist -= y1;
  xdist -= x1;

  return(floor(sqrt(ydist*ydist + xdist*xdist))*BASE_COST);
}

And yes, I've tested the heap code to make sure it didn't have any bugs in it. I've tried various descriptions of the A* algorithm and have redone this like 4 or 5 times with the same results... which suggests I'm missing something, but I can't figure out what it is. What is going on here? Using alternative heuristics like, e.g. diagonal (max of x/y distances) doesn't help it, though it's not curved anymore, it has either a long straight segment before diagonaling down (FIFO) or it diagonals down, then goes straight for a while, before a short diagonal up to the destination point (LIFO).

[corremn]

Here is what my A* looks like.  Of course I am not allowing diagonals in this.

Code: [Select]

My H function

float xd = abs( float(  x - nodeGoal.x  ));
float yd = abs(float(  y - nodeGoal.y ));

return xd + yd ; //manhattan moving.
But that is not your problem.

Code: [Select]

################################################################
################################################################
################################################################
################################################################
#####..............................#############################
##################################.#############################
##################################..############################
###################################..###########################
####################################.###########################
####################################.###########################
####################################.###########################
####################################.###########################
################################################################
################################################################
################################################################
################################################################
################################################################
################################################################
and here it is with diagonal movement and a sqrt H function

Code: [Select]

################################################################
################################################################
################################################################
################################################################
################################################################
#####.##########################################################
######.#########################################################
#######.########################################################
########.#######################################################
#########.######################################################
##########.#####################################################
###########..........................###########################
################################################################
################################################################
################################################################
################################################################
################################################################
################################################################
################################################################
################################################################

[mike3]

So then why would my program be giving such a weird result?

[Xecutor]

So then why would my program be giving such a weird result?

Most likely there is a bug in you implementation of A*.
While it's relatively simple algorithm, there are plenty of
opportunities to make a mistake.
Result of corremn looks correct for given functions.

[mike3]

That would seem to make some sense, but what could the bug be, and how could I possibly find it? Remember: I rewrote this thing several times. Which means if I've missed something, it's got to be highly fundamental, and it's quite possible it could be a caveat that is not mentioned in the sources I used to implement from. I looked at 2 sources (3 now) and the algorithms in each gave the same result. I also tried 2-3 heap implementations and a simple searched/sorted-list format.

[Krice]

Not that I understand this algorithm, but that code looks like you try to write shortest possible way and that might be a source of subtle bugs. The compiler doesn't care how short code you write, it's not going to be any faster. Could be slower.

[Joshua Day]

The underlying problem here is that every path from A to B is the same length, as long as it has the requisite diagonals somewhere along the way -- and if it takes an extra diagonal step or two that's fine as long as it takes them back.  Giving a different heuristic won't give you reliable control over which path you get back.  Use the A* heuristic is a way to speed up the search, not a way to prune it.

Since you're not using this to plot a monster's path, be imaginative.  The cost of a step might be the distance from that cell to the straight-line path between A and B, for instance.  (The distance from a point to a line segment is easy to calculate.)  Instead of asking which cell is closer by your game's rules, ask yourself which cell you want A* to pick and charge accordingly.

[mike3]

Not that I understand this algorithm, but that code looks like you try to write shortest possible way and that might be a source of subtle bugs. The compiler doesn't care how short code you write, it's not going to be any faster. Could be slower.

No, I don't consciously try to write real short code, it just turns out that way. And those code was just a couple of distance estimation functions, just mathematical one-line formulas (the first is just a constant, the second is just the Pythagorean theorem), so there's not much longer they can really be. They're not the full program.

[mike3]

The underlying problem here is that every path from A to B is the same length, as long as it has the requisite diagonals somewhere along the way -- and if it takes an extra diagonal step or two that's fine as long as it takes them back.  Giving a different heuristic won't give you reliable control over which path you get back.  Use the A* heuristic is a way to speed up the search, not a way to prune it.

Since you're not using this to plot a monster's path, be imaginative.  The cost of a step might be the distance from that cell to the straight-line path between A and B, for instance.  (The distance from a point to a line segment is easy to calculate.)  Instead of asking which cell is closer by your game's rules, ask yourself which cell you want A* to pick and charge accordingly.

I intended this as a general purpose pathfinding code, not specifically for the dungeon generation (though that'll be one use). Thus I'd like to get a cleaner-looking path than those.

What I wonder then is, how come the other poster's code yielded a cleaner-looking path, while mine didn't? Is there a bug in mine or is it correct?

[AquaTsar17]

As far as I can tell, your code is returning a correct result: a path from A to B with minimal length. The problem is how it decided which square to take next. Since all directions have the same cost, it's probably just using whichever square is first (or possibly last, I'm not sure) in the list of squares and continuing from there. Additionally, you're using floor to keep the H cost an integer but that could be your problem.

My recommendation would be to first try getting rid of the floor call and see what happens. Then I'd do a walk through of your algorithm to see the order of the tiles chosen. That should let you know why it's creating the path it is.

[mike3]

So then it's not a bug, it's just a matter of tweaking the routine. You are correct: depending on which type of heap tiebreaking is used, when dealing with equal-cost entries, either the last one to be put on comes off first (last-in-first-out, i.e. LIFO, which gives the first picture you see) or the first one to be put on comes off first (first-in-first-out, i.e. FIFO, which gives the second picture you see).

Actually, I just tried getting rid of the floor call, and that made the path better (looks like the second one in corremn's post now)

Using the Manhattan also seems to give the same path as the floorless Euclidean (at least when diagonals are enabled), but it explores a great deal more squares. (even ones toward directions _away_ from the goal points! Why's that? Can something be done about that?).

[mike3]

Just answered my own Q about the Manhattan. Apparently I had this:

Code: [Select]

float HCostFuncs_Manhattan(u16 y1, u16 x1, u16 y2, u16 x2)
{
  return(BASE_COST*abs(static_cast<int>(y2) - y1) +
abs(static_cast<int>(x2) - x1));
}

which didn't have parentheses separating the metric part from the multiplication by BASE_COST, which meant the Y-axis was getting a dramatic boost in cost! (YIKES!) I corrected it to:

Code: [Select]

float HCostFuncs_Manhattan(u16 y1, u16 x1, u16 y2, u16 x2)
{
  return(BASE_COST*(abs(static_cast<int>(y2) - y1) +
    abs(static_cast<int>(x2) - x1)));
}

and it is working well now.