Game development: reducing scope (traffic simulation)

One of the tricks of game development, especially that done by small teams, is reducing scope of each feature or element to a minimum necessary level. It is critical to make efficient use of developers’ time since there is only so many cycles available, and the longer a project goes on the more likely it is to get cancelled or postponed. The more games you get under your belt the more you start to care more about this kind of stuff.

To give an example of this – one of the core elements of my latest game in development is a series of connected roads with cars running through them, a little like what you would see in a modern version of a SimCity-type game. Starting several weeks ago, I experimented with several different ways to implement this “traffic simulation” element in my game.

Initially, I started with the idea that I would use Unity 3D, since that would allow me to show a very realistic simulation of cars moving through a network of roads. I was inspired by the mobile game Does Not Commute, which uses a 3D engine to good effect.

However, after learning a little more about the Unity 3D workflow, I realized I would be spending a big chunk of my time on the graphics and other 3D elements, which would make the core gameplay elements (behavior, logic, rules) take that much longer to do. Though the end result might look quite attractive, I had doubts that I could finish the game on my own if I took this route.

So for the time being I decided to make the game 2D. My next decision was whether I should use a physics engine or not. I’ve been interested in physics engines myself for some time, having made very simple ones years ago, so I decided to download and experiment with a few different frameworks, including Box 2D. In only a few hours, I was able to get some test programs running and there was a surprisingly rich set of functionality for the free frameworks I tested.

But again, I posed the question to myself – do I really need detailed physics simulation? Is having cars collide, spin out of control, and follow a physically accurate path really critical to my game’s core gameplay? While this would be a cool feature, I eventually decided this was overkill, and again reduced the scope of my traffic simulation efforts.

At this point I entered into prototype development, spending my evening hours making a bear-bones traffic simulation where each car was resented with only a handful of properties such as color, location, and speed. I got this working and am now experimenting with different game objectives, and creating stages to see what is actually fun (and challenging) – the most important aspect of any game.

If things go well and I feel I’ve made an entertaining prototype, I can continue to polish the visuals, or even consider going back to 3D. With a proven game idea, the risk for failure would be greatly reduced.

If I had determined that simulating cars as individual entities was not a critical element of my game, I could reduce scope yet again and simulate at a coarser granularity. For example, in the original SimCity game (which happened to be the first game I purchased with my own money), traffic was handled by road-piece granularity, where a stock animation was selected based on the traffic density of that area at the given time. You couldn’t follow a single car around since they would appear and disappear if you looked closely. While a system of roads was important in building an efficient city, tracking an individual car from point A to B wasn’t necessary, and players had more to concern themselves with. Also, I believe the original SimCity was only made by two or three developers. In more recent versions of that series it seems that cars are modeled as individual entities.

I’ll post some more about this project as things progress.

Programming Trick: Speeding up your recursive loops with a creative technique

Lately, I’ve been working on a new game project which is very different than all the other ones I’ve done so far. I’m planning on waiting until it gets a little further before I write about it in detail on this blog, but I ran into an interesting technical challenge and I’d like to discuss how I solved it.

To implement the game mechanics I need a graph of nodes, with various connections between each node. I have a need to find the shortest path between two nodes, where the path is calculated by the sum of the length of all connections as part of the path.

I started out with a simple recursive algorithm that started from each node and worked backwards to find all possible paths to get to it, and used a map to store the best connection to move, given a certain intermediate node and a certain destination node. This worked really well, although after around 13-14 iterations on a graph with many connections it started taking over a second to compute and them getting exponentially worse.

One option was for me to search for a more proper algorithm to find the shortest path, and I am sure this has been perfected by  programmers over the last few decades. But I had a secondary requirement to also store all non-optional paths as well, so some of those algorithms probably wouldn’t suffice.

Looking at my recursive function, I realized that there really wasn’t much going on in terms of sub-functions it called that do any significant calculation. If there was, I could try to optimize those or cache up some result. But the question remained – what was taking up all the time?

Looking at the function again I saw that I was passing four different arguments into it. If you have ever studied assembly, you probably know that there are several instructions just to push and pull each of these to and from the stack, and since the function is called so frequently I thought that maybe this added up to a big chunk of the total time.

I decided to test my hunch by making all the parameters into global variables. I purposefully didn’t use class variables since I knew there would be extra lookups required, translating to extra work for the CPU.

It was a bit of work to make this transformation, since for non-pointer variables I had to manually save the state before calling the recursive function, and then re-set it. But this was only for two of the variables since the other two were pointers anyway which were supposed to change (one was the map which stored the nodes that had already been traversed so far, and I already had code to adjust that when returning from the recursive function).

The resultant code was a bit harder to follow, but the performance was significantly better. For the test case I was using I was able to get several more iterations before it got significantly slow (>1 second), if I remember correctly to at least 19-20 iterations.

If I keep adding nodes and connections eventually it still gets slow again, but I will probably put limits on these anyway so I may be safe with this solution for the time being.

Although I enjoy designing games from a high level, after many years of coding I still enjoy these types of algorithmic challenges, and the satisfaction of a well-tuned function.