游戏开发论坛

 找回密码
 立即注册
搜索
查看: 5160|回复: 12

关于寻路算法的问题

[复制链接]

87

主题

790

帖子

806

积分

高级会员

Rank: 4

积分
806
QQ
发表于 2007-7-5 01:51:00 | 显示全部楼层 |阅读模式
首先先说明关于策划行军部分的描述:
(1)移动
部队可以向与自己所在格同行或同列的邻移动。任何两个部队都不能同处一个格子中。
在军队或运输队命令菜单中选择移动命令后,鼠标若置于可移动的格子切该格没有部队,鼠标旁出现一个去字;若该格有己部队,出现跟字;若有敌部队,出现攻字;若置于不可移动或本部队所在格,出现一个X。鼠标旁出现X时,按下鼠标没有反应;否则,运行寻路AI。在AI选择的路径的每一格的中心显示一个小圆点(直径5像素左右),若鼠标再在其他地方按下,重新运行AI并显示路径。若与上次在同一个格子内按下,即为选定目标,命令完毕,部队状态变为移动,生成移动点参数(值为0)。若所选的目标格没有部队,将AI选择的格子的坐标依次存入部队的目标1、目标2……中。若有部队,则将目标部队编号存入本部队的目标属性。
以固定格为目标的,进行后,部队每日增加移动点2,待部队移动点达到当前所在格的离开点数时,移动点减去当前格的离开系数值,部队向目标1移动。这时,部队所在坐标变为原来的目标1坐标,目标1变为原来的目标2……类推。
以部队为目标的,待本部队移动点达到所在格的离开系数后,再运行寻路AI,向重新选择的目标1移动。每次移动都如此(此类移动的部队永远无法到达自己的最终目标)。
如果部队移动点达到当前格的离开系数,而目标1的格子有部队或其他原因不能移动进去。如目标1是最终目标:部队原地不动;如目标1不是最终目标:则将目标1的格子视为禁止格,重新运行寻路AI,然后再移动。如果没有其他路径可走,部队原地不动--千万不要回头!
如果两部队将在下一日到达同一格,随机一个部队移动,另一个部队的情况就是目标1有部队的情况。
部队到达目标或玩家命令停止,移动结束,状态改为无,移动点参数清0,目标属性取消。

关于寻路AI的说明见附件

sf_20077515118.doc

50 KB, 下载次数:

87

主题

790

帖子

806

积分

高级会员

Rank: 4

积分
806
QQ
 楼主| 发表于 2007-7-5 01:54:00 | 显示全部楼层

Re:关于寻路算法的问题

逻辑部分说明:分为移动循环和寻路两个函数,移动次数即移动步数,寻路的目的是为了寻找一个从源地到目的地中的花费移动点最小的路线.
移动循环(目标坐标)
是否找到=否
坐标集清空
do
移动点加1
寻路(源坐标,目标坐标,移动点,移动次数)
loop 当是否找到为否时

寻路(源坐标,目标坐标,移动点数,移动次数)
当是否找到为否时
向上:
如果地图在坐标范围内
如果该坐标是可移动的
如果坐标不是当前要移动部队的坐标
如果坐标的移动点数小于参数中的移动点数
检查坐标集中是否存在该坐标,如果存在结束本次判断
根据移动次数删除坐标集中的坐标
坐标集增加该坐标
如果该坐标为目标坐标,则是否找到为真,退出整个寻路,如果不是目标坐标,则运行
寻路(该坐标,目标坐标,参数的移动点数-该格的移动点数,参数的移动次数+1)
向下:处理同向上
向左:处理同向上
向右:处理同向上

所得坐标集为所寻的路

87

主题

790

帖子

806

积分

高级会员

Rank: 4

积分
806
QQ
 楼主| 发表于 2007-7-5 01:59:00 | 显示全部楼层

Re:关于寻路算法的问题

这种算法的问题有二,一是速度慢;二是最严重的问题,如果从源地到目的地找不到路线的话,程序会陷入死循环,因为在移动循环函数中,一旦找不到路线,移动点数就会加1再继续,但是无论怎么加也找不到路线

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2007-7-5 11:07:00 | 显示全部楼层

