# Revealing the logic of moving path selection in Summoner Canyon?

2020-11-09 16:06:36

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  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 ：

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

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