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
- Cocos Creator 2.3.4
- TypeScript
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:
- BFS (Breadth-first search-Wikipedia): breadth-first traversal
- DFS (Depth-first search-Wikipedia): depth-first traversal
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:
- When the map has been generated, find the way from the entrance to find the exit.
- 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:
