Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Wed, 21 May 2003 01:26:07 GMT
|
Original-From:
|
scott davis <RCX2MAN@spamcakeHOTMAIL.COM>
|
Viewed:
|
1343 times
|
| |
|
|
One way to map a maze is to put each square into an array and use cartesian
coordinates (X,Y) corisponding to each square.
A 5 X 5 maze would look like so:
[X,Y]
[0,0][0,1][0,2][0,3][0,4]
[1,0][1,1][1,2][1,3][1,4]
[2,0][2,1][2,2][2,3][2,4]
[3,0][3,1][3,2][3,3][3,4]
[4,0][4,1][4,2][4,3][4,4]
To access each square use:
mazearray [ maze height*X + Y]
For a 5 X 5 maze, your maze height would be 5.
I hope this helps
scott
----- Original Message -----
From: "Ralph Töpper" <Ralph.Toepper@t-online.de>
To: "scott davis" <rcx2man@hotmail.com>
Sent: Tuesday, May 20, 2003 7:39 PM
Subject: Re: maze solving algorithm
> Ok, im watching this newsgroup since a longer time. I have never stated • anything
> to it. But now, i ve got an idea, thats challingeing me. Its the idea • about
> doing a maze algorithm.
>
> If you visit the standard theoretical problem sites, you only find the • classic
> problem solution.
>
> This solution will tell you, how to solve a maze, after it has been • mapped.
>
> It tells you nothing about how to map a maze.
>
> Now, if you think about mazes, you can imagine two kinds of them:
>
> 1.) the one, that does not have loops in it. This means, there is no way • in the
> maze, that goes back to a node, where it comes from.
>
> 2.) a loopy maze.
>
> Now if you think about loopy mazes, you'll find, that you need something • to
> identify the node. You can never build a maze mapping algorithm to satisfy • a
> loopy maze without identifing the nodes, when the robot reaches them. • Imagine,
> you can identify a node by GPS data.
>
> In the first case, with no loops in the maze, to map the maze is no • problem,
> since all paths are individual. The robot can only be forced to drive back • to a
> node where he has been at before, after reaching a dead end. The • theoretical
> data structure is a tree.
>
> Ralph
|
|
Message is in Reply To:
 | | maze solving algorithm
|
| Hi, I was wondering if somebody could help me out with different types of maze solving algorithms. I'm using a synchrodrive robot to navigate the maze and a hitechnic distance sensor to find where the walls are. I'm trying to tackle the problem of (...) (21 years ago, 10-May-03, to lugnet.robotics)
|
6 Messages in This Thread:
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
