I''m back again for help on this maze naviagation problem. You CAN''T have a robot that follows the walls, because the maze will be designed in such a way that you cannot get to the end using this method. I need some algorithm to get through a maze, hopefully using a method of remembering where the robot has been, and making sure that it doesn''t go back to dead end areas. I was thinking about using an array at first, but decided that wouldn''t be a good idea because I''d have to be sorting and re-assigning old values with new data (example, if the robot started in the middle of one wall, it would start at (0,0) and some values would go negative which would mean that I''d have to be always re-assinging and moving values around in the array). Now I''m thinking about using a tree to hold the data, but I''m not sure if it''ll work. The purpose is to get through the maze the fastest. If anyone knows a good way of doing this, or has any ideas, let me know.

This isn''t guaranteed to be the fastest meathod or even the best but it is something to work off of.

To store your information used a linked list, I am pretty new to programming so I am sure there are better ways to do this.

struct _ll{
int x,y,last,count;
_ll * next;
};

where x= your relative x cordinate to where you started from
y= your relative y cordinate to where you started from
last= your last move (I initialize to go to the right)
count= How many times you visit a certain spot.

First you go through the linked lists to find which direction is the prefered direction to go. (x,y) cordinates don''t exist means you haven''t been there yet, so it is the best, or if you''ve been all directions go to the one you''ve been to least.

In the case you have two or more directions that are equal. First go to the right if it is one of the values, if not go straight, if you can''t go straight, go to the left, last option is to go back where you came from.

A way to increase speed is to make imaginary walls in dead ends.
What I mean is if there are three walls, or imaginary walls around you, move back and make that spot an imaginary wall, that way you won''t go back down the dead end. What I would do would be define a wall with a large number like 11000, and an imaginary wall with another large number like 10000.

Again, I am new to this, but maybe this can get some better programmers thinking.

Here is the code I wrote. I don''t know windows programming so if you want to try to run it you get to watch a ''X''. All you need for your robot is the find_path() fuction.


#include
#include

struct _ll{
// x=x cordinate, y=y cordinate,
// last = last direction, count = number of times in that spot
int x,y,count;
// *next is next node of linked list. NULL if the last node
_ll *next;
} *head;
// head is the starting point, always 0,0

const int YMAX=10, XMAX=10, WALL=11000, IWALL=10000;

int curr_x,curr_y, last;

// search algorythm
void find_path();

// since I don''t know windows programming you watch an X run around
void display();

// the maze you have to run through
// 0=space, 1=wall, 2=exit
int MAZE[YMAX][XMAX]={1,1,1,1,1,1,1,1,1,1,
1,0,1,0,1,0,0,0,0,2,
1,0,1,0,0,0,0,1,1,1,
1,0,0,0,1,1,0,1,0,1,
1,0,1,0,0,1,0,1,0,1,
1,0,0,0,1,1,0,0,0,1,
1,0,1,0,0,0,0,1,1,1,
1,0,0,0,1,0,0,1,0,1,
1,0,1,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1};
// used to test for walls in the maze
// actual position = (head->x + relative_x, head->y + relative_y)
// choose the robots starting position with these two variables
// both have to be greater than 1 and less than MAX-1
int relative_x=4, relative_y=4;

int main(){
// initialize the robots know position
head = new _ll;
head->x=0;
head->y=0;
// I use 1=East, 2=South, 3=West, 4=North
last=1;
// since this is the first time visiting this point
head->count=1;
head->next=NULL;
// initialize the current position
curr_x=head->x;
curr_y=head->y;
// run through maze until you break out!
while(MAZE[curr_y + relative_y][curr_x + relative_x]!=2){
display();
find_path();
}
display();
cout << "Done!";
getch();
}

void display(){
int a,b;
clrscr();
for(a=0;a for(b=0;b if(curr_x+relative_x!=b || curr_y+relative_y!=a){
switch(MAZE x=100;
}
}

// this means we have visited a new spot
if(x!=100){
sorc = new _ll;
sorc->x=curr_x;
sorc->y=curr_y;
sorc->count=1;
sorc->next=NULL;
// get to the end of our list
for(dest=head; dest->next!=NULL; dest= dest->next);
dest->next=sorc;
}
}
' Target=_Blank>Link

sorry about the above. It didn''t like the code I pasted to it. obviously the code shown will not work. If you try to edit it, it will show you the actual code I wrote.

The term fastest seems mis-leading. Maybe consistently fast? What comes to my mind would be the use of one of two methods. Number one, use recursion to travel the maze. It would travel until it meets a dead end or a spot already visited, then return to the previous function which would try another path and so on. The second method would be doing the same thing with an iterative function and a stack. Either way you still need to keep track of which paths have been traveled. But now you only need an array of boolian values the size of the number of paths.

now is this going to be an actual robot that gets put down in a physical maze or is this going to be done on a computer screen where the data for the maze will be in some sort of array or you will be able to call a function that tells you which directions you can go from your present location ?
if it is the latter then using recursion would be my best bet as the way to do it like the guy above me said. but be careful if the maze is too large then you may run out of memory and your program wont work or it will crash

"Now go away or I shall taunt you a second time"
- Monty Python and the Holy Grail
We are creating a Multi-player space strategy/shoot-em-up/RPG game.
Development is well under way and we do have a playable demo.
Always looking for help.
Digital Euphoria Soft

This is going to be an actual physical robot. The program being put onto it is a .lx file (the RCX box''s chips were replaced by a college and the new chip runs the linux kernel on it), and it has to be coded in C only. What I mean by fastest is actually being able to get the robot to get through the maze faster than the others, so it needs to get through it with the best time possible. If you need any more information, just ask.

Hey, Slayer-X, guess who?!?!?!

I think i figured out a little way to cheat the system on this maze competition. When we follow the left or right wall it seems we always come back to the same place with the special maze designs. What if there were some way that we could get the robot to sense the first opening on the right when we are following the left wall. I know this will be difficult but it will work. When the robot senses the first opening on the opposite side we can have the robot turn towards the opening and continue to follow that wall which we previously couldn''t get to following the original wall. This will allow us to follow the second wall all the way to the finish no matter how the course is layed out. Of course there is a catch to it----We are going to need 2 programs to compensate for the possibility of the course working from the inside out. But that isn''t as difficult as it sounds. You can test it if you look at that maze example we looked at. Just remind me to show it to you or you can go to http://www.ecst.csuchico.edu/~kend/apec/apec98r.htm to see it. I was looking at other maze designs and all of them seem to be the same. I am not 100% sure that this method will work on all mazes, but if my theory is right then we might just win. It is all going to boil down to how the Engineer designs the maze and the ability of our robot to find an opening on the opposite wall.

~Michael