preface

This article is a sample article after I study the book of JavaScript data structures and algorithms, there are many places that are not very good, please forgive me.

I. Example screenshot

Second, preparation

1, the HTML

<! DOCTYPEhtml>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="Width = device - width, initial - scale = 1.0">
    <title>BFS Maze</title>

    <link rel="stylesheet" href="style.css">
</head>
<body>
    <main>
        <h2>Realization of maze pathfinding algorithm</h2>

		<! Here is the beginning of the console area -->
        <div class="mtb-30 flex">
            <div class="mr-10">The number of rows<input type="number" class="row" value="10" min="1">
            </div>
            <div class="mr-10">The number of columns<input type="number" class="col" value="10" min="1">
            </div>
            <div>
                <button class="mr-10 reset">reset</button>
                <button class="mr-10 calc">To calculate</button>
                <button class="random">Random obstacles</button>
            </div>
        </div>
		<! -- Here is the end of the console area -->

        <div class="table">
        	<! -- Where to store the maze grid -->
            <div class="grid"></div>
        </div>
    </main>
    
    <! -- index file is our highlight -->
    <script src="index.js"></script>
    <script>
        const maze = new Maze();// Create a maze object
        const rowInput = document.querySelector(".row");
        const colInput = document.querySelector(".col");

        /** * DOM event listener */
        rowInput.onchange = function() {
            maze.init(rowInput.value,colInput.value);// Initialize the map
        }

        colInput.onchange = function() {
            maze.init(rowInput.value,colInput.value);// Initialize the map
        }

        document.querySelector(".reset").onclick = function() {
            maze.init(rowInput.value,colInput.value);// Initialize the map
        }

        document.querySelector(".random").onclick = function() { 
            maze.randomObstacle();// Random obstacles
        }

        document.querySelector(".calc").onclick = function() { 
            maze.defaultSearchPath();/ / pathfinding
        }
    </script>
</body>
</html>
Copy the code

2, CSS,

* {
    padding: 0;
    margin: 0;
    box-sizing: border-box;
}

body {
    display: flex;
    justify-content: center;
    align-items: center;
    width: 100%;
    height: 100vh;
}

main {
    width: 600px;
    height: 700px;
}

.mtb-30 { margin: 24px 0; }
.mr-10 { margin-right: 10px; }

.flex { display: flex; }

.table {
    width: 600px;
    height: 600px;
    border: 1px solid # 000;
}

.grid { 
    display: grid; 
    width: 100%;
    height: 100%;
}

.grid div {
    position: relative;
    border: 1px solid # 000;
}

.grid div.start::after..grid div.end::after..grid div.obstacle::after {
    position: absolute;
    width: 100%;
    height: 100%;
    background-size: cover;
    background-position: center;
    content: "";
}

.grid div.start::after {
    background-image: url(start.png);
}

.grid div.end::after {
    background-image: url(end.png);
}

.grid div.obstacle::after {
    background-image: url(obstacle.png);
}

.grid div.active {
    background: yellow;
}
Copy the code

3. Picture materials

Barricade: obstacle. PNG

Starting point: start. PNG

The end: end. PNG

3. Functional analysis

Before we can implement a feature, we first need to understand what we are doing, and what we need in order to do it.

Let’s analyze it step by step.

1. Required functions

The first step is to analyze and make a maze finding, which methods we need.

(1) Maze generation

As an example of maze finding, then of course maze generation.

Without the maze, this method is like making bricks without straw.


(2) Random obstacles

Since in this case, the obstacle is not initially initialized, we need to implement a random obstacle method to help us.

Of course, we can also bind click events to each cell (except the start and end) when we initialize the maze.

When clicking the grid, determine whether there are obstacles in the current grid, if there are, then we will remove the obstacles in this position.

If not, then we add obstacles to the location.


(3) Path search

This example is half done when we can initialize the map and random obstacles.

This path search literally searches for the shortest possible path from the beginning to the end.

There are three cases of this method.

The first is that the next node of a node is not the destination

In this case, we just recurse.

Second: the next node of a node is the endpoint

This is one of the baseline conditions for the end of our recursion.

Third: no way out

This is another condition of the recursive baseline condition.

