3
\$\begingroup\$

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. A simple case

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?

\$\endgroup\$
  • \$\begingroup\$ Until you have stuff like mazes, it's safe to assume the closest object is the closest in space \$\endgroup\$ – Bálint Dec 28 '16 at 8:46
  • \$\begingroup\$ 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? \$\endgroup\$ – Eric Dec 28 '16 at 8:46
  • \$\begingroup\$ 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. :-) \$\endgroup\$ – Eric Dec 28 '16 at 8:49
  • 1
    \$\begingroup\$ @Eric updated the question. \$\endgroup\$ – 0x81915 Dec 28 '16 at 10:19
  • 1
    \$\begingroup\$ You can flood fill (BFS) a bit array that size rather quickly. It will give you the path and the distance in pixels. \$\endgroup\$ – wolfdawn Dec 28 '16 at 12:17
2
\$\begingroup\$

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.

You can use a low res representation 250^2 / 100^2 if you can afford to lost a little bit of accuracy.

https://en.wikipedia.org/wiki/A*_search_algorithm

\$\endgroup\$
  • 1
    \$\begingroup\$ The remarks on A* here may be misleading. A* does guarantee that it will find the shortest path. It uses a heuristic to speed up the search by choosing seemingly-promising directions first, but that does not reduce its accuracy because it still goes through all the steps to validate its guess (provided the heuristic is "admissible" meaning that it never over-estimates the distance). You could use A* with a heuristic that is the shortest Euclidean distance to any obstacle, for example. \$\endgroup\$ – DMGregory Dec 28 '16 at 14:25
  • \$\begingroup\$ How would it speed up the process if it it "still goes through all the steps to validate its guess"? If you go through all the steps, you are running plain old Dijkstra, no? You mean it avoids checking paths that will not lead to a target? \$\endgroup\$ – wolfdawn Dec 28 '16 at 14:27
  • 1
    \$\begingroup\$ Because validating one answer often takes fewer steps than exhaustively checking all answers. While Dijkstra will tend to search in an expanding circle, even if all the goals are in one direction, A* will beeline toward the goals, and only return to search the other possibilities if its way is blocked. A*'s advantage is that it prioritizes the directions the heuristic finds most promising, reducing aimless search in unfruitful areas. This prioritization does not affect the correctness of its answer as long as you use an admissible heuristic. \$\endgroup\$ – DMGregory Dec 28 '16 at 14:33
  • \$\begingroup\$ Oh yeah, I read your comment again and the description and you"re absolutely right. \$\endgroup\$ – wolfdawn Dec 28 '16 at 14:34
  • \$\begingroup\$ The idea of using bit array and low resolution representation solved the problem. Thanks a lot. \$\endgroup\$ – 0x81915 Dec 29 '16 at 15:31

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.