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?

Improve this question
\$\endgroup\$
5
  • \$\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, 2016 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, 2016 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, 2016 at 8:49
  • 1
    \$\begingroup\$ @Eric updated the question. \$\endgroup\$
    – 0x81915
    Dec 28, 2016 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\$
    – AturSams
    Dec 28, 2016 at 12:17

1 Answer 1

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

Improve this answer
\$\endgroup\$
6
  • 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, 2016 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\$
    – AturSams
    Dec 28, 2016 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, 2016 at 14:33
  • \$\begingroup\$ Oh yeah, I read your comment again and the description and you"re absolutely right. \$\endgroup\$
    – AturSams
    Dec 28, 2016 at 14:34
  • \$\begingroup\$ The idea of using bit array and low resolution representation solved the problem. Thanks a lot. \$\endgroup\$
    – 0x81915
    Dec 29, 2016 at 15:31

You must log in to answer this question.

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