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

Project1

 找回密码
 注册会员
搜索
查看: 2685|回复: 2

[推荐问答] SRPG 格子的算法

[复制链接]

Lv2.观梦者

梦石
0
星屑
451
在线时间
228 小时
注册时间
2015-2-23
帖子
241
发表于 2015-12-9 21:50:08 | 显示全部楼层 |阅读模式

加入我们,或者,欢迎回来。

您需要 登录 才可以下载或查看,没有帐号?注册会员

x
本帖最后由 枫の叶 于 2015-12-10 16:12 编辑

  最近在弄一个SRPG游戏脚本,角色移动需要在地图上绘出移动范围的格子。
Image 001.jpg

已知角色坐标 x, y ,角色最大移动距离 6 格 。
求计算出在这个距离内,角色能移动到的所有坐标,并剔除角色本身坐标和地图不通行的坐标,以及角色不能到达的坐标。
  本来自己弄了一个,觉得有点臃肿,求更精简的算法。

评分

参与人数 2星屑 +135 收起 理由
myownroc + 100 推荐回答
RyanBern + 35 手动认可奖励

查看全部评分

制作XP特效,找我。

Lv4.逐梦者 (版主)

梦石
0
星屑
9467
在线时间
5073 小时
注册时间
2013-6-21
帖子
3580

开拓者贵宾剧作品鉴家

发表于 2015-12-9 23:39:54 | 显示全部楼层
本帖最后由 RyanBern 于 2015-12-10 00:13 编辑

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

点评

电脑坏了是不用修的,越修越容易坏,直接换新的。  发表于 2015-12-10 16:13
回复 支持 反对

使用道具 举报

Lv3.寻梦者

梦石
0
星屑
2739
在线时间
2629 小时
注册时间
2013-1-16
帖子
5657

贵宾

发表于 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
(Created by @喵kano)


施工现场:hotege.github.io
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

拿上你的纸笔,建造一个属于你的梦想世界,加入吧。
 注册会员
找回密码

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

GMT+8, 2024-3-29 18:03

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

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