[Programming Question] How to quickly calculate the distance between buildings in a tile system.

Hi all,

my friend and I are currently working on a city builder game like Anno/Cities Skylines but with some own ideas and tweaks. (of course, on a much smaller scale)

Currently, we are struggling a bit with implementing the economy system and hoped that we could get some ideas for the implementation.

Residence buildings and all other buildings (production/service) are connected by roads. For our service buildings (fire stations, police, etc.) we would like to have a distance-based system instead of an area of influence. That means, depending on how many tiles a residence building is away from a service building the lower the effect.

Currently, I tried one approach with a breath deep algorithm.

The algorithm starts at the service building and progresses along the road. The algorithm first searches for adjacent roads and then writes them into a list of roads. It then saves the current tile distance into the road gameobject before moving to the next road in the list. (I tried to illustrate it in the picture)

Although the algorithm works well and is compatible with multiple service building overlapping, the main drawback of this approach is the performance.

  • Testing with 10 buildings or so, caused strong frame drops/freezing of the game.

  • I would also have to run this regularly as the player can remove roads and service buildings so I have to update it to account for any changes in buildings. (–> back to problem 1)

  • Since the values are saved on the road. All buildings also have to check the road they are connected to regularly. (Didn’t test it yet but I guess this would also take a heavy toll on the performance.)

I could try to use threading/ the job system to reduce the workload from the main thread and prevent freezing of the game. But my current implementation relies on game objects and the Unity API which is not compatible with threading (afaik). I think I could rewrite it to be compatible but I also think that the approach itself is flawed.

Another idea I had was to use an A* algorithm to check the distance of the residential building to the nearest service building. That way I would not have to save the data on the roads but it would still be pretty computation intensive. (I already started to implement this, (also with threading in mind) but I have a few bugs and the algorithm currently does not work properly at all.

As I said I don’t think my approach is the most elegant one. Does someone have a better algorithm or a better approach to store the data in our game to allow faster access and calculations?

If you need further details I will try to provide more details on my current implementation.

We also appreciate every idea and suggestion on the general data management structure to allow efficient data handling for the economy (production, good consummation, taxes, etc.)

Lastly, we are sorry if this is a stupid question. We are not the most experienced programmer and are learning on the fly :slight_smile:

If you’re using a tile based system, A* should be fairly quick, I don’t consider it to really be that computationally intensive. Also, you don’t have to run it regularly, you only need to run it when something changes.

Using the Road Values system you mentioned at the beginning, you don’t even have to search all the values whenever a tile gets updated. You only really need to check the tiles that have greater distance than the one you’re adding/removing with the Flood-Fill/Breadth-First-Search.

Hi,
thanks for the input.
I will try to get the A* working properly and then test it again. It just feels a bit inefficient to use the algorithm for all residential buildings.

Regarding the last part. I agree with you but I think I have the problem that the roads with a greater distance from the adding/removing road could have another service building that overlapped in the area. So in that case I would have to recheck all values.
Not sure if you get what I mean because it is difficult to describe.

Also do you have any other general suggestions regarding the data structure and access for an economy simulation game?

I could see why it might be slow in some cases depending on the sample size, although I think you’d have to test it yourself to see if the speed is acceptable for you.

I was pretty confident I thought it through and saw it covered all the cases, so that you don’t have to recheck all values. Feel free to let me know if there’s a case I missed though.

Any value less than the value of the road added or removed would never need to be checked because the shortest path up to that point hasn’t been changed. There’s no scenario where the changed road would be part of the path to a road closer than it. eg. if the road has a distance value of 6, then there’s no way a road with a value of 5 would have it on its path, as it doesn’t make sense to have the distance go up when you go closer to the target. I can draw some pictures later if it still doesn’t make sense.

You need to check all the values higher than it because the new road could be the new shortest path, or if removing it, tiles might have to find a new path. Tiles less than it don’t have to find a new path, because that path was longer anyways.

I’ve never built a simulation game, so I don’t really know about specifics for economy simulation games.

1 Like

Hi,
Thank you!
I talked it through with my friend and I think I get what you mean.
Feel free to post a picture if you have the time. Maybe it reveals something I forgot or misunderstood.
But I think that I have an approach now to improve the breadth-first algorithm to calculate the values only if something has changed and not regularly.
I will try to implement it tomorrow and see if it works out.

Any other suggestions or ideas are still welcome.