Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I want to find a path for each point to its Destination so that the points do not collide with each other in (x, y, t) where t is time.

Imagine dots moving continuously across a screen so that they go to their respective destinations and do not hit into each other. The paths do not need to be the shortest paths.

How do people recommend going about this problem? I have heard the options of an A* search and running a simulation, where dots feel a "repulsive force" when they become too close to each other. Thanks!

  • $\begingroup$ The dots could get non-integer coordinates? Does variable t denotes no collision at time t, or you mean that when paths are drawn, none of them intersect (meaning at any t)? How do you evaluate good approach? Say, you write straight line for the first point, then you go around 1px from line, until you draw all of them. Would it work for you? If not, do you want to minimize sum of paths length? $\endgroup$
    – Evil
    May 4 '18 at 20:27
  • $\begingroup$ Yes the dots can get non-integer coordinates. In regard to the variable t, I mean the latter. It describes that points can never have the same (x, y, t) on respective paths. If they do, this would mean they are at the same place at the same time (a collision). However, this is an over-simplification of the problem--really the points need to stay outside a certain radius of each other. As for the straight line approach, I'm a bit confused if you could rephrase. I should add that the points all move simultaneously--not one by one. I do not to need to minimize the sum of path length. $\endgroup$ May 4 '18 at 20:44
  • $\begingroup$ Ok, they move simultanously, but the task is online or offline? Meaning you can calculate paths in advance or dots move and you avoid collisions. If the first, you can greedily assign path to some dot, then make offset (the radius you mentioned) and calculate another one by one. If the later, the repulsion method seems very convenient. How many dots are there? If I understood your task, A star will work (the lines I proposed is something similar). Task seems like connecting start to end points so that paths do not intersect without constraints besides path radius, is it right? $\endgroup$
    – Evil
    May 4 '18 at 21:39
  • $\begingroup$ Paths can be calculated in advance or the dots can move and avoid collisions. I will probably implement the "repulsive" approach for sure, but I'd like to also test the pre-computing approach. I like the greedy idea--that seems to be a simple approach to calculating the paths in advance. Say there will be at most 12 dots. Yes the task is that, except that the paths can intersect in (x, y), just not (x, y, t). How would I conceptualize pre-computing the paths with continuous coordinates? I'm not sure what a graph traversal would look like there. $\endgroup$ May 4 '18 at 21:58
  • $\begingroup$ iis.sinica.edu.tw/JISE/1999/199909_07.pdf or shiweisong.com/files/pathfind_v2.pdf ? $\endgroup$
    – Evil
    May 5 '18 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.