Maze-solving algorithm: Difference between revisions

Revision as of 20:27, 25 February 2020

Revision as of 18:07, 11 May 2020

Line 57:

== Recursive algorithm ==

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. Here is a sample code in [[Java (programming language)|Java]]:

<sourcesyntaxhighlight lang="java">

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

boolean[][] wasHere = new boolean[width][height];

Line 104:

return false;

}

</syntaxhighlight>

</source>

== Maze-routing algorithm ==

Line 110:

Maze-routing algorithm uses the notion of [[Manhattan distance]] (MD) and relies on the property of grids that the MD increments/decrements ''exactly'' by 1 when moving from one ___location to any 4 neighboring locations. Here is the pseudocode without the capability to detect unreachable locations.

<sourcesyntaxhighlight lang="C++">

Point src, dst;// Source and destination coordinates

// cur also indicates the coordinates of the current ___location

Line 126:

}

}

</syntaxhighlight>

</source>

== Shortest path algorithm ==