Squirrels are going NUTS - fun, educational adventure games

PART TWO

(continued from Squirrels are going NUTS - amazing world of computer games) 

 

Squirrels are going NUTS uses a maze solving algorithm. In this video we can watch how Skoory is being chased by clever insects who track the squirrel with a maze solving algorithm. Could the squirrel win? Play the game and find out!

 

 

Maze solving algorithms

The act of finding the route from start to finish of a maze is called maze solving. Maze solving algorithms take into account the amount of information a maze solver has access to: in other words, is bird's eye imagery available or not?

Some maze solving methods can be used by a solver from within the maze. Others are intended to be used when an overview of the maze is available to the solver.

Charles PierreTremaux

One of the first to analyze plane mazes mathematically was Tremaux.

Charles Pierre Tremaux (1859-1882) is another hard-to-track down mathematician who has contributed to the history of maths. He may have been a telegraph engineer in France.

Trémaux’s algorithm

The algorithm is defined in such a way that it chooses a randomized path every time a junction is encountered. All the paths heading from an encountered junction are classified as unvisited and every path gets marked once every time it has been visited.

This means that a path is either unvisited, marked once or marked twice.

When a path has been marked twice, you know that the path leads to a dead end. When the goal has been reached, the solution to the maze consist of the paths that only have been visited once.

Tremaux’s algorithm is a method for finding your way out of a maze by putting down signposts to show where you’ve been:

• Every time you enter or leave a section, you put down a sign.
• Every time you enter a junction:
  • If all of the sections are unmarked, take one of them (the choice doesn’t change the end result)
  • Otherwise, if the section you’ve just visited has one sign only, go back along it (putting a second sign with the one you’ve just put down).
  • If the path you’ve arrived from has two signs, follow whichever other path has the fewest signs on it (the choice doesn’t change the end result).

The algorithm guarantees a path (not necessarily the shortest path) from the starting point to the exit by visiting all the sections and junctions marked with a single sign.

 

How it works

The rules for the algorithm are:

1. Every time you visit a section (cell), mark it with a sign.
2. If you hit a dead end, then turn around and go back.
3. If you arrive at a junction you haven't visited before, pick a path at random.
4. If you're walking down a new section and arrive at a junction you have visited twice, treat it like a dead end and go back.
5. If walking down a path you have visited before (i.e. marked once by a sign) and you arrive at a junction, take any new path available, otherwise take a previously visited path (i.e. marked with a sign once).
6. When you finally reach the end, follow sections (cells) marked exactly once back to the start.

The large green dot shows the current position, the small blue dots show single marks on paths, and the crosses show double marks. Once the exit is found, the route is traced through the singly-marked paths. (Image source: Wikipedia)

(Part One: Squirrels are going NUTS - amazing world of computer games)