[EMAIL PROTECTED] wrote:
Dijkstra is designed to find the shortest path through a graph (i.e. between a number of nodes) given a link-state database and variable link weightings.Andre,
That sounds like allot of fun! The objective of plotting the shortest path sounds very similar to what Strabo Pathfinder does. Strabo is a program used by robotics enthusiasts to map out the rooms of their home to allow a robot (we'll assume that it is a mars rover) to move freely on the map without crashing into walls and furniture. More info about Strabo Pathfinder can be found at:
http://www.wehali.com/robotics/strabo.htm
Anyways, the algorithms used to plot the shortest route is one that are Dijkstra and A* (commonly used in games). I have no clue as to how it works, but I would love to see the algorithm recreated in transcript.
I think to apply it to this problem, you'd need to make each cell a node, and you'd have a fairly dense link-state because each cell is connected to each of its neighbours; this would mean you'd run a rather large (and space- and time-consuming) Dijkstra calculation. (Note that the most common use of Dijkstra is in ISIS and OSPF routing - where the general guideline is to keep each area down to 50 or fewer nodes).
This problem looks to me much more like a Hightower routing problem (see various CAD papers from the 60s and 70s - I know this makes it too old to be fashionable :-) I think either a Lee-Moore style expanding cell or Hightower-style line-probe algorithm would be perfectly able to solve this problem with far fewer resources than an SPF calculation.
In either case, the tricky part will be mapping the acceleration / steering constraints onto the ideal shortest-path solution you find.
-- Alex.
-- No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.300 / Virus Database: 265.7.0 - Release Date: 17/01/2005
_______________________________________________ use-revolution mailing list use-revolution@lists.runrev.com http://lists.runrev.com/mailman/listinfo/use-revolution
