Archive for May, 2014


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


Casting Rays in Roguelikes

I’ve gotten back into building my rogue-like again. It’s good to be spending a little bit each day on the various parts of it. My main focus recently has been on implementing the fog of war / vision such since I’ve always found those to be the funnest parts of a rogue-like.

Raycasting in DoomRL

Most rogue-likes do a field of vision that has a maximum range and also allows you to into corridors. One of the ways this is implemented is using Ray Casting. The way this works is you choose a point (often the player) and cast rays from their position in all directions. When a ray hits an opaque object the ray stops, otherwise we mark that position on the map as seeable and keep casting the ray. Typically we’ll cast these rays in the various octants because we want our Field of Vision to be around the player.

My initial implementation was going to use Bresenham’s line algorithm but I wasn’t really getting any results and it was sort of tricky to debug (hint, I was getting stuck in loops). I hit up roguebasin to grab one of the Ray Casting algorithms that people had decided to share. One thing that really stood out for me was that it had a very old-school programmer feel to it. Maybe I’m bad at math, but the code was somewhat tricky to understand. I’m also not sure if media wiki nommed up some mathematical symbols because there were some really important mathematical functions missing. I want to really understand what is going on, and this is even more important since I’m implementing the game in Go not C, so I can’t even copypasta this. Understanding what is going on is key or I’d just end up with magic in my codebase and I hate magic.

After a bit of confusion and head-scratching I was able to get my implementation of the algorithm is working alright. There were a few parts in the roguebasin example that I skipped, mainly because I don’t think they were necessary and couldn’t actually understand what was going on. Considering the results I have, I am pretty happy to have avoided implementing that code.

My implementation of raycasting does make a few assumptions:

  1. The raycaster is initialized with the dungeon/maze/map
  2. The maze is what is responsible for fetching the tiles
  3. Tiles provide the information regarding their opacity

The meat of the algorithm is as follows (Note: I’ve reordered the code such that you can read it top to bottom):

func (r *Raycaster) flushOverlay() {
    for x := range r.overlay {
        for y := range r.overlay[x] {
            r.overlay[x][y] = false
        }
    }
}

var OCTANT_CALCULATIONS map[int][]int = map[int][]int{
    0:  {1, 1, 1, 0},
    1:  {1, -1, 1, 0},
    2:  {-1, 1, 1, 0},
    3:  {-1, -1, 1, 0},
    4:  {1, 1, 0, 1},
    5:  {1, -1, 0, 1},
    6:  {-1, 1, 0, 1},
    7:  {-1, -1, 0, 1},
    8:  {1, 0, 1, 0},
    9:  {0, 1, 1, 0},
    10: {-1, 0, 0, 1},
    11: {0, -1, 0, 1},
}

func (r *Raycaster) calculateFieldOfView(x, y, intensity int) {
    for _, values := range OCTANT_CALCULATIONS {
        sx, sy, dx, dy := values[0], values[1], values[2], values[3]
        r.doOctant(x, y, intensity, sx, sy, dx, dy)
    }
}

// Algorithm from Rogue Basin
// http://www.roguebasin.com/index.php?title=Ray-Tracing_Field-Of-View_Demo
func (r *Raycaster) doOctant(x, y, radius, sx, sy, dx, dy int) {
    for i := 0; i != radius; i++ {
        var lastTile *dungeon.Tile
        var lastAdjacentTile *dungeon.Tile
        for j := 0; j != radius; j++ {
            tileX := x + (sx * i)
            tileY := y + (sy * j)
            if tileX >= r.maze.Width || tileX < 0 || tileY >= r.maze.Height || tileY < 0 {
                break
            }
            tile := r.maze.FetchTile(tileX, tileY)

            adjacentTile := r.maze.FetchTile(tileX-(sx*dx), tileY-(sy*dy))
            if lastTile != nil {
                if lastTile.Name != "wall" {
                    r.overlay[tileX][tileY] = true
                } else {
                    if tileX <= 0 {
                        break
                    }

                    tileIsWall := tile != nil && tile.Name == "wall"
                    adjacentTileIsClear := adjacentTile != nil && adjacentTile.Name != "wall"
                    lastAdjacentTileIsClear := lastAdjacentTile != nil && lastAdjacentTile.Name != "wall"

                    if tileIsWall && adjacentTileIsClear && lastAdjacentTileIsClear {
                        r.overlay[tileX][tileY] = true
                    } else {
                        break
                    }
                }
            }
            lastTile = tile
            lastAdjacentTile = adjacentTile
        }
    }
}

// The public interface is the following
func (r *Raycaster) CastRays(x, y, intensity int) {
    r.flushOverlay()
    r.calculateFieldOfView(x, y, intensity)
}

func (r *Raycaster) IsLighting(x, y int) bool {
    return r.overlay[x][y]
}

