声明:本人并非OIer，没有系统学习过算法，故不足之处还请见谅，如有好的想法非常非常非常欢迎提出
背景
笔者正在为游戏noita设计一个自动化控制角色的脚本mod，最终目的是可以全自动完成主线。
noita的地形相当复杂，如何在复杂的地形中前往指定地点就成了不得不面对的问题，且不同于战斗逻辑有现成的游戏原生算法可以参考，寻路只能从头开始构建。在经历了几天痛苦地碰壁后，借由此文重新梳理思路。
问题描述
输入：终点坐标
输出：可以使角色到达终点的移动逻辑
备注：角色基本操作已经过封装，可以方便地调用，包括左右移动，上飞，踢击。有大量的游戏api感知环境状态。不考虑游戏内开路，不考虑怪物影响
思路
问题可以分为两个层面，一个比较宏观，如何找到一条通往终点的道路；另一个相对微观，如何在崎岖不平的道路上移动而不被卡住
问题重新定义为：
函数1：寻路
输入：终点坐标
输出：通往终点的，连续无障碍路径
函数2：避障输入：保证路途中无障碍的坐标
输出：一系列移动逻辑可到达该坐标
考虑是否可以看做已知问题的变体
noita的地形是相当复杂的，而且碍于笔者经验有限，很难找到一种已知的简单策略迁移过来，暂时作罢
考虑对输入做处理
输入是一个坐标，以及通过游戏api获取到的信息，对于后者也许需要离散化处理。
考虑最笨也最显而易见的办法
如果可以将游戏地图抽象成一个离散的格子图，显然是可以用穷举的办法解决的，但是如何抽象显然是一个棘手的问题。
游戏本身已经是相对离散的了，也许最笨的办法，寻路即记忆走过的坐标并尝试所有可能的路径，避障即尝试所有的移动组合，如果都无效就确认是死路，根据记忆回溯
或者在游戏地图上撒足够密的点，然后通过射线机制确定点与点之间的连通性，这样就抽象出了一个图，然后用一个最短路径搜索算法求路径即可
考虑尽可能多的贪心算法
第一个想法是模拟人的寻路，即在视野内找到无阻碍的、离终点最近的“中继点”，然后前往该点，再找下一个。
但是在遇到“洞穴”地形时会在洞的尽头反复退出一步再撞墙，对于两面受阻的“山脚”地形也没有处理能力，故而只作为一种“避障”函数的策略，效果还是不错的。
具体实现为以玩家坐标为中心，30°、40单位长度为步长，在玩家周围半径200单位长度生成65个可能的中继点，根据射线机制筛掉隔着墙的不可达点，再根据与玩家的距离（不太近）和与终点的距离（尽可能小）计算一个分数，把分数最高的作为当前中继点，以此为目标赶路。
中继点系统也具有少量路径规划能力，体现在根据一些函数检测到卡住时，将当前选择的中继点加进黑名单，其中心半径50单位的范围在生成新的中继点时效果等同于墙壁
其它
按书中的方法，接下来是分治、dp、NP问题简化等等，但此问题并不适合
A*算法：一种启发式搜索算法，结合dijkstra算法的已有代价和贪心策略的距离终点的预估从而在多数场景下既能得到全局最优
尝试用A*算法作为寻路，结果并不理想，由于离散化是基于65个中继点的，故无法进行过于深的路线计算，而短途计算并没有比原有的贪心策略更优秀
dfs：将当前位置的中继点离终点的距离排序，递归搜索前5个，控制递归深度为10。略有效果但并不明显，而且由于计算量极大给游戏造成了明显的卡顿。原因是终点距离起点很远，且连通性需要自己判断，性能上不支持足够深的搜索
离散化的巨大负担是根本原因，考虑重新做离散化
考虑更加直接的离散化策略，把5050坐标看做一个格子，连通性用一次中心到中心的射线判断，在此基础上重新尝试A算法，即根据代价函数得出当前位置附近的最优格子，然后检测连通性，继续探索直到找到终点，得出路径