Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Sun, 1 Jun 2003 03:03:36 GMT
|
Viewed:
|
1011 times
|
| |
|
|
In lugnet.robotics, "scott davis" <rcx2man@hotmail.com> wrote:
> I'm using a rotation sensor and a HiTechnic Distance Sensor.
>
>
> I'd like the robot to search the whole maze.
>
> It's a maze but i'd like to do something more than just follow a wall.
Does the distance sensor swivel to scan the surrounding area and identify walls
or passages?
Ok, if you are going for the mapping and logical searching idea, then its going
to be a lot more complicated.
First off, to logically maneuver through a maze, you need to remember the maze
that you've been through.
Now, to identify the maze layout, you'll need the robot to keep a record.
Typically, you'd use 5*5=25 variables (in an array), but that would restrict
your variable usage a huge amount (32-25=8 ...... try navigating comfortably
with that!).
So instead, you can use a type of compression. Since the variables in NQC are
limited to 16 bit signed integers, the number can only go up to 65536.
Each square of the maze has 4 walls, which can either be there or not. So 2
options per wall ^ 4 walls = 16 possible combinations. Unless you can think of
another type of compression, this is what I think you are going to have to do.
Starting with the “east” wall and traveling around clockwise, we will give each
wall a binary digit. So if the east and west walls were passages, and the north
and south were walls, the number would be 0101 (Binary) = 5 (Decimal). Next, if
all the walls were passages, it would be 1111=15.
This procedure might be a little messy, but it should cut the maze map down to 8
variables.
Since we need 2 digits to hold the ID for each “cell”, and the integers only
hold 5 digits (and a sign) we’ll need to use almost every bit. For the first
“cell” lets say that all the walls are passages=1111=15. Given this, we would
enter -50000 as the number. The negative sign holding the 10s places in 15, and
5 holding the 1s place. The next two can be easily dealt with by storing them in
the next pairs of digits; I.E. 15,15,15, would be -51515.
Make sense?
I’ll try to continue this later with the navigation algorithm, compression
subroutine, and logical searching.
Timothy
|
|
Message has 1 Reply:
 | | Re: maze solving algorithm
|
| I've decided to try and use brickos instead of nqc, so the amount of variables won't matter. So if you could continue on with the array idea, that would be nice. Thanks scott ----- Original Message ----- From: "Bluey" (...) (21 years ago, 1-Jun-03, to lugnet.robotics)
|
Message is in Reply To:
| | Re: maze solving algorithm
|
| ----- Original Message ----- From: "Bluey" <Wolf_and_eagle@spam...yahoo.com> To: <lego-robotics@crynwr.com> Sent: Saturday, May 31, 2003 4:44 PM Subject: Re: maze solving algorithm (...) or (...) and (...) I'm using a rotation sensor and a HiTechnic (...) (21 years ago, 31-May-03, to lugnet.robotics)
|
10 Messages in This Thread:
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
