# How to find the nearest object from another, in a non tile based game where obstacles are present?

The nearest object means the path from the initial position to this object is shorter than the path from initial position to any other object. The path is the smallest number of pixels this object must move to reach the target object while making sure that it does not collide with any obstacle.

Like in this example below, consider that object A has to determine which object is closer, object B or object C. The pink rectangle is an obstacle. Now if we consider the euclidean distance, object B will be closer but due to the presence of an obstacle euclidean distance will give false answers.

Another solution would be to find the distance using some pathfinding algorithm (like A*), which will give the correct solution, but will be slower than simply calculating euclidean distance.

The ideal solution should give the answer as an object the path to which is no more than 10% larger than to the nearest object. And it should take no more than 10 millisecond on a modestly powered computer to find the nearest object for 1000 different objects on a map that has upto 1000 obstacles of different sizes and the map is no larger than 1000*1000 pixels (like in the image above the nearest object for A is C, for B it is A and for C it is A). Also it should not take more than 50 MB of RAM (excluding the size of RAM used to store the coordinates of objects and obstacles and their sizes).

And the map is dynamic. The solution need not return the path between the objects, it need to only find the nearest object.

What will be the ideal solution of this problem?

• Until you have stuff like mazes, it's safe to assume the closest object is the closest in space – Bálint Dec 28 '16 at 8:46
• Re: the content of the question. You need to define 'nearest' in some way, and given a plane with arbitrary obstacles this definition will most likely be based on path distance. I don't really see a way around path finding in some form. What have you tried in this respect? – Eric Dec 28 '16 at 8:46
• Re: the question itself. You should at the least put an upper bound on 'slow': how often do and how many of your objects move (per frame, per minute) and how often should 'the nearest object' be updated? And since you seem to allow for a trade-off between 'correct' and 'fast' (do you?) a more precise definition of 'ideal' may also be required. :-) – Eric Dec 28 '16 at 8:49
• @Eric updated the question. – 0x81915 Dec 28 '16 at 10:19
• You can flood fill (BFS) a bit array that size rather quickly. It will give you the path and the distance in pixels. – AturSams Dec 28 '16 at 12:17

Considering the settings described in the question with a map limited to 1000^2 in size, that constantly changes, you can draw the obstacles on a bit array and then run A* where h(n) is the path length until node n and g(n) is the distance in pixels.