Tuesday, September 12, 2017 Eric Richards

TLDR; the Microsoft Automatic Graph Layout library is pretty slick at automatically generating state transition diagrams.

One of the products that I work on for my day job is an instant message-based call center/helpdesk application. It's a pretty complicated beast, but at the heart of it, what it does is:

  • Allow users to contact a central endpoint.
  • Process the incoming request
  • Route the request to a member of a predefined group that can assist the end-user
  • Broker the conversation between the end-user and the helpdesk/call center agent.
  • Perform post-processing on the chat session once it has ended.
Internally, each incoming chat session uses a state machine to keep track of the session and its progression through the workflow. For each stage in the pipeline, we've got a State class that handles operations during that particular stage. There is also a table in our state machine which determines what the valid transitions between the states are, so that we can easily assert that the session is following the expected workflow.

This state machine started out fairly simple, with just a few states, but as always happens, we began to accrete features, and so more and more stages were added into the pipeline, and the complexity and number of state transitions grew. The state machine definition that originated as a hastily drawn scrawling on a sheet of printer paper blossomed into a Visio diagram, then eventually wilted into irrelevance as more and more states were added and documentation efforts fell behind. Like most manual processes, it became a pain point, and was neglected.

Things came to a head recently when it was discovered that a state transition had been added as a code path in certain situations, but the state machine transition table had not been updated accordingly, and so it was possible for chats to attempt to make a transition that the state machine would reject as invalid, leaving the chat session in limbo. Not ideal. Ideally, we'd have caught this in some way with compile or build-time static analysis, but getting that implemented is going to have to be an exercise for the future. Failing that, exhaustive unit-tests validating the state transition rules was the easier task, but ran into the difficulty that the hand-written design documentation had fallen out of date, which necessitated a tedious and time-consuming search through the code base to trace out the logic. Once that was complete, there remained the task of updating the Visio docs... which is less than fun to do by hand.

Earlier that week, I had run across a link to the Microsoft Automatic Graph Layout library, a nifty open-source project that makes it stupidly easy to define a graph and then either display it in a Windows Form or render to an image file. While it may not be quite as nice looking as a hand-crafted Visio doc, it's not too unattractive, and better, can be completely automated. So we can just pipe our state transition definitions into it from the source code, and right out comes a legible diagram. We can even run it as a post-build step in our build to automatically keep the documentation up-to-date. Hooray!


Tuesday, May 16, 2017 Eric Richards

Last time, I had started working through Jamis Buck's Mazes for Programmers. I've made quite a lot of progress in the meantime, but haven't managed to keep up with posting about that progress. Today, we're going to work through the meat of Chapter 3, where we'll implement a simplified version of Dijkstra's Algorithm (really a breadth-first search), which we'll use to find paths through our mazes. We will also use this algorithm to help visualize the biases that exist in our two previous maze generation algorithms, by coloring the backgrounds of each cell according to its distance from a starting point.

You can download the code for this post by downloading or cloning the Post_2 branch from my GitHub. Going forward, I'm going to try and tag the code for each post in a new branch - I'm still used to the old SVN model, but I'm trying to figure out how to take advantage of Git a little more.

Below you can see an example of where we'll end up, drawing the longest path through a maze, and coloring each cell according to its distance along the path.

Let's get started!


Sunday, April 09, 2017 Eric Richards

A few weeks back, I picked up a copy of James Buck's Mazes for Programmers: Code Your Own Twisty Little Passages. (The title is, of course, an homage to one of the original text adventure games, Colossal Cave Adventure, or Adventure for short, which featured a maze puzzle where every room was described as "You are in a maze of twisty little passages, all alike"). I read through most of it on my veranda in the mornings, looking out over Long Bay in Antigua while I was on vacation, wishing I had brought my laptop along with me (although my girlfriend is probably happy I did not...). Once I got back, I started diving into implementing some of the ideas from the book - it's been quite a joy, and a much needed break from debugging UCWA applications at the day job.

The code in the book is implemented in Ruby, however, I'm not a Rubyist, so I decided that I'd work through the examples in my language of choice, C#. The code is pretty simple, so porting it over has been pretty straight-forward. I also figured it would be an interesting exercise for trying out some of the newer features in the more recent versions of C# - I've been stuck using C# 5.0 due to some tooling that we haven't had a chance to upgrade yet at work. Today, I'm going to mostly cover the examples from Chapter 2, which lays out the general plumbing of the framework that the rest of the book builds on, and implements two simple maze-building algorithms, the Binary Tree and Sidewinder algorithms. For the full code, you can check out my GitHub repository; things there may change slightly from the version presented here as I work through more of the book, but the general structure should remain similar.


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.


Bookshelf

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