0
\$\begingroup\$

I am currently working on a City Builder Game and I often come across the problem of having to decide wich location to use.

Examples:

  • The citizen has a job and needs a home. There are several buildings with open slots.
  • The citizen is at a positon and is hungry. There are several restaurants on the map.

How can I choose the right building to go to? I don't really wan't to check the distance for each, because there could potentially be hundreds of buildings and that decision problem occurs quite often.

I also don't care for the optimal solution, any nearby result is fine.

Currently all buildings register them self in a LinkedList. When searching for something I'd start at the beginning and the first occurrence that was 'good enough' would be returned. Citizen now drive across the map for something that was right next to them if the one far away was built earlier in the game.

Any suggestions?

\$\endgroup\$
  • 2
    \$\begingroup\$ You could implement a space partitionning algorithm such as k-d trees. Then, according to the precision you want, you go find the node at the depth n (the bigger is n, the more chance you have to get the nearest point in space) \$\endgroup\$ – Hellium Aug 30 '18 at 12:05
  • \$\begingroup\$ Take a look at quad trees for a simple, 2-dimensional-specific implementation of a space partitioning algorithm. \$\endgroup\$ – Ed Marty Aug 30 '18 at 12:50
  • 1
    \$\begingroup\$ @Hellium that looks like it could make a good answer to this question. \$\endgroup\$ – DMGregory Aug 30 '18 at 21:19
  • 1
    \$\begingroup\$ @DMGregory: Because I have never used these techniques, I would not be able to provide a decent answer explaining how one would implement such algorithm. That's why I prefered giving this clue as a comment. \$\endgroup\$ – Hellium Aug 31 '18 at 6:35
1
\$\begingroup\$

The comments suggesting spatial partitioning are a decent choice, but the easiest solution would be to put different building types in different collision layers. Then just incrementally use something like Physics.OverlapSphere(...) or grow a spherical trigger.

You can the sort the results, or just choose the first one within an acceptable distance threshold

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.