Using the ray-caster is fairly straight-forward, I’m going to assume that the maze is already initialized:

raycaster := MakeRaycaster(maze)
raycaster := CastRays(5, 10, 10)

The result of using this in my game is the following.

Raycasting in Eugor

There are a few little bugs that need to be fixed, those primarily being able to see through walls and some walls being hidden when looking directly at them.

As always, you can peruse the source on github at your own pleasure.


Reflections on TO Jam 2014

TO Jam Notes

The past weekend I participated in my second game programming competition called TOjam. The goal was to simply make a game in under 48 hours, similar to Ludum Dare though with a local community to build your games with.

Compared to the Toronto Global Game Jam, I'd say things definitely went a lot better for me this time. The big reason was because I was on a team so we were able to distribute work and test iterate over the ideas relatively quickly.

The main idea of the game was to build out a western-style shootout but with princesses as the people in the standoff. The theme changed around a few times though the end product was something we were all super happy with.

Day 1 – Spinning

The first day, Friday, consisted of us mainly trying to figure out how we wanted the mechanics to work in order for the shootout to happen. One thing I thought that might've been interesting was to have a QWOP style interaction with drawing your pistol. This could've ended up being something interesting, though given my lack of experience with Box2d and how janky the experience felt we decided to scrap it.

you-are-the-dead

We also weren't super sure on what kind of art style we wanted to go with. We decided to spend a bit of time trying out a few different art styles, though it was uncomfortable and definitely slowing the designers down.

Day 2 – Locking down the mechanics

When I came in on Saturday we did a brief discussion about what we were looking to do and how to get there. I started working on more prototypes using boxes and such until I had some rough assets to drop in.

Most of the work for me consisted of getting all the collision detection working, controlling the various player states and managing things like the bullets that were being fired. One part of the project that was starting to really hurt was how player state was being managed. Initially I was simply having it driven by button presses which lead to some really weird edge-cases that would cause players to die when they shouldn't and so on.

This was around the time when one of the designers, David Rusak needed to know how we were going to be handling the animations. Initially I was simply going to perform a bunch of transforms on various parts of the sprite (such as rotating the arm) but after talking to some more experienced jammers at the event, decided to go with frame-style animations instead.

The big thing I wanted to avoid was the use of Sprite-sheets. For super detailed things they are awesome, but depending on your frame rate and how you are updating them, they can be really hard to tweak. Another thing that I was worried about was figuring out when certain parts of the animation had finished. I sat down with David and we chatted about an idea I had that would make it super easy for designers to tweak timings that didn't require developer intervention.

I want to say this worked out really well because we were using Löve2D and Lua which has that lovely benefit where code can be data. Writing out the data-structure was extremely straight-forward, and "parsing" it was practically trivial. Another added benefit was we were able to add events that would be fired when a frame of the animation had completed. This meant I was able to move over to a callback pattern for controlling player state.

Once we had the animations setup I took to helping out the designers with some work. They were super busy working on all their art so I took to building out the various aspects of the UI that could still look good but be built out by a developer. This mainly consisted of stuff like the DRAW! screen and instructions. Initially I grabbed some ancient assets from Microsoft to use as the buttons though they made us pretty sad. They were super dated looking for one, and really didn't fit in with anything we had built out.

three-two-one-draw

By the end of day 2 we had made some awesome progress! There were a few missing pieces, but overall it was at the point where we just needed to add the finishing polish.

Day 3 — The Final Day

The Final Day

It was pretty much all about polish during the last day. I spent a bit of time within Audacity to tweak some sound effects to fill in some of the empty parts of our game. Another thing I spent time on was trying to figure out where the loop points of our game music was. I'd say there is a bug in Löve2d when it comes to playing audio, even when you are playing sounds set to loop. The problem is when the music is over there will be dead air before the music starts up again which is quite jarring.

When we started getting closer to the end of the event, I figured it would be a good idea for us to get together and hammer out all the remaining pieces that needed to be worked on in order for us to consider the game done. There were going to be a few missing features, but a big thing for me was something that didn't crash and played well. 7pm was pencils down, so I figured we could call our tojam release time to be an hour before. This would give us enough time to catch any last minute problems and put together the binaries for release.

Post-Jam

I'd have to say this was one of the better hackfests/jams I've participated in. The one thing that really stood out is there was a vision that was easy to realize and a scope that wasn't too crazy. I also feel that we weren't afraid to cut out things that might've ended up in some features that might've been cool but could've compromised the integrity of the project. Finally, I had chosen to use tools I was familiar with which meant that while I was still spending time learning, the slope wasn't as steep as it's been in the past.

If you're interested in playing the game, you can grab a copy for Windows or Mac. I also suggest that you take a look at the other games that were built during the jam as well!