Why is it the shortest path to find? The reason is simple, because the recursion stops when you find the end point in the first place. So the one that comes back is the one that finds the destination first. Since it is the first one to find the destination position, it means that this path consumes the shortest time, which in turn means that this path is the best path (shortest path) (although there may be multiple shortest paths, but this algorithm will only take one).

At this point, we’ve pretty much laid out the methods we need to implement to complete this example.

But in order to implement this logic in a simpler way, we also need to use the linked list and queue data structures.

Here we create the corresponding classes for each of these data structures (including the classes implemented by our three methods).

2. Required classes

(1) Maze

This class is the primary class.

It is responsible for:

  1. Maze initialization
  2. Random obstacle
  3. The path search

The functions listed above.

(2) Node class (linked list class)

This class is used to store a node and its predecessor.

This class allows us to backtrack when we find the end point.

(3) Queue class

This class is used to temporarily store nodes to be accessed.

A node is removed after it has been accessed.

Create a class

1, the Maze

class Maze {
	constructor() {
		this.row = 10;
		this.col = 10;
		this.graph = [];
		this.visited = [];
		this.init(this.col,this.row); }}Copy the code

Here we have created the Maze class and its constructor.

Row, col, graph, and Visited properties are declared in the constructor.

Where row represents the maze rows and COL represents the maze columns.

Graph is used to store the entire maze grid, and Visited is used to store the state (whether or not it has been visited) of each grid.

After declaring the four properties, we call the init method to initialize the map. (The Maze method will be implemented below.)

2, the Node type

class Node {
    constructor(x,y,parent) {
        this.x = x;
        this.y = y;
        this.parent = parent; }}Copy the code

As with the Maze class, once we have created the Node class and its constructor, we add three properties to it.

X represents the x position of the node, and y represents the Y position of the node.

Parent points to the node above it.

3. Queue

class Queue {
    constructor() {
        this.arr = [];
    }

    push(element) {
        this.arr.push(element);
        return true;
    }

    shift() {
        return this.arr.shift();
    }

    size() {
        return this.arr.length; }}Copy the code

Since queues follow FIFO rules, we need to use push to put elements in and Shift to remove them.

Fifth, implementation method

Once we have created the three classes, we are ready to implement the methods in the Maze class.

1. Init method

Just as init means, we use it to initialize the maze and the state of each cell.

This method takes two arguments, COL and row.

