设为首页收藏本站|繁體中文

Project1

 找回密码
 注册会员
搜索

SRPG 格子的算法

查看数: 3022 | 评论数: 2 | 收藏 0
关灯 | 提示:支持键盘翻页<-左 右->
    组图打开中,请稍候......
发布时间: 2015-12-9 21:50

正文摘要:

本帖最后由 枫の叶 于 2015-12-10 16:12 编辑   最近在弄一个SRPG游戏脚本,角色移动需要在地图上绘出移动范围的格子。 已知角色坐标 x, y ,角色最大移动距离 6 格 。 求计算出在这个距离内,角色 ...

回复

myownroc 发表于 2016-1-16 22:04:26
帖子有讨论价值于是挖个坟(如有讨论请点评)


寻路/移动范围的算法通常可以参考图的广度优先(百度搜索“广度优先”的结果适用于更一般的图,初学者看起来比较吃力)。
具体思路就是不断搜索待搜索节点周围的节点直至满足约束条件搜索结束。


首先要有一个列表openlist,用来储存待搜索的节点。
当然还要有closelist列表,储存已搜索的节点。
最初,这两个表都是空的。

一开始,往openlist里塞进起点。
以下是核心
从openlist里拎出一个节点设为当前节点,
寻找周围尚未搜索(即closelist均无的节点)并可以到达的节点。
如果周围的点存在于openlist,则要判断如果从当前节点到达该点是否更省力,如果是则修改该点的消耗。
将找到的点塞进openlist,并记录各个点的消耗。
当openlist为空时,中断循环;否则,以上循环。
核心结束

来张图助助兴……

注释:
图1:紫色为起点,执行第一次循环后的结果。红色表示openlist的点,绿色钩表示closelist已经存在该点;
图2:新的一轮循环。3号图块由于已经存在于closelist,故未添加至openlist;
图3:若干次循环后;
图4:由于灰色块不可到达,故也没有添加至openlist。

点评

说实话,楼主截图里的移动范围生成的并不是很好。  发表于 2016-1-16 22:05
RyanBern 发表于 2015-12-9 23:39:54
本帖最后由 RyanBern 于 2015-12-10 00:13 编辑

首先我要问一下「角色不能到达的坐标」的含义,按照我的理解,你所给出的图最上方那个位置虽然可以通行,但是角色只能绕过限制的区域然后到达,这个位置就是所谓不可到达的地方。或者,角色上方有一条很细的墙,长度超过了13,那么墙上方的位置应该视为不可到达。
如果我的理解正确,那么建议你使用bfs方法,具体请在技术区搜索我的帖子「dijkstra算法在地图上的应用」(名字可能不准确,但是前面dijkstra算法这几个字应该有),那里面有详细的算法说明。值得注意的是,由于楼主只需要搜索的部分,所以算法中有关寻路的地方都可以去掉,换句话说,这种情况只需要进行bfs6层即可。具体细节如果不太清楚,等我电脑修好之后再详细回答。

点评

电脑坏了是不用修的,越修越容易坏,直接换新的。  发表于 2015-12-10 16:13
拿上你的纸笔,建造一个属于你的梦想世界,加入吧。
 注册会员
找回密码

站长信箱:[email protected]|手机版|小黑屋|无图版|Project1游戏制作

GMT+8, 2024-11-23 08:37

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

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