One, foreword

Before formally introducing this article on pathfinding algorithms, I want to briefly talk about two classic algorithms: depth-first and breadth-first.

Depth-first search

Depth-first-search (DFS) is an algorithm for traversing a Search tree or graph. The algorithm searches the branches of the tree as deep as possible. We generally use heap data structures to assist the IMPLEMENTATION of DFS algorithms.

Let’s take a look at the wiki definition:

The algorithm searches the branches of the tree as deep as possible. When all sides of node V have been explored, the search goes back to the starting node of the edge where node V was found. This process continues until all nodes reachable from the source node have been discovered. If there are undiscovered nodes, one of them is selected as the source node and the process is repeated until all nodes have been accessed.

In a nutshell,

  1. Access to the verticesv
  2. In turn, fromvThe graph is traversed depth-first. Until the diagram is neutralvAll vertices with paths connected are accessed
  3. If there are still vertices in the graph that have not been accessed, the depth-first traversal is performed again starting from an unvisited vertex until all vertices in the graph have been accessed

As follows:

1, 2, 3, 4, 5, 6, 7, 8Copy the code

According to the search rules, we first visit vertex 1, then look for its neighbor 2, then look for neighbor 4 of 2, and so on. When 8 is found, there is no adjacency point. In this case, we return to the previous node 4 to find whether there are still unvisited nodes. If there are no unvisited nodes, we search 2 to find whether there are unvisited nodes. Five are accessed. The final search path is 1 – > 2 – > 4 – > 8 – > 5 – > 3 – > 6 – > 7.

As shown below:

Note: the arrows in the figure above are somewhat misleading, so change them later (you can compare them with the numerical order provided above).

Third, breadth first search

Breadth-First-Search (BFS) is a graphic Search algorithm. According to its characteristics, we generally use queues to assist the implementation of BFS algorithm.

Its main implementation ideas are as follows:

  1. Put the root node into the queue
  2. Extract the first node from the queue and verify that it is the target. Search results are returned if the target is found. Otherwise, all of its immediate children that have not yet been verified are added to the queue
  3. Returns if the queue is empty
  4. Repeat Step 2

In fact, it is known as horizontal first search. Its search path is as follows:

BFS has a lot of applications, and in this article, Ms. Winter uses it to search and calculate how many JavaScript native objects there are in the browser.

4. Pathfinding algorithm

After reading the introduction of the first two algorithms, I believe you have a general understanding of the depth and breadth first search algorithm. For our pathfinding problem, we need to look “nearby” to see if there is a point that meets the requirements, so we choose breadth-first search.

The specific search ideas are as follows:

  1. Specify a starting pointv, put into queue
  2. Extract the first node from the queue and verify that it is the target node. If so, the search results are returned. Otherwise, check whether its “up”, “down”, “left”, and “right” nodes are target points.
  3. Returns if the queue is empty
  4. Repeat Step 2

According to the above search method, we can query the specified target node. The following is the path graph:

As you can see from the path above, this breadth-first search is a very “dumb” search method. It doesn’t plan its route according to a strategy, so it spends a lot of time searching areas that aren’t necessary. It would be nice if our search algorithm algorithm could directly calculate the path based on the distance between the start point and the end point.

(1) Heuristic (A*) pathfinding

We modify it in the breadth-first algorithm: we let 2. Fetch the first node from the queue, fetching the smallest value in the queue, every time we fetch the value. This ensures that our query path can be “strategically” pathfinding.

If you haven’t figured it out yet, here’s an example:

We now want to go from point A to point B in the diagram below. The steps to find the way are:

  1. First, put node A into the queue
  2. Take out node A, a is not the target node, then put the “child nodes”, “up”, “down”, “left” and “right” of A into the queue respectively
  3. Extract a node that is closest to B. So it’s node “1” in the graph.
  4. Repeat the above steps

The final path is shown in the figure below (green is the child node judged by it and purple is the path) :

Instead of breadth-first search, heuristic pathfinding is a refinement of the method of obtaining values: each point is the shortest distance between a given two points. Of course, the method presented in the code is only one idea, we can also use different methods to do the shortest path judgment, such as the least binary heap.

Well, that’s the end of the core of this article. You are welcome to discuss with me

MacOS Catalina 10.15.7 Browser Version: Chrome 87.0.4280.88 (official Version) (x86_64)