Hello, my name is 💎 three diamonds from Tech Galaxy.

Path finding algorithm practice

What are the benefits of learning pathfinding algorithms?

Pathfinding is a breadth-first search algorithm
All search algorithms have very similar ideas
So we can go through the depth-first search class as well as the breadth-first algorithm
Search is a particularly important algorithm, the general type is also a particularly good kind of algorithm
So this is going to help you get a little bit better at the algorithm

Visualize to understand the algorithm

There’s a UI part to the algorithm as well
And there are some JavaScript specific parts
This section will improve your familiarity with the JavaScript language
And gain a deeper understanding of how the language works
And most importantly, I’ll teach you something about visualization through the nature of asynchronous programming
By visualizing the steps of the algorithm, we can see the operation of the algorithm very intuitively

Definition of pathfinding problem

Pathfinding is the problem of assigning a starting point and an end point on a map and finding a path from the starting point to the end point in all directions.

In our exercise we will make a 100 x 100 grid map and plot our path from start to finish.

At the beginning, we will use a simple horizontal and vertical direction to find our end point, because the oblique path will have a certain difference, especially when the map is relatively empty. We will gradually add various features until we have solved all of the search.

Map editor

For pathfinding problems of this magnitude, the first thing we need to do is make a map editor. Its functions are as follows:

You can draw a map by clicking the left mouse button, or by clicking and dragging
You can clear the map by right clicking, or clicking and dragging
You can save the map data, refresh the map, you can also draw out

First we need to draw the base of our map, before we draw we need to add CSS to our HTML.

Our chassis is a 100 x 100 grid, so we need to give each grid a style. Here we just need to use Flex for layout. Suppose we make each cell 6px wide and high, and then arrange 100 in each row. So our HTML layout code looks like this:

<div id="container">
  <div class="cell"></div>
  <div class="cell"></div>
  <div class="cell"></div>
  <div class="cell"></div>.</div>
Copy the code

containerThat’s the outsource box
cellIt’s the inside cell

The CSS layout looks like this:

body {
  background: #0f0e18;
  /* make the whole content play */
  display: flex;
  flex-direction: column;
  align-items: center;
}
.cell {
  display: inline-block;
  line-height: 7px;
  width: 6px;
  height: 6px;
  background-color: #2d2f42;
  border-bottom: solid 1px #0f0e18;
  border-right: solid 1px #0f0e18;
  vertical-align: bottom;
  transition: all 400ms ease;
}
#container {
  padding-bottom: 1rem;
  display: flex;
  flex-wrap: wrap;
  width: 701px;
}

