地图寻路算法的速度优化

摘要

本发明涉及计算机图形技术领域，更具体地说，基于可见点的A*地图寻路系统，根据场景结构，在碰撞的凸角上放置一个路点；采用离线的方法，模拟主角移动，测试所有路点之间的是否可以直达，生成可见点网格；通过离线生成可见点和可见点的可见性，最大限度的简化了搜索空间，相比传统的矩形和多边形网格寻路，大大的提高了寻路速度，减少了寻路路点的存储空间，非常适合大型网络游戏中的寻路。

主权项

地图寻路算法的速度优化，对A*算法的搜索空间进行优化，其步骤如下：1）根据场景结构，在碰撞的凸角上放置一个路点；2）采用离线的方法，模拟主角移动，测试所有路点之间的是否可以直达，生成可见点网格；3）当角色从一点寻路到另外一点的时候，首先要把角色的寻路转化到可见点寻路上；计算寻路启点与目的地与所有可见点的可见性；4）确定起始点的可见点之后，对可见点进行A*寻路，确定最终的寻路路径。