基于定位点和路径复用的大型多人在线游戏寻路算法

计算机应用 ›› 2010, Vol. 30 ›› Issue (12): 3215-3217.

基于定位点和路径复用的大型多人在线游戏寻路算法

梁毅¹,周刚²

1. 四川大学计算机学院
2. 四川大学

收稿日期:2010-07-01 修回日期:2010-08-19 发布日期:2010-12-22 出版日期:2010-12-01
通讯作者: 梁毅
基金资助:
教育部留学回国启动基金项目

Path finding algorithm in massive multiplayer online games based on anchor points and path reuse

Received:2010-07-01 Revised:2010-08-19 Online:2010-12-22 Published:2010-12-01

摘要/Abstract

摘要： 针对当前寻路算法不能很好满足大型多人在线游戏对于可靠性和低消耗的要求，提出一种基于定位点和路径复用的大型多人在线游戏寻路算法。通过定位点的使用和路径复用，使得无用空间的探索大幅减少，降低了服务器的负载，最终探索出一条接近最优的路径。实验结果表明，该算法具有更高的效率，对于大型多人在线游戏寻路是一个切实可行的解决方案。

关键词: 大型多人在线游戏, 寻路算法, 定位点, 路径复用, 空间探索

Abstract: In order to solve the low performance of path finding algorithm in massive multiplayer online games, this paper proposed a path finding algorithm in Massive Multiplayer Online Games (MMOG) based on anchor points and path reuse. The algorithm reduced the unnecessary search space by using anchors and path reuse, and reduced load on server. Finally it discovered a near optimal path. The experimental results indicate that the algorithm is more efficient, and it is a practical and feasible approach to path finding in online games.

Key words: Massively Multiplayer Online Game （MMOG）, path finding algorithm, anchor point, path reuse, space search

梁毅周刚. 基于定位点和路径复用的大型多人在线游戏寻路算法[J]. 计算机应用, 2010, 30(12): 3215-3217.

[1]	李钊, 董霄霄, 黄程程, 任崇广. 基于启发式搜索的浮点表达式设计空间探索方法[J]. 计算机应用, 2020, 40(9): 2665-2669.
[2]	师小丽张发存. LS RISC微处理器仿真研究[J]. 计算机应用, 2008, 28(10): 2690-2692.