/* Add button style for better look, optional! * /
button {
  background: transparent;
  /* border: none; * /
  color: var(--blue-color);
  border: 1px solid aqua;
  padding: 0.5 rem 1rem;
  cursor: pointer;
  transition: all 400ms ease;
}
button:hover {
  background: var(--blue-color);
  color: # 333;
}
Copy the code

This is the CSS for the layout, but the entire chassis needs to be built with data so that we can use it later for our pathfinding problems. So here we need to add JavaScript to do the whole rendering process.

For the HTML section, add a div with an ID of container:

<div id="container"></div>
Copy the code

Implementation idea:

Create an array of 10,000 data and fill them all0
Loop through all the chassis cells from left to right and top to bottom
Creating while traversingdivElements,class 为 cell
Traversal encountered a value of1Gives the background color#7ceefc
addmousemove(mouse movement) monitor
There are two cases of mouse movement monitoring: if the left mouse button is clicked, the background color will be added; if the right mouse button is clicked, the current background color will be clear
Finally put to useappendChild 把cellTo join thecontainerAmong the
Use localStorage to record our chassis data

Code implementation:

// Define 100 x 100 chassis data
// Use localStorage, if not, create a new one
let map = localStorage['map']?JSON.parse(localStorage['map') :Array(10000).fill(0);

// Get the container element object
let container = document.getElementById('container');

// Iterate over all squares
for (let y = 0; y < 100; y++) {
  for (let x = 0; x < 100; x++) {
    // Create map squares
    let cell = document.createElement('div');
    cell.classList.add('cell');
    // If the state of the grid is 1, give the background color
    if (map[100 * y + x] == 1) cell.style.backgroundColor = 'aqua';
    // Add mouse movement listening events
    cell.addEventListener('mousemove'.() = > {
      // Execute only under mouse click state
      if (mousedown) {
        if (clear) {
           // 1. Right click to see the state of the grid
          cell.style.backgroundColor = ' ';
          map[100 * y + x] = 0;
        } else {
          // 2. Left click to draw the grid state
          cell.style.backgroundColor = 'aqua';
          map[100 * y + x] = 1; }}});// Add to the containercontainer.appendChild(cell); }}let mousedown = false;
let clear = false;

// Set mouse click status to true when the mouse button is clicked
document.addEventListener('mousedown'.e= > {
  mousedown = true;
  clear = e.which === 3;
});
// After leaving the mouse button click, change the state to false
document.addEventListener('mouseup'.() = > (mousedown = false));
// Since we need to use the right button, we need to disable the right button by default
document.addEventListener('contextmenu'.e= > e.preventDefault());
Copy the code

Finally, we added a save button to save our edited map when we refresh the page:

<div id="container"></div>
<! Save map data to localStorage -->
 <button onclick="localStorage['map'] = JSON.stringify(map)">save</button>
Copy the code

The result looks like this:

View effect | view code | like the classmate 🌟star thank you!

Implement breadth-first search

Now let’s dive into the pathfinding problem, which we defined above as “finding a starting point and an ending point, and then we need to find a path from the starting point to the ending point without crossing our borders or walls.”

When we look at the past 100 x 100 grid, it does seem that this problem is not particularly easy to solve. In the process of calculating this path, there is a lot of data that we need to calculate. But we can make it a little bit easier.

We go to the starting point, and we start thinking from the starting point. Ask ourselves a question: “Where can we go from here? “

We still have a lot of problems here. There are a lot of places to go. Because the starting position may not have any obstacles, nor any edge. Does that mean you can go anywhere?

Ok, so let’s narrow it down a little bit. “Let’s start at the beginning. Where do we go first?” . All right, the key to this question is step one.

Assuming we ignore the diagonal case (which we’ll worry about later, because the end point here is simplification), we can go up, down, left, and right. If we mark these positions counterclockwise we will get the following path mark.

That’s it. We’ve completed the first step of pathfinding. Let’s see where we can go next. If all of the ones labeled 1, 2, 3, and 4 are available, where do we now go on cell 1, following the idea we just had?

That’s right. If we go counterclockwise, we have 5,6,7 cells. So we can go 2,3,4 all the way. Finally we find the following path:

Finally, let’s take a look at the animation below to see what the process looks like.

So we’re just going to keep going out and looking for where we can get to, until we find our destination. This will help us find the route from start to finish. Of course, when we’re looking, if we come across a boundary or an obstacle, we jump over it, because it’s impassable.

The problem with this idea is that it’s easy to think recursively, but it’s not a good idea to use recursively. If we use recursion, we must have found the one cell, and then we would have started to expand around it. Then 5,6,7 will be executed before 2, 3, and 4 (since it’s recursion, we’ll expand it layer by layer).

So if we were to default to recursion, the pathfinding would become depth-first, but depth-first is bad for pathfinding problems, and breadth-first is good.

Why is pathfinding breadth-first better than depth-first?

Let’s take an example to understand it better.

Suppose we are now in a maze with thousands of ends in front of us, and we have two ways to find our way out

Solution a:

Alone, choose left or right and follow each branch there until you reach a dead end, then turn back to the other branch. We just keep going and switching branches until we find the exit branch. If you’re lucky, you’ll find an exit pretty quickly. If you’re unlucky, you’ll have to basically walk through all the branches to find an exit.

Scheme 2:

We are all alone, but we have “two halves”, and when we come to a fork we can try every fork. For example, A, B and C branches, we can take A step for route A, then take A step for route B, and finally take A step for route C. Here, we have A uniform step, just like in our dynamic diagram above, we keep expanding to all branches to find A route. So we can go one step at a time at each of the N forks until we find the exit. This approach is equivalent to finding each fork in turn, which is obviously better than the first search. (I don’t know about you, but having the ability to be in two places already makes me feel like I’ve won pathfinding!)

If you go back to the algorithm, plan 1 is actually “depth-first search”, and Plan 2 is “breadth-first search”! It’s clear that breadth-first search is more efficient in pathfinding!

Implement breadth-first search code

Those of you who have done maze-running will remember that when we do maze-running, we mark our paths so that we know where we have gone, and then we can use these records to find the path to the end. Our pathfinding problem is no exception. According to our analysis above, we start from the beginning and expand out to find a grid to go to. Every time we find a grid to go to, we need to record.

In algorithms we add data to a “set” that is the “soul” of all search algorithms. All the difference in search algorithms is in this queue.

And a queue is a data structure, we call it a queue, and it has the property of first in, first out, one in, one out. Actual effect and figure below:

Are there any data structures like queues in JavaScript? There are! Arrays in JavaScript are natural queues, and arrays in JavaScript are natural stacks.

JavaScript arrays have two common groups of handlers, shif and unshift, and push and POP. But if we mix and match them, our array becomes a different data structure.

push 与 shiftorpop 与 unshiftTogether, then the array is oneQueue (Queue)
push 和 popIn combination so an array is oneThe Stack (Stack)(Of course, shif and unshif are also possible, but we generally don’t use this combination for the stack because we consider JavaScript array implementations, which can be slow to use.)

With all of this in mind, we can start to think about how to write code:

We need to declare a queue, so we need to declare a queuequeueAnd put our starting point in the queue by default. (In JavaScript we use arrays.)
Write a method that “joins the queue” with the condition that if you hit an edge or obstacle, you jump out of the method, which is a non-walkable grid so you won’t join our queue.
If this is not the case, we can first put the available grid in ourmap(an array declared when implementing our map data) records a state that we can use here2Theta represents this cell that we’ve already gone through, and here we add a tag.
Loop through the available cells in our queue, and the main goal here is to find all the available cells recordedon.Under the.On the left.right“, and queues all the available cells, and then enters the next loop to find out where the newly queued cells can go, and then requeues the cells found later, and so on.
The loop has a cutoff condition, which is that if we find the end cell as we loop through each cell, we can just go backtrue“Means we have found the end.

Good idea again, let’s take a look at the code implementation:

// The last part of the code is ignored here...
// Just modify this part of the code after the previous part

// After leaving the mouse button click, change the state to false
document.addEventListener('mouseup'.() = > (mousedown = false));
// Since we need to use the right button, we need to disable the right button by default
document.addEventListener('contextmenu'.e= > e.preventDefault());

/** * find the way *@param {Array} Map map data *@param {Array} Start Start example: [0, 0] *@param {Array} End End for example, [50, 50] *@return Boolean* /
function path(map, start, end) {
  var queue = [start];
  
  function insert(x, y) {
    // Stop at the edge of the chassis
    if (x < 0 || x >= 100 || y < 0 || y >= 100) return;
    // Stop when you encounter the wall of the map
    if (map[y * 100 + x]) return;
    // The state of the cell that marks possible paths is 2
    map[y * 100 + x] = 2;
    // Push the available path into the queue
    queue.push([x, y]);
  }

  // Loop a 4-sided cell
  while (queue.length) {
    let [x, y] = queue.shift();
    console.log(x, y);

    // When you reach the destination, you can return
    if (x === end[0] && y === end[1]) return true;

    // Push up, down, left, and right into the queue
    insert(x - 1, y);
    insert(x, y - 1);
    insert(x + 1, y);
    insert(x, y + 1);
  }

  return false;
}
Copy the code

In order to debug and see if our code is correct, let’s add a button and let it execute our path finding method.

<div id="container"></div>
<! Save map data to localStorage -->
<div>
  <button onclick="localStorage['map'] = JSON.stringify(map)">save</button>
  <button onclick="Path (map, (0, 0), (50, 50))">find</button>
</div>
Copy the code

Here our button will perform a pathfinding method that starts at x = 0, y = 0, and ends at x = 50, y = 50. After clicking this button, we can see the x and Y that we walked through during the pathfinding process in the console of the browser’s debugging tool. And if our code is right, eventually we’re going to see it stop running at 50, 50.

View effect | view code | like the classmate 🌟star thank you!

Add Async and Await to facilitate debugging and display

In the last code, you actually implemented the main part of the pathfinding algorithm. But there are some problems:

The algorithm, though, eventually returns our destination, and returnstrueIt seems to have met our expectations. But we can’t be sure it’s right.So we want to have a visual view of how the pathfinding algorithm works.
We’re finding a path, the final path that we haven’t figured out yet.

We’re going to work through these in the next few steps.

We have talked about using async and await to insert asynchronous operations in the middle of functions.

For this part of the code, we have made some code modifications:

thepath()Function insteadasyncfunction
theinsert()Function insteadasyncfunction
becauseinsert()We programmed the asynchronous function, so wewhile()Insert calls in the loop need to be added firstawait
We also need to add a wait functionsleep(), it must return onepromise
After we queue, change the current cell state to2Previously, we changed the background color of the cells in the DOM element so that we could see the pathfinding process
Because we need to see this process, we need to give a wait time of 1 second each time we queue, which is the useasync 和 awaitThe benefits of. Before we add this background color, we can add oneawait sleep(1), so there is a 1 second delay before queuing and changing the color of the grid background.

Without further ado, let’s see what happens to the code:

// The last part of the code is ignored here...
// Just modify this part of the code after the previous part

// After leaving the mouse button click, change the state to false
document.addEventListener('mouseup'.() = > (mousedown = false));
// Since we need to use the right button, we need to disable the right button by default
document.addEventListener('contextmenu'.e= > e.preventDefault());

/** ** wait function *@param {Integer} T time (s) *@return Promise* /
function sleep(t) {
  return new Promise(function (resolve) {
    setTimeout(resolve, t);
  });
}

/** * path finding (asynchronous) *@param {Array} Map map data *@param {Array} Start Start example: [0, 0] *@param {Array} End End for example, [50, 50] *@return Boolean* /
async function path(map, start, end) {
  var queue = [start];

  /** * Join queue method (asynchronous) *@param {Integer} x
       * @param {Integer} y* /
  async function insert(x, y) {
    // Stop at the edge of the chassis
    if (x < 0 || x >= 100 || y < 0 || y >= 100) return;
    // Stop when you encounter the wall of the map
    if (map[y * 100 + x]) return;
    // Add a 30-millisecond pause so we can see the changes on the UI
    await sleep(1);
    // Add a background color to the grid of the searched path
    container.children[y * 100 + x].style.backgroundColor = 'DARKSLATEBLUE';
    // The state of the cell that marks possible paths is 2
    map[y * 100 + x] = 2;
    // Push the available path into the queue
    queue.push([x, y]);
  }

  // Loop a 4-sided cell
  while (queue.length) {
    let [x, y] = queue.shift();
    // console.log(x, y);

    // When you reach the destination, you can return
    if (x === end[0] && y === end[1]) return true;

    // Push up, down, left, and right into the queue
    await insert(x - 1, y);
    await insert(x, y - 1);
    await insert(x + 1, y);
    await insert(x, y + 1);
  }

  return false;
}
Copy the code

Finally, the result of our implementation:

View effect | view code | like the classmate 🌟star thank you!

Handling path issues

In the last step we used an animation to make it very clear to understand the entire pathfinding algorithm process. However, we have not solved the second problem mentioned in the previous step. So what we’re trying to do here is figure out what the final path is, and how do we get a path that goes from the beginning to the end, once we finally get through the pathfinding algorithm?

The path problem is also very simple. Let’s look at the pathfinding idea we talked about earlier:

From the diagram above, we already remember that as we visited each cell, we expanded out to find the available cells. In this process, we know that each extended cell is self-extended by the previous one. In other words, each cell knows that we are extending from that cell.

Let’s say the 5, 6, and 7 cells are all extended from the 1 cell. Since we know every source given from the previous step, can we put a source on every grid given to the self record? So in the code, can we record an X and y axis given to us when we join the team?

So we have an idea, how do we find the final path from this record?

Let’s say we end at 8, and when we get to 8 we’re expanding from where we started, but we can actually shrink back to where we started by recording the precursor of each cell?

That is to say, we start at 8, 8 goes from 2, and 2 expands from the starting point, and we end up at the starting point. If we keep track of the cells visited during contraction, we end up with the entire path from the start to the end! Isn’t that amazing? !

In fact, it can also be understood as a “backtrack” effect!

Don’t freeze the chicken yet. Hold on! Let’s look at how the code works:

Basically our code hasn’t changed much
The first is thatwhilein-cycleinsert()Call with a pass parameter for the previous coordinate added
Here we also incidentally add horizontal walkable cells to the queue
Here because we need to record the precursor coordinates of all the cells, we need to declare onetableIs used to store this data
Before we queue, we store the value of the current queued cell as the coordinate of the previous cell (this is to find the entire path for us to shrink later).
Finally, inwhileIn the loop, when we get to x and y at the end, we add a segmentwhilecycle
thiswhileJust go back until we find the starting point. As we go back, change the background of each cell we pass to another background color, so we can draw a path on our map!

Good thinking clear, let’s go to a wave of code!

// The last part of the code is ignored here...
// Just modify this part of the code after the previous part

/** * path finding (asynchronous) *@param {Array} Map map data *@param {Array} Start Start example: [0, 0] *@param {Array} End End for example, [50, 50] *@return Boolean* /
function sleep(t) {
  return new Promise(function (resolve) {
    setTimeout(resolve, t);
  });
}

/** * Join queue method (asynchronous) *@param {Integer} x
     * @param {Integer} y* /
async function findPath(map, start, end) {
  // Create a record table
  let table = Object.create(map);
  let queue = [start];

  /** * Join queue method (asynchronous) *@param {Integer} x
       * @param {Integer} y
       * @param {Array} The coordinates of the previous grid: [x,y] */
  async function insert(x, y, pre) {
    // Stop at the edge of the chassis
    if (x < 0 || x >= 100 || y < 0 || y >= 100) return;
    // Stop when you encounter the wall of the map
    if (table[y * 100 + x]) return;
    // Add a 30-millisecond pause so we can see the changes on the UI
    // await sleep(1);
    // Add a background color to the grid of the searched path
    container.children[y * 100 + x].style.backgroundColor = 'DARKSLATEBLUE';
    // Mark the value of the cell passed by, marking the x and y positions of the previous cell
    table[y * 100 + x] = pre;
    // Push the available path into the queue
    queue.push([x, y]);
  }

  // Loop a 4-sided cell
  while (queue.length) {
    let [x, y] = queue.shift();
    // console.log(x, y);

    // When you reach the destination, you can return
    if (x === end[0] && y === end[1]) {
      let path = [];

      // Go back until you come to the beginning
      // Then I can draw the best path
      while(x ! = start[0] || y ! = start[1]) {
        path.push(map[y * 100 + x]);
        [x, y] = table[y * 100 + x];
        await sleep(1);
        container.children[y * 100 + x].style.backgroundColor = 'fuchsia';
      }

      return path;
    }

    // Push up, down, left, and right into the queue
    await insert(x - 1, y, [x, y]);
    await insert(x, y - 1, [x, y]);
    await insert(x + 1, y, [x, y]);
    await insert(x, y + 1, [x, y]);

    // Push the four hypotenuses into the queue
    await insert(x - 1, y - 1, [x, y]);
    await insert(x + 1, y - 1, [x, y]);
    await insert(x - 1, y + 1, [x, y]);
    await insert(x + 1, y + 1, [x, y]);
  }

  return null;
}
Copy the code

