Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Sun, 8 Jun 2003 02:32:32 GMT
|
Viewed:
|
1048 times
|
| |
|
|
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 less memory, but it will make it easier
for the robot to uncompress the data.
Or, you can use a larger 32 bit variable to hold more info efficiently at 32 *
5=120 bits=20 bytes. This down side to this is, it will take more time to
uncompress this, and it won’t fit in a an array as well (since each variable
would hold 5 of the “cells”; therefore needing an extra subroutine to extract
the number.)
I’m going to assume you chose the 16 bits per cell in an array option.
Instead of wrapping our cell info into a 2 digit number, we can leave the raw
binary info in the 5 digit variable. So, if our “cell” has no walls, we can just
enter the number 00000 into the variable.
Now for the next problem. The robot now has the ability to maneuver and map a
5x5 maze, but one thing that might not come to mind is the robot doesn’t know
where it is in the map when you start it out. For all it knows, when it enters
the maze it could be in the middle of the bottom of the maze, or to the left or
the right. Unless it know where the entrance is, it won’t know where to place
the map info it gathers. Make sense?
The only two options I can think of are, 1. Have the entrance of the maze at a
standard point in the maze (I.E. 3 “cells” from the right”)
(provided you are going to start the robot on the outside of the maze going in
through an entrance), or 2. Have the robot construct a temporary map that is
[(2*5)-1]x[(2*5)-1]=9x9 so that no matter where you put it to enter the maze, it
start its mapping in the middle of the maze in it memory (I.E. coordinates 5,5),
and will have space to fit.
I don’t know how you would create “temporary” variables in BrickOS unless you
used disposable inline variables or classes (if those can be deconstructed at an
earlier time). The problem is that the temporary map would need to be used as
the main map until it figured out where it was......
Or here is another idea, have the robot use a 5x5 memory map, and have it think
it starts at (3,3). Then as it finds that a passage is actually the edge of the
map, have it move the known map over one "cell" to accommodate the new info. In
other-words, if you start the robot actually at the bottom middle of the maze,
and the robot starts at (3,3) (in its map) and then it moves "up/north" 2
"cells" (physically and in its map) then in its map, it will reach the top,
middle "cell" of the "map in memory". Therefore, when it moves "north" one more
space, it will be off the map, it could then see if there is an empty row at the
bottom of the map. If there is an empty row, it could move all the cells down
one space knowing that the map was oriented too far "north" compared to the
actual maze.
Do you understand? if not, I'll try explaining it again.
I'm sorry if this is complicated or confusing. I'll try to elaborate on anything
I didn't make clear.
Timothy
In lugnet.robotics, "scott davis" <rcx2man@hotmail.com> wrote:
> 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
|
|
Message has 1 Reply:
 | | Re: maze solving algorithm
|
| I'm back to working with NQC. I gave up on brickos. I think I have a program that works, I just need to find some time to test it. Thank you for your help. Scott ----- Original Message ----- From: "Bluey" <Wolf_and_eagle@spam...yahoo.com> To: (...) (21 years ago, 8-Jun-03, to lugnet.robotics)
|
Message is in Reply To:
| | 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)
|
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
|
|
|
|
