Oh...

#6013 posted by

metlslime on 2009/08/26 00:14:15

and as for the question of why vis takes so long...

First, imagine shaking hands with everyone in the room. With a room of 10 people, there are 90 handshakes needed. With 100 people, there are 9900 handshakes needed. So the cost of adding a person is greater with more people already in the room, it's not linear.

Vis is even worse than that, though....

Imagine you have to pass notes to everyone in the room. If people are far away your note has to be passed between many people to get to the recipient. So in a room of 10 people, 90 notes need to be passed, but each note requires an average of (say) 5 passes, that's 450 passes.

With 100 people, that's 9900 notes to pass, with an average of 50 passes per note, for 495000 passes.

Okay, but Vis is even worse than that....

Now imagine you need to send a note to everyone in the room and you need to send a copy of that note through every possible route that connects you to the recipient. That's pretty much what vis does.

This exponential growth far outpaces the geometric growth of CPU power in the last twelve years.

This is why vis seems best suited for smaller, less detailed, less open maps. The exponential growth can take something that seems trivial (2 minute vis) and turn it into something insane (200 hour vis) over a relatively small growth in map complexity (say, 4x the geometric details.)

Big O Notation

#6014 posted by

Preach on 2009/08/26 00:14:53

For people who know some computer science, particularly complexity theory, it's worth considering just how complex vis is to process. If you have n leafs, then you need to make n*n visibility tests. But don't be fooled into thinking that makes it O(n^2).

The problem is that one visibility test consists of seeing if ANY of the other n-2 leafs lie in-between the two leafs you are testing. The two bits of good news:

1) If you find any leaf which totally separates the two leafs, then you can stop. Obviously this is more beneficial in maps where line-of-sight is blocked.

2) You only need to look as far as the common node of the two leafs in the bsp tree. Anything on the other side of the separating plane at the node above can't come between the two leafs you are testing.

The latter point is helpful for leafs which are close together, as it should mean that they also near on the bsp tree. However, the problem for open maps in 1) is made worse by 2). Once you start having two leafs which can see each other from a great distance away, you have a huge chunk of the bsp to test in order to verify that they can see each other, and you have to test it all.

So I think in the worst case, like a big open subdivided cube where every leaf sees every other one, you have to conclude that vis is O(n^3), which is why it gets so much longer as you make the maps larger. In the worst case, that means doubling vis time every time you increase the leafs by 25%.

*Disclaimer: I did not refer to any of the source code for the above code, it's all just off the top of my head, so correct me if anything is inaccurate*