Pathfinding algorithm bugged?
in [General Programming]
|
From: mike3 on 23 Mar 2010 04:46 Hi. I was trying to implement the A* pathfinding algorithm for a game, and I can't seem to figure out why it's doing what it's doing. When running a simple test between two points with no obstructions, I get this: ################################################################################ ################################################################################ ################################################################################ ################################################################################ ####.########################################################################### #####.########################################################################## ######.######################################################################### #######.######################################################################## ########.####################################################################### #########.###################################################################### ##########.########################.############################################ ###########.######################.############################################# ############.##################...############################################## #############.##############...################################################# ##############.########.....#################################################### ###############.##.....######################################################### ################..############################################################## (used fixed-width font for best viewing) For the cost functions, I use a fixed-cost G-function (i.e. move to any of the 8 neighbors is the same cost) and a Euclidean H-function (rounded down so it is consistent w/the G-function). The open list is managed as a binary heap with a secondary key that breaks ties in a "LIFO" manner (so among squares with identical F score, the one put on last is the first to come out). Though there doesn't seem to be any shorter path in terms of number of squares (this has 32), it looks strange. Now, If I switch the heap tiebreaking to FIFO instead of LIFO, the path looks like this: ################################################################################ ################################################################################ ################################################################################ ####.......##################################################################### ###########.......############################################################## ##################.....######################################################### #######################.....#################################################### ############################...################################################# ###############################...############################################## ##################################.############################################# ###################################.############################################ ################################################################################ ################################################################################ ################################################################################ ################################################################################ ################################################################################ ################################################################################ which is a bit more reasonable but still has a "curve" to it that doesn't feel right. What can/should be done here? Again this path has 32 squares. I suspect the problem is due to how the algorithm chooses among multiple shortest paths on the grid, but how can I get it to choose ones that look nicer? But before that, I want to find out if my A* implementation is even correct. Should these paths be gotten when using LIFO/FIFO tiebreaking, a G-function so that move-to-neighbor equals base cost, and H-function equal to a floored Euclidean (with sqrt!) times the base cost? P.S. I check the neighbors of a square by going around it clockwise, like 123 8 4 765 (This may also affect the queue order.) If you want the source code, I could post it.
From: Patricia Shanahan on 23 Mar 2010 09:49 mike3 wrote: .... > For the cost functions, I use a fixed-cost G-function (i.e. move to > any of the 8 neighbors is the > same cost) and a Euclidean H-function (rounded down so it is > consistent w/the G-function). ... Your G-function appears to be inconsistent with your wishes. Your G-function treats a move to any of the 8 neighbors as equal cost, but you dislike results that are optimal according to that rule. If you want fewer diagonal moves, perhaps you should make the cost of a diagonal move higher. Patricia
From: mike3 on 23 Mar 2010 14:47 On Mar 23, 7:49 am, Patricia Shanahan <p...(a)acm.org> wrote: > mike3 wrote: > > ... > > > For the cost functions, I use a fixed-cost G-function (i.e. move to > > any of the 8 neighbors is the > > same cost) and a Euclidean H-function (rounded down so it is > > consistent w/the G-function). ... > > Your G-function appears to be inconsistent with your wishes. Your > G-function treats a move to any of the 8 neighbors as equal cost, but > you dislike results that are optimal according to that rule. If you want > fewer diagonal moves, perhaps you should make the cost of a diagonal > move higher. > So is that why it takes those paths that aren't nice and straight like that, esp. that one that jogs down and then up? Interestingly, in that mode, it explores a lot less squares than in the other. Is the algorithm implementation correct, though, that is, with these functions and queue type, we should get the result shown?
From: Patricia Shanahan on 23 Mar 2010 18:57 mike3 wrote: > On Mar 23, 7:49 am, Patricia Shanahan <p...(a)acm.org> wrote: >> mike3 wrote: >> >> ... >> >>> For the cost functions, I use a fixed-cost G-function (i.e. move to >>> any of the 8 neighbors is the >>> same cost) and a Euclidean H-function (rounded down so it is >>> consistent w/the G-function). ... >> Your G-function appears to be inconsistent with your wishes. Your >> G-function treats a move to any of the 8 neighbors as equal cost, but >> you dislike results that are optimal according to that rule. If you want >> fewer diagonal moves, perhaps you should make the cost of a diagonal >> move higher. >> > > So is that why it takes those paths that aren't nice and straight like > that, > esp. that one that jogs down and then up? Interestingly, in that mode, > it explores > a lot less squares than in the other. > > Is the algorithm implementation correct, though, that is, with these > functions > and queue type, we should get the result shown? I don't know the algorithm. However, I do see that, given the assumption that moving diagonally is equal cost to moving straight, each path is a minimum distance path. In your type of grid, especially with cheap diagonal movement, there are many, many, minimum length paths between any pair of points. I took a quick look at the Wikipedia page, http://en.wikipedia.org/wiki/A*_search_algorithm, and it seems to call for g() being the distance from the start to the current point, not just from the current point to a neighbor. Patricia
From: mike3 on 23 Mar 2010 20:42 On Mar 23, 4:57 pm, Patricia Shanahan <p...(a)acm.org> wrote: > mike3 wrote: > > On Mar 23, 7:49 am, Patricia Shanahan <p...(a)acm.org> wrote: > >> mike3 wrote: > > >> ... > > >>> For the cost functions, I use a fixed-cost G-function (i.e. move to > >>> any of the 8 neighbors is the > >>> same cost) and a Euclidean H-function (rounded down so it is > >>> consistent w/the G-function). ... > >> Your G-function appears to be inconsistent with your wishes. Your > >> G-function treats a move to any of the 8 neighbors as equal cost, but > >> you dislike results that are optimal according to that rule. If you want > >> fewer diagonal moves, perhaps you should make the cost of a diagonal > >> move higher. > > > So is that why it takes those paths that aren't nice and straight like > > that, > > esp. that one that jogs down and then up? Interestingly, in that mode, > > it explores > > a lot less squares than in the other. > > > Is the algorithm implementation correct, though, that is, with these > > functions > > and queue type, we should get the result shown? > > I don't know the algorithm. However, I do see that, given the assumption > that moving diagonally is equal cost to moving straight, each path is a > minimum distance path. In your type of grid, especially with cheap > diagonal movement, there are many, many, minimum length paths between > any pair of points. > > I took a quick look at the Wikipedia page,http://en.wikipedia.org/wiki/A*_search_algorithm, and it seems to call > for g() being the distance from the start to the current point, not just > from the current point to a neighbor. > The G-*function* is from point to neighbor, G-*cost* is the cost along the path already traversed. The latter is built up using the G-function as we hop to a neighbor.
|
Pages: 1 Prev: ANN: Seed7 Release 2010-03-21 Next: Alternatives to C: ObjectPascal, Eiffel, Ada or Modula-3? |