|« Mid-Week Rant||Superbowl XLIV and Commercials »|
So ZooElite, our AI for Transport tycoon I mentioned earlier is now in full development. One of the first things I've been working on is determining the optimal placement for a given number of bus stations in a given city. This little info bit will explain how I'm choosing station placements. Read on for details!
Each bus station has a certain radius (3), which it pulls passengers from. So ideally they shouldn't overlap any. Furthermore, they must be built either on a straight road tile or an empty tile adjacent to the road.
To start with, we need to figure out just how far we have to search away from the city center. To do this, I take the square root of the number of houses in the city. If the city were square this would give us the exact radius needed to cover the entire city. However to account for roads and for oddly shaped cities, we also use a multiplier to expand the radius. Below, you can see a city and the radius that will be used (7).
Now we get the list of all tiles within that square and start to narrow it down. First, we eliminate all tiles with houses on them. Next we eliminate all tiles which are not straight road tiles. Lastly, we eliminate all tiles not adjacent to a piece of road. This leaves us a subset of tiles which will either be suitable for a drive-through or a bus depot. So now we do a combinatorial optimization to see which set of tiles yields the highest amount of passengers. For this particular city, we end up with a configuration of two as shown below:
I don't think this is actually the optimal configuration. But the way we've implemented the algorithm favors speed over accuracy. So the first station is placed near the center of the city (Red), then additional cities are placed as space permits (Purple). Lastly, a depot is built in the city (green). Now we have all the city bus stations built!
The nice thing about this algorithm is that it can be run multiple times as the city expands, and it will always create the optimal solution for the given current configuration and parameters. Here is another city which is covered using 3 stations.
So now that we've covered the city, we'd like to connect this city to other cities. That's next time! I'll show you how I'm building rail stations to handle long distance hauls. Till then!