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

Kimu

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

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

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

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


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


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


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


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

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

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

Kimu

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

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

Kimu

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

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

Kimu

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

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

Kimu

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

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

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

Kimu

a1072126939 发表于 2012-1-4 06:43
逮究吥（日：没关系）。在刀塔的视野里也是如此，要做到完美角度战争迷雾效果实在系灰常困难，再者多注意一 ...

困难提出来了就要挑战,没有解决不了的困难

Kimu

九夜神尊 发表于 2012-1-4 02:14
计算量并不大。可以说是很小。
你们那些公式我不懂，不过我给你讲一下过程你就有感觉了。
就光说遍历吧这是 ...

说真的,我没看懂,

从左上角开始向主角判断?怎么走的?

Kimu

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

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

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

Kimu

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

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

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

Kimu

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

工程很乱就不发了