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:
- Check for new walls and update the wall map.
- “Re-flood” the maze with new distance values and update the distance array.
- 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