Author Topic: Micromouse coding and algo  (Read 3128 times)

0 Members and 1 Guest are viewing this topic.

Offline mohit sharmaTopic starter

  • Jr. Member
  • **
  • Posts: 28
  • Helpful? 0
Micromouse coding and algo
« on: January 17, 2010, 11:58:48 AM »
Hi can anyone help me to know how to do coding for micromouse using floodfill algo. I have studied about this algo bt it seems very typical. Can anyone explain me how to code ?
I m also confused that how will mouse read the no of cells it covered & how many subroutines & interrupts i have to call ? I m using ATmega16 and i have completed a line follower. Plz help me i havent find anything vry good on net till now....... ???

Offline Pratheek

  • Contest Winner
  • Robot Overlord
  • ****
  • Posts: 125
  • Helpful? 3
Re: Micromouse coding and algo
« Reply #1 on: January 22, 2010, 08:19:58 AM »
Do you want the algorithm or the code itself?

Google and I'm sure you will get the algorithm, you may even get the code.

Offline mohit sharmaTopic starter

  • Jr. Member
  • **
  • Posts: 28
  • Helpful? 0
Re: Micromouse coding and algo
« Reply #2 on: January 27, 2010, 03:23:47 AM »
I have got to know that how floodfill algo works (as i want to use that in my micromouse) bt still i have a lot of questions ?
1 How will we flood the maze ?
2 How will mouse come to know that it crossed how much no of cells ?
3 How will it update the maze it self ?
plzz explain me how to start coding and anything abt sensors used for micromouse

Offline Pratheek

  • Contest Winner
  • Robot Overlord
  • ****
  • Posts: 125
  • Helpful? 3
Re: Micromouse coding and algo
« Reply #3 on: January 27, 2010, 08:13:24 AM »
I have got to know that how floodfill algo works (as i want to use that in my micromouse) bt still i have a lot of questions ?
1 How will we flood the maze ?
2 How will mouse come to know that it crossed how much no of cells ?
3 How will it update the maze it self ?
plzz explain me how to start coding and anything abt sensors used for micromouse


Its all there in http://www.micromouseinfo.com/

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,659
  • Helpful? 169
    • Society of Robots

Offline mohit sharmaTopic starter

  • Jr. Member
  • **
  • Posts: 28
  • Helpful? 0
Re: Micromouse coding and algo
« Reply #5 on: January 27, 2010, 11:52:53 PM »
sir i have read a lot about floodfill algo can u help me to generate a code using that . I have visited all forums and websites mentioned .

 #define NORTH      1
#define EAST       2
#define SOUTH      4
#define WEST       8           
#define VISITED      16
#define ONROUTE      32

#define NOTNORTH  (255-NORTH)
#define NOTEAST   (255-EAST)
#define NOTSOUTH  (255-SOUTH)
#define NOTWEST   (255-WEST)
#define ALLWALLS  (NORTH|EAST|SOUTH|WEST)     

 
   
// maze storage
#define NUMCELLS 256
extern CELL maze[NUMCELLS] ;
extern CELL map[NUMCELLS];

/*
  floodMaze solves the maze using wall data found in the array maze
  and places the flooding data - effectively the routemap - into
  the array map. The destination cell is passed in to the function
  to allow solving for any location.
  The state of map on entry is not important and it is not important
  whether all the walls have been found. The algorithm simply performs
  the flood based on what it knows at the time it is called.
  At worst, up to 255 passes are made through the maze date in generating
  the map. If that many passes are made, there has been an error and
  the maze should be considered to be seriously in error.
  Passes of the algorithm are made until either the limit has been reached
  or the change flag indicates that none of the map data has changed in
  that pass. At that point the maze can be considered to have been solved.
  Clearly, unless all the walls have been observed, the map will contain
  invalid paths. The mouse will discover new walls and call the solver again
  as needed.
  The function returns the number of passes required to solve the maze.
  A returned value of 255 indicates an error.
  Note that the array is allowed to wrap around in a most dangerous
  manner by relying on the 8 bit pointer.
  This should not be a real problem in as much as the existence of the outer
  walls means we never have to make use of the value
*/

UCHAR floodMaze(UCHAR goal)
{
  UCHAR i,j;
  UCHAR now,next;
  UCHAR passes;
  UCHAR cellwalls;    // the wall data for a given cell
  UCHAR changed;

  i = 0;
  do{
    map[i--] = 255;
  } while (i);

  map[goal]=0;
  passes = 0;
  now = 0;
  next = now+1;
  do
  {
    changed = 0;
    i = 0;
    do
    {
      if (map==now)
      {
        cellwalls=maze;
        if ((cellwalls & NORTH) == 0)
        {
          j = i+1;
          if (map[j] == 255){ map[j] = next; changed=1;}
        }
        if ((cellwalls & EAST) == 0)
        {
          j = i + 16;
          if (map[j] == 255){ map[j] = next; changed=1;}
        }
        if ((cellwalls & SOUTH) == 0)
        {
          j = i + 255;
          if (map[j] == 255){ map[j] = next; changed=1;}
        }
        if ((cellwalls & WEST) == 0)
        {
          j = i + 240;
          if (map[j] == 255){ map[j] = next; changed=1;}
        }
      }
      i--;
    } while(i);
    now  = now+1;
    next = now+1;
    passes++;
  } while(changed);
  return passes;
}



this is the code that i found on forum can u explain it , i have read all comments but can u explain how maze is flooded in it and it stored the shortest path.

 


Get Your Ad Here

data_list