Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Fri, 20 Jun 2003 20:17:49 GMT
|
Viewed:
|
942 times
|
| |
|
|
Timothy wrote in his posting (2003.06.01):
> 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.
I dont know if i understand you right, but you should not put the ID into the
cells but use all 16 bits of an array cell to store 4 maze cells in the way you
propose. You can use SHIFT RIGHT operation to get the bits from higher nibbles
(a byte consists of 2 nibbles) and AND operation to separate the desired nibble
from the rest in the 16 bit number (mask it out), OR operation to combine
nibbles. Next, div (division) and mod (modulo) operations are usefull to handle
the addressing. NQC: 7 % 5 = 2. 7 modulo 5 result is 2. After you
divide 7 by 5, two will remain.
Now let (x,y) be the maze cells coodinates, with x, y ranging from zero to four.
z will be the nibble address and
u the NQC array index.
w is the nibble address inside a 16 bit number. You get:
1 2
z 0123 4567 8901 2345 6789 0123 4
x 0123 4012 3401 2340 1234 0123 4
y 0000 0111 1122 2223 3333 4444 4
u | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
w 0123 0123 0123 0123 0123 0123 0123
z = y * 5 + x;
u = z / 4; /* integer division with integer result */
w = z % 4;
Accessing x or y greater then four, what will result in z greater than 24 is
error condition. Same to negative values.
We need two methods to access the maze cells. One to store and one to retrive
data, lets name them setmc( x, y, cell ) and getmc( x, y ). mc: maze cell.
int maze[7]; /* use access functions! */
void setmc( int x, int y, int cell ) {
int z, u, w, c;
z = y * 5 + x;
u = z / 4;
w = z % 4;
c = maze[u];
switch(w) {
case 0:
c &= 0x0FFF; /* clear requested nibble */
c |= cell << 12; /* shift requested nibble into position */
break;
case 1:
c &= 0xF0FF;
c |= cell << 8;
break;
case 2:
c &= 0xFF0F;
c |= cell << 4;
break;
case 3:
c &= 0xFFF0;
c |= cell;
break;
}
maze[u] = c;
}
int getmc( int x, int y ) {
int z, u, w, cell;
z = y * 5 + x;
u = z / 4;
w = z % 4;
switch(w) {
case 0:
cell = maze[u] >> 12; /* shift requested nibble to 2^0 position */
break;
case 1:
cell = maze[u] >> 8; /* shift nibble */
break;
case 2:
cell = maze[u] >> 4; /* shift nibble */
break;
case 3:
cell = maze[u];
break;
}
cell &= 0x000F; /* clear unused bits */
return cell;
}
I did not test it. I hope, it contains no errors, if not even severe ones. Note:
no error handling regarding subroutine parameter array indexes checking is
programmed.
Probably you will find it usefull to know, if a given maze cell has been already
explored. This one bit information can easily be stored using the 3 free nibbles
(12 bits) at array index 6 and giving it 16 more bits in a further index.
In this case, we need some more subroutines, using the "shift", "and", "or"
technique described above:
initmc : clear the visited bits
setmcVisited( x, y ) : set a visited bit for a specific cell
ismcVisited( x, y ) : check the visited bit
RCX2 NQC has 32 global and 16 local variables. We need 8 global variables to
store the maze map with the special visited map array, 7 without.
What do you think about this idea, Timothy?
Greetings,
Ralph
|
|
1 Message in This Thread:
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
