Shadowcasting in C#, Part Three

re: Shadowcasting in C#, Part Three

Ross Morgan-Linial — Tue, 20 Dec 2011 10:31:56 GMT

Geometrically, the only important points on a cell are the top-left corner and the bottom-right corner, because they are farthest apart as seen from the origin. If the bottom-right corner is above the field of view, or the top-left corner is below the field of view, the entire cell is outside the field of view; otherwise at least part of the cell is inside the field of view, even if just one point in the corner.

So the solution to eliminate the artifact in case 4 is to do the calculation for the bottommost visible cell in a column using the left edge, and keep using the right edge for the topmost visible cell.

re: Shadowcasting in C#, Part Three

pete.d — Tue, 20 Dec 2011 00:35:50 GMT

"Under what circumstances can it be even? Can you find an example?"

Hmmm...I admit, that question confuses me. Are you suggesting that outside of the particular example, it's not possible for "top.Y" to be even? I agree in the example at hand, top.Y is odd (having the value of 3) and so the dividend is odd and so the remainder must be odd.

But I don't see any reason that for any given integer Y, I cannot find some direction vector that has that value of Y as its "rise" (Y) coordinate, including even values. For that matter, an equivalent value of (3,1) as in the first example of the page would be (6,2). Likewise, I can change the (5,3) vector in the final example to (10,6). Even values for Y are even easier, because I can just take any known vector and extend it by a factor of 2.

Assuming that the magnitude of the direction vector actually doesn't matter (as stipulated earlier), it seems trivial to find legal direction vectors for arbitrary values of Y (presumably in the expression at hand, I should always get the same remainder value for any equivalent representation of a given direction vector).

Thus, if I can arbitrarily make "top.Y" an even number, I can likewise arbitrarily make the expression "((2 * x + 1) * top.Y)" (the dividend) even..

Give your original statement along with your follow-up, I'm left to assume that you have a proof in mind that would show the contrary. This implies I've overlooked something (perhaps hidden in the "exercise for the reader" :) ). Suffice to say, at least from my own point of view, if such a proof exists then I think maybe some elaboration on the question is warranted.

(Oh, by the way...I found that typo: "It sure seems light it ought to be..." Should read "It sure seems like it ought to be..." :) )

re: Shadowcasting in C#, Part Three

Oisin Grehan — Mon, 19 Dec 2011 23:50:53 GMT

Have you seen this "teleglitch" indie game demo vid? It's a really nice example of shadowcasting coupled with a top-down early grand-theft auto view. Elements of that old arcade classic, "Smash TV" there too. Check it out at www.youtube.com/watch (No, I'm not the author.)

re: Shadowcasting in C#, Part Three

pete.d — Mon, 19 Dec 2011 20:23:44 GMT

On the topic of the final proposal: it seems to me that the main innovation in this particular solution is to shift the point of consideration half a cell to account for the nature of visibility. While the actual math is different to accommodate that and remain in integer computations, as near as I can tell the rounding aspect is still basically the same as in the third proposal ("round to nearest").

For what it's worth, I agree with other commenters about the effectiveness of the narrative. It's pleasurable to be given the opportunity to come to one's own realization rather than having it just spread out in an initial article. For example, the statement "When you propose three different plausible calculations and they all turn out to be wrong in different ways, there might be an invalid assumption somewhere in the mix" is essentially the same conclusion I'd already come to by the time I got that far in the article.

It's an example of a more general rule that I have, which is that if something starts to seem too difficult, I probably have made it that way and I'm missing some easier way to solve the problem. I've found this to be often true in the real world, but especially so in the environment of programming. There are exceptions, especially when working at very low levels where huge numbers of special cases, all of which have to be gotten exactly right. But in most cases, if the path appears to lead toward writing a lot of extra code to deal with lots of special cases that the generalized solution doesn't address, it just means that the wrong generalization has been made.

"Path of least-resistance". It's not just for fluids, light, and electricity. :)

re: Shadowcasting in C#, Part Three

pete.d — Mon, 19 Dec 2011 20:06:47 GMT

I have to admit, I found the passage from "Suppose the direction vector is (3, 5)..." to "...the remainder will always be an odd number" difficult to understand. The stumbling blocks for me:

* I have become accustomed to thinking of the vectors/slopes as being written in (x,y) form, but "(3,5)" appears to be written in (y,x) form.

Whoops, that was a typo. (5,3) is what I intended to write. Fixed, thanks. -- Eric

* As I understand it, "The remainder is the number of tenths..." applies to this particular example only; with a run of 5, doubling that produces a divisor of 10, thus all remainders are in tenths.

Correct. -- Eric

* Similarly, the statement that the dividend will always be odd appears to apply only in this example. With a "top.Y" that's odd, multiplied by an expression that itself will always be odd, the result is always odd. But "top.Y" could be even for other scenarios.

Under what circumstances can it be even? Can you find an example? -- Eric

In the second and third issues above, the main point of confusion for me is that the article does not call those statements out as being particular to the example. As a programmer, I am so used to dealing with generalizations and abstractions that when I read claims about the innards of an algorithm, my initial interpretation is to assume those claims refer to the algorithm generally. Given this (IMHO perfectly natural and reasonable assumption) I think it would be clearer and speed comprehension if the passage is explicit about the specific nature of those statements.

Sorry if the above seems like nitpicking. I'm just trying to offer what I think would be useful pedagogical improvements.

Good points all; I'll clarify it. -- Eric

I thought I'd seen a simple typo early in the article, but after reloading the page I can't find it any more. So either I was mistaken, or you've fixed it already. :)

re: Shadowcasting in C#, Part Three

Tom — Mon, 19 Dec 2011 19:45:08 GMT

Pre-build a lookup table for each cell based on your algorithm will significantly speed up its computation. The computation time is significant when the radis of visible cells is 8 or more.

re: Shadowcasting in C#, Part Three

Joshua Ganes — Mon, 19 Dec 2011 18:57:24 GMT

I like that you were willing to take this explanation down a few false starts before coming to a more optimal approach. I feel like this is how I might have organically explored the problem myself. I agree that the artifacts from scenario four are not too big a worry, but I would probably not allow the view angle to increase as a result. It's such a simple check that I feel it is worth doing to prevent strange "seeing around corners" artifacts.

This series is very much a product of how I "organically explored" the algorithm. I spent a rather confusing Saturday afternoon trying to understand various different implementations of this algorithm and the subtle choices made -- possibly accidentally -- by the implementers. I thought it might be a nice public service to document what I learned from that process. -- Eric

re: Shadowcasting in C#, Part Three

Virtlink — Mon, 19 Dec 2011 18:51:20 GMT

Great series! In your implementation of the game in part 1, when you stand on the left or right side of a wall, but not too close to it, then you can see past the wall. For example: [ . . . X . . . @]. This doesn't happen in the vertical direction or on any of the diagonals. I assume that this may be the case due to artifacts with determining the bottom cell of a column portion?

Correct; I deliberately introduced those artifacts. We'll discuss how they arise in Thursday's episode of FAIC. -- Eric