If you have played MMOARPG games, such as World of Warcraft, you will find that the walking of characters is very interesting. In order to simulate the real experience of walking, they will choose the shortest route to reach the destination, avoiding mountains or lakes, and bypassing boxes or woods until they reach the destination you selected.

This seemingly ordinary pathfinding requires a certain pathfinding algorithm to solve when implemented in a program. How to find the shortest route in the shortest time is the first problem that the pathfinding algorithm must consider.

In this article, we will explain step by step how pathfinding algorithms have evolved. You will see the problems encountered by an algorithm from simple to efficient, as well as the process of improvement. Read with questions in mind to understand faster.

This article mainly contains the following contents:

1. Picture

2. Width *** search,

3. Dijkstra algorithm,

4. Greedy algorithm,

****Search Algorithm,

6. B* search algorithm,

1. How do characters in the game find their way?

The way you see people walking:

How developers actually see it:

Or this:

For a map, developers need to convert it into data objects through certain schemes. The most common one is to cut the map into grids. Of course, the map division method does not necessarily have to be grids. Polygons can also be used. This depends on your game. Generally, maps of the same area use fewer vertices, and the pathfinding algorithm will be faster. The commonly used data structure in pathfinding is the graph. Let's take a look at it below.

2. Picture

Before we talk about the pathfinding algorithm, let's first understand a data structure - graph. Data structure is the basis for our algorithm calculation. A good data structure not only makes it easier for us to understand the algorithm, but also improves the efficiency of the algorithm. In a sense, the grid is also an evolution of the graph, but the graphics have changed. Understanding the concept of graph can help us better understand the pathfinding algorithm.

Basic definition of a graph:

The formal expression of a graph is G=(V,E), where V is a set of vertices. E and V are a binary relationship, which can be understood as an edge. For example, if there is an edge from vertex U to vertex V, then E can be represented by (u,v). Directed and undirected graphs are also distinguished by whether the edge has a direction. For ease of understanding, all data demonstrations in this article are based on grid maps. The following are several relationship arrangements, with A as the vertex and BCDE as sub-vertices. We can also regard each grid as a vertex.

3. Search Algorithm

Searching a graph means visiting its vertices in a particular order. For multi-graph algorithms, both breadth-first search and depth-first search are very important because they provide a systematic way to visit graph data structures. We will focus on breadth-first search.

Depth-First Search

The depth-first algorithm has little to do with the minimum path, so we will only briefly introduce it.

Depth-first search (DFS) is an algorithm used to traverse or search a tree or graph. It traverses the nodes of a tree along the depth of the tree, searching the branches of the tree as deeply as possible. When all the edges of node v have been explored, the search will backtrack 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 found.

Breadth-First Search

The breadth-first search algorithm (BFS for short), also known as width-first search, is a graph search algorithm that is very suitable for exploring the first model of the shortest path. We will continue to talk about it along this line of thought.

BFS is a blind search method that aims to systematically expand and check all nodes in the graph to find the result. In other words, it does not consider the possible address of the result and thoroughly searches the entire graph until the result is found. Its steps are as follows:

- First put the root node into the queue.

- Take the first node from the queue and check if it is the target.

- If the target is found, the search ends and the result is returned.

- Otherwise, add all its direct child nodes (neighboring nodes) that have not been checked yet to the queue.

- If the queue is empty, it means that the entire map has been checked - that is, there is no target to be searched in the map. End the search and return "target not found".

Grid:

Let's look at the code (js):

var frontier = new Array();

frontier.put(start);

var visited = new Array();

visited[start] = true;



while(frontier.length>0){

current = frontier.get();

//Find surrounding vertices for(next in graph.neighbors(current)){

        var notInVisited = visited.indexOf(next)==-1;

//Not visited if(notInVisited) {

            frontier.put(next);

            visited[next] = true;

}

}
}

From the above, we can see that the breadth search starts from the starting vertex, visits its child nodes (in the grid, visits the surrounding nodes), and then continuously loops this process until the target is found. This algorithm is more in line with conventional logic and enumerates all vertices. However, this method also has obvious disadvantages.

defect:

1. Low efficiency, time complexity is: T(n) = O(n^2)

2. There is no weight between each vertex, so it is impossible to define the priority and find the best route. For example, if you encounter a body of water, you need to walk around it, which cannot be involved in the width algorithm.

How to solve this problem? Let's look at Dijkstra's algorithm.

4. Dijkstra algorithm

The breadth-first search algorithm solves the path planning problem from the starting vertex to the target vertex, but it is not the best and most suitable one because its edges have no weights (such as distance) and the path cannot be estimated to compare the best solution. Why is the weight so important? In the real environment, the route between two vertices is not always a straight line. It is necessary to bypass obstacles to reach the destination, such as forests, lakes, and mountains, which all need to be bypassed instead of directly passing through.

For example, if I use the breadth-first algorithm, in the following situation, it will directly pass through the obstacle (green part), which is obviously not the result we want:

Solve pain points:

Finding the shortest and least weighted path from one vertex to another in the graph is a very important refinement process. We add a weight to each edge between vertices to track the cost of the chosen path. If the new path to a location is better than the previous best path, we will add it and plan the new route.

The Dijkstra algorithm is an improvement based on the breadth-first algorithm. It adds the shortest edge to the shortest path tree and uses the greedy algorithm to calculate and eventually produce the best result. The specific steps are as follows:

1. Each vertex contains an estimated cost (the distance from the starting point to the current vertex), and each edge has a weight v. Initially, only the estimated cost of the starting vertex is 0, and the estimated values ​​d of other vertices are all infinite.

2. Find the vertex A with the smallest cost value and put it into the path queue

