Friday, August 26, 2016 Eric Richards

A little over two years ago, I first saw Amit Patel's article on Polygonal Map Generation, and thought it was incredibly cool. The use of Voronoi regions created a very nice, slightly irregular look, compared to grid-based terrains. At the time, I had just finished up working on my DX11 random terrain code, and it looked like a fun project to try to tackle.

I then proceeded to spend several months messing around with different implementations of Fortune's Algorithm in C# to get started and generate the Voronoi polygons used to generate a terrain along the lines of Amit's example. At this point, I've lost track of all of the different versions that I've sort of melded together to produce the code that I've ended up with in the end, but some of the more influential are:

The original goal was to create a map generator, suitable for a kind of overworld/strategic level map. But, alas, life happened, and I got bogged down before I got that far. I did, however, wind up with a fairly cool tool for generating Voronoi diagrams. Because I had spent so much time trying to iron out bugs in my implementation of the algorithm, I ended up producing a WinForms application that allows you to step through the algorithm one iteration at a time, visualizing the sites that are added to the diagram, the vertices and edges, as well as the position of the beach and sweep lines. Eventually I also worked in options to show the circles through three sites that define where a Voronoi vertex is located, as well as the Delauney triangulation of the sites.

Voronoi regions, with the edges drawn in white, and the sites as the blue points.

Delauney triangulation, with triangle edges in green.

Showing both the Voronoi regions and the Delauney triangles.

I won't pretend that this code is fantastic, but it's kind of interesting, and I worked at it for quite a while, so better to have it out here than moldering on a hard drive somewhere. If you'd like to see the source, it is available on GitHub. You can also download the executable below if you like - I make no promises that it will work everywhere, but it is a pretty standard .Net 4.5 Windows Forms application. I've also got some videos below the fold, if you'd like to see this in action.

 Download Voronoi

Sunday, April 10, 2016 Eric Richards

Alright, ready for the third installment of this ray tracing series? This time, we'll get some actual rays, and start tracing them through a scene. Our scene is still going to be empty, but we're starting to get somewhere. Although the book I'm working from is titled Ray Tracing in One Weekend, it's starting to look like my project is going to be more like Ray Tracing in One Year...

Once again, I'm going to put all of the relevant new code for this segment up here, but if you want to see the bits I've missed, check out my GitHub project. We will be circling back to the Vector3 structure I created last time, since I inevitably left out some useful operations...

The core of what a ray tracer does is to trace rays from an origin, often called the eye, for obvious reasons, through each pixel in the image, and then out into our scene to whatever objects lie beyond. We don't have any objects to actually hit, yet, but we are going to lay the groundwork to start doing that next time. Below, you can see the setup of our eye, the image plane, and the rays that shoot from the eye through the image and into the scene beyond.

Sunday, March 06, 2016 Eric Richards

It's going to take me considerably longer than one weekend to build out a ray tracer...

Last time, I laid the groundwork to construct a PPM image and output a simple gradient image, like the one below.

This time around, I'm going to focus on building some useful abstractions that will make work going forward easier. This is going to focus on two areas:

  • A Vector3 class, which will be helpful for representing 3D points, directional vector, RGB colors and offsets. We'll implement some useful operators and geometric methods in addition.
  • A Bitmap class, which will represent our output raster and handle the details of saving that raster out as a PPM image file.
Ultimately, we'll be producing the same image as in the last installment, but with considerably less boilerplate code, and lay the groundwork for making our lives much easier going forward when we get to some more meaty topics. As always, the full code is available on GitHub, but I'll be presenting the full code for this example in this post.

Thursday, February 18, 2016 Eric Richards

Whew, it's been a while...

A few weeks ago, I happened across a new book by Peter Shirley, Ray Tracing in One Weekend. Longer ago than I like to remember, I took a computer graphics course in college, and the bulk of our project work revolved around writing a simple ray tracer in Java. It was one of the few really code-heavy CS courses I took, and I really enjoyed it; from time to time I keep pulling down that old project and port it over to whatever new language I'm trying to learn. One of the primary textbooks for that course was Fundamentals of Computer Graphics, aka "the tiger book," of which Mr. Shirley was also an author. Since that's one of the more accessible graphics textbooks I've encountered, I figured this new offering was worth a look. It didn't disappoint.

Ray Tracing in One Weekend is, true to its title, a quick read, but it packs a punch in its just under 50 pages. Even better, it's running at around $3 (or free if you have Kindle Unlimited). I paged through it in a couple of hours, then, as I often do, set about working through the code.

If you want to follow along, I've put my code up on Github, although it's still a work in progress; we're wrapping up a new release at the day job and so I've not had a huge amount of time to work on anything extra. Fortunately, each example I'll be doing here is pretty self-contained, and so all of the code will be up here. We'll start at the beginning, with a simple Hello World a la raytracing.

Sunday, August 09, 2015 Eric Richards

Last time, I started exploring the finite-state machine implementation from Matt Buckland's Programming Game AI by Example. Today, we are going to continue that exploration, moving beyond that very simple example, abstracting out the implementation of the finite-state machine, adding an additional agent, and implementing a message-passing mechanism to allow our entities to communicate.

In addition to Miner Bob, we are going to add an additional entity to our quaint Wild West simulation, his wife, Elsa. Like Bob, Elsa has a pretty simple existence - she concerns herself with keeping their humble home tidy and cooking up dinner when Bob comes back home from his grubbing in the mine.

In the previous example, our entities had no knowledge of any other entities - Miner Bob was alone in his little world, and there was no necessity of him responding to any external stimuli. Now, with the introduction of Elsa, we need a mechanism for them to interact, and alert each other of their presence. To do this, we will introduce a message passing system, which will allow our entities to broadcast and respond to events, both instantaneous and delayed. To support this, we are going to need to build up some infrastructure: a structure to encapsulate a message, a centralized message queuing and dispatching system, a timing subsystem to support delayed messages, and an entity registration system, to allow indexing and cross-referencing entities.

The full code for this example can be viewed on GitHub, at


I have way too many programming and programming-related books. Here are some of my favorites.