Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Sun, 1 Jun 2003 04:45:38 GMT
|
Original-From:
|
scott davis <(rcx2man@hotmail.)stopspam(com)>
|
Viewed:
|
1050 times
|
| |
|
|
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" <Wolf_and_eagle@spamblock.yahoo.com>
To: <lego-robotics@crynwr.com>
Sent: Saturday, May 31, 2003 11:03 PM
Subject: Re: maze solving algorithm
> 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
|
| Ok, so did you get the idea about using the Binary system to identify the “cell”? Now, the next choice is what type of variable to use: You can use a small 16 bit variable for each “cell” which will take up 400 bits=50 bytes. This was will conserve (...) (21 years ago, 8-Jun-03, to lugnet.robotics)
|
Message is in Reply To:
| | Re: maze solving algorithm
|
| (...) 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 (...) (21 years ago, 1-Jun-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
|
|
|
|