Note: We changed the name of the path function to findPath because we used path as the variable in the while loop to find the path. Another thing to note here is that the function calls inside the find button need to be changed as well.

<! Save map data to localStorage -->
<div>
  <button onclick="localStorage['map'] = JSON.stringify(map)">save</button>
  <button onclick="FindPath (map, (0, 0), (50, 50))">find</button>
</div>
Copy the code

The final result is as follows:

View effect | view code | like the classmate 🌟star thank you!

Heuristic Pathfinding (A*)

At this point we have completed the entire breadth-first pathfinding algorithm. But is broad-based pathfinding the best solution? Not really!

Through the efforts of mathematical scientists, they have proved one thing. There is a way to speed up pathfinding, by not having to go through each one in a very silly way.

This is called heuristic pathfinding.

Heuristic pathfinding uses a function to determine the priority of the extension of these points. As long as we judge the priority, we can purposefully do priority finding in the direction of the experimenter grid.

“But is the path found the best path? It’s so magical. “To be honest, this idea of us ordinary people doesn’t come in handy. But one thing mathematicians have shown is that if we use heuristic functions to estimate values, and those values can be less than the length of the path from the current point to the end point, then we can always find the optimal path.

This heuristic pathfinding that finds the optimal path is called “A*” in computers. The A in here represents A heuristic pathfinding that does not necessarily find the optimal path. So A* is A special case of A pathfinding, an algorithm that can find the best path.

