lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

FYI - Clicking through one of the external links given on wikipedia's A* page, I found the following information about A* variations, including the aforementioned D*:

There are also some links there to related papers, and if I remember correctly, the same paper I mentioned in my previous response is linked to here (it's in postscript format, if you don't have a PS viewer you might want to do a google search for ghostview). Have a look if you're interested.


From: "Mark Meijer" <>
Reply-To: Lua list <>
Subject: Re: Implementing the Dijkstra Algorithm
Date: Wed, 23 Nov 2005 11:03:13 +0000

On a side note, as also suggested on that wikipedia page, and depending on what exactly you are using the algorithm for, you might want to consider using the A* algorithm instead. Or perhaps another variant dubbed the D* algorithm, where the shortest path found can be dynamically updated "en-route" in real-time (i.e. while actually travelling) as circumstances might change over time. I found a research paper about this once, I could email it to you if you like, just let me know. The algorithm was designed to be implemented on robots for navigation, and I'm sure it could be useful for other applications as well, such as games and simulations.