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\$
4
  • 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
    Commented Aug 30, 2018 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
    Commented Aug 30, 2018 at 12:50
  • 1
    \$\begingroup\$ @Hellium that looks like it could make a good answer to this question. \$\endgroup\$
    – DMGregory ♦
    Commented Aug 30, 2018 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
    Commented Aug 31, 2018 at 6:35

1 Answer 1

Reset to default
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\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .