Sign in to follow this  
GarrickW

What's wrong with my A* algorithm?

Recommended Posts

GarrickW    115
So before I go and write it in C++, I decided to write an A* algorithm in Python, just to wrap my head around it. I've mostly got things working, but by algorithm seems to be searching far too many tiles. I'm not sure if this is normal, but it doesn't look very logical. The image at the end of the post shows the issue; black is the final path chosen, and dark grey is everything in the [i]closed [/i]list that's not in the final path (you can guess what the open list looks like, there's nothing wrong with that).

I'm not sure why it's searching such a huge circle; probably something that slipped my notice. When I work too long on something, my brain stops paying attention. :P Theoretically, it should only be searching the member of the open list that is closest to the (green) target; there is no reason for it to be looking everywhere in that circle. It's especially suspicious since it's a very neat and tidy circle.

The important code (the stuff relevant to the pathfinding) is as follows. It'd be awesome if someone could spot where I'm being stupid. I'll also happily upload the whole source, if anyone is interested (uses Python 2.6 and PyGame 1.9).

[code]def distance(self, tile1, tile2):
self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE)
self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE)
self.totalDist = math.sqrt(pow(self.xDist, 2) + pow(self.yDist, 2))
return self.totalDist

def examine(self, tile):
self.closedList.append(tile)
tile.color = CLOSED
pygame.draw.rect(windowSurface, (0, 0, 0), tile.rect)
self.openList.remove(tile)
self.neighborsAssigned = 0
for a, b in ((tile.col + 1, tile.row), (tile.col - 1, tile.row),
(tile.col + 1, tile.row + 1), (tile.col + 1, tile.row - 1),
(tile.col - 1, tile.row + 1), (tile.col - 1, tile.row - 1),
(tile.col, tile.row + 1), (tile.col, tile.row - 1)):
if self.tileMap[b][a].pathable and self.tileMap[b][a] not in self.openList and self.tileMap[b][a] not in self.closedList:
if self.distance(tile, self.tileMap[b][a]) * TILE_SIZE <= self.straightCost:
self.G = tile.score[1] + self.straightCost
self.H = self.distance(self.tileMap[b][a], self.endTile)
self.F = self.G + self.H
else:
self.G = tile.score[1] + self.diagCost
self.H = self.distance(self.tileMap[b][a], self.endTile)
self.F = self.G + self.H

#Append to list and modify variables.
self.tileMap[b][a].score = (self.F, self.G, self.H)
self.tileMap[b][a].parent = tile
#self.tileMap[b][a].color = OPEN
self.openList.append(self.tileMap[b][a])
self.neighborsAssigned += 1
print self.neighborsAssigned

def path(self):
self.openList.append(self.startTile)
self.examine(self.openList[0])
self.startTile.color = START
while self.endTile not in self.openList:
self.smallestScore = MAX_DIST
for tile in self.openList:
if tile.score[2] < self.smallestScore:
self.bestTile = tile
self.smallestScore = tile.score[2]
self.examine(self.bestTile)
self.openList = []
self.closedList = []
self.finalPath = []
self.currentTile = self.endTile
pygame.draw.rect(windowSurface, self.currentTile.color, self.currentTile.rect)
while self.startTile not in self.finalPath:
if self.currentTile.parent == self.startTile:
print "Done!"
self.finalPath.append(self.currentTile.parent)
elif self.currentTile.parent not in self.finalPath:
self.finalPath.append(self.currentTile.parent)
self.currentTile = self.currentTile.parent
self.currentTile.color = PATH
pygame.draw.rect(windowSurface, self.currentTile.color, self.currentTile.rect)
else:
print "Error"
self.finalPath.reverse()[/code]

[url="http://imageshack.us/photo/my-images/862/path.jpg/"][img]http://img862.imageshack.us/img862/8240/path.jpg[/img][/url]

Share this post


Link to post
Share on other sites
GarrickW    115
I found a tutorial that uses the Manhattan method and tried that, but I just get a diamond-shaped closed list rather than a circle-shaped one. The distance is calculated thusly:

[code]def distance(self, tile1, tile2):
self.xDist = abs(tile1.col * TILE_SIZE - tile2.col * TILE_SIZE)
self.yDist = abs(tile1.row * TILE_SIZE - tile2.row * TILE_SIZE)
self.totalDist = self.xDist + self.yDist
return self.totalDist[/code]

Either way, the problem seems to be that it's running through the open list and selecting tiles which are not the nearest to the target, then treating them as though they were. This doesn't make sense; that part of my code seems to be pretty straightforward. Go through the open list, if the H score is smaller than the current candidate score, update the candidate. I've tried variations, like making the algorithm check the tiles most recently added to the open list first (which makes odd squiggly lines that go all the way to the side of the screen), but nothing seems to be improving.

[url="http://imageshack.us/photo/my-images/832/pathl.jpg/"][img]http://img832.imageshack.us/img832/9651/pathl.jpg[/img][/url]

EDIT: With a modified algorithm, I get this instead. This one does away with TILE_SIZE, which I thought might be skewing the results. Still searching a huge, unnecessary area, though.

[img]http://i.stack.imgur.com/gFhQa.jpg[/img]

Share this post


Link to post
Share on other sites
ApochPiQ    23059
Remember that for A* to be optimal, you need an admissible heuristic, i.e. your heuristic score must never be greater than the actual minimum score needed to reach the tile. Depending on your straightCost and diagCost values, you might be running into a case where you're using an inadmissible heuristic. The best way to test this is to simply do something like inflating all of your edge costs by a factor of 100; you can then easily tell if your heuristic is yielding incorrect exploration of nodes, or if there's a different bug in the implementation.

I only briefly scanned the code, but for what it's worth I didn't see any glaring errors.

Share this post


Link to post
Share on other sites
Dezzles    100
I don't think it's abnormal for an A* search algorithm to spread out a little bit like in your above example. As you get closer to the target, your cost along the path you're exploring is getting higher, while the distance is getting smaller. The result of this often means that you'll get a little bit of spread happening depending on how you pick the next node. I'm not completely sure what the issue is (it's been a while since I've worked in python) but there is definitely something funny happening (your first example doesn't look like it's following the shortest path)

I'd recommend looking at
[url="http://www.policyalmanac.org/games/aStarTutorial.htm"]http://www.policyalmanac.org/games/aStarTutorial.htm[/url]

Share this post


Link to post
Share on other sites
XXChester    1364
I am still fairly new to the AI field but I don't see a problem with your A* screen shots. A* works basically in waves around the starting point until it reaches the end point. So from your screen shots I wouldn't say I see a problem. The only concern I have is that near the end there doesn't appear to be any searching it just finds the path...but this could just be because the left position is the first location you search.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this