You are not logged in.

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

synthead
Member
From: Seattle
Registered: 2006-05-09
Posts: 1,326

A* path finding question!

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:

situation1.png

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)


Touch my kernel

Offline

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

Rip-Rip
Member
Registered: 2008-11-09
Posts: 32

Re: A* path finding question!

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.

Offline

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

synthead
Member
From: Seattle
Registered: 2006-05-09
Posts: 1,326

Re: A* path finding question!

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?


Touch my kernel

Offline

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

Rip-Rip
Member
Registered: 2008-11-09
Posts: 32

Re: A* path finding question!

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.

Offline

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

synthead
Member
From: Seattle
Registered: 2006-05-09
Posts: 1,326

Re: A* path finding question!

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

best-first-search-trap.png


Touch my kernel

Offline

Board footer

Powered by FluxBB