Abstract ： In the game , Just a little mouse click , The system immediately looks for the closest route to the character . What is the mystery of the behavioral logic behind this ？

author ：_JohnserfSeed_

** But , What is the mystery of the behavioral logic behind this ？ How would you write this pathfinding algorithm ？**

Generally, we encounter this kind of path search problem , The first thing you can think of is ** Breadth first search algorithm (Breadth First Search)**、 also ** Depth first (Depth First Search)**、** Freud （Floyd）**、** dijkstra (Dij)** And so on, these very famous path search algorithms , But in most cases, the shortcomings of these algorithms are exposed ：** Time complexity is high **.

therefore , In most environments, we use a name called **A* (A star)** Search algorithm

When it comes to the shortest path , We have to mention breadth first traversal （**BFS**）, It's a universal algorithm , It's not just for On the question of finding a way or searching .**windows** System Tools ： Drawing board The paint barrel in is a typical example .

** Here is a simple example of path search **

Suppose we search for the shortest path on a grid

We can only move up and down , Do not cross obstacles . The purpose of the algorithm is to let you find a shortest path from the starting point to the site

Suppose you can go up and down, left and right every time 4 Move in one direction

After each round of traversal, the algorithm marks the blocks explored in this round, which is called boundary （Frontier）, These are the green squares .

Then the algorithm will start from these boundary blocks in a circular way , Explore them up and down, left and right , Until the algorithm traverses to the end of the square will not stop . The shortest path is the path explored by the algorithm before . In order to get the whole path explored by the algorithm , We can record the direction of the path in the process of searching .

For example, the white arrow on the square represents the position of the previous block

Every time we explore the path , All we have to do is record this extra information

it is to be noted that , All the paths we've explored need to be marked gray , On behalf of them “ Has been visited “, In this way, the sub algorithm will not repeatedly explore the path that has been taken .

Breadth first algorithm can obviously help us find the shortest path , But it's a little silly , Because its search for the path is not directional , It will probe in all directions .

The worst case scenario is to traverse the entire map , So it's not smart , We need a more efficient algorithm .

That's what we're going to introduce this time **A * （A star）** search algorithm

## A* Search Algorithm

”A* search algorithm “ It's also called “ Heuristic search ”

What's different from breadth first is , We don't explore all the boundary blocks in each cycle （**Frontier**）, And will choose the current “ cost （**cost**）” The lowest box to explore .

there “ cost ” That's interesting , It's also A* Where algorithms are smart .

We can divide the cost here into two parts , Part of it is “ The cost of the current journey （ It can be expressed as **f-cost**）”： For example, how many squares do you walk through from the starting point ,**f-cost** Just a few .

The other part is “ Estimate the cost （ It can be expressed as **g-cost**）”： Used to indicate how many steps it takes to move from the current block to the final square , Estimate, estimate, so it's not an exact number , It doesn't mean that starting from the current position will definitely go that far , However, we will use this estimation to guide the algorithm to search for more promising paths first .

Most commonly used “ Estimate the cost ” There is Euler distance （**Euler Distance**）“, It's the linear distance between two points **(x1 - x2)^2 + (y1 - y2)^2**

And, of course, there's something easier to calculate “ Manhattan distance （**Manhattan Distance**）”, It's the sum of the vertical and horizontal distances between the two points **|x1 - x2|+|y1 - y 2|**

Manhattan distance does not need to square , Fast , So in A* In the algorithm, we can use it as **g-cost.**

Next , All we have to do is add the two costs mentioned before to get the total cost ：**f-cost + g-cost.**

And then in the explore box , Choose the block with the lowest total cost to explore , In this way, we will take fewer detours

And the search path must be the shortest path .

In the first cycle , The algorithm explores the four squares around the starting point , And calculate “ The current cost ” and “ Estimate the cost ”.

Like here **1** From the beginning to the current block has gone 1 Step

there 4 Represents the Manhattan distance from the square to the end , In these four boundary blocks , The right square costs the least , So in the next cycle, it will be searched first

In the next cycle , We have calculated the price of the block in the same way , The lowest value of the square on the right is still found , So in the next cycle , We search for it

The algorithm goes on and on like this , Until the end of the search

Increase the order of magnitude of the squares ,**A*** The algorithm can also find the right shortest path

The most important thing is , The number of blocks it searches for is significantly less than that of breadth first traversal , So it's more efficient .