init(col,row) {
    this.row = row;
    this.col = col;

    this.graph = [];
    this.visited = [];

    for ( let r = 0; r < row; r++ ) {
        this.graph[r] = [];
        this.visited[r] = [];
        for ( let c = 0; c < col; c++ ) {
            this.graph[r][c] = 1;// 1 indicates that the road is accessible, 0 indicates that the road is not accessible.
            this.visited[r][c] = 0;// 0 indicates no access, and 1 indicates access}}this.buildDom();
}
Copy the code

BuildDom method

This method generates the corresponding Dom element from the Graph array and binds the click event to it.

buildDom() {
	// Get the parent Dom of the maze grid
    const grid = document.querySelector(".grid");

	// Clear all elements in the parent Dom of the maze grid without setting their styles
    grid.innerHTML = "";
    grid.style.cssText = `grid-template-columns: repeat(The ${this.col},1fr); grid-template-rows: repeat(The ${this.row},1fr); `;

    for ( let row in this.graph ) {
        for ( let col in this.graph[row] ) {
			// Create a Dom element for the corresponding grid
            let div = document.createElement("div");

            div.setAttribute("data-key".`${row}-${col}`);// Set the corresponding properties for it

			// Bind events to it
            div.onclick = () = > {
            	// Terminate the execution if the Dom is the starting or ending point
                if ( row == 0 && col == 0 || row == this.row - 1 && col == this.col - 1 ) return;

                if ( div.classList.contains("obstacle")) {// If the current element has a barrier
                    div.classList.remove("obstacle");
                    this.graph[row][col] = 1;
                } else {// If the current element does not have a barrier
                    div.classList.add("obstacle");
                    this.graph[row][col] = 0;
                }
            }

            grid.append(div);// Add a Dom element}}document.querySelector(`.grid div[data-key="0-0"]`).classList.add("start");/ / starting point
    document.querySelector(`.grid div[data-key="The ${this.row - 1}-The ${this.col - 1}"] `).classList.add("end");/ / the end
}
Copy the code

3. RandomObstacle method

/** * gets the element */ in a random position
randomObstacle() {
    let { row , col } = this.getRandom();
    document.querySelector(`.grid div[data-key="${row}-${col}"] `).click();
}

getRandom() {
    let row = Math.floor(Math.random() * this.row),
        col = Math.floor(Math.random() * this.col);

    if ( row === 0 ) row = 1;
    if ( col === 0 ) col = 1;
    if ( row === this.row ) row = this.row - 1;
    if ( col === this.col ) col = this.col - 1;

    if ( this.graph[row][col] === 0 ) {
        let random = this.getRandom();
        row = random.row;
        col = random.col;
    }

    return { row,col };
}
Copy the code

DefaultSearchPath method

This method is the default search, from the top left to the bottom right of the maze, followed by the main event.

defaultSearchPath() {
    this.BFS([0.0], [this.row - 1.this.col - 1]);
}
Copy the code

5. BFS method (Breadth-first search algorithm)

BFS(from,to) {
    let flag = false,current,
        queue = new Queue();

    const move = [
        [0.1],
        [1.0],
        [0, -1], [...1.0]]. queue.push(new Node(from[0].from[1].null));

    const bfs = () = > {
        current = queue.shift();

        if ( current.y == to[0] && current.x == to[1]) {let parent = current;
            flag = true;

            while( parent ! =null ) {
                document.querySelector(`.grid div[data-key="${parent.y}-${parent.x}"] `).style.background = "yellow";
                parent = parent.parent;
            }

            return console.log("Matched to end point");
        }

        for ( let v = 0; v <= 3; v++ ) {
            let y = Math.min(current.y + move[v][0].this.row - 1),
                x = Math.min(current.x + move[v][1].this.col - 1);

            if (this.graph[y][x] === 1 && this.visited[y][x] == 0 ) {
                queue.push(new Node(x,y,current));
                this.visited[y][x] = 1; }}if ( queue.size() <= 0 && !flag ) return console.log("No end in sight.");

        bfs();
    }
    
    bfs();
}
Copy the code

First let’s look at declared variables.

Flag, which is used to determine if we have found the endpoint.

Current, which holds the node we are currently walking to.

Queue, which is a queue that stores the nodes we want to access.

Move, this constant is used for operations such as if we are going up, down, etc., to help us see if nearby siblings have been accessed, etc.

After we declare these variables/constants, we store the starting position in the queue to be accessed.

Then call the BFS method, which is used for recursive path finding.


In the BFS method, we first remove the first element in the queue and assign it to current.

current = queue.shift();
Copy the code

We then decide whether the current node is our destination.

If so, we change the flag variable to true to indicate that we have found the endpoint {*2}.

And declare a variable to hold the current node {*1}.

Then we go back to the last node of this node through the while loop, and mark the Dom element corresponding to this node with a yellow background color until we go back to the starting point {*3}.

After this sequence of operations, we jump out of the recursion by returning.

if ( current.y == to[0] && current.x == to[1]) {let parent = current;/ / {1}
    flag = true;/ / {2}

    while( parent ! =null ) {/ / {3}
        document.querySelector(`.grid div[data-key="${parent.y}-${parent.x}"] `).style.background = "yellow";
        parent = parent.parent;
    }

    return console.log("Matched to end point");
}
Copy the code

If we determine that the current node is not the destination, then we perform the following method.

for ( let v = 1; v < 4; v++ ) {/ / {1}
    let y = Math.min(current.y + move[v][0].this.row - 1),
        x = Math.min(current.x + move[v][1].this.col - 1);

    if (this.graph[y][x] === 1 && this.visited[y][x] == 0 ) {/ / {2}
        queue.push(new Node(x,y,current));
        this.visited[y][x] = 1; }}Copy the code

In this loop, we will visit the top, bottom, left, and right adjacent nodes of the current node {*1}.

And if a nearby node has not been accessed and there is no roadblock, the node is queued and its status is changed to visited {*2}.

if ( queue.size() <= 0 && !flag ) return console.log("No end in sight.");/ / {1}

bfs();/ / {2}
Copy the code

Finally, if the element in our queue is empty and flag is false, we have not found the end point. So we also jump out of the recursion {*1}.

Otherwise the recursion {*2} continues.

At this point, our maze finding is complete.

The complete index code is shown below.

class Maze {
    constructor() {
        this.row = 10;
        this.col = 10;
        this.graph = [];
        this.visited = [];
        this.init(this.col,this.row);
    }

    init(col,row) {
        this.row = row;
        this.col = col;

		this.visited = [];
        this.graph = [];

        for ( let r = 0; r < row; r++ ) {
            this.graph[r] = [];
            this.visited[r] = [];
            for ( let c = 0; c < col; c++ ) {
                this.graph[r][c] = 1;
                this.visited[r][c] = 0; }}this.buildDom();
    }

    buildDom() {
        const grid = document.querySelector(".grid");

        grid.innerHTML = "";
        grid.style.cssText = `grid-template-columns: repeat(The ${this.col},1fr); grid-template-rows: repeat(The ${this.row},1fr); `;

        for ( let row in this.graph ) {
            for ( let col in this.graph[row] ) {

                let div = document.createElement("div");

                div.setAttribute("data-key".`${row}-${col}`);

                div.onclick = () = > {
                    if ( row == 0 && col == 0 || row == this.row - 1 && col == this.col - 1 ) return;

                    if ( div.classList.contains("obstacle") ) {
                        div.classList.remove("obstacle");
                        this.graph[row][col] = 1;
                    } else {
                        div.classList.add("obstacle");
                        this.graph[row][col] = 0; } } grid.append(div); }}document.querySelector(`.grid div[data-key="0-0"]`).classList.add("start");
        document.querySelector(`.grid div[data-key="The ${this.row - 1}-The ${this.col - 1}"] `).classList.add("end");
    }

    randomObstacle() {
        let { row , col } = this.getRandom();
        document.querySelector(`.grid div[data-key="${row}-${col}"] `).click();
    }

    getRandom() {
        let row = Math.floor(Math.random() * this.row),
            col = Math.floor(Math.random() * this.col);

        if ( row === 0 ) row = 1;
        if ( col === 0 ) col = 1;
        if ( row === this.row ) row = this.row - 1;
        if ( col === this.col ) col = this.col - 1;

        if ( this.graph[row][col] === 0 ) {
            let random = this.getRandom();
            row = random.row;
            col = random.col;
        }

        return { row,col };
    }

    defaultSearchPath() {
        this.BFS([0.0], [this.row - 1.this.col - 1]);
    }

    / * * * *@param {array} from 
     * @param {array} to 
     */
    BFS(from,to) {
        let flag = false,current,
            queue = new Queue();

        const move = [
            [0.1],
            [1.0],
            [0, -1], [...1.0]]. queue.push(new Node(from[0].from[1].null));

        const bfs = () = > {
            current = queue.shift();

            if ( current.y == to[0] && current.x == to[1]) {let parent = current;
                flag = true;

                while( parent ! =null ) {
                    document.querySelector(`.grid div[data-key="${parent.y}-${parent.x}"] `).style.background = "yellow";
                    parent = parent.parent;
                }

                return true;
            }

            for ( let v = 0; v <= 3; v++ ) {
                let y = Math.min(current.y + move[v][0].this.row - 1),
                    x = Math.min(current.x + move[v][1].this.col - 1);

                if (this.graph[y][x] === 1 && this.visited[y][x] == 0 ) {
                    queue.push(new Node(x,y,current));
                    this.visited[y][x] = 1; }}if ( queue.size() <= 0 && !flag ) return console.log("No end in sight."); bfs(); } bfs(); }}class Node {
    constructor(x,y,parent) {
        this.x = x;
        this.y = y;
        this.parent = parent; }}class Queue {
    constructor() {
        this.arr = [];
    }

    push(element) {
        this.arr.push(element);
        return true;
    }

    shift() {
        return this.arr.shift();
    }

    size() {
        return this.arr.length; }}Copy the code