Faster Maze Solving

While the in-place flooding method is reliable and easy both to understand and implement, you may want to opt for a faster algorithm.

You can create a queue in memory and deal with each cell once only. The code to do this is a little more complicated and you will need up to 256 bytes of additional memory. The payoff is in performance. The method described below will be 20 to 50 times faster for typical mazes.

There is no absolute need for fast solving but I can see how cutting the total time for a solve cycle from, say 0.5 seconds to 10 milliseconds would be a worthwhile improvement.

We will call the queue the frontier. You will see why when you look at the sequence shown below. As the maze is flooded, a wave front expands outwards from the target cell. It is only these cells that we actively deal with in the queue. As soon as the frontier reaches the starting cell, we are done flooding.

In general, the starting cell is any cell. To solve the whole maze, set the starting cell to the first cell in the maze. To reverse your path, set the target to the first cell and the starting cell to be the centre or your current location.

maze2.gif (1403 bytes) Using the second method, first mark any cells that are adjacent to and reachable from the goal as frontier cells. Flag them and added to a queue of cells to be processed.  maze2a.gif (1392 bytes) While there are cells in the frontier queue, process each one. The contents of each is replaced with the distance to the goal (either stored in the frontier queue or calculated from the neighbours as you go. 
maze2b.gif (1413 bytes) The replaced cell then has its neighbours marked and placed in the frontier queue. maze2c.gif (1412 bytes) The frontier moves toward the start and the visited cells fill with numbers.

The next sequence shows the rest of the maze being flooded.

maze2d.gif (1466 bytes) maze3.gif (1476 bytes) maze4.gif (1533 bytes) maze5.gif (1545 bytes)
maze6.gif (1602 bytes) maze7.gif (1618 bytes) maze8.gif (1654 bytes) maze9.gif (1659 bytes)
mazea.gif (1677 bytes) mazeb.gif (1668 bytes) mazec.gif (1692 bytes) mazed.gif (1691 bytes)
mazee.gif (1692 bytes) mazef.gif (1697 bytes) You can clearly see how dead ends are handled and what happens when there is more than one way through. You will need to be careful about not adding a cell twice to the frontier list.
Once the frontier reaches the start cell you are done. The shortest route that you know of is now traced by simply moving to the neighbouring cell with the lowest value.

The algorithm will look something like this:

       create and initialise a queue with 256 elements
       create a routing map as an array of 256 bytes
       fill the array with the value 255
       fill the target cells(s) with the value 0
       add the target cell locations to the queue
       while there are items in the queue
         get a location from the tail of the queue
         if the cell does not contains the value 255 then
           for each accessible, unfilled neighbour
             put in it a value one more than the current cell
             add it to the queue
           end for
         end if
       end while

You can run this algorithm as often as you have processor time for.

There is actually no need to run it any more often than when you are in a junction cell and you want to decide which way to go.

One way to optimise your route for a speed run is to assign different weights to the neighbouring cells depending on whether you will have to turn to get to them and so on. With a fast flooder/solver, your mouse could try several strategies with test fills to determine the best possible route.

4 thoughts on “Faster Maze Solving

  1. Sumanth

    Hiii..I want to make a micro mouse so i started searching for maze solving algos and found this one..got nice info here..thanks for providing this much info for us…

  2. Rachel

    I am doing a report about micromouse and plan on one day being apart of a team. This is a great bunch of information
    Ty.

  3. Michael

    Interesting concept but I found it doesn’t work in practice for mazes where the destination is the center cell. Instead I looked for the check where the current cell that the mouse is occupying has been assigned a flood fill number, this massively reduces the iterations of the algorithm as the mouse approaches the destination cell.

  4. Peter Harrison Post author

    In what way did it fail to work?

    I have used this without any trouble. It is true that you can make it faster by only flooding out as far as the current mouse location. However, I flood all the way to the start so that I can test whether the mouse has enough information to finish the search early and return for a fast run.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.