Project1

标题: 【讨论】关于视野判定这种东西 [打印本页]
作者: Kimu    时间: 2011-12-31 20:02
标题: 【讨论】关于视野判定这种东西
本帖最后由 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
中心点的连线不经过障碍格，怎样？不过实现上可能有困难……
作者: Kimu    时间: 2011-12-31 21:05
本帖最后由 Kimu 于 2011-12-31 21:05 编辑
IamI 发表于 2011-12-31 20:59
中心点的连线不经过障碍格，怎样？不过实现上可能有困难……


如果每一个都去计算的话,一旦视野和障碍物都很多的时候,计算量会很大,
不说编程复杂度,估计要想不卡帧还得多帧计算
作者: 各种压力的猫君    时间: 2011-12-31 21:47
不考虑主角的朝向么……
作者: Kimu    时间: 2011-12-31 22:03
各种压力的猫君 发表于 2011-12-31 21:47
不考虑主角的朝向么……

主角的转身时间视为瞬时,不考虑
作者: IamI    时间: 2011-12-31 22:27
其实只算两个角，拒绝掉几个点，避免实数运算可以达到秒出的效果的（目测
作者: 九夜神尊    时间: 2012-1-3 11:29
每一个格子和主角连线测试。然后看是否经过障碍物。，这种东西简单的跟1一样。
什么，你说光是格子看起来不爽?想要平滑，我最喜欢用四叉树了，具体怎么整不详谈。
你想要高效算法的话。
就是可以先从主角出发四面扩张可见区域，遇到障碍物的话判断，障碍物在主角偏上，则上方争议下方可见，其他方向类推。这样就算出来一大片了，
然后就是遍历连线了，虽然不是最优。

说一个效率测试
当年我写了一个无优化的视野系统，每秒重复计算30次的锤子，结果全屏毫无卡针现象。
作者: Kimu    时间: 2012-1-3 22:09
九夜神尊 发表于 2012-1-3 11:29
每一个格子和主角连线测试。然后看是否经过障碍物。，这种东西简单的跟1一样。
什么，你说光是格子看起来不 ...

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

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

仅此而已1111
作者: Kimu    时间: 2012-1-3 22:42
本帖最后由 Kimu 于 2012-1-3 22:43 编辑
九夜神尊 发表于 2012-1-3 22:29
我只是表示这种算法并不会导致卡帧现象，实际操作中只有主角坐标改变了才进行计算。
然而我每2帧计算一次 ...


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

而且没有非O(c)算法是不会卡帧的,随着参数的增大,必然会导致卡帧
作者: 九夜神尊    时间: 2012-1-4 02:14
本帖最后由 九夜神尊 于 2012-1-4 02:56 编辑

计算量并不大。可以说是很小。
你们那些公式我不懂，不过我给你讲一下过程你就有感觉了。
就光说遍历吧这是很蛋疼的东西从左上角开始向主角1格一格的判断，当遇到第一个障碍，则前面的全部不可见，然后接着向主角，一直当碰到主角，然后最后一组为可见，如果查看过程中有已经确定的，就直接计算下一格。这样顺着屏幕计算一周，也就是周长。
你说有多大的计算量|
80*80才320次计算。
作者: a1072126939    时间: 2012-1-4 06:43
逮究吥（日：没关系）。在刀塔的视野里也是如此，要做到完美角度战争迷雾效果实在系灰常困难，再者多注意一下地图画法吥就ok了。
作者: Kimu    时间: 2012-1-4 12:04
a1072126939 发表于 2012-1-4 06:43
逮究吥（日：没关系）。在刀塔的视野里也是如此，要做到完美角度战争迷雾效果实在系灰常困难，再者多注意一 ...

困难提出来了就要挑战,没有解决不了的困难
作者: Kimu    时间: 2012-1-4 12:06
九夜神尊 发表于 2012-1-4 02:14
计算量并不大。可以说是很小。
你们那些公式我不懂，不过我给你讲一下过程你就有感觉了。
就光说遍历吧这是 ...

说真的,我没看懂,

