I think the demo at the top is pretty good but the description of the algorithm is mediocre. I want to improve that.
- [x] Show the polar coordinate version of the map. As we sweep across angles in the main map, we're sweeping left to right in the polar coordinate version. As we pick the closest segment in the main map, we're picking the lowest radius in the polar coordinate version. See the Skyline Problem link at the bottom of the page for what it'd look like. Abandoned — tried it but didn't think it added enough to understanding the algorithm
- [ ] Note that expanding circle algorithm is easiest to see in polar coordinates. The regular algorithm sorts by angle, then distance, and the alternate algorithm sorts by distance, then angle.
- [ ] Explain how to intersect the output with a triangle if you want to limit visibility to the direction the player is facing. Alternatively, scan a smaller angular range.
- [ ] Explain the implementation detail about sorting start/stop endpoints correctly so that adjacent edges behave properly.
- [ ] Explain the implementation detail about NOT stopping the ray at the first line segment, but extending it to the first "open" line segment after the current one is closed.
- [ ] Eliminate second pass by building initial list of segments that cross 0° line.
- [ ] List alternative algorithms: 1. shadow areas instead of visible areas. 2. union-find based incremental algorithm. Note that some of these depend on whether your map is large relative to the visible area. 3. The HN/Reddit discussions also pointed to BSPs. 4. Expanding circle that meets each endpoint sorted by distance.
- [ ] The main idea is sweeping. This is useful in other things, like collision detection and voronoi.
- [ ] Add more demos of stealth-like games. Visibility, lighting, grenades, etc. could demonstrate each additional concept.
- [ ] Maybe implement all the algorithms on http://en.wikipedia.org/wiki/Visibility_polygon
- [x] Update code to use Haxe 3
- [x] Update code to not use structural types, so that Java and C# outputs are cleaner
- [x] Include Java and C# outputs as part of build/download process
- [ ] Investigate bug reported here: http://www.redblobgames.com/articles/visibility/#comment-1281596922
- [ ] Also see beam casting: http://sadumbrella.blogspot.se/2010/11/beamcasting.html
- [ ] Also see 2d shadow casting in gpu: http://minimal.sh/shadow-mapping-in-two-dimensions/
- [ ] Extension: backface culling to skip line segments that will never be needed.
- [ ] Extension: line segments can be replaced by polylines