Improved genetic algorithm for path planning in games NPC

LI Jing-song; QIAN Qian; SUN Ming-hui

doi:10.13873/j.1000-9787(2017)06-0114-05

Chinese

您当前的位置：

首页 >

文章列表页 >

Improved genetic algorithm for path planning in games NPC

更新时间：2025-09-11

- Improved genetic algorithm for path planning in games NPC
- Vol. 36, Issue 6, Pages: 114-118(2017)
- 作者机构：
  
  1. 昆明理工大学云南省计算机技术应用重点实验室
  2. 吉林大学符号计算与知识工程教育部重点实验室
  3. 吉林大学计算机科学与技术学院
- 作者简介：
- 基金信息：
- DOI：10.13873/j.1000-9787(2017)06-0114-05
  CLC： TP18
- Published：2017
- 稿件说明：
移动端阅览
[1]李井颂,钱谦,孙铭会.用于游戏NPC路径规划的改进遗传算法[J].传感器与微系统,2017,36(06):114-118.

LI Jing-song, QIAN Qian, SUN Ming-hui. Improved genetic algorithm for path planning in games NPC[J]. 2017, 36(6): 114-118.
[1]李井颂,钱谦,孙铭会.用于游戏NPC路径规划的改进遗传算法[J].传感器与微系统,2017,36(06):114-118. DOI： 10.13873/j.1000-9787(2017)06-0114-05.

LI Jing-song, QIAN Qian, SUN Ming-hui. Improved genetic algorithm for path planning in games NPC[J]. 2017, 36(6): 114-118. DOI： 10.13873/j.1000-9787(2017)06-0114-05.

摘要

针对游戏非玩家控制（NPC）路径规划中传统遗传算法计算速度慢、正确率低等问题

设计了改进型遗传算法。提出了最佳种群规模估计方法

设计了基于精英主义思想的遗传算子。根据游戏地图的特点

引入了基于启发式深度优先搜索的变异操作。与传统遗传算法以及其他学者的改进算法进行了对比实验。实验结果表明:算法能够在保证正确率的前提下

提高计算速度

并且在多目标的环境下同样适用。

Abstract

To improve the performance of genetic algorithms for path planning in games

an improved genetic algorithm is proposed. A way to estimate the optimal population size is used. New genetic operators based on elitist strategy is designed. A mutation method based on heuristic depth-first search is introduced. The proposed algorithm is compared with the traditional genetic algorithm and the improved algorithms proposed by other researchers to show the validity of the algorithm. Experimental results prove that the proposed algorithm can shorten the running speed of the algorithm while assuring success rate and it is also effective in multi-objective environment condition.

关键词

Keywords

references

基于多智能体遗传算法的战术航段优化 [J]. 饶卫平,杨任农,雷晓义,柴毅哲. 传感器与微系统 . 2016(03)

基于多目标遗传算法的游戏路径规划研究 [J]. 刘大瑞,冯镍. 软件导刊 . 2014(01)

游戏引擎最短路径搜索优化遗传算法设计 [J]. 黎忠文,覃志东,王全宇,倪仲余. 计算机应用研究 . 2014(01)

基于贪心算法和遗传算法的仓储车辆调度算法 [J]. 王友钊,彭宇翔,潘芬兰. 传感器与微系统 . 2012(10)

基于量子遗传算法的无线传感器网络路由研究 [J]. 唐义龙,潘炜,李念强,廖一尔,徐明峰. 传感器与微系统 . 2011(12)

基于遗传算法的最短路径问题求解 [J]. 康晓军,王茂才. 计算机工程与应用 . 2008(23)

基于遗传算法的移动机器人动态路径规划研究 [J]. 王海英,蔡向东,尤波,张礼勇. 传感器与微系统 . 2007(08)

游戏编程中的寻路算法研究 [J]. 付朝晖,丁梦,喻昕. 湖南工业大学学报 . 2007(04)

一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A * 算法的比较 [J]. 李擎,谢四江,童新海,王志良. 北京科技大学学报 . 2006(11)

基于遗传算法的最短路径路由优化算法 [J]. 孙宝林,李腊元,陈华. 计算机工程 . 2005(06)

基于改进遗传算法的机器人路径规划 [J]. 段俊花,李孝安. 微电子学与计算机 . 2005(01)

An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph [J] . Jaesung Lee,Dae-Won Kim. Information Sciences . 2016

An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots [J] . Hong Qu,Ke Xing,Takacs Alexander. Neurocomputing . 2013

An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems [J] . Linzhong Liu,Haibo Mu,Xinfeng Yang,Ruichun He,Yinzhen Li. Applied Soft Computing Journal . 2011 (1)

A genetic algorithms to solve the bicriteria shortest path problem [J] . Cheikh Mohamed,Jarboui Bassem,Loukil Taicir. Electronic Notes in Discrete Mathematics . 2010

Views

217

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on path planning for target tracking process based on genetic algorithm

Research on dynamic path planning of mobile robot based on genetic algorithm

Enhanced egret swarm optimization algorithm for robot path planning

Path planning for guide robot based on improved bitterling fish optimization algorithm

Improved RRT algorithm for manipulator path planning based on dynamic probability sampling

Related Author

JU Cheng-en

ZHAO Xiao-xia

WANG Ming-xing

LI Zhen-hong

WANG Hai-ying1

CAI Xiang-dong1

YOU Bo1

ZHANG Li-yong2

Related Institution

Faculty of Information Engineering and Automation,Kunming University of Science and Technology

School of Automation,Harbin University of Science and Technology

School of Measurement-Control Technology and Communications Engineering,Harbin University of Science and Technology

School of Electrical Engineering,Guangxi University

School of Automation,Nanjing University of Information Science & Technology

⁰