I tweeted about a month ago about an “interactive storyboard” that I was working on for my city builder design. But I only made it halfway through my intended development before I got distracted with my planet generation and turn based strategy shenanigans. The result was that I never got it to the point where I was planning to blog about it. Since it is apparently delayed indefinitely, maybe I should at least show what I do have available.
You can try it out yourself here, though be warned that the UI and overall user experience is far from perfect. This was in part an experiment to get a feel for how the interface would function (or not) after all! (more…)
Having decided to declare my latest project a prototype, and further to declare that it has outlived its usefulness (see my prior post), it’s time for a prototype retrospective.
As I described in my previous post, I failed to outline ahead of time the questions that the prototype would seek to answer, so it’s hard to say whether the prototype achieved its goals. But I can at least go back and infer what those questions might have been, given the answers I have acquired. (more…)
Understand the data, and understand how it is used.
Over the past few weeks, I’ve been struggling to get past a point of excessive complexity in the simulation code for my city builder prototype. I went through a few different refactoring attempts trying and generally failing to manage the complexity. But the most recent attempt finally appears to have succeeded, and I think it has also has gotten me one step closer to properly grokking data oriented design. (more…)
Residential, commercial, and industrial zones along a few roads.
Two and a half weeks ago I found myself in a bit of a difficult situation. I was satisfied for the time being with the knowledge I had gained from my pathfinding experiments, and there had recently been some good discussion on Simtropolis regarding traffic simulations. I was left with the question, “What next?” It was a more difficult question than I had anticipated.
After flailing around for a few days, I decided two weeks ago to force myself to do some project planning; I obviously needed the guidance. I had to go through a few stages that I’ll describe below before I had any kind of actionable plan, but what I eventually ended up with was a three week plan. By the end of the three weeks I hoped to have a city builder prototype with what I considered incredibly primitive implementations of the most core elements of what I currently envision as the end product.
Project planning in software development (and other fields, I am sure) is notoriously difficult and unreliable. I’m sure people often question its value. When I came up with my three week plan, I noted on Twitter that it would probably be completely inaccurate by the time the three weeks were up. But even if that were true, it had real value because it gave me a place to start; it gave me traction when I had been spinning my wheels. I am now about half way through that plan, and things are going well. (more…)
After fighting with some silly bugs, and fiddling with map generation and the data structures used to represent the map, I finally reached the point last week where I could begin to assess performance. It was immediately obvious that the pathfinding algorithm was the bane of my program’s execution. Something absurd like 98% of the running time was dedicated to pathfinding. The subsequent operation of following the paths found and adding to congestion was trivial in comparison.
To more effectively focus on just pathfinding, I created a new project that was designed to run two different pathfinding algorithms over the exact same list of origin/destination pairs, and collect both timing data and algorithmic data on each. One of the pathfinding algorithms would generally be a baseline that I had already tested, and the second would involve some form of experimental tweaking.
The tweaks came in two flavors, which I’ll call technical and algorithmic. The technical tweaks were not intended to change behavior significantly, but were only for improving the performance of the operations already being done. The algorithmic tweaks on the other hand were intended to make the A* algorithm behave very differently, with the intention of making it intelligently consider fewer nodes along the way to finding an acceptable path. (Under normal operation for the types of maps I’m dealing with, a basic A* algorithm will consider a large number of nodes that it eventually decides aren’t part of the final best path. It would be nice to just ignore those nodes altogether, but to do that perfectly, the algorithm would need to see into the future.)
By the end, I was able to calculate around 12,000 paths per second on a grid-like map of highways, major roads, and minor roads that was roughly 100 square miles (260 square kilometers) in size. Each path on average was about 7 miles long, and took roughly 7.5 minutes to travel. Larger maps shouldn’t really affect the speed nearly as much as longer paths would. As long as most paths stay around 7 miles in length, the same speeds should remain achievable on larger maps. (The bigger difficulty would largely come from more paths needing to be computed, as there would probably be more people moving around.)
Below is a (perhaps excessively detailed) chronology of tweaks that I went through over the past week. As a summary, though, I’ll note the following takeaways: (more…)
My second discussion over on the Simtropolis forums focuses on traffic simulation. As a summary, I’m investigating player opinions regarding three particular questions.
The first regards performance: How long would you be willing to wait for the simulation to process one in-game year?
The second is about interface: What type of transit-related structures would you most like to see have a well designed interface?
The third concerns game mechanics: Which transit network features would you like to have mostly for aesthetic purposes, and which are desired primarily for behavioral control? Which ones are important for both reasons?
I took a walk in the snow and promptly realized what my pathfinding issue was. Essentially, the algorithm was going out of its way to intentionally find a bad path.
More precisely, (more…)
stupidly long path
Over the past week, I’ve been working on a traffic simulation prototype in order gauge the feasibility of various levels of simulation detail, given typical computation and memory limits of a consumer computer. I’ve made some progress on getting an initial unoptimized representation of the data structures needed, and visualizing the results of basic pathfinding.
But as is usual for me, although my first attempt at writing the A* algorithm for this particular data representation doesn’t violate any legalities of following the graph edges, it most definitely does not reliably find an optimal path, as the image here demonstrates. Three quick right turns would be sufficient, but nope, it has to go through an intersection, make a left turn at another intersection, then a couple of right turns, go back through the intersection where it turned left, through the first intersection that it originally passed, right by its starting point, a final intersection right turn, and then it arrives at its destination. Brilliant!
You can examine some other silly paths on the prototype page. Now to find out what’s causing this absurdity.
This morning I introduced myself over at the city builder game community Simtropolis.com, and have started a discussion about my city builder project. In particular, my first focus is on what a proper implementation of multiplayer might look like. If you are a member of Simtropolis, join in on my intro post and multiplayer discussion, or feel free to post any thoughts here on my blog.
The game concept that has generated the greatest amount excitement for me thus far is a modern large-scale city builder, naturally inspired most strongly by the SimCity series. I have waffled on whether I should even try to make any progress on this project right now, as it is a large one, perhaps monumental, and it is arguably unwise to get bogged down on such a big project right out of the gate. But I gave myself a Christmas gift and allowed myself to take a pause from my other prototype projects and to begin digging into this one. No reason to fight one’s inspiration, and nothing wrong with having multiple projects ongoing. (more…)