多人在线角色扮演游戏中智能寻路的设计与实现

摘要

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

目录

多人在线角色扮演游戏中智能寻路的设计与实现

THE DESIGN AND IMPLEMENTATION OF INTELLIGENT PATH-FINDING IN MASSIVE MULTIPLAYER ONLINE ROLE PLAYING GAME

摘 要

Abstract

目 录

第1章 绪论

1.1 课题背景

1.1.1多人在线角色扮演游戏

1.1.2游戏的发展趋势及游戏中的寻路技术

1.2 本课题研究的目的及意义

1.3 人工智能定义在工程与学术上的差别

1.4 智能寻路的研究现状和挑战

1.4.1 RPG中的地图

1.4.2 寻路算法对MMORPG服务器性能的影响

1.5 本文主要研究内容

第2章 基于A*及优化A*的游戏寻路

2.1 引言

2.2 多人在线角色扮演游戏中存在的问题

2.3经典寻路算法

2.3.1 先深搜索算法

2.3.2 先广搜索算法

2.3.3 启发式搜索

2.4 多人在线角色扮演游戏中的地形分析及地图表示

2.5 启发式算法A*在游戏中的寻路

2.6 改进方法的必要性

2.7 基于优先队列的A*

2.7.1 PA*复杂性分析

2.8 基于新存储结构的改进A*

2.8.1 关于算法初始化的改进

2.8.2 基于栈数组的改进A*

2.9 PA*以及SLA*实验

2.9.1 测试条件

2.9.2 运行环境

2.9.3 实验结果及分析

2.10 本章小结

第3章 基于边缘搜索方法的游戏寻路

3.1 迭代深度优先A*

3.2 基于深度优先的边缘搜索方法

3.3 简化边缘搜索算法复杂性分析

3.3.1 时间复杂性分析

3.3.2 空间复杂性分析

3.4 边缘搜索实验及结果

3.5 边缘搜索、PA*和SLA*寻路算法的对比实验

3.5.1 实验数据

3.5.2 统计量的选择与分析

3.5.3 边缘搜索与其他寻路算法的实验数据比较结果

3.6 本章小结

第4章 基于预判障碍的寻路方法的实现

4.1 算法组合

4.2 地图预判机制

4.2.1 特征量的选取

4.2.2 预判的准确率

4.3 基于预判机制的路径搜索

4.3.1 混合寻路算法设计与实现

4.3.2 算法流程

4.4 实验数据及结果分析

4.4.1 增加测试算法的统计量

4.4.2 混合算法的复杂性分析

4.4.3 实验数据以及结果分析

4.5 本章小结

结 论

参考文献

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致 谢