To implement this heuristic, we don’t need to change much of the code in our findPath() function. What we’re going to change is the data structure that we store, which is our queue.

We’re going to turn the fifo queue into a Prioritized queue.

So we need to build a Sorted class that does several things:

This class can store our previousqueueThe data in the queue
Can support passing in sorting functions (i.e., and usarray sortFunction like function, you can pass in a collation function, also calledcompareFunction)
Give us the minimum value in the data when we get the value from this class
We don’t need to sort when we insert data, we just save it
Each time the data is removed, the output data can be deleted in the class data
So we can keep getting data in there until there’s no more data
Finally add a length that can get the current data (this is needed in our pathfinding algorithm)

Here we implement the Sorted class with a very unwieldy array, but there are many other ways to implement this sort on a computer. For example, winner tree, heap, sorted binary tree and many other different ideas to achieve ordered data structure.

Without further ado, let’s see how to implement this data structure:

/** Sort data class */
class Sorted {
  constructor(data, compare) {
    this.data = data.slice();
    this.compare = compare || ((a, b) = > a - b);
  }
  take() {
    // It is not appropriate to return null since null can also participate in the comparison
    if (!this.data.length) return;
    // Record the minimum value
    // The first position is the minimum by default
    let min = this.data[0];
    // Record the minimum position
    let minIndex = 0;

    // Start comparing all the values in the array, find a smaller value, record as min
    // Record both the minimum value and the position of the minimum value
    for (let i = 1; i < this.data.length; i++) {
      if (this.compare(this.data[i], min) < 0) {
        min = this.data[i]; minIndex = i; }}// Now we want to remove the minimum value, so we need to remove it from our current data
    // We don't consider splice here, because splice removal involves moving the elements of the array forward
    // Then splice will have O(N) time complexity
    // Here we use a trick to move the last digit of the array to the position where the smallest value is currently found
    // Use pop to remove the last bit of data
    this.data[minIndex] = this.data[this.data.length - 1];
    this.data.pop();
    // Print the minimum value
    return min;
  }
  give(value) {
    this.data.push(value);
  }
  get length() {
    return this.data.length; }}Copy the code

