搜索
查看: 1853|回复: 4

于寻路算法的问题

[复制链接]
2007-7-5 02:10:48

主题

好友

1008

积分

太守

首先先说明关于策划行军部分的描述:
(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的说明见附件
回复 举报
2007-7-5 02:16:04

主题

好友

1008

积分

太守

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

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

所得坐标集为所寻的路
回复 举报
2007-7-5 02:18:08

主题

好友

1008

积分

太守

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

主题

好友

136

积分

亭长

do
移动点加1
寻路(源坐标,目标坐标,移动点,移动次数)
如果 移动点 大于  "N"  那么 离开 LOOP 'N根据地图大小而定
loop 当是否找到为否时
回复 举报
2007-7-26 10:53:59

主题

好友

569

积分

县令

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

第二种情况除非地图有问题,比如说
A1111
11000
110B0
11000

从A都B,但其实B是进不去的,电脑就会死。除此之外,不可能会死。
回复 举报

本版积分规则

Archiver|手机版|Langya.Org ( 浙ICP备05062527号-1 )

GMT+8, 2022-10-8 05:21 , Processed in 0.063177 second(s), 21 queries .

Powered by Discuz! X3.4 Licensed © 2001-2012 Comsenz Inc. Design by 360cd.cn

返回顶部