Programming Contest: Mars Rescue.
alex at tweedly.net
Tue Jan 18 20:05:30 EST 2005
Roger.E.Eller at sealedair.com wrote:
>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:
>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.
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
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.
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
More information about the Use-livecode