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

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[a].pathable and self.tileMap[a] not in self.openList and self.tileMap[a] not in self.closedList:
if self.distance(tile, self.tileMap[a]) * TILE_SIZE <= self.straightCost:
self.G = tile.score[1] + self.straightCost
self.H = self.distance(self.tileMap[a], self.endTile)
self.F = self.G + self.H
else:
self.G = tile.score[1] + self.diagCost
self.H = self.distance(self.tileMap[a], self.endTile)
self.F = self.G + self.H

#Append to list and modify variables.
self.tileMap[a].score = (self.F, self.G, self.H)
self.tileMap[a].parent = tile
#self.tileMap[a].color = OPEN
self.openList.append(self.tileMap[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()

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:

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

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.



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.

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
http://www.policyalmanac.org/games/aStarTutorial.htm