Recently, I read some articles and codes related to graphics and algorithm visualization, which were very interesting, so I learned to do some things myself.

Maze generation algorithm

I played with mazes as a child, but I never thought about how they were designed. I thought someone had just drawn them slowly. After reading this article on the Internet, I know that it can also be randomly generated:

Maze Generation – Visualizing Algorithms

I found some reference materials, tried to achieve several, just slowly understand some of the principles.

The maze discussed in the algorithm satisfies one condition: there is only one path between any two points in the maze.

It seems pretty complicated to randomly generate mazes that satisfy these conditions. But when you change your mind, it turns out that the problem isn’t that complicated.

Trees actually satisfy this condition:

  • All branches and leaves can be connected by branches and trunks
  • Since the branches do not cross, there are no rings, so the path between the branches and leaves is unique

So the problem of generating random mazes is transformed into the process of generating random trees. Further, it can be broken down into the following processes:

  • Select a random point as a “root” in the maze grid
  • Start at the root of a tree and grow in a randomly chosen direction
  • Until the branches of the tree grow, branching and filling all the grids of the maze

There are two main differences between different algorithms for maze generation:

  • The maximum length that is generated from a location and continues in a random direction: some are replaced immediately after extending a mesh, others are replaced only after extending no further
  • The method of selecting the location of the replacement growth point: either recording the current stem passing through the grid and moving backward, or simply choosing a point at random that has the potential to grow outward

Depth-first algorithm

Depth-first algorithm, also known as recursive backtracking algorithm. It grows in a random direction until it can’t be generated, moves back one space, and continues to grow until all the grids are filled.

A depth-first maze would have a significantly longer path because there was plenty of room for long branches when the tree was first created.

Prim algorithm

The Prim algorithm does not always explore a path, but tries random points of growth. Therefore, the maze generated by Prim algorithm will have more forks:

Algorithm implementation

Combining the above two algorithms, I do not want to have too long path, nor do I want to have too many forks, so I try to extend along a path with a certain length at most, and then randomly select the growth point to perform the same process.

Below is the effect of growing up to 15 meshes per branch on a 40-by-40 maze grid:

This is executed after a period of time when most of the maze has been covered:

This is the final result:

Online DEMO: Maze generation algorithm for the wafbotang

Algorithm visualization

In the example above, the maze is generated using HTML

All the grids of the whole maze are represented by a two-dimensional array, and the state of each grid includes whether it is accessed or not, and the connectivity with adjacent grids, etc.

The execution process of the algorithm is driven by timer, one step at a time, so as to have the effect of animation.

Shortest path algorithm

Graph related shortest path algorithm, in life should be widely used, from one location to another, with the help of the existing road network, calculate the shortest path. Of course, results can vary depending on road conditions, temporary obstacles, and user preferences.

For the graph, the basic elements are:

  • node
  • Edges: Depending on the scene, there are also direction and weight attributes

Dijkstra algorithm

Dijkstra algorithm is a well-known algorithm for calculating shortest paths, which was published as early as 1956.

Dijkstra’s algorithm, if you look at the detailed execution of the algorithm, is a little bit complicated, but the basic idea, if you do it, looks pretty simple.

If the shortest path from A to B is determined, B is connected to C, and the distance from A to B plus the distance from B to C is less than the current distance from A to C, A to B and then to C is the shortest path from A to C.

As shown in the figure above, initially from A, the shortest path to C is A -> C, and the distance is 4. However, after continuing to explore B, it is found that the distance between A -> B and B -> C is only 3, which is smaller than the distance between A -> C, so the shortest path from A to C is updated as: A -> B -> C.

Algorithm implementation

The basic idea has been introduced above, and the details are that each time a node is explored, the node with the shortest distance from the source point is selected, so that the path from the source point to the current point is already the shortest path.

Algorithm visualization

The visualization of the graph is more complicated, but it is not difficult to draw it out, but it is more troublesome to carry out a reasonable layout of nodes and edges, which is another topic.

I chose to draw the graph with the Network provided by vis.js, and then update the graph by executing the algorithm step by step.

This is the initial state:

During execution, the system records whether the node is accessed, the current shortest path, and the corresponding distance:

After all execution is complete, we get the shortest path from the source point to all nodes in the graph:

DEMO: Dijkstra algorithm – orphoporphang

The Github Pages configuration of the project has a problem, so you can only open the page after downloading it locally.

conclusion

None of this is particularly difficult to implement; there is plenty of data and code available. But no matter what rice, have to eat, digestion is their own. So, I wrote down the “nutrition” I absorbed, and if you are interested, you can try it yourself.

Finally, thanks for reading!