Maze Solver Help..

[jagzviruz]

Hello all members.

I am a n00b in robotics. I am trying to build a maze solver .I have built a machine that follows walls and turns at absence of wall an proceeds.This however does not ensure that ut will always reach the centre depending on the design of the maze.I have read materials on the net like the flood algorithm etc on sites like micromouseinfo.com and micromouse.cannock.com .While i have been able to understand the algo itself i am stumped as to how to implement it.I mean how do u store the map?

I am using a AT89s52 for the bot driving 2 motors via a l329d with ir sidelooking sensors and front sensors.

Do i have to use an external memory ?plzz help ..with schematics and mebbe a sample code will help me as well...

Thanks in advance.

 

[Pommie]

The flood algorithm isn't that hard to implement. When you meet a dead end, or already explored path, you backup to the last place that you had a choice and take the untrodden path. If you have already trodden that path then backup some more. When implementing the flood algorithm for graphics, you have to keep a software stack to keep track of where you had a choice, with a maze you can reverse until you have an adjoining square with a unknown wall status and follow down that path.

As for storing the maze, you should be able to fit it in the internal memory. Assuming the maze is 16*16 squares and you store the top and left wall status as 2 bits each you will need 16*16*2*2 = 1024 bits or 128 bytes. I suggest 2 bits per wall so you have 00=unknown 10 = no wall and 11 = wall.

I'm not familiar with the AT chips so can't help with example code.

Mike.

 

[jagzviruz]

Thanks for such an early reply Mike.

The At89s52 has 8k flash and 256bytes RAM.. is it possible to store the program ?Even if you can help me with a program for AVR or PIC will be helpful. I will try to modify it for my CHIP .

 

[Nigel Goodwin]

You've already looked at MicroMouse sites - there is code on those, and full explanations of the methods used. That's the place to be looking for help!.

 

[jagzviruz]

Hi Goodwin...

yeah I have looked at the micromouse sites but .. havent been able to get the codes... could you plz redirect me to them ?

 

[Nigel Goodwin]

A quick google finds this which may give you some ideas?.

 

[panic mode]

the simplest working method to solve maze is "one finger" approach.
when you enter, touch one wall with your finger and make sure
it stays in touch with the wall until you are out (don't change hands).
this is not the fastest method so don't use it for competition
(unless other robots suck and can't even make it through).
since you already have sensors, this should be very simple to implement.
with this method you don't need to log progress, turns or anything, just
go till you are out.

 

[Pommie]

I am currently working on a VB program that will simulate a micromouse. It is written in VB and will consist of a module that provides simple test/command type enviroment.

I'm writting it so my son can appreciate programming more.

I'll post details when I have it at a usable level.

Mike.