« American Top 40Dollhouse »

Intelligent Geographic Transportation Networks

01/22/10 | by Charlie [mail] | Categories: TTD AI

Transport Tycoon is a game released in 1994. It was my 3rd video game ever right after Jetfighter 3 and Red Alert (Thanks Dad!). In fact, it's so old that I actually have the DOS cd-rom. The game was created by Chris Sawyer, and is perhaps best know for two things. First, if one were to open up the game, their first comment would be, "This looks like Roller Coaster Tycoon!". Because, yes it does. Chris Sawyer also wrote the much more successful game Roller Coaster Tycoon, however that came out much later. The engine and concept are essentially the same in terms of the block map setup. Second, you would also notice that Transport Tycoon has the BEST music for any game ever, because it is, in-fact Blues and Jazz. But not just any Blues and Jazz, MIDI Blues and Jazz. That's right MIDI MUSIC. It rocks.

So why have we chosen a more than 15-year old game as the medium for our work? Well it turns out that this game was so much fun, that people decided to rewrite the entire game with open-source code. This means that the game is now 100% open-source, so things got real different. A number of new features have been added and improved so that they make more sense, there are WAY too many configurable options, but most importantly, they've added an AI Framework to create AIs.

Given all that, it remains, to my knowledge, the only multiple-mode transportation simulator (Chris Sawyer made a new game called Locomotion, but ignore that). It's also a fairly simple game in terms of mechanics which makes it very easy to analyze almost all of the data involved in the game.

In terms of our AI, we don't know how far we'll be able to get in one semester, but the hope is that we can make a fairly competitive AI which creates realistic and efficient transportation networks to connect every city on the map. To do this, we'll be borrowing a couple concepts from Graph Theory and Geographic Transportation Network Theory. The idea is that we want to create a network where each house in a city is close to a bus station, then each station in the city feeds into a rail station, which interlinks to various other cities and regions. In this way the capacity of the farthest out stations will be smaller, while the main veins (Inter-City/region) will be very high-volume.

It's not terribly ambitious in terms of overall design, mostly representing a graph and doing operations on it in terms of an array or other data structure. But what makes the project interesting is to see how many factors we can take into account when making building decisions (Subsidies, competition, demand symmetry, etc.) and also how fast we can make it run. Due to bureaucratic regulations, we had to breakup the project into two parts, so my primary responsibility will be doing the COO duties, meaning managing operations. This means that my duties start when I am instructed to build a specific kind of route between two places. In addition, I'll probably do a couple other algorithms to manage technology upgrades, routing and life-cycle management.

Of course we'll be working together on most areas since any good AI should be connected and fluid through all stages of the network design. There will undoubtedly be any number of barriers we'll encounter and things we are considering outside the scope of our design (Boats and trams, for instance, will not be used by our AI...airplanes probably will not be, but we'll see). During the beginning stages, we are also ignored a number of factors we hope to be able to address later such as competitors and subsidies.

Hopefully by this point the real world implications of this project should be fairly obvious. It will of course help develop our programming and algorithm writing abilities, but we also hope that it will give us a better sense of how to create efficient network flows. The game also is not that far off from how real-world networks operate. In fact if you go online in the game (As you can since it was open sourced), you'll find massive worlds where people collaborate to create incredibly realistic and advanced networks. Some of the rail junctions they create are mind-blowing, there's a whole set of standards for working on such networks online. Our AI won't come anywhere near that, but it'll try...despite any implementation barriers we might face, we hope that the theory behind how we create our networks will be sound throughout the process.

If you're interested in checking out the game, it can be downloaded/compiled for any platform (Except macs because they suck) here: http://www.openttd.org/en/ But actually you can't get it for mac because they don't have anyone to compile and test it for mac.

As for the future, I'll be posting more about our progress with examples of what I'm working on as I do it. I actually finished one interesting (and important) aspect already, and am just putting the finishing touches on it now, but I'll save that for another day!

Till then, happy networking!


1 comment

Comment from: Patty [Visitor]
PattyMaybe the folks at Delta will hire you after this so that my planes will be on time.
01/23/10 @ 20:36
A collection of musings from my time at Yale along with some thoughts about my "Freshman year of life" in San Francisco.


XML Feeds

blogging software