3. Loop through the direct child vertices of A, get the current cost value of the child vertex and name it current_cost, and calculate the new path new_cost, new_cost = cost of parent node A + v (edge ​​weight from parent node to current node), if new_cost < current_cost, the cost of the current vertex = new_cost

4. Repeat 2 and 3 until no vertices can be accessed.

Let’s look at the following example:

Let's look at the code (js):

var frontier = new PriorityQueue();

frontier.put(start);

path = new Array();

//Each vertex path consumes cost_so_far = new Array();



path[start] = 0;

cost_so_far[start] = 0



while(frontier.length>0){

current = frontier.get();


if current == goal:

break

//Find surrounding nodes for(next in graph.neighbors(current)){

        var notInVisited = visited.indexOf(next)==-1;

        var new_cost = cost_so_far[current] + graph.cost(current, next);

//Not visited or the path is closer if(notInVisited || new_cost < cost_so_far[next]) {

            cost_so_far[next] = new_cost;

            priority = new_cost;

            frontier.put(next, priority);

            path[next] = current;

}

}

}

We can see that although the Dijkstra algorithm is smarter than the breadth-first search and can avoid long routes or inaccessible areas based on cost_so_far, it still has a tendency to search blindly. A common situation in maps is to find the path between the target and the starting point, which has a certain directionality. As can be seen from the above figure, the Dijkstra algorithm also diffuses from the starting point to the child nodes in all directions.

shortcoming:

1. The running time complexity is: T(n) = O(V^2), where V is the number of vertices. It is not very efficient.

2. Target search is not directional

How to solve the problem of not blindly searching the whole disk? Let's look at the Greedy Best First Search algorithm.

5. Greedy *** First Search

In Dijkstra's algorithm, I have found its ultimate flaw, the search is blind. Here, we only use greedy first-order search to solve this pain point. How to solve it? We just need to change our concept slightly. In Dijkstra's algorithm, the priority queue uses the estimated value of each vertex to the starting vertex to sort. In the greedy first-order search,

Solve pain points:

We use the distance from each vertex to the target vertex to sort. One uses the distance from the starting vertex to sort, and the other uses the distance from the target vertex to sort (sort by distance from the target)

Which one is faster? Let's look at the following picture (breadth-first on the left, greedy-first on the right):

From the above figure, we can clearly see that the algorithm on the right (greedy first-priority search) is faster than the one on the left. Although its path is not the longest and shortest, it is fast enough when there are the least obstacles. This is the advantage of the greedy algorithm, which searches based on the goal rather than a complete search.

Let's look at the algorithm (js):

frontier = new PriorityQueue();

frontier.put(start, 0)

came_from = new Array();

came_from[start] = 0;



while(frontier.length>0){

current = frontier.get()



if current == goal:

break



       for(next in graph.neighbors(current)){

           var notInVisited = visited.indexOf(next)==-1;

//Not visited if(notInVisited ) {

//The closer the distance to the goal, the higher the priority priority = heuristic(goal, next);

             frontier.put(next, priority);

             came_from[next] = current;

}

}

}



function heuristic(a, b){

//Distance from the target return abs(ax - bx) + abs(ay - by)

}

shortcoming:

1. The path is not the shortest path, it can only be a better path

How to search for as few vertices as possible while ensuring the shortest path? Let's look at the A* algorithm.

6. A* Algorithm

From the evolution of the above algorithms, we gradually found two solutions for the shortest path and the least number of search vertices, Dijkstra algorithm and greedy *** first search. So is it possible for us to take advantage of the two algorithms and make the path search algorithm fast and efficient?

The answer is yes. The A* algorithm does just that. It draws on the cost_so_far in the Dijkstra algorithm, sets weights for each edge length, and continuously calculates the distance from each vertex to the starting vertex to obtain the shortest route. It also draws on the advantage of the greedy first-order search algorithm of continuously moving toward the goal, and continuously calculates the distance from each vertex to the target vertex to guide the search queue to continuously approach the goal, thereby searching fewer vertices and maintaining efficient pathfinding.

Solve pain points:

The priority queue sorting method of the A* algorithm is based on the F value:

F = cost (distance from vertex to starting vertex) + heuristic (distance from vertex to target vertex)

Let's look at the algorithm (js):

var frontier = new PriorityQueue();

frontier.put(start);

path = new Array();

cost_so_far = new Array();

path[start] = 0;

cost_so_far[start] = 0

while(frontier.length>0){

current = frontier.get()

if current == goal:

break

       for(next in graph.neighbors(current)){

           var notInVisited = visited.indexOf(next)==-1;

           var new_cost = cost_so_far[current] + graph.cost(current, next);

//Not visited and the path is closer if(notInVisited || new_cost < cost_so_far[next]) {

              cost_so_far[next] = new_cost

//Queue priority = new_cost (distance from vertex to starting vertex) + heuristic (distance from vertex to target vertex)

            priority = new_cost + heuristic(goal, next)

            frontier.put(next, priority)

            path[next] = current

}

}

}

function heuristic(a, b){

//Distance from the target return abs(ax - bx) + abs(ay - by)

}

The following are the pathfinding radar diagrams of the Dijkstra algorithm, the greedy algorithm, and the A* algorithm. The grids with numbers have been searched. You can compare the three efficiencies:

7. B* Algorithm

The B* algorithm is a more efficient algorithm than the A* algorithm. It is suitable for automatic path finding of monsters in games. Its efficiency far exceeds that of the A* algorithm. After testing, the efficiency is dozens or hundreds of times that of the ordinary A* algorithm. I don't want to introduce the B* algorithm. Go to Google and search for it yourself.

Through the continuous evolution of the above algorithms, we can see the limitations of each algorithm, as well as the solutions that emerge in the extended new algorithms. I hope it will facilitate your understanding.