游戏AI：（一）图、树与寻路算法

一、图

无向图：

有向图：

权重图：

 哈密顿图：

定义：经过所有的顶点并且只经过一次的路径，加哈密顿路径，闭合的哈密顿路径叫哈密顿回路。

例如送快递，快递车从快递公司出发，遍历每个小区，且每个小区只去一次，最后回到快递公司。这就是一条哈密顿回路。

例如我最近玩的一个游戏，第一次通关之后开启迷宫扫荡功能，但是这个游戏显然没把扫荡算法写好(也许是故意不让我把道具拿完...)，迷宫里随机位置有很多道具，每次扫荡道具都没拿完就直接打BOSS了((＃￣～￣＃))

根据上面讲的想必你也想到了，每个道具点可以看做一个顶点，BOSS所在位置是终点，起点随机(但别踩BOSS头上)，搜索出一个哈密顿回路就行了。

那么怎么表示图上节点之间的关系呢？

方法一：01矩阵（0表示没有路径，1表示有路径）

 上图用01矩阵表示如下：

[1 1 0 0]   //1和1有路径是因为上图中1有一个回路

[1 0 1 0]

[0 1 0 1]

[0 0 1 0]

方法二：链表 

1->1->2

2->1->3

3->2->4

4->3

哪种方式更好要看具体情况，链表没有冗余信息，有就是有，没有就不写。矩阵则把所有信息都表示出来了，但是在游戏里，有时地图数据是从json文件里读出来的，这样就可以把配置地图工作交给策划，用一个矩阵来表示地图上的每个点会很方便，点可以定义成一个类，所以每个点可以表示很多信息。

二、树

二叉树：什么是二叉树？国家出台二胎法，要求每个家庭最多可以生两个孩子，所以只要有一个节点生了三个子树那就违法了，赶出二叉树家族。

满二叉树：他是二叉树家族的一员，所以也在二胎法环境下，但他们家多了一条家训，每个家庭要么不生，要生就必须生两个。生一个的非吾族类，虽远必诛。

完全二叉树：

满二叉树也是完全二叉树。

前面生一个的被满二叉树家族排挤了，完全二叉树长老说，别怕，来我这儿，但是你生的这一个是儿子还是女儿啊？这男左女右，要是你生的是儿子(左子树)，我就让你加入，你只有一个女儿(右子树)那就不行了。

所以完全二叉树家族的家训是，要么不生，要么先生儿子(左子树)。

平衡二叉树：左右子树的深度差<=1，通俗来说就是：我兄弟（兄弟节点：就是同一个妈生的左子树和右子树）有孩子（不管左右）了，我还没有，我不着急。但是我兄弟有孙子（子孙节点）了，我连孩子都没有，我就不平衡了。

二叉查找树：

 对于每个根节点，左节点值小于父节点，右节点值大于父节点。

 红黑树：

 红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。

寻路算法

1. 广度优先搜索 BFS & 深度优先搜索 DFS

广度优先搜索 BFS：顾名思义，广度优先就是从根节点出发，先遍历它所有的子节点，再遍历第一个子节点所有的子节点，一层一层下去。

优点：可以找出最短路径

缺点：遍历了所有顶点

深度优先搜索 DFS：从根节点出发，先访问它的子节点，然后是子节点的子节点，一直访问到叶子节点，再一层层回溯前面的过程。

缺点：找到的路径往往不是最短的

2. Dijkstra 算法

采用贪心算法策略，每次都选择距离最短的节点。

A* 算法

 g(n)表示该点距离起点的代价，h(n)表示该点距离终点的代价。所以这个点的总开销=到起点的代价+到终点的代价。

下面讨论几种情况：

h(n)=0 ： 即只有g(n)在起作用，总开销=到起点的代价，那么每次都会选择距离最近的点，这等同于Dijkstra算法。

g(n)=0 ：即只有h(n)在起作用，总开销=到终点的代价，这种情况叫最佳优先搜索算法。

那么怎么求代价呢？

如果只能上下左右四方向移动，那么可以用曼哈顿距离，即 abs(node.x-nextNode.x)+abs(node.y-nextNode.y)

如果可以走斜线，那么可以用欧几里得距离，计算三角形的对角线就行了。sqrt(pow(abs(node.x-nextNode.x),2)+pow(abs(node.y-nextNode.y),2))，不用真的每次都傻傻的计算这么大一串，一般我们取的是边长为1的正方形，按曼哈顿距离，到达对角顶点每次要走两条边，按欧几里得距离直接走对角线，就是sqrt(2)，约等1.4。

下面我们用Unity来测试一下A*算法：

1）先创建Node类，这个类得包含坐标，父节点，该节点是路还是障碍，寻路消耗

1 public enum NodeType
2 {
3 Walk,
4 Stop
5 }
6 public class Node
7 {
8 //坐标
9 public int x;
10 public int y;
11 //父节点
12 public Node father;
13 //节点能不能走
14 public NodeType type;
15 //寻路消耗
16 public float G;
17 public float H;
18 public float F;
19 public Node(int x,int y,NodeType type)
20 {
21 this.x = x;
22 this.y = y;
23 this.type = type;
24 }
25 public void SetNode(Node father,float g,float h)
26 {
27 this.father = father;
28 this.G = g;
29 this.H = h;
30 this.F = g + h;
31 }
32 }

2 )创建AStar寻路算法类

