A* path finding question!

synthead · 2012-09-28 05:01:13

I'm writing a tower defense game in Python as my way of learning the language! So far, it's coming right along. But I've ran into a situation that has left me confused. Take a look:

The cyan squares represents the current shortest path, the violet squares represent paths the algorithm has tested, and the dark gray squares are walls. So currently, the algorithm has backed the "best path" into a corner. What would the A* algorithm do here?

Last edited by synthead (2012-09-28 05:03:39)

Rip-Rip · 2012-09-28 06:16:36

You should probably look at the wikipédia article on A*. There is an animated gif that shows a problem similar to yours.

The issue here, is that the violet squares should be on the "open set", so should not have been tested by the algorithm.

synthead · 2012-09-28 06:23:49

I saw the animated gif and the pseudocode, but I'm still a little confused. Also, why would the violet bits not be tested? Shouldn't they be tested as it continues along the path to make sure it's following the lowest g score?

Rip-Rip · 2012-09-28 06:53:17

Dijkstra (and A*), doesn't in theory compute the shortest path between a source and a destination, but between a source and all the nodes. On those algorithms, once you've tested a node you know 1) it's distance to the source, 2) where the shortest path came from, so you cannot recompute a shortest path for a node.

Here you should test the node that has the lowest "distance from src + heuristic", so probably one of the node adjacent to the violets.

synthead · 2012-09-28 15:32:02

If I continue the path from one of the rightmost violet squares, the algorithm would run into this problem:

Arch Linux

#1 2012-09-28 05:01:13

A* path finding question!

#2 2012-09-28 06:16:36

Re: A* path finding question!

#3 2012-09-28 06:23:49

Re: A* path finding question!

#4 2012-09-28 06:53:17

Re: A* path finding question!

#5 2012-09-28 15:32:02

Re: A* path finding question!

Board footer