Using Bresenham’s Line Algorithm for Raycasting

Last week I wrote about my first stab and implementing a proper field of vision for my rogue-like. The implementation left me somewhat disappointed because it didn't really work for what I wanted.

After sitting down with the code and studying it a bunch I realized why the code wasn't working and what would need to be done to improve it. The problem rested in the fact that it simply iterated over these octants but was completely ignorant of any state around in one of the directions. The outer loop had no context as to when we should stop incrementing. The result was being able to see through eastern and western doors.

Another problem I had with this implementation is it didn't give me that really nice viewing region that I've grown to love in rogue-likes. The algorithm was too aggressive and would allow me to see through thin walls and so fourth. It had to be rewritten. One thing I liked about using this suboptimal algorithm (for my purpose) was that it gave me a better understanding of what I was doing and how to solve it.

I went back to the wikipedia article and started implementing various versions of Brasenham's Line Algorithm.

The first version was the Optimization of the algorithm. I went with this one first because I found the code was easier to understand and would help ease me into the simpler/faster ones. After implementing the algorithm one of the flaws in it became somewhat apparent.

hmm something isn't quite right

The first optimization doesn't do anything to establish the direction of where the rays are coming from. The result was that rays would be cast inwards toward the point instead of outwards. I needed them to be cast outwards since that would give me the wonderful fields of view we get when entering rooms or corridors that we see in our rogue-likes.

The second optimization does exactly what I wanted. It determines how to move outward from starting point towards the end of the line. During the line-building process, if I encountered an opaque object, I'd kill the line drawing then and there.

The one thing with the line algorithm is that it just does a line, we are still responsible for telling it where all those lines should be cast. I saw a couple of guides on how to do it but they felt really awkward. It involved using macros to do things a bunch of times which just felt wrong to me. Since we are casting rays from a point in a circle, instead of using octants or whatever, why don't we just us polar co-ordinates?

The nice thing about polar coordinates it they give us a perfect circle around our character and the calculations from polar to cartesian are extremely easy to understand.

oh yeah I need to add the original point to my calculations

After a tiny bit of head scratching because I forgot to add my starting point to the calculations I had my rays!

eugor in action