Tutorial: Generating a maze with DFS and BFS Algorithm Implementations

Generating a maze with DFS and BFS Algorithm Implementations

Inspiration

This tutorial is inspired by this GitHub repo.

Let’s take the above GitHub repository as inspiration and re-create this idea using Cocos Creator using TypeScript. The full project can be found in this GitHub repo.

Run animation

Demonstration of non-recursive random map generation process:

Demonstration of the pathfinding process of non-recursive random map generation:

Development environment

Labyrinth definition

What does the labyrinth look like? The definition of the maze is as follows:

  • Only one entrance, only one exit
  • Only one solution
  • The path is continuous
  • Draw on a square canvas: not other graphics, circles, etc.
  • Wall and path both occupy one cell

Tthe entrance is in the first column of the second row, and the exit is in the second last row:

Algorithms and data structures

The algorithm used to generate and find the maze:

The data structure involved is nn the Script/algorithm folder:

  • List: An interface definition for linear lists, queues and stacks
  • Queue: breadth-first traversal non-recursive implementation needs to be used
  • Stack: depth-first traversal non-recursive implementation needs to be used
  • RandomQueue: makes the generated map more random, but still a bit like BFS
  • RandomQueue2: an improved version of RandomQueue, the map is more random

Demo of the code

The demo of the code contains two parts:

  1. When the map has been generated, find the way from the entrance to find the exit.
  2. How to generate a map, dynamically demonstrate the map generation process in the presence of fog.

There are a total of 10 demos, which can be selected through the visualType attribute in the editor:

Support map size modification and map grid size modification:

2 Likes