A short History of Simutrans Development
I started developing Simutrans in Summer 1997. There were several reasons which made me start this project:
Making money was never a goal of Simutrans development. In addition, the usability of Simutrans for someone else was no goal, it was just intended to teach myself OOD, OOP and to learn the features of the C++ programming language. During Simutrans evolution, this goals changed a bit. As Simutrans became more and more popular, at least the usability for other people became an important goal, too.
Now, four years later, I learned a lot about OOD and OOP, and I think I know most features of C++ quite thoroughly now. Nowadays Simutrans is more or less my playground to test my ideas of producing easy to maintain and extensible software. Although making lots of mistakes in early Simutrans OO design, I learned how to gradually improve bad designs and to avoid quite some of the traps in new projects right from the start.
Programming techniques to avoid making bugs or at least techniques to find them quickly are now on top of my list of things to learn. Unfortunately, when I started Simutrans I knew very little about making robust programs and the various tradeoffs between speed and stability. OTOH learning from mistakes is maybe the strongest way to learn things, and so, Simutrans is a very good project to learn about error prone coding techniques and how to avoid them. Simutrans is now 35.000 lines of code and in a project of this size some coding rules seem to be absolutely necessary.
Early stages of development
In the beginning I documented all my ideas on paper only. Transforming them into electronical form without loosing the historical aspect of them is very hard. My only idea how to make the information available here was to scan the pages and offer the images here, along with a short description of the 'whys' and 'hows'.
How did it all start?
As mentioned in the introduction, in summer 1997 I had the idea to create a transport simulation, coded in C++ and designed as an object oriented program. Well, an idea is nice but a first step must be made to actually let the idea become a project.
In a lesson about robot construction at the university I was very bored and figured out the formulas for an isometric graphics engine. This engine was planned to be the base for my transport simulation. It was called the 'Simugraph' engine, 'graphics for simulation games'. This engine was intended to be a reusable piece of software and in fact it was not only used in Simutrans but in another game, Iso-Angband, too. For efficency the core of the Simugraph engine is coded in C. I was just beginning to learn C++ that time, and it's probably quite natural to use a well known language to build the core of a bigger project.
There are two sketches of the design of the Simugraph engine. What is written there was changed many times in the meantime, but that was the start:
Ah, yes, all those design sketches are written in German. That's my mothers tongue and when I made those sketches I never thought Simutrans could become that popular that I write a history and make it available in the internet.
What was the next step?
Landscapes are fun, but a transport simulation needs cities, too. After creating a initial version of the Simugraph engine I thought about ways to build cities automatically. The main difficulty was to create a good road network in the cities. Random placement couldn't be the answer, those roads are used by the player later in the game, and so they need to be quite usable. In addition, it turned out that roads are something like a skeleton of a city, and nice cities need a well formed skeleton.
I decided to use a rule based AI to build the roads, and then just place the buildings along the roads. Another set of rules to choose the right house type (residential, commercial or industrial) and an appropriate level completed the city building AI. If you look carefully, you'll see that cities in Simutrans tend to cluster industrial buildings in industrial areas, often a little outside the cities core, but well mix commercial and residential buildings as well as commercial and industrial buildings.
Some of the city road building rules (a very rough sketch):
Let the player interact with things
After landscape and cities were done, a new need showed up: The player wants to know about the things he sees. He wants also to interact with things in the game. Some kind of UI had to be implemented for this.
This is one of the darkest chapters in Simutrans history. The first design of the UI turned out to be much too narrow to be useful for anything else but small information windows. The second design allowed windows of arbitrary complexity but it turned out to be far to complex and creating new windows took much too long. In late 2000, a third design was made which is flexible and easy enough to allow to create all kind of windows quickly. Unfortunately the old stuff still exists and there is no time to rewrite it, so in fact, three different UI class hierarchies exist in Simutrans, leading to big confusion much too often.
The initial info window design:
I don't want to play alone!
Well in 1997 networking code was a book with seven seals for me. The only chance to add some opponents to the game was to create an AI. After the experience with Transport Tycoon Deluxe, this was intended to be a real good AI. Ok, now, some years later I know creating good AIs is very hard. Nevertheless I think the AI in Simutrans is much better than the AI of TTD.
Like the city building AI the player AI is a rule based AI. Often this kind of AI is called an 'expert system' (I hope this is the right translation of the German term 'Expertensystem').
The rules are simple, something like this:
What's written above in a few words is pretty hard work for an AI. Well, Simutrans AI at least solves the first task (building new routes) pretty well, but it is a bit clueless about the latter task. The first rule alone needs roughly 3000 lines of code for the full implementation ... writing a good AI still seems to be a big and challenging task. But somehow, it's fun to create an AI and watch it working.
I need something to transport!
A transport simulation needs things which are transported. Classical this are passengers, mail and goods. Goods are produced and transformed into other goods by industries and finally consumed by people in shops and supermarkets. The sketch below shows the original concept of goods in Simutrans. As you can see by the writing this sketch got some annotations by a friend of mine.
Goods in Simutrans:
Stops and stations
A transport simulation of course needs stops and stations where goods and passengers can enter transport vehicles and also transfer from one transport vehicle to another. In Simutrans goods and passengers have destinations, and they use all available transports to reach their destination.
Routing of goods uses Dijkstra's shortest path algorithm for finding the shortest route to the destination. Length in sense of Dijkstra's algorithm is measured in hops. This means the goods use the route with the least number of intermediate stations to their destination. This is not necessarily the shortest route if measured in miles, kilometers or map squares.
Where are the vehicles?
Somehow, no sketches about vehicle movement and routing exist. Maybe this explains the bad design of that part of the program.
In the beginning there was a lot of uncertainty about the implementation of vehicles, and until late 1999 it was quite unclear how this all should work. One thing was clear all the time: a 'perfect' routing algorithm has to be used. After some experiments with Dijkstra's shortest path algorithm, finally the A* algorithm was used. A* allows to find 'perfect' routes while using a lot of CPU time as well as finding 'good' routes in much less time. Currently Simutrans uses A* with settings for 'good' routes. This means vehicles in Simutrans never go wrong and get stuck in dead ends, but they don't use always the shortest route. The current settings allow routes to be roughly 10% longer than the absolutely shortest route, but most of the time the used route is indistinguishable from the best route by the player.
About OO Design
Maybe this is a bit off topic here, but since Simutrans was designed as an OO program, I think I should show the very first class diagram of Simutrans. The classes and their relations changed a bit in the meantime (this diagram is four years old!) but the core classes still exist.
First class diagram from 1997:
Please note that this is my very first try to design an OO program, so please don't blame me for mistakes I did that long ago! As written above I programmed Simutrans to learn OO design and over the past four years of Simutrans development I learned lots about the mistakes and weaknesses of the design shown above.
Rail block management
Rail block management (signaling) was introduced very lately. The initial design proofed to be unusable and I made several tries to improve it. Finally I dumped the first design and its implementation. The version which is implemented now, should work fine and be able to handle all special cases, but it is still a bit of fragile code.
Rail block management was introduced lately into Simutrans, in several steps from autumn 1999 to spring of 2000.
Dirty tile list
The purpose of the dirty tiles list is to speed up the graphics by just rendering the changed graphics on screen. To track the changed areas either dirty rectangle or dirty tile list can be used. Dirty rectangles are 'perfect' but it's expensive in terms of CPU time to split overlapping rectangles into non overlapping rectangles. Dirty tile list tend to mark bigger areas as dirty but they are very simple to implement and quick to compute. Simutrans uses a dirty tile list, to speed up the graphics by an average of 30%.
Similar to the rail block management this was introduced lately into Simutrans, in August 2000.
Dirty tile list design:
You see, most of the design was done in 1997. After that, in the following years this design was implemented, and lots of images were painted, sound routines were implemented and hundreds of bugs were found and fixed.
Lately bug fixing became the main effort in Simutrans development, so currently I'm reworking Simutrans for more robustness and easier bug fixing. Concepts of 'bomb-proof' programming were adopted and included. More advanced memory management techniques like garbage collection (which I hope reduces the number of mistakes in memory management) and key-lock mechanisms for better error checks in memory management were evaluated and partly integrated.
I started to create a log of all bugs and their solutions, along with statistics about the time to fix that bug and the places in the code which needed to be changed to fix that bug. Here's an excerpt of the bug log. I hope this bug log will help me to fix future bugs more quickly or to avoid making the same mistakes again in future projects.
Software testing is another one of this issues which arose lately. I wrote a suite of automated tests for Simutrans, but unfortunately it only covers 5-10 percent of the overall functionality. But at least the railroad building routines and the rail block management can be checked automatically. While writing this test suite, an amazing experience was to see that even the simplest automated test gives a good benefit in regression testing. There are many stupid mistakes one makes in daily work, and even simple test discover lots of them. But still, I don't know how to make good UI tests.
The course of development clearly changes from implementing new code to maintaining and expanding existing code currently and so do the things I learn from this project. The emphasis in learning moved from design and coding to testing and maintenance issues, and from bad experience with bugs to different coding techniques which hopefully reduce the number of bugs or at least make it easier to detect and fix them. Pointers are evil, I can tell!