4 ms·
Related: 1) a tutorial on the same topic by Red Blob Games: http://www.redblobgames.com/articles/visibility/ http://www.redblobgames.com/articles/visibility/
by dllu 13y ago
Related:
1) a tutorial on the same topic by Red Blob Games: http://www.redblobgames.com/articles/visibility/ 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/ 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 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.
- a1k0n 13y agoI 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.
- frownie 13y agoI 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... :-) )