Re:关于寻路算法的问题

寻路是游戏中的基本算法问题之一。

两年前我在这里发算法讨论,结果LZ认为不实际,游戏之家认为没用。

当时就讨论过关于寻路算法的问题,LZ可以自己翻翻老帖子。

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2007-7-5 11:12:00 | 显示全部楼层

Re:关于寻路算法的问题

寻路的本质是搜索。

你如果了解了DFS和BFS基本上就可以解决一般的寻路问题了。

现在一般的寻路算法都是各种优化过的A*算法,网上太多了。

大概看了一下你的算法描述,就是DFS,速度是比较慢,因为没有使用启发式搜索,搜索过程是盲目的。
而且得到的结果一般不会是最优的,最优(最短路径)要使用BFS搜索。

关于死循环什么的,我没说了,你自己练一练简单的递归习题吧。


我一直坚持观点:做游戏程序,一个好的算法基础是有必要的。

87

主题

790

帖子

806

积分

高级会员

Rank: 4

积分
806
QQ
 楼主| 发表于 2007-7-5 11:33:00 | 显示全部楼层

Re: Re:关于寻路算法的问题

sandy_zc_1: Re:关于寻路算法的问题

寻路是游戏中的基本算法问题之一。

两年前我在这里发算法讨论,结果LZ认为不实际,游戏之家认为没用。

当时就讨论过关于寻路算法的问题,LZ可以自己翻翻老帖子。

我并不是说寻路算法没用,而是你以前贴子里都是竞赛式题目,虽然题目是用到所学知识,但是题目本身数学性太强了,在游戏中很难实际用到.关于算法,我的观点是要以游戏为背景而不是以数学为背景,这样才能更贴近实际.

87

主题

790

帖子

806

积分

高级会员

Rank: 4

积分
806
QQ
 楼主| 发表于 2007-7-5 11:38:00 | 显示全部楼层

Re:关于寻路算法的问题

至于你所说的算法基础,我是这么认为的,我不赞成在做游戏之前整天抱着书啃算法,等啃透了再来做游戏,这样是枯燥无味,做游戏的热情很早就会被打击没了.我提倡的是在做游戏过程中学习算法,这样一方面更容易学,另一方面也没有那么枯燥无味.再说业余时间本来就是有限的,不可能有那么多时间专门研究算法,只要把游戏中用到的掌握了就行.

1

主题

7

帖子

7

积分

新手上路

Rank: 1

积分
7
发表于 2007-7-5 14:49:00 | 显示全部楼层

Re:关于寻路算法的问题

数学式的东西 作用确实不大…… 理论结合实际 才是王道阿

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2007-7-5 21:11:00 | 显示全部楼层

Re:关于寻路算法的问题

我从来没有让谁整天抱着书啃算法,除了那些搞竞赛的。

我当初发那些的目的是为了营造一个研究学习算法的氛围,而且那些题都是很基础的,里面涉及到的算法在之后都是很有用的。并不是什么数学性很强的不实用的题。有些基础知识还是需要具备的,之后碰到什么问题可以很快反应过来至少知道该向哪个方向做。


好啦关于之前观点的争论就到此为止吧,关于你的要求我建议你去看看搜索方面的算法,首先就是DFS,然后看看A*,以及它的优化。启发式搜索很关键。


你可以根据自己的需要尝试不同的启发函数,确定一个最适合自己游戏的,这个当然要练了。

15

主题

2093

帖子

2093

积分

金牌会员

Rank: 6Rank: 6

积分
2093
发表于 2007-7-5 22:31:00 | 显示全部楼层

Re: Re: Re:关于寻路算法的问题

陈?: Re: Re:关于寻路算法的问题


我并不是说寻路算法没用,而是你以前贴子里都是竞赛式题目,虽然题目是用到所学知识,但是题目本身数学性太强了,在游戏中很难实际用到.


既然不了解这些算法,那从何得出“很难在实际中用到”这样的结论……

或者说干脆就是这样的观点:“我不会的算法,肯定就是用不到的”?

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2026-1-25 22:15

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表