Maze creation and path finding algorithm source code written by Java.
The maze creation algorithm uses the binary tree algorithm to create a maze.
- Designate all edges as unreachable walls 2. All even-numbered tiles are made into walls.
- If you do this, all non-wall areas (green tiles) will be surrounded by walls on all sides.
- Edge (1) is also blocked by a wall (because it’s an even number).
- In this state, the wall in one of the two directions, either to the right or downward based on the tile rather than the wall, will be made green and drilled through.
Summary: From the perspective of one accessible tile, one of the two walls to the right and bottom is randomly selected and changed into the accessible tile. In other words, it randomly selects one of two directions and clears the path.
Referenced document: Maze creation algorithm (Binary Tree, Side Winder) with C#
BFS (G, s) //Where G is the graph and s is the source node.
let Q be queue.
Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.
mark s as visited.
while ( Q is not empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = Q.dequeue( )
//processing all the neighbours of v
for all neighbours w of v in Graph G
if (w is not visited) and (w is a passable node) and (w is in corret range)
Q.enqueue( w ) //Stores w in Q to further visit its neighbour
mark w as visited.
Referenced document: Breadth First Search Tutorial
DFS (S, s) //Where G is the graph and s is the source node.
let S be stack.
S.push( s ) //Inserting s in stack until all its neighbour vertices are marked.
mark s as visited.
while ( S is not empty)
//Removing that vertex from stack, whose neighbour will be visited now
v = S.pop( )
//processing all the neighbours of v
for all neighbours w of v in Graph G
if (w is not visited) and (w is a passable node) and (w is in corret range)
S.push( w ) //Stores w in Q to further visit its neighbour
mark w as visited.
Referenced document: Breadth First Search Tutorial
Let us call the heuristic weight function
At this time,
Euclidean distance from
A* (G, s) //Where G is the graph and s is the source node.
let PQ be priority queue. //And PQ is sorted in ascending order based on the heuristic function f(x).
PQ.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.
mark s as visited.
while ( PQ is not empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = PQ.dequeue( )
//processing all the neighbours of v
for all neighbours w of v in Graph G
if (w is not visited) and (w is a passable node) and (w is in corret range)
PQ.enqueue( w ) //Stores w in Q to further visit its neighbour
mark w as visited.
Let us call the heuristic weight function
At this time,
Manhattan distance from
Thus,
A* (G, s) //Where G is the graph and s is the source node.
let PQ be priority queue. //And PQ is sorted in ascending order based on the heuristic function f(x).
PQ.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.
mark s as visited.
while ( PQ is not empty)
//Removing that vertex from queue,whose neighbour will be visited now
v = PQ.dequeue( )
//processing all the neighbours of v
for all neighbours w of v in Graph G
if (w is not visited) and (w is a passable node) and (w is in corret range)
PQ.enqueue( w ) //Stores w in Q to further visit its neighbour
mark w as visited.
Referenced document: A* search algorithm
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent