Friday Dev News #84 - Pathfinding for Bigger Maps
Hello everyone!
Today we don't show any new graphics or art concepts, instead we go on a little deep dive on game performance on big maps.
Bigger maps are one of the most common community requests and since we're doing the terraforming update anyways, it's a good point in time to check if they are possible.
There are actually 2 different types of problems to solve:
The first one is just simple simulation performance of production buildings, cars, trains, etc. When we quadruple the map size, we just have to speed up the simulation performance by 400%. Sounds like a lot, but doable.
The other problem is pathfinding performance. This is a lot more difficult since the the time to find a path for a car to take does not grow linearly with performance - it grows a lot faster.
We did our experiments on a city with 100k citizens. This is waaaay more than needed to reach the current endgame, but it's close to the max of what players can fit onto a current InfraSpace map. I have only seen 2 players reach that kind of city size so far.
A 100k city looks like this:
This save game features around 7,000 roads (14,000 road directions to do pathfinding on, since most roads are 2-way), 16.000 buildings and 15,400 active cars - and we want to quadruple that.
Before we look into general game performance, we need to check if we can deal with the pathfinding problem appropriately - otherwise bigger maps won't be possible, period.
In order to simulate bigger cities, we use a simple random road network generator. It's not a perfect recreation of player city networks, but it's a good enough approximation. We can generate road networks of different sizes easily for performance testing:
The green lines are highways.
In order to make pathfinding feasible, we use a 2-step algorithm that preprocesses the road network first to enable lightning fast pathfinding queries later, called contraction hierachies (paper).
With a 100k city, the preprocessing step only takes 11 seconds, that means it takes 11 seconds for cars to take your new road after you placed it - that's good enough for such a huge city.
With a 400k city, the network becomes much more complex to preprocess, taking 225 seconds or almost 4 minutes. That's too long.
While other team members were working on the terrain generation, I focused on some deep optimizing and found a 2-part solution: First we cut down the size of the graph by replacing some stretches of road with simple shortcuts. Then we run a much more optimized version of the contraction hierarchy preprocessing time.
The results for the 100k city look like this:
The 400k city takes a lot longer, but is still in an ok range because this is only for players that push InfraSpace to it's max even when we quadruple the size:
So it seems like we may be able to increase the map size when it comes to pathfinding. There are a lot of other optimizations that need to be done and I'm not sure we'll actually change the size for the terraforming update, but it's good news nonetheless.
I hope you enjoyed the technical deep dive post for a change, and as always, happy playing!
Today we don't show any new graphics or art concepts, instead we go on a little deep dive on game performance on big maps.
Bigger maps are one of the most common community requests and since we're doing the terraforming update anyways, it's a good point in time to check if they are possible.
There are actually 2 different types of problems to solve:
The first one is just simple simulation performance of production buildings, cars, trains, etc. When we quadruple the map size, we just have to speed up the simulation performance by 400%. Sounds like a lot, but doable.
The other problem is pathfinding performance. This is a lot more difficult since the the time to find a path for a car to take does not grow linearly with performance - it grows a lot faster.
We did our experiments on a city with 100k citizens. This is waaaay more than needed to reach the current endgame, but it's close to the max of what players can fit onto a current InfraSpace map. I have only seen 2 players reach that kind of city size so far.
A 100k city looks like this:
This save game features around 7,000 roads (14,000 road directions to do pathfinding on, since most roads are 2-way), 16.000 buildings and 15,400 active cars - and we want to quadruple that.
Before we look into general game performance, we need to check if we can deal with the pathfinding problem appropriately - otherwise bigger maps won't be possible, period.
In order to simulate bigger cities, we use a simple random road network generator. It's not a perfect recreation of player city networks, but it's a good enough approximation. We can generate road networks of different sizes easily for performance testing:
The green lines are highways.
In order to make pathfinding feasible, we use a 2-step algorithm that preprocesses the road network first to enable lightning fast pathfinding queries later, called contraction hierachies (paper).
With a 100k city, the preprocessing step only takes 11 seconds, that means it takes 11 seconds for cars to take your new road after you placed it - that's good enough for such a huge city.
With a 400k city, the network becomes much more complex to preprocess, taking 225 seconds or almost 4 minutes. That's too long.
While other team members were working on the terrain generation, I focused on some deep optimizing and found a 2-part solution: First we cut down the size of the graph by replacing some stretches of road with simple shortcuts. Then we run a much more optimized version of the contraction hierarchy preprocessing time.
The results for the 100k city look like this:
The 400k city takes a lot longer, but is still in an ok range because this is only for players that push InfraSpace to it's max even when we quadruple the size:
So it seems like we may be able to increase the map size when it comes to pathfinding. There are a lot of other optimizations that need to be done and I'm not sure we'll actually change the size for the terraforming update, but it's good news nonetheless.
I hope you enjoyed the technical deep dive post for a change, and as always, happy playing!
