Geek asks and answers

Simple implementation of the maze generation method (arbitrary DFS)

In an interview, my interviewer asked me this question:

Design a function to create a random maze

This is a rather complicated question that needs to be resolved in 30 minutes if you have not yet resolved this issue. There are many solutions on the Internet, but none of them seem simple. The method must respect this limitation:

  • it must take the size of the maze (square maze NxN)
  • it should only consist of Walls and Path
  • to make it simple, the algorithm does not need to set the record and exit

I will send an answer using a solution so that other people can find this question.

An example of a generated maze:

. # # . # . . . . . 
. . . . . . # # # . 
# . # # # # . . . . 
. # . . . . # . # . 
. # . # # . # . # . 
. # . # . . # . . # 
. . . # . # . # . . 
. # . # . . . # # . 
# . . . # . # . . . 
. . # . # . . . # .
+1
source share
1 answer

DFS. NxN, , :

function generateMaze(&$maze, $point) {
    $dirs = [
        [0,-1],
        [1,0],
        [0,1],
        [-1,0],
    ];

    shuffle($dirs);

    foreach($dirs as $dir) {
        $newPoint = [$point[0] + $dir[0], $point[1] + $dir[1]];

        if (isGoodPath($maze, $newPoint)) {
            $maze[$newPoint[0]][$newPoint[1]] = '.';
            generateMaze($maze, $newPoint);
        }
    }

    return $maze;
}

isGoodPath(), , , ( "" )

: https://ideone.com/oufifB

25x25:

# . . # . . . # . . . . . # . . . . . . . # . # . 
. # . # # # . . . # # # . . # # . # # # . . . . . 
. # . . . . # . # . . . # . . . # . . . . # . # . 
. . # # # . # . . # . # # # # . . . # # . # . . # 
. # . . # . . # . # . . # . # # # # . . # . # . . 
. . # . # # . # . . # . . . . . . # . # . . . # . 
# . . . . # . . # . . # . # . # # . . . . # # . . 
. . # # . . # . . # . # . # . . . . # # . . # . # 
. # . . # . # . # . . # . . # # . # . . # . # . . 
. . . # . . # . . . # . . # . # . # . # . . . # . 
# # . # . # . # # # . # # . . . . # . # . # # . . 
. . . # . . . . . . . . # . # # # # . . . # # . # 
# # # . . # # # # . # . . . # . . . . # # . . . # 
. . . # # . . . . # # . # . # . # # # # # . # # . 
. # . . . . # # . # . . # . # . . . . # . . # . . 
. . # . # # . . . . # # # . . # # # # . . # # # . 
# . . # . . . # # . . . . # . # . . . . # . # # . 
. # . . # . # . # # . # . . . # . # # # . . . . . 
. . # . . # . . . . # . # # . # . # . . # # . # . 
# . . # . . . # # . # . . . . # . . # . . . . # . 
. . # . . # # . # . . # # . # . # . . # . # # . . 
# . . . # . . . . # . . . # . . # # . # . # . # # 
# # . # . . # . # . # # . # # . . . . # . . . . . 
# . . . # # # . . . # # . . # # . # # . # # # # . 
. . # . . . . . # . . . # . . . . . . . . . . . .

" " , .

+3

More articles:


All Articles