java-如何提高我的A *路径查找器的性能？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java-如何提高我的A *路径查找器的性能？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1488字，纯文字阅读大概需要3分钟。

内容图文

因此,基本上,我编写了一个A *路径查找器,该路径查找器可以找到通过障碍物的路径并进行移动.我基本上将http://www.policyalmanac.org/games/aStarTutorial.htm的伪代码实现为真实代码,并且还使用了二进制堆方法从开放列表中添加和删除项目.

使用二进制堆可以显着提高性能,比我以前使用的插入排序算法快约500倍.

问题在于它仍然平均需要150万纳秒,大约是0.0015秒.

所以问题是,我的计划是制作一个塔防游戏,每次我向地图添加塔时,每个暴民的寻路都需要更新.如果我在地图上最多只能容纳约50个生物,那么更新整个生物的所有路径将花费约.0015 * 50 = .075秒.游戏基本上每1/60秒滴答(所有游戏中的物品更新),即0.016秒,因此问题在于更新路径的时间比滴答的时间更长,这将导致巨大的延迟.那么我应该怎么做呢？我是否需要找到一种更好的算法来对打开列表进行排序,或者以某种方式划分寻路任务,以使每个刻度都只执行X个寻路任务,而不是全部.

解决方法:

而不是从每个敌人到检查站搜索,而是一次从检查点向外搜索到每个敌人.这样,您只需要进行一次搜索,而不用进行50次搜索.

更具体地说,只需从玩家向外进行广度优先搜索(如果您的图形已加权,则为djikstra’s),直到找到每个敌人为止.

您可以通过将启发式的EstimatedDistanceToEnd(aka h(x))更改为对任何敌人的最小估计值,来更改此策略以与A *一起使用,但是对于许多敌人而言,这可能比简单的选择要慢.试探法必须为consistent才能起作用.

此外,请确保您正在使用correct tie-breaking criteria.

而且,最重要的是,请记住,对于大多数游戏,您不需要在每一帧上都运行探路器-根据游戏的不同,您通常每秒只能走一两次,甚至更少.

如果那仍然太慢,您可以考虑使用D* lite在后续搜索之间重用信息.但是,我敢打赌,运行单个广度优先搜索将足够快.

(摘自我对gamedev的a similar question的回答)

内容总结

以上是互联网集市为您收集整理的java-如何提高我的A *路径查找器的性能？全部内容，希望文章能够帮你解决java-如何提高我的A *路径查找器的性能？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端