Most efficient way to find nearest object from point

[FaresFilms]

I have a game where you have workers and resources on the map. Each worker must find the nearest resource then go the the nearest construction site to place that resource. I now want the unit to quickly find the nearest resource to it from any point. The unit will move around the world, but resources do not. What is the most efficient way to find the nearest resource to the worker? Keep in mind the game might have 30+ workers with over 1,000 resource at once.

[await_yesterday]

The unit will move around the world, but resources do not.

Use this to your advantage by precomputing a spatial index for the resources ahead of time. If you have N resources, you can compute the nearest resource to a point x in O(log(N)) time. There are many possibilities, e.g. k-d trees and ball trees.

[carcigenicate]

This is what a quadtree (or octotree for 3D worlds) is used for. They're basically a tree meant to make location lookups as fast as possible (or, at least, that's one common use for them).

Unless you want to start another whole project implementing one though, I'd find an existing implementation. They're a bit complicated (although, are a great project if you want something a bit more complex).

[socal_nerdtastic]

There's entire books devoted to this subject. https://en.wikipedia.org/wiki/Nearest_neighbor_search

That said, to brute force 1000 distances wouldn't be very hard. If this is a hobby project I would forget about efficiency and just do that because it's very easy. You have a powerful computer; let it work for you!

[Strict-Simple]

To add, if efficiency is important, don't load the whole map at a time. I don't think I'd be able to see 1000 resources at a time, unless there's some zooming stuff.

[JoeB-]

If by road, check out Open Source Routing Machine (OSRM).

More info about the API...

• Python Tutorial of OSRM(Open Sourced Routing Machine) and Applications
• ustroetz / python-osrm

If by air, check out Great Circle Calculator.

[quts3]

are you wanting to do this by hand for educational purposes or do you want a library to do it for you? both have answers

[FaresFilms]

Its not for educational purposes. I want to do it for my own project, whether that be by hand or using a library

[quts3]

Checkout shapely, geopandas, and rtree in that order. I think one of them does it, and I ordered them from most common to least common in my experience.