Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Mon, 12 May 2003 07:49:53 GMT
|
Original-From:
|
Paul Szego <PAUL.SZEGO@NEBULON.saynotospamCOM>
|
Viewed:
|
1011 times
|
| |
|
|
For the shortest path, something like Dijkstra's algorithm is a starting
point:
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
http://carbon.cudenver.edu/~hgreenbe/sessions/dijkstra/DijkstraApplet.html
Just do a search and you will find any number of hits, lots woth coding
examples in your favourite language. If you want more advanced, search
in general for "shortest path" problems (there's plenty of variations).
So now all you need to do is encode the maze as a graph. As you navigate
you need to detect each point where you can make a choice, e.g. a
T-junction or cross-road. These points become vertices in the graph.
You'll also need to encode the start and end points as vertices also.
For each path that connects these junctions you add an edge between
them. The "cost" of the edge should be some relative measure of the
distance between them, however you choose to measure that. It could be
just the distance you've travelled, or time taken (considering
difficulty of navigating corners etc.) or whatever else you choose.
Then run the "shortest path" algorithm and it will find the set of edges
that gets you from point A to B with the lowest cost.
If however you want to know "what's the best way to explore the maze in
the hope of finding the way out" in the shortest possible time, that's
another problem altogether.
HTH, Paul.
scott davis wrote:
> I'm looking for ways to map out the maze and determining which path is the
> shortest.
> thanx
> scott
|
|
Message is in Reply To:
 | | Re: maze solving algorithm
|
| I'm looking for ways to map out the maze and determining which path is the shortest. thanx scott ---- Original Message ----- From: "Paul Szego" <paul.szego@nebulon.com> To: "scott davis" <rcx2man@hotmail.com> Cc: <lego-robotics@crynwr.com> Sent: (...) (21 years ago, 12-May-03, to lugnet.robotics)
|
6 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
