Search code examples
random-forestmaze

How to find the farthest two points in a randomly generated maze?

Note: I already have a method of randomly generating a maze, found here:

https://en.wikipedia.org/wiki/Loop-erased_random_walk

I'm looking for an algorithm to find the two farthest cells in the completed randomly generated maze. I don't mean the farthest, as in if you were to draw a straight line from one cell to another, the line would have the longest length. That would always result in one of two things:

  1. The top-left cell and the bottom-right cell are chosen.

  2. The top-right cell and the bottom-left cell are chosen.

I intend to find an algorithm to find the two cells that if you were to travel from the first cell to the second cell by one adjacent cell at a time (up, down, left, or right), while not passing through the walls of the maze, it would require you to travel through the most cells.

Example of Randomly Generated Maze Using the Algorithm Found in the Link Above

Thank you in advance.

Solution

  • A maze generated by the algorithm you're using is always a tree. The longest path in a tree is called its diameter, and if you google "diameter of a tree", you'll find algorithms that work.

    The one I suggest for mazes is:

    1. Pick any dead end in the maze. Call this cell A.
    2. Find the furthest cell from A. In case of a tie, any furthest one will do. Use breadth-first-search for this and remember the last cell found. Call it B.
    3. Find the furthest call from B using the same method. Call it C.

    B-C is a diameter of your tree.