从左上角开始向主角判断?怎么走的?
作者: 九夜神尊    时间: 2012-1-4 15:21
假设左上角为0，0点，主角在8，4
那么连线就会经过0.0，1.0，2.1，3.1，4.2……8.4，以上小数为坐标，手机麻烦。具体这些数字咋算出来的，数学初中水平即可，从屏幕左上角开始和主角连线，假设到了4.2处有障碍，则0.0---4.2均不可见（可以考虑障碍物可见），
然后接着向主角连线，假设到了6.3又有障碍，则4.2---6.3不可见，然后继续往主角判断，最后到了主角坐标，则6.3一直到主角均可见。

这样算法从画面左上角到右上角，再到右下角，左下角，左上角，转一圈一张画面就好了。

其中可以优化，已经判断可不可见的地方可以不再次判断。
作者: IamI    时间: 2012-1-6 12:19
今天想了想……可以用空间换时间的方法达到基本线性的视野判定。
不过我想先吐槽一句……O(n)是不可能的，因为视野格子数本身就成平方关系。
工程量很大（主要是分数计算很烦），所以等寒假再扔工程吧>_<
作者: 禾西    时间: 2012-1-6 12:34
本帖最后由 禾西 于 2012-1-6 19:10 编辑

這是我的意見：

白色的圖塊是不確定的視覺點（位于可視與不可視之間）
綠色的圖塊可視，小麥色的圖塊不可視。

遍歷的方法是以原始點爲中心，逐步向四方向增長。一個點的可視度由夾角點的可視度決定。

一次的計算量大概是 3n

夾在兩個可視點之間的新節點設置為可視：

夾在兩個不可視點點之間的新節點設置爲不可視：

可視與不可視之間的是不確定點：

不確定點與不確定點之間的由斜方向的上一點確定：

作者: 越前リョーマ    时间: 2012-1-6 15:54
按照人来讲，当然是从主角位置发出射线，经过障碍物的两边端点，然后那范围之类的看不见 = =
不过感觉不管怎么做都好鸡肋囧
作者: 九夜神尊    时间: 2012-1-6 20:18
不用想了，没有比我提出的方法更优化的，不过我那方法改一下，就是从主角往边上发射线更快。
计算量   （长＋宽）的平方最坏的情况，每次计算量极小，每次只有一个简单的赋值。不牵扯任何math函数。
作者: Kimu    时间: 2012-1-6 22:02
本帖最后由 Kimu 于 2012-1-7 12:55 编辑

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

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

@禾西 你到最后还是没把不确定点的确定方案给出来......
作者: 九夜神尊    时间: 2012-1-6 23:30
Kimu 发表于 2012-1-6 22:02
@IamI
哎?我好像没说过我想要一个O(n)的,原来我想的是看看有没有比O(n^2)低的算法,现在发现好像不可能实现 ...

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

因为运算量比一个if语句还要小。
作者: Kimu    时间: 2012-1-7 00:10
本帖最后由 Kimu 于 2012-1-7 00:10 编辑
九夜神尊 发表于 2012-1-6 23:30
从来都是讲只枚举边上的线。
为什么我不会建议你去判断一个点是否已经被判断过了， 然后再运算呢？


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

p.s.我对帧的时间及计算量效率不是很清楚
作者: Kimu    时间: 2012-1-7 16:10
测试完毕,的确不会有任何卡,即使不优化视野调到10也不会有任何卡

工程很乱就不发了
作者: chd114    时间: 2012-5-28 14:00
魔塔样板直接采用事件+图片，只涉及到少量脚本但是视野范围有问题（方格范围，1*1、3*3、5*5、7*7···）
作者: viktor    时间: 2012-5-30 11:15
本帖最后由 viktor 于 2012-5-30 11:21 编辑

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

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

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

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

当然@kimu 直接按照直线计算似乎也不错 最近有时间的话希望能把两个都实现以下。
我想参考下楼主的脚本呢
作者: Kimu    时间: 2012-5-30 11:47
本帖最后由 Kimu 于 2012-5-30 11:48 编辑
viktor 发表于 2012-5-30 11:15
我更倾向于用17楼@禾西的办法，递推。
分四个方向， 一个格子的不透明度是相邻两个格子的平均数。墙的不透 ...


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

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

理论上还是直线最靠谱,以距离判定不透明度,
或许我应该去看看war3的视野判定
作者: viktor    时间: 2012-5-30 16:14
这个是自己凹的办法……果然不科学
不过效率上应该不差。我先熟悉下Tilemap这个类吧。

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



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1