路径规划算法

A*搜索算法

A*算法是启发式搜索方法，但是在游戏开发中，A*算法会受到一些因素的制约：

• 计算开销和实时性问题

在图比较大的时候可能非常耗时，尤其是在需要频繁计算路径的实时游戏中。游戏中的路径寻找需要快速响应，尤其是在开放世界或有动态元素的场景中。而且A*算法通常是在静态地图上执行的，但是许多环境玩家、敌人、障碍物会发生改变，每当发生改变的时候都需要重新计算路径，导致性能问题。

• 平滑性

  A*算法生成的路径通常是“阶梯状”的，并不自然。可能导致拐角过多，移动不平滑，而如果再去平滑路径，又增加了额外的计算开销。

把代价分成两部分：

• 当前代价：一共走过多少格子
• 预估代价：从当前位置到终点位置需要走多少格子

可以使用曼哈顿距离或欧拉距离，将两部分代价相加起来。永远走向代价最小的位置。