Table of Contents
The artificial intelligence built inside this game is one of the best ones that exist. The basic task of it is to find the right way of a vehicle from source station to destination station. The common abbreviation for artificial intelligence is AI. German talking players use the term KI (künstliche Intelligenz). AI is used by the computer player extensively, meaning for all actions (vehicle building, station building, route building). For human player, it is used for the vehicles to find the correct route. For the public hand, it is used for town manipulation. Simutrans uses the A* algorithm. It is an exact algorithm, meaning, the vehicles do not use stations as their destinations, but a grid coordinate. If you have a station over multiple grid coordinates, the vehicle tries to get to his given coordinate, and if it sees a longer station, then it goes to the edge of it. Also, based on the exactness, each vehicle uses only one specific platform on the multicoordinate stations. To help the pathfinding, it is the best to always use an optimal route to any part of the industry chain.
Simutrans uses a variation of the A* algorithm. The simple explanation for it is:
the whole map is divided in a grid
Any vehicle, passenger, cargo, mail searching a route, tries the possible routes thorough the grid coordinates. It ignores invalid paths. Yes, the scheme is the same for all of them.
The shortest route is chosen and vehicle chooses it automatically.
By altering some part of the network, the vehicle just moves on. When it notices, it cannot drive on the old route anymore, the vehicle stops, and the route is recalculated. This has some disadvantages by concept. The vehicles are always directed to the GRID, not the exact station (in case the station is longer than a grid). This concept also makes it difficult to ever implement twoway tram tracks on a single street! If you make a station longer, the vehicle tries to adapt. The drawback of the A* algorithm is, it is static! Moving vehicles are not taken in account, so it seems in game on a few occasions, as vehicle pass through each other. There is NO collision detection implemented!
There are some things to reconsider : All rails are equal! Tram and train use the same. So, the vehicle might choose a route on tram rails! This is not very reallistic though. Althorough, there are some tram system in the real world with a partial common rails for both the tram and train systems...
This is roughly the generic A* algorithm. Like said , Simutrans uses a variation to it:
Add the starting grid square (or node) to the open list.
Repeat the following:
Look for the lowest F cost grid square on the open list. We refer to this as the current square.
Switch it to the closed list.
For each of the grid squares adjacent to this current square …
If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
Stop when you:
Add the target square to the closed list, in which case the path has been found (see note below), or
Fail to find the target square, and the open list is empty. In this case, there is no path.
Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.