Now that we have the Sorted data structure, we can use it to solve our pathfinding problem, allowing us to find the best path.

To add the logic of the optimal path, we need to change the following points:

So let’s rewrite our data storequeue, use usSortedSort data structure of
Write adistance()Function to calculate the straight-line distance between any cell and the terminal cell
Change all incoming and outgoing calls to useSortedThe inside of the classtakeThe values andgiveInsert valued function
Pretty much nothing else has changed, you know

Let’s see how the code is implemented:

// The last part of the code is ignored here...
// Just modify this part of the code after the previous part

/** * path finding (asynchronous) *@param {Array} Map map data *@param {Array} Start Start example: [0, 0] *@param {Array} End End for example, [50, 50] *@return Boolean* /
async function findPath(map, start, end) {
  // Create a record table
  let table = Object.create(map);
  let queue = new Sorted([start], (a, b) = > distance(a) - distance(b));

  async function insert(x, y, pre) {
    // Stop at the edge of the chassis
    if (x < 0 || x >= 100 || y < 0 || y >= 100) return;
    // Stop when you encounter the wall of the map
    if (table[y * 100 + x]) return;
    // Add a 30-millisecond pause so we can see the changes on the UI
    await sleep(1);
    // Add a background color to the grid of the searched path
    container.children[y * 100 + x].style.backgroundColor = 'DARKSLATEBLUE';
    // Mark the value of the cell passed by, marking the x and y positions of the previous cell
    table[y * 100 + x] = pre;
    // Push the available path into the queue
    queue.give([x, y]);
  }

  /** * gets the distance between cells *@param {Array} Point Indicates the coordinates of the current grid: [x,y] */
  function distance(point) {
    // Calculate the distance using the triangle x^2 + y^2 = z^2
    return (point[0] - end[0]) * *2 + (point[1] - end[1]) * *2;
  }

  // Loop a 4-sided cell
  while (queue.length) {
    let [x, y] = queue.take();
    // console.log(x, y);

    // When you reach the destination, you can return
    if (x === end[0] && y === end[1]) {
      let path = [];

      // Go back until you come to the beginning
      // Then I can draw the best path
      while(x ! = start[0] || y ! = start[1]) {
        path.push(map[y * 100 + x]);
        [x, y] = table[y * 100 + x];
        container.children[y * 100 + x].style.backgroundColor = 'fuchsia';
      }

      return path;
    }

    // Push up, down, left, and right into the queue
    await insert(x - 1, y, [x, y]);
    await insert(x, y - 1, [x, y]);
    await insert(x + 1, y, [x, y]);
    await insert(x, y + 1, [x, y]);

    // Push the four hypotenuses into the queue
    await insert(x - 1, y - 1, [x, y]);
    await insert(x + 1, y - 1, [x, y]);
    await insert(x - 1, y + 1, [x, y]);
    await insert(x + 1, y + 1, [x, y]);
  }

  return null;
}
Copy the code

The final result is as follows:

View effect | view code | like the classmate 🌟star thank you!

I’m Three diamonds from Tech Galaxy: “Learning is to grow, growing is not to regress. Persistence can succeed, failure is just because there is no persistence. Come on, students! See you next time!”

If you enjoyed these articles, please follow the weibo public account “Technical Galaxy”

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Implementation of pathfinding algorithm in JavaScript – programming training

Path finding algorithm practice

Definition of pathfinding problem

Map editor

Implementation idea:

Code implementation:

Implement breadth-first search

Why is pathfinding breadth-first better than depth-first?

Implement breadth-first search code

Add Async and Await to facilitate debugging and display

Handling path issues

Heuristic Pathfinding (A*)

Implementation of pathfinding algorithm in JavaScript – programming training

Path finding algorithm practice

Definition of pathfinding problem

Map editor

Implementation idea:

Code implementation:

Implement breadth-first search

Why is pathfinding breadth-first better than depth-first?

Implement breadth-first search code

Add Async and Await to facilitate debugging and display

Handling path issues

Heuristic Pathfinding (A*)

Related Posts

Vue popup component specification writing

Chrome80’s default SameSite causes iframe to fail to obtain cookies

Compare Vue2 and Vue3 in principle and performance