Re: Question about the Closed list in A* (pathfinding)
- From: Mika Viljanen <mika.viljanen@xxxxxxxxxxxxxxxx>
- Date: 23 Mar 2008 16:33:32 GMT
Jonathan Campbell <jg.campbell.ng@xxxxxxxxx> wrote:
If you want to email me, I can send you the demonstration program
that I've adapted; that would help also understanding the trace
contained in 'astar1.txt'. It badly needs refactoring, but I have
not time to do that before I present the lectures on pathfinding.
Thank you. However, I have just written a small Java framework to test
a couple of A*-based algorithms myself and I was mostly just
digressing with my question. Of course it is an important one when
writing one's own implementation of A* but I'm pretty confident now
that I can leave out checking the cost of the nodes on the closed list
when running into them in later iterations. (And if I feel like they
must be checked, that is simple to do, only with some effenciency
cost.)
Incidentally, another book whose 'breadth-first' and A*
implementations I would have great confidence in [...]
I had actually used (and quoted) a pseudo-code listing by James
Matthews[1] but just today I noticed that - in addition to mentioning
both lists for updating the cost value - his listing is missing the
part when a node is actually placed on the closed list after exploring
it. (A simple mistake, I guess, and he does write about it in his
article, just not in the listing.)
I have come across e.g. these two sites showing different views on the
subject:
http://www.policyalmanac.org/games/aStarTutorial.htm
("For each of the 8 squares adjacent to this current square...
If it is not walkable or if it is on the closed list, ignore it.")
http://wiki.gamegardens.com/Path_Finding_Tutorial#Pseudo-code_A.2A
("if (this neighbor is in the closed list and our current g value is
lower) {
update the neighbor with the new, lower, g value
change the neighbor's parent to our current node
}")
So I guess the issue is not very clear even to people who write
tutorials about it...
Anyway, thanks for your replies.
Best regards,
Mika V
1: @INCOLLECTION(matthews02,
BIBITEMLABEL = "Mat02",
AUTHOR = "James Matthews",
TITLE = "Basic {A*} Pathfinding Made Simple",
BOOKTITLE = "{AI} Game Programming Wisdom",
YEAR = 2002,
EDITOR = "Rabin, S.",
PUBLISHER = "Charles River Media")
.
- References:
- Question about the Closed list in A* (pathfinding)
- From: Mika Viljanen
- Re: Question about the Closed list in A* (pathfinding)
- From: Jonathan Campbell
- Re: Question about the Closed list in A* (pathfinding)
- From: Mika Viljanen
- Re: Question about the Closed list in A* (pathfinding)
- From: Jonathan Campbell
- Question about the Closed list in A* (pathfinding)
- Prev by Date: Re: Question about the Closed list in A* (pathfinding)
- Next by Date: Re: Numbrosia Puzzle AI Challenge
- Previous by thread: Re: Question about the Closed list in A* (pathfinding)
- Next by thread: Re: Question about the Closed list in A* (pathfinding)
- Index(es):
Relevant Pages
|
|
