Re:How to create 2D visibility/shadow effects for your game
by a1k0n on Tuesday March 11, 2014 @05:00PM
(#7382096)
I didn't see this mentioned in those articles, so I figured I'd mention it: If the level has a lot of geometry, you could also make a BSP tree, and then at runtime you'd just have an O(log n) lookup, plus an O(m log m) running of the same algorithm on a pruned subset of m vertices stored in the BSP node. Each BSP node would contain only the edges which can possibly be seen from a particular area. The tree might be kind of big, though.
Re:How to create 2D visibility/shadow effects for your game
by frownie on Wednesday March 12, 2014 @03:30AM
(#7384402)
I think this particular idea of storing information in the BSP leaves was the big innovation brought to us by Id Software. Now, the elephant in the room is : how to build a well balanced BSP tree... But well, that's an entirely different question (I was a computer geometry researcher years ago... :-) )
1) a tutorial on the same topic by Red Blob Games: http://www.redblobgames.com/articles/visibility/
2) a public domain Javascript visibility polygon library that runs in O(n log n), which is actually used in the Nothing to Hide game: https://code.google.com/p/visibility-polygon-js/
3) a blog post by author of said library discussing the algorithm: http://byronknoll.blogspot.ca/2013/05/on-log-n.html
Shooting a ray to every vertex and then naively computing intersections takes O(n^2) since there are n rays with up to O(n) intersections each. It is interesting to read and think about O(n log n) algorithms for computing the visibility polygon.