Vision - I

Finally got a Line of Sight (LOS) algorithm implemented.

My first quick-and-dirty "ingenious" idea that struck at around 11:00 at night (PROTIP: you should never code when you're tired, even though I'm going to break this tip (again) as soon as this post is done) was to use a filling algorithm in the vein of breadth-first-search, i.e. starting from the tile the Character is on, giving each tile considered a value of the current tile's value+1 and pushing on a priority queue until the current value was greater than the player's LOS distance. Then I realized that I'd need to increase the value by sqrt(2) for diagonal values, unless I wanted the player to be able to see in a square.

It wasn't until AFTER I'd finished coding it that I realized that this would let the player's sight "spill" around walls. By this point, it was nearly midnight, and 8am class was beginning to rear its ugly head at me from the future, so I put my code, my computer, myself to sleep.

My next idea (a.k.a the right way how to do it) was to get a series of points in a circle around the player at a distance R, then draw lines from the player to those points, stopping if a wall interuppted a line. Take all the points a line went through and store them in an array (STL vector, naturally) associated with a Character. Thus we have all the Tiles that any given Character can see, and from there we can either show the player visible tiles, or see if an enemy can see the player.

As an aside, I'm wondering if there's a better way to show the duller tiles that are out of the active visibility field than storing a second surface for each image color multiplying by a down-factor (20% darker?), or storing a second surface at a slightly smaller size. For now I'm going to implement the second image with a color multiply, but I'm thinking out loud here. And scowling to myself, knowing "there's gotta be a better way".

On LOS: my first instinct was to repurpose code I'd written earlier for a different project that would draw lines circles with pixels, changing the "putPixel" faux-routines I'd written into adding Tiles to a vector and returning it (I didn't have a putPixel function written, but that was thanks to the horrendous overhead of the thousands of function calls it wound up making; something the inline command failed to help with at all). This, of course, led to several issues.

Firstly, the lines would start inside of walls sometimes, and not draw in certain directions others, but only in some positions. Quickly, I realized it was because the particular implementation of the Bresenham algorithm I was using didn't necessarily draw lines from the point 1 to point 2, so I had to rework it a bit so it would work without swapping the points.

Still, though, the visible field it gave me was completely off. The line-drawing algorithm worked perfectly sometimes, so that probably wasn't it. It turned out to be that in my reimplementation of the circle-drawing algorithm, I hadn't referred to the code that actually produced a working circle, but instead some notes on circle geometry that hadn't worked out so well at all (but looked convincing on paper). How I was doing it was dividing the circle into 1-tile-high slices from j = y - R to j = y + R and using the points on the left and right edges of each slice. The problem was, I was taking the width of each slice as w = 2*R*sin(acos((R-j)/R)) which anyone can see will cause problems. For those who actually care, the correct width was 2*sqrt(R^2-(R-j)^2).

That worked much better, and gave me a contained field in the shape of a circle that the player could see and moved consistently with the player. All well and good, but it had several holes in it near the y-axis for no apparent reason. Then it clicked that while the slice-based algorithm worked acceptably well for drawing full circles with rectangles, it only considered one point per horizontal line, which left noticable gaps near the top parts of the circle, where the slope of the tangent was much flatter.

So I buckled down and looked up the "Bresenham" circle-drawing algorithm (not actually designed by Bresenham, but similar enough to his line-drawing algorithm that people give him credit for it). The version that I shamelessly stole off Wikipedia is fairly inelegant to my eyes (I much prefer minimizing lines of code; ironic then that I'm writing a roguelike), but I so far cannot be bothered cleaning it up with for loops instead of eight explicit putpixel functions (on reflection, an idea for which has just struck; it also involves bitwise operations, which are pretty as far as I'm concerned). For LOC, it works significantly better, and gives a mostly-full circle (dropping, amusingly, only the 45-degree angles).

Now I'm off to improve it using floating-point values for x,y offsets of the points on the circle, which I'd put off until now because I'd been reimplementing the way Tiles displayed themselves and their contents. I.e., I finally started giving Tiles contents.