Probably the most head-scratching, frustrating feature I’ve tackled so far has been calculating line-of-sight. It’s something that can’t work 90% of the time, or fail on some edge cases. It has to work 100%. And that’s the part that kept me busy with the graph paper checking the math.
My first approach was to “walk the squares” out from the miniature and test collision with any walls encountered. This “marching squares” algorithm was working well and as expected, but it failed on corner cases. As the LOS rays traversed across the map, there were cases wherein the ray would miss potentially visible squares by passing precisely through the corner and ignoring the squares on either side. I spent a while trying different solutions, but none of them were satisfactory.
I moved on to casting rays from the miniature through the end points of each wall section to the edges to check for collision. The rays were then sorted by angle and the collision points connected to form visibility triangles. When considered all together, these triangles formed the potential visibility. Again it was failing on the edges. This time, rather than a miss, I was getting early rejection. The ray was intersecting the end of the wall segment and stopping. It was working well enough, unless the miniature was standing in a doorway or narrow opening between walls.
I tried a few a few tweaks: shortening the walls slightly at the end of the segments, tweaking the angle of the rays. None of these solutions were 100%. Finally, I settled on splitting the rays—guaranteeing that one ray would collide with a wall and the other, if it was open on one end, would slip past. This has doubled my ray count, but it should be a negligible difference once optimizations are in place. A linear increase is far more desirable than an exponential or logarithmic one.
In order to prevent the player from “peeking around corners,” the line-of-sight is only reset when the player drops the miniature and movement is restricted to those squares that are visible. There is still a slight issue. When a visibility triangle intersects a square, that entire square is visible. So the player can sometimes see slightly around corners. I have a couple of avenues to address this issue. Real-time shadows and render-to-texture are cleverly disabled in the free version of Unity, so with an upgrade to the Pro version this may no longer be a problem. Additionally, I have the triangles calculated. Those calculation are accurate and could be used to create a stencil, either for rejecting pixels at render, or for creating a projection mask for the spot light that hovers over the miniature.
I am contemplating revealing a 2D map for any squares that the player has already seen, but are not currently visible. This help prevent the player from getting lost. I only hope that it doesn’t spoil the dungeon feel that is achieved by only rendering part of the map. I’m also calculating visibility for 360 degrees around the player and not considering miniature facing. It will be trivial to do so and will likely be an option.
There are number of optimizations remaining. Primarily the walls for collision testing need to be sorted by proximity to the player. As it stands now, the routine runs at framerate for smaller maps, but slows to a crawl on large maps. For now, it is functional and, as I like to say, “I’ll burn that bridge when I come to it.”
Unity-LOS-debug from C. Lewis Pinder on Vimeo.
Unity-LOS from C. Lewis Pinder on Vimeo.
That’s a lot of progress and overall the decisions seem sound. On the mapping thing I have two comments.
One. Make is a checkbox option. I think auto-mapping is one of those pen and paper religious issues. So you need to let the GM or individual group decide.
Two. Is it simple to track when mapping is on and when it is off. If so you could allow it to be turned on and off by a GM when players are “actively” mapping or a skill or spell is used to auto map.
I like Rob’s suggestions about the mapping. I would vote for auto mapping, but if you can toggle it, then you have the best of both worlds.
I don’t think you need to worry about the small remaining line of sight issues. You’ve pushed it farther than I would have. I’d have been, “Close enough. The GM can warn people about Bugbears in those hard to see corners.”
Auto-mapping will definitely be optional, though I suspect most people will leave it on. Especially if the use of Roll20 is an indicator.
I really felt like this wasn’t a close enough is good enough feature. There is an expectation that, if the computer is handling line-of-sight, you can just believe the results without double-checking.