Maze-solving algorithm: Difference between revisions

Revision as of 11:08, 1 October 2020

Revision as of 11:13, 1 October 2020

Line 56:

If given an omniscient view of the maze, a simple recursive algorithm can tell one how to get to the end. The algorithm will be given a starting X and Y value. If the X and Y values are not on a wall, the method will call itself with all adjacent X and Y values, making sure that it did not already use those X and Y values before. If the X and Y values are those of the end ___location, it will save all the previous instances of the method as the correct path.

This is in effect a depth-first search, whereexpressed thein term of grid points. The omniscient view prevents revisitingentering pointsloops by memoization. Here is a sample code in [[Java (programming language)|Java]]:

<syntaxhighlight lang="java">

int[][] maze = new int[width][height]; // The maze