特别大的地图A*算法优化思路
·
-
搜索优化：
小技巧：
1.openList（用于存放可以搜索的点）使用优先队列来实现。
优先队列（小顶堆）：插入一个点的复杂度为O（logN），取出一个最值点复杂度为O（1）
2.深度限制：有时要搜的路径非常长，利用A*算法搜一次付出的代价很高，造成游戏的卡顿。那么为了保证每次搜索不会超过一定代价，可以设置深度限制，每搜一次则深度+1，搜到一定深度限制还没搜到终点，则返还失败值。
针对大地图优化：
1.把地图瓦块变大减少节点数量。
2.多线程寻路(适用于多个角色同时寻路)。
3.把大地图分块，分成n个小地图：
如果起点和终点相隔几个小地图，那么寻路流程如下：
step1：根据起点和终点的方向算出走出当前小地图出口点，用A*寻路到出口点。
（注：当前小地图出口点也就是要经过的下一个小地图的入口点）
step2：让角色向下一个小地图的入口点移动，(移动的过程中可以继续寻下个小地图的出口路径，或者到达出口点后再寻路）
step3：若下一个小地图不是终点所在的地图，那么把这个入口点作为起点重复step1：根据入口点到终点的方向计算出，当前小地图的出口点，用A*找到出口点的路径。
若一个小地图是终点所在小地图那么就再用A*寻路到终点即可。
可以走到每个小地图的入口点后再对这个小地图的出口寻路
4.网格地图简化成路标形式(减少网格节点)
注：变成路标形式后每个节点之间的路径不再是1了，而是节点之间的实际距离
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)