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

九夜神尊

计算量并不大。可以说是很小。
你们那些公式我不懂，不过我给你讲一下过程你就有感觉了。
就光说遍历吧这是很蛋疼的东西从左上角开始向主角1格一格的判断，当遇到第一个障碍，则前面的全部不可见，然后接着向主角，一直当碰到主角，然后最后一组为可见，如果查看过程中有已经确定的，就直接计算下一格。这样顺着屏幕计算一周，也就是周长。
你说有多大的计算量|
80*80才320次计算。

a1072126939

逮究吥（日：没关系）。在刀塔的视野里也是如此，要做到完美角度战争迷雾效果实在系灰常困难，再者多注意一下地图画法吥就ok了。

Kimu

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

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

Kimu

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

说真的,我没看懂,

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

九夜神尊

假设左上角为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

今天想了想……可以用空间换时间的方法达到基本线性的视野判定。
不过我想先吐槽一句……O(n)是不可能的，因为视野格子数本身就成平方关系。
工程量很大（主要是分数计算很烦），所以等寒假再扔工程吧>_<

禾西

這是我的意見：

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

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

一次的計算量大概是 3n

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

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

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

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

越前リョーマ

按照人来讲，当然是从主角位置发出射线，经过障碍物的两边端点，然后那范围之类的看不见 = =
不过感觉不管怎么做都好鸡肋囧

九夜神尊

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

Kimu

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

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

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