After understanding the basic principle of the algorithm , Next is the code , Here I quote directly **redblobgames** Of **Python** Code implementation , Because it's really good ！

Plain Text

1

def heuristic(a, b): #Manhattan Distance

2

(x1, y1) = a

3

(x2, y2) = b

4

return abs(x1 - x2) + abs(y1 - y2)

5

6

def a_star_search(graph, start, goal):

7

frontier = PriorityQueue()

8

frontier.put(start, 0)

9

came_from = {}

10

cost_so_far = {}

11

came_from[start] = None

12

cost_so_far[start] = 0

13

14

while not frontier.empty():

15

current = frontier.get()

16

17

if current = goal:

18

break

19

20

for next in graph.neighbors(current):

21

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

22

if next not in cost_so_far or new_cost < cost_so_far[next]:

23

cost_so_far[next] = new_cost

24

priority = new_cost + heuristic(goal, next)

25

frontier.put(next, priority)

26

came_from[next] = current

27

28

return came_from, cost_so_far

Let's take a look at the top lines first ,**frontier** Contains all the border blocks we've explored in this round ( The green squares in the previous picture )

Plain Text

1

frontier = PriorityQueue()

**PriorityQueue** Represents that it is a priority queue , That means it can use “ cost ” Automatic sorting , And take it out every time ” cost “ The lowest square

Plain Text

1

frontier.put(start, 0)

In the queue, we first store an element , That's where we start

Plain Text

1

came_from = {}

The following **came_from** It's a map from the current block to the previous one , Represents the direction of the path

Plain Text

1

cost_so_far = {}

there **cost_so_far** Representing the square “ The current cost ”

Plain Text

1

came_from[start] = None

2

cost_so_far[start] = 0

These two lines will start with **came_from** empty , And set the current cost of the starting point to 0, In this way, the validity of the algorithm data can be guaranteed

Plain Text

1

while not frontier.empty():

2

current = frontier.get()

Next , as long as **frontier** This queue is not empty , The cycle will continue , Every cycle , The algorithm extracts the least expensive block from the priority queue

Plain Text

1

if current = goal:

2

break

Then check whether the block is the end block , If it's the end of the algorithm , Otherwise, go ahead

Plain Text

1

for next in graph.neighbors(current):

Next , The algorithm will check the adjacent blocks on the top, bottom, left and right of this block , That's in the loop **next** Show the box to do the following operations

Plain Text

1

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

The algorithm will calculate this first **next** square “ New cost ”, It's equal to the cost before Plus from **current** To **next** The price of the block

Because we use grids , So the second half is **1**

Plain Text

1

if next not in cost_so_far or new_cost < cost_so_far[next]:

And then just **next** Blocks have not been detected , perhaps **next** The current cost is lower than before

Plain Text

1

frontier.put(next, priority)

We just put him in the priority queue , And the total cost here **priority** be equal to **“ The current cost ”** add **” Estimate the cost “**

Plain Text

1

priority = new_cost + heuristic(goal, next)

The estimated cost is what I mentioned earlier “ Manhattan distance ”

Plain Text

1

def heuristic(a, b): (x1, y1) = a (x2, y2) = b return abs(x1 - x2) + abs(y1 - y2)

Then the program goes to the next loop , Repeat all the previous steps

This program is really cleverly written , It may be difficult to understand, but if you look at it more than once, you may suddenly have a bright light

## expand

If you expand the map to grid form （**Grid**）, Because there are too many nodes in the graph , Traversal can be very inefficient

So we can simplify the grid map to Signposts with fewer nodes （**WayPoints**）

And then it's important to note that ：_** Here, the distance between any two nodes is no longer 1 了 , It's the actual distance between nodes **_

We can also store maps hierarchically from top to bottom

Like this ** quadtree （Quad Tree）**

Or like unity Used in ** Navigation triangulation （Navigation Mesh）**, In this way, the speed of sub algorithm will be further optimized

in addition , I also recommend **redblobgames** A tutorial for

Visualization of various algorithms , And clearly see the traversal process of various algorithms 、 In the middle

And the comparison between various methods , It's very intuitive , It's also helpful to understand the algorithm .

Reference resources ：

[1] Zhou Xiaojing . Based on improvement A_ Algorithm of game map pathfinding research [D]. Southwest University ,2010._ _[2]_https://www.redblobgames.com/... _[3]_https://en.wikipedia.org/wiki...

Click to follow , The first time to learn about Huawei's new cloud technology ~