Thursday, 1 December 2011

Week 6: September 5 to September 11, 2011


Literature Review

Project Tittle: The Inception of Chedda: A detailed Design and Analysis of Micromouse
Author: Tondra De & Drew Hall

Software Development

There are a few maze-searching algorithms that have been discussed by the authors. Among the algorithms are:

i)                   Wall-Following
ii)                  Depth-First Search
iii)                Flood-Fill

Flood-Fill is better suited to the Micromouse as it uses a sophisticated system of distance and wall information to refine a short path to the centre of the maze. Since the maze has a fixed size of 16 cells by 16 cells that is already known to the Micromouse, it must first assign a value to each cell in the maze representing the distance from that cell to the centre and store these values in an array. The Micromouse must also store a wall map which will be continually updated with information as the sensors detect new walls in the maze. At each cell, the Micromouse performs the following steps:

  1. Check for new walls and update the wall map. 
  2. “Re-flood” the maze with new distance values and update the distance array. 
  3. Move to the neighbouring cell with the lowest distance value.
Modified Flood-Fill is a derived version of regular Flood-Fill in which only those values which need to be changed are actually updated when searching the maze rather than re-flooding the entire maze as in regular Flood-Fill.

The following diagrams are a pictorial illustration of the Modified Flood-Fill algorithm:


No comments:

Post a Comment