# How to quickly calculate the number of tiles between buildings in a tile system

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 :)

• How often does this run? How big is the graph (# of nodes in the BFS)? Jun 2, 2022 at 22:08
• If you got severe stutter with only 10 buildings, it sounds like you most likely made mistakes in your BFS algorithm. Perhaps you should share the code so we can help you identify problem areas, before attempting a more complex algorithm. Jun 2, 2022 at 22:23
• @Pikalek I currently tested it in a setting with 10 buildings. I then started the road update manually using a button. The number of nodes depends on how many roads are placed. This increases depending on the size of the city I guess. But my current test was quite small and already caused problems. Jun 3, 2022 at 17:43
• @Kevin That's possible. I am currently rewriting the algorithm and already found some unnecessary parts. If it is finished and I still struggle with the performance I will post the code. Thanks for your help! Jun 3, 2022 at 17:46