1 public class AStar :MonoBehaviour
2 {
3 public static AStar instance; //这里只是为了方便使用，这种写法并不规范
4
5 int mapWidth;
6 int mapHight;
7
8 public Node[,] nodes;
9 List openList = new List();
10 List closeList = new List();
11 private void Awake()
12 {
13 instance = this;
14 }
15 public void InitMap(int w,int h)
16 {
17 mapWidth = w;
18 mapHight = h;
19 nodes = new Node[w, h];
20 //随机生成地图
21 for(int i = 0; i )
22 {
23 for(int j = 0; j )
24 {
25 Node node = new Node(i, j, Random.Range(0, 10) <3 ? NodeType.Stop : NodeType.Walk);
26 nodes[i, j] = node;
27 }
28 }
29 }
30 public List FindPath(Vector2 startPos,Vector2 endPos)
31 {
32 //判断传入的两个点是否合法
33 if (startPos.x <0 || startPos.x > mapWidth || startPos.y <0 || startPos.y > mapHight
34 || endPos.x <0 || endPos.x > mapWidth || endPos.y <0 || endPos.y > mapHight)
35 {
36 Debug.Log("开始或结束结点超出地图范围");
37 return null;
38 }
39 Node startNode = nodes[(int)startPos.x, (int)startPos.y];
40 Node endNode = nodes[(int)endPos.x,(int)endPos.y];
41 if (startNode.type == NodeType.Stop || endNode.type == NodeType.Stop)
42 {
43 Debug.Log("开始或结束结点是阻挡物");
44 return null;
45 }
46
47 //清空关闭和开启列表
48 openList.Clear();
49 closeList.Clear();
50
51 //开始点放入关闭列表中
52 startNode.SetNode(null, 0, 0);
53 closeList.Add(startNode);
54
55 while (true)
56 {
57 //从起点开始找周围的点
58 //左上
59 FindNeighbors(startNode.x - 1, startNode.y - 1, startNode, 1.4f, endPos);
60 //上
61 FindNeighbors(startNode.x, startNode.y - 1, startNode, 1.4f, endPos);
62 //右上
63 FindNeighbors(startNode.x + 1, startNode.y - 1, startNode, 1.4f, endPos);
64 //左
65 FindNeighbors(startNode.x - 1, startNode.y, startNode, 1.4f, endPos);
66 //右
67 FindNeighbors(startNode.x + 1, startNode.y, startNode, 1.4f, endPos);
68 //左下
69 FindNeighbors(startNode.x - 1, startNode.y + 1, startNode, 1.4f, endPos);
70 //下
71 FindNeighbors(startNode.x, startNode.y + 1, startNode, 1.4f, endPos);
72 //右下
73 FindNeighbors(startNode.x + 1, startNode.y + 1, startNode, 1.4f, endPos);
74
75 //选出开启列表中F值最小的点
76 openList.Sort(CompareNode);
77
78 //放入关闭列表中，并从开启列表移除
79 closeList.Add(openList[0]);
80 startNode = openList[0];
81 openList.RemoveAt(0);
82
83 //如果这个点是终点，则返回结果
84 if (startNode==endNode)
85 {
86 return closeList;
87 }
88 }
89 }
90 private void FindNeighbors(int x,int y,Node father,float g,Vector2 endPos)
91 {
92 //判断这些点是否是边界或阻挡或在开启或关闭列表中，都不是才能放入开启列表中
93 if (x <0 || x >= mapWidth || y <0 || y >= mapHight)
94 return;
95 Node node = nodes[x, y];
96 if (node == null || node.type == NodeType.Stop ||
97 closeList.Contains(node) || openList.Contains(node))
98 return;
99 //我离起点的距离=我父亲离起点的距离+我离父亲的距离
100 node.SetNode(father, father.G + g, Mathf.Abs(node.x - endPos.x) + Mathf.Abs(node.y - endPos.y));
101 openList.Add(node);
102 }
103 private int CompareNode(Node a,Node b)
104 {
105 if (a.F > b.F)
106 return 1;
107 else
108 return -1;
109 }
110 }

3）接下来是测试的代码

1 public class Test : MonoBehaviour
2 {
3 //格子坐标
4 public int beginX=-3;
5 public int beginY=3;
6 //格子之间的偏移位置
7 public int offsetX=1;
8 public int offsetY=-1;
9 //地图大小
10 public int map_" + j;
25 cubes.Add(obj.name, obj);
26 Node node = AStar.instance.nodes[i, j];
27 if (node.type == NodeType.Stop)
28 {
29 obj.GetComponent().material.color = Color.red;
30 }
31 }
32 }
33 }
34 private void Update()
35 {
36 if (Input.GetMouseButtonDown(0))
37 {
38 RaycastHit hitInfo;
39 Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
40 if(Physics.Raycast(ray,out hitInfo, 1000))
41 {
42 if (beginPos == Vector2.right * -1)
43 {
44 string[] strs = hitInfo.collider.gameObject.name.Split('_');
45 beginPos = new Vector2(int.Parse(strs[0]), int.Parse(strs[1]));
46 hitInfo.collider.gameObject.GetComponent().material.color = Color.yellow;
47 }
48 else
49 {
50 string[] strs = hitInfo.collider.gameObject.name.Split('_');
51 Vector2 endPos = new Vector2(int.Parse(strs[0]), int.Parse(strs[1]));
52 hitInfo.collider.gameObject.GetComponent().material.color = Color.yellow;
53 List list = AStar.instance.FindPath(beginPos, endPos);
54 if (list != null)
55 {
56 for(int i = 0; i )
57 {
58 cubes[list[i].x + "_" + list[i].y].GetComponent().material.color = Color.green;
59 }
60 }
61 }
62
63 }
64
65 }
66 }
67 }

测试结果：