Nerf omnidirectional sonar reveal

[davidyu]

The omnidirectional sonar should die after hitting an edge.

In implementation this just means:

Construct a line from the center of the omnidirectional sonar to the closest point on an edge. If it passes through another line, then do not continue to perform the circle-line intersection test.

[davidyu]

Problem: what about partially obstructed edges?

What if, for example, there was a small island?

[davidyu]

Here's a complex implementation I'd rather not do:

1. Acquire the intersection result from a circle-line intersection test (either point, none, or line. But we only consider the line because the other two are trivial cases)
2. Shoot two lines from the center of the sonar to each endpoint of the line segment. Again, we only consider the case where only one of two lines are obstructed because when neither or both are obstructed, the results are trivial. Call the obstructed endpoint o and the clean endpoint p.
3. Shoot a line to the middle of this new line and check if it is obstructed. Call this point m.
4. For obstruct(m):
   • If false, check the middle of the line segment formed by connecting the original obstructed endpoint (o) and this midpoint (m). Call this new point m'. Recursively continue for some predetermined depth, and return the midpoint at that level (m"), and just draw the line from point p to m".
   • If true, check the middle of the line segment formed by connecting the original obstructed endpoint (o) and the halfway point between m' and e. Call this new point m'. Recursively continue, as above, with minor adjustments to logic.

This is complicated and there is plenty of room for error. And it intuitively feels slow. So think of something better.

[davidyu]

Here's an optimization of the above.

Instead of steps 3 and 4, which are cumbersome, leverage the fact that an obstruction should also give us the exact edge against which we tested collision with.

Given this edge, shoot a line from the center of the sonar to the endpoints of this edge. Extend these lines to the original intersecting line to create one or two points. Perform a subtraction of lines. The resulting line is the unobstructed trace.

It is important to continue to test against other edges instead of just breaking at the first. It is very well possible that there is another edge that obstructs a larger portion of the trace.

To further optimize this, only test against the edges corresponding to the current living set of traces. Because if a trace has not been created for some edge, then that edge is not visible and needs not be tested against.

[davidyu]

There's something wrong with this logic.

If you connect the endpoints of a line to the center of the sonar and try to search for obstructions (and only acting if you do find an obstruction), you'll totally miss the case where an island obscures a portion of a wall completely within the two endpoints!

Here's a better, and more efficient algorithm: map all traces (lines) to a radian range of the sonar, and declare those radian range to be "obscured." So, everytime we get a trace, we map it to a radian range, and check if that radian range has already been obscured. If yes, we want a new (list of) radian range(s) that represents the portions of walls we can see.

How to implement this without using a lot of complex data structures...

[davidyu]

Fuck it. Create an array of float-tuples to represent an obscured radian range (start, end). Do a linear search through this array when doing our checks.

To speed up lookups, we can keep this list of radian ranges sorted.

For ease of implementation, we should probably keep the list of radian ranges sorted. Ideally, we have a function:

(start, end) -> obscured( List<(start, end)> UnobscuredPortions ) or (start, end) -> clear

Internally, this function will iterate through each obscured range, and subtract each obscured range from the target range, creating a null range (if the entire target range is covered), one unobscured range, or two unobscured ranges. Keep these in some list (the unobscured ranges list)The next iteration should test against every range in this list. In the end we have an undeterminate number of ranges that we return.

If we wanted to refactor out the range subtraction into a function, it would have this signature:

minuend :: (start, end) -> subtrahend :: (start, end) -> [] | [ (start, end) ] | [ (start, end) , (start ,end) ]

There's probably no need to create type/enums for the result since it's just an array.

[davidyu]

For any point p and center of sonar c, we have:

The "radian" measure of this particular point can be found by:

With proper adjustments made for a point in the four quadrants relative to the center.

SonarCmp should have a list of start, end ranges. SonarSys is responsible for maintaining this list.

Cons of this implementation: maybe expensive? Need to run profiler on game. The constant trigonometric calls are bound to slow down the game if there are enough of them in a short period of time.

An alternate algorithm that came up during a discussion with another developer is to look into hardware or low-level culling. Or simulate culling in software: everytime we construct a trace, we add it to the list of potential boundaries to cull against. Before construct another trace, we look through this list and compare the position of the new potential trace against the old trace (the cull trace). The trick here is to convert the coordinate system into one relative to the cull-trace. such that the cull-trace becomes the y-axis, so we can run a very simple comparison: if (WLOG) x > 0 && r < 0 && y < cull-trace.length && y > 0, then don't draw (or draw partially in the case when y > cull-trace.length && y > 0), otherwise draw the new trace and add it to the list.

Software culling can be optimized into a neater system too: if we build a general system that is able to convert the world space into a square space where (0,0) is the center of the sonar, and (1,1), (-1,-1), (1,-1), (-1,1) are defined by the endpoints of the cull trace (and its reflection across the center of the sonar), then we have a simple check: if any of the x or y component of any point is above or below 1 and -1, respectively, then it must be culled.

[davidyu]

Done in 11c7da653fc9bcf4ab404fdaa6221f46764792fb.

Postmortem: deciding to do radian-based culling maybe wasn't the best idea.

I ran into a lot of pain trying to normalize the radian conversions (in both directions), and the range-comparing code is very very messy and sensitive to degenerate and edge cases. But I'm glad to have finished it. If I were able to write shaders in Haxe and Flash, I definitely would have used a fragment shader and done per-pixel raytracing instead.

Barring that, there are a lot of optimizations to be done on the software culling. A lot of cleanup and refactoring as well.