# 揭秘在召唤师峡谷中移动路径选择逻辑？

2020-11-09 16:06:36 华为云开发者社区

## A* Search Algorithm

”A*搜索算法“也被叫做“启发式搜索”

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

Plain Text

1

frontier = PriorityQueue()

PriorityQueue代表它是一个优先队列，就是说它能够用“代价”自动排序，并每次取出”代价“最低的方块

Plain Text

1

frontier.put(start, 0)

Plain Text

1

came_from = {}

Plain Text

1

cost_so_far = {}

Plain Text

1

came_from[start] = None

2

cost_so_far[start] = 0

Plain Text

1

while not frontier.empty():

2

current = frontier.get()

Plain Text

1

if current = goal:

2

break

Plain Text

1

for next in graph.neighbors(current):

Plain Text

1

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

Plain Text

1

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

Plain Text

1

frontier.put(next, priority)

Plain Text

1

priority = new_cost + heuristic(goal, next)

Plain Text

1

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

## 拓展

[1]周小镜. 基于改进A_算法的游戏地图寻径的研究[D].西南大学,2010._ _[2]_https://www.redblobgames.com/... _[3]_https://en.wikipedia.org/wiki...

https://segmentfault.com/a/1190000037774398