论文部分内容阅读
近年来,随着游戏产业的不断发展,人工智能在游戏中的作用也越来越大,并且成为了一项热门技术。智能寻路系统作为人工智能的一个分支在现代网络游戏中占据着重要的地位。当前大部分游戏中的智能寻路系统都放在客户端完成,这样在处理上简单易实现。但当玩家恶意修改时,服务器不能准确的做出判断,从而导致了游戏的不公平性。为了避免这个问题,需要实现服务器端的智能寻路系统,这就要求智能寻路系统既不能影响游戏服务器的正常逻辑处理,还要能支持尽可能多的用户同时请求,而现在比较流行的寻路方法A*在平均寻路时间上无法达到这一要求,需要寻找一种快速寻路方法。 为此,本文首先改进了基于A*的寻路策略,提出了懒惰初始化,栈数组策略。探讨了利用A*中的启发式估价函数的特性对路径节点进行分类管理。对比优化后的算法和传统的优先队列算法的实验数据,在不同障碍率下,优化算法的运行时间变化趋势与改进前方法基本一致。在平均寻路时间上,改进后的算法虽然有一定优势,但还是不能达到支持大量用户并发寻路的要求。 因此,本文讨论了基于深度优先搜索的寻路策略,提出了优化方法,实现了快速寻路。经过实验测试,应用快速寻路方法之后,平均寻路时间由原来的0.13毫秒降低到0.067毫秒,寻路效率显著提升;其不足是,障碍率越大,寻路准确率越小,在高障碍率的情况下,寻路准确率低于50%。 为了弥补这一缺点,本文提出了一种基于预判障碍的混合寻路的新方法。此方法先利用一种称为边缘搜索的搜索算法对地图进行扫描,然后对地图中的障碍率进行评估,从而选择最佳的寻路算法。既保证了高效的搜索效率,又能保证寻路的准确率。实验结果显示,低障碍率下,混合方法平均寻路时间低于0.1毫秒,高障碍率情况下平均寻路时间也在0.1毫秒左右,最坏情况下寻路时间为4.9毫秒。 因此在大多数情况下,混合寻路方法都取得了较短的寻路时间。能够支持大量用户的同时寻路请求,又不影响服务器的正常逻辑处理。