【讨论】关于视野判定这种东西

Kimu · 发表于 2011-12-31 20:02:19

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

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

x

本帖最后由 Kimu 于 2012-1-7 16:10 编辑

===========================
一些符号(均来自于RMVX):
稻草人:主角
岩石:障碍物
海洋:只要主角位置及视野不变,他一辈子也看不到的地方
草地:确信无疑,没有太多争议的可见视野
小路:确信无疑,没有太多争议的不可见视野
雪地:争议视野
===========================
注意:

Q:各种压力的猫君发表于 2011-12-31 21:47
不考虑主角的朝向么……

A:主角的转身时间视为瞬时,不考虑
===========================
在制作一些RPG(例如ARPG,SRPG)时,有时会碰到一种叫做视野的东西

下面是一种很常见的方格类视野判定(视野为4个单位(单位下文省略))

当我们在主角周围加一些岩石之后,视野变成了这样(视野为3)

但是一旦视野增大,比如增大到5,就出现了几个争议地区(为了表达清楚,我特意增加了2,视野为4时也会有一些争议地区,这里不作考虑)

而且如果障碍物不是在主角正斜对面的话,会出现更多的争议地区(视野为5)

求讨论一种更为普遍的视野判定方式

===========================

Kimu:一种方法是人为制定,定义一系列的规则然后判定任何一个点是否可见
或者使用计算几何,但是由于每一个方格都有大小,这个视野的出发点以及目标点是否可见如何判定,仍然需要制定

viktor · 发表于 2012-5-30 16:14:21

这个是自己凹的办法……果然不科学
不过效率上应该不差。我先熟悉下Tilemap这个类吧。

我也想看看War3的视野判定。求资料啊

Kimu · 发表于 2012-5-30 11:47:51

本帖最后由 Kimu 于 2012-5-30 11:48 编辑

viktor 发表于 2012-5-30 11:15
我更倾向于用17楼@禾西的办法，递推。
分四个方向，一个格子的不透明度是相邻两个格子的平均数。墙的不透 ...

思想是很好的,但是还是存在不科学的地方,

不透明度下限的值不好取,比如说最靠左下角的那个"64"理论上是无法被猪脚看到的,但是却会显示.
而该点右上方的80乃至88也应该是被一个竖直墙挡住了而看不见,
所以这个方法还是要修改一下(我暂时没有什么思路)

理论上还是直线最靠谱,以距离判定不透明度,
或许我应该去看看war3的视野判定

viktor · 发表于 2012-5-30 11:15:35

本帖最后由 viktor 于 2012-5-30 11:21 编辑

我更倾向于用17楼@禾西的办法，递推。
分四个方向，一个格子的不透明度是相邻两个格子的平均数。墙的不透明度按照0算。然后当不透明度小于一个固定值（比如60）的时候，就认为他看不见了。

再加上修改Tilemap 给格子加上一个透明度，就能实现更加自然的Tilemap了
至于哪些是墙哪些是地面可以通过地图标记，方便地制定

像这个样子
红色的是墙（墙体显示出来，背后的东西不会显示），
黄色的是竖直墙（墙体和在其上方的墙体要显示出来，但是背后的东西不会显示）
绿色的是可以通行的地方
数字是透明度（亮度）

缺点是没法并行，只能一点点推过去

当然@kimu 直接按照直线计算似乎也不错最近有时间的话希望能把两个都实现以下。
我想参考下楼主的脚本呢

chd114 · 发表于 2012-5-28 14:00:46

魔塔样板直接采用事件+图片，只涉及到少量脚本但是视野范围有问题（方格范围，1*1、3*3、5*5、7*7···）

Kimu · 发表于 2012-1-7 16:10:07

测试完毕,的确不会有任何卡,即使不优化视野调到10也不会有任何卡

工程很乱就不发了

Kimu · 发表于 2012-1-7 00:10:20

本帖最后由 Kimu 于 2012-1-7 00:10 编辑

九夜神尊发表于 2012-1-6 23:30
从来都是讲只枚举边上的线。
为什么我不会建议你去判断一个点是否已经被判断过了，然后再运算呢？

正在写,刚才把一个简略的地图类写完了,主角移动也解决了,不早了,明天来晚上算法,看看时间效率

p.s.我对帧的时间及计算量效率不是很清楚

九夜神尊 · 发表于 2012-1-6 23:30:05

Kimu 发表于 2012-1-6 22:02
@IamI
哎?我好像没说过我想要一个O(n)的,原来我想的是看看有没有比O(n^2)低的算法,现在发现好像不可能实现 ...

从来都是讲只枚举边上的线。
为什么我不会建议你去判断一个点是否已经被判断过了，然后再运算呢？

因为运算量比一个if语句还要小。

Kimu · 发表于 2012-1-6 22:02:39

本帖最后由 Kimu 于 2012-1-7 12:55 编辑

@IamI
哎?我好像没说过我想要一个O(n)的,原来我想的是看看有没有比O(n^2)低的算法,现在发现好像不可能实现

@九夜神尊
我原来是想的爆搜每个点,和主角位置连起来,计算所得直线的斜率,然后每次计算的数值四舍五入确定方格坐标,如果有障碍则这个点不可见,借鉴了你的算法之后我觉得可以改进一下,只枚举边界点,与中心连线,从中心向外扩散试试,这个周末我试试把它写出来

@禾西你到最后还是没把不确定点的确定方案给出来......

九夜神尊 · 发表于 2012-1-6 20:18:08

不用想了，没有比我提出的方法更优化的，不过我那方法改一下，就是从主角往边上发射线更快。
计算量（长＋宽）的平方最坏的情况，每次计算量极小，每次只有一个简单的赋值。不牵扯任何math函数。

帐号		自动登录	找回密码
密码			注册会员

[已经解决] 【讨论】关于视野判定这种东西

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

点评

评分

点评

开拓者

贵宾