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

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

IamI · 发表于 2011-12-31 20:59:22

中心点的连线不经过障碍格，怎样？不过实现上可能有困难……

Kimu · 发表于 2011-12-31 21:05:35

本帖最后由 Kimu 于 2011-12-31 21:05 编辑

IamI 发表于 2011-12-31 20:59
中心点的连线不经过障碍格，怎样？不过实现上可能有困难……

如果每一个都去计算的话,一旦视野和障碍物都很多的时候,计算量会很大,
不说编程复杂度,估计要想不卡帧还得多帧计算

各种压力的猫君 · 发表于 2011-12-31 21:47:04

不考虑主角的朝向么……

Kimu · 发表于 2011-12-31 22:03:02

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

主角的转身时间视为瞬时,不考虑

IamI · 发表于 2011-12-31 22:27:34

其实只算两个角，拒绝掉几个点，避免实数运算可以达到秒出的效果的（目测

九夜神尊 · 发表于 2012-1-3 11:29:24

每一个格子和主角连线测试。然后看是否经过障碍物。，这种东西简单的跟1一样。
什么，你说光是格子看起来不爽?想要平滑，我最喜欢用四叉树了，具体怎么整不详谈。
你想要高效算法的话。
就是可以先从主角出发四面扩张可见区域，遇到障碍物的话判断，障碍物在主角偏上，则上方争议下方可见，其他方向类推。这样就算出来一大片了，
然后就是遍历连线了，虽然不是最优。

说一个效率测试
当年我写了一个无优化的视野系统，每秒重复计算30次的锤子，结果全屏毫无卡针现象。

Kimu · 发表于 2012-1-3 22:09:58

九夜神尊发表于 2012-1-3 11:29
每一个格子和主角连线测试。然后看是否经过障碍物。，这种东西简单的跟1一样。
什么，你说光是格子看起来不 ...

每秒计算30次就是两帧一次了?
朴素算法的话是O(n^2)吧,你的n是多大的?

九夜神尊 · 发表于 2012-1-3 22:29:01

Kimu 发表于 2012-1-3 22:09
每秒计算30次就是两帧一次了?
朴素算法的话是O(n^2)吧,你的n是多大的?

我只是表示这种算法并不会导致卡帧现象，实际操作中只有主角坐标改变了才进行计算。
然而我每2帧计算一次都不会卡。

仅此而已1111

Kimu · 发表于 2012-1-3 22:42:15

本帖最后由 Kimu 于 2012-1-3 22:43 编辑

九夜神尊发表于 2012-1-3 22:29
我只是表示这种算法并不会导致卡帧现象，实际操作中只有主角坐标改变了才进行计算。
然而我每2帧计算一次 ...

......我想知道一次计算量多大

而且没有非O(c)算法是不会卡帧的,随着参数的增大,必然会导致卡帧

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

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

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

点评

点评

开拓者

贵宾