地图障碍信息的获取

• 自动寻路全部在客户端执行，不经过服务器，原理上相当于模拟鼠标的点击操作。当然也可以放在服务器上用于NPC的寻路，实现的原理是一样的，只是在服务器上要考虑很多的性能问题，要进一步做一些处理。本文的范畴仅限于客户端。
• 第一步就是要获取地图的障碍信息，在不同的游戏中是不同的处理操作，因此也就不做详细的介绍。获取得到的地图障碍信息将保持在一张障碍信息表中。障碍信息表用二维数组来组织，目的就是为了方便后期能够快速的进行读写操作。
• 刚开始的障碍信息表中的数据只有2种可能，用 0 表示通过，1 表示障碍。
• 障碍信息的读取时机: 切换地图时。作为错误预防，每次寻路时比对当前地图与障碍信息表表示的地图的编号，确保地图一致。

地图预处理

• 找出地图中无法到达又不是障碍的区域（称之为孤岛）、提高寻路效率
• 时机：第一次寻路、或者玩家切换了可连通区域时
• 开始时，障碍信息表只有2种数值：Pass（即0）Obstacle（即1）
• 将玩家所在点标记为 Reachable ,并加入处理列表。循环进行下列操作：从处理列表中取出一个点，遍历其周围8节点，如果其周围节点是Pass，就将其改为Reachable，并压入处理列表
• 处理列表为空即结束循环，此时剩下的所有Pass点就是孤岛，将其改为IsLand，然后将所有Reachable还原为Pass
• 处理结束时地图上有3种点：Pass、Obstacle、IsLand

A* 寻路算法

• 节点数据：节点坐标、父节点坐标、从起点到此节点的代价（G）、从此节点到终点的预计代价（H）
• 一个正方格的边长代价定于为10，H 采用曼哈顿法近似，即（X方向格子数 +  Y方向格子数）* 10，经过格子的总代价 F = G + H
• 两个数据结构：Open列表和Close列表，存储节点及其相关数据
• 将初始节点压入 Open 然后进行下列循环：

• 在Open中找到F值最小的节点，将其取出并加入Close，这个节点称为当前节点。

  遍历当前节点周围8节点，计算周围节点的G、H、F值（G值为当前节点的值加10或者14，H、F值按前面方法计算）。

  如果这个周围节点不可通过，或者在Close中就不处理。

  如果这个周围节点在Open中就比较刚刚计算得到的G值和Open中保存的G值，如果Open中比较小就不处理，否则把新的G,H,F更新到Open中并把当前节点作为父节点也更新到Open中。

  如果这个周围节点可通过又不在Open中就将其加入Open，它的父节点是当前节点。

• 循环退出: Open表空（路径不存在）、某个周围节点是终点（找到路径）
• 输出路径：路径节点都在Close中，在Close中找到终点，然后依次找父节点就是路径了。
• 优化一：如果终点是障碍或者孤岛直接返回找不到路径
• 优化二：加入Open、Close时将障碍信息表中该点标记为Open、Close。这样就不用遍历Open和Close来找寻节点在不在其中。记得结束时把所有Open和Close标记还原成Pass

二叉堆

• A* 算法效率是十分低下的。性能瓶颈就在要经常在Open表中找出F值最小的元素。因此将Open改为由二叉堆实现，效率大幅提高。
•  二叉堆是一种完全二叉树。二叉堆的特性在于，所有的子节点的权值都比父节点大，因此最小节点永远在堆顶。
• 增加元素: 将新元素插入堆尾，然后依次和它的父节点比较，如果比父节点小就同父节点交换位置，直到父节点比它大或者达到堆顶。
• 取出最小元素：将堆顶的最小元素取出并删除，将堆尾元素X取出放到堆顶。将X反复同他的左右子节点比较，如果其中有一个比他小就进行交换，如果都比他小就同较小的一个子节点交换。直到没有可交换的子节点为止。
• 更新元素的权值：先更新该元素的权值，然后和父节点、子节点比较，看是否要调整堆，如果要调整是向上还是向下调整，然后按增加删除元素的方法来调整堆。
• 二叉堆的存储: 因为二叉堆是一种完全二叉树，可以很容易用数组来存储。父节点的ID为（当前ID / 2），左节点ID为（当前ID * 2），右节点的ID为（当前ID * 2 + 1）