   Optimally move point-array
  Hey everybody,I've got two arrays of coordinates (say, for a unit of soldiers), one is the "actual positions" and the other is the "future positions" array.I've been searching for a solution for optimal allocation of "future positions" to the actual positions, so that all soldiers have to walk about the same distance and the same ammount of time.My present take on the problem is going through all the future positions to find the "farthest" one from the actual positions of the soldiers. Then I allocate this coordinate to the nearest soldier to this position (for this I have to go through all actual positions and find the nearest one).I mark this future position and the soldier as "done" and then start the loop again, jumping over "done" positions, so I get the second farthest position etc. etc.As you can see this is really a killer since its duration is at least 2 * n^2.The Total War series (e.g. Rome, Medieval 2) have solved this perfectly, sadly I can't peek at the code. I'm sure somebody has thought about this before, any help would be really appreciated!Thanks!   
  This is a special cast of the assignment problem. An O(n3) algorithm exists which gives the optimal solution (which, incidentally, your algorithm does not), but I don't know of any more efficient exact approaches. Your algorithm can easily be improved to O(n log n) through the use of a spatial culling structure (like a k-D tree) for the nearest-neighbor queries, though.   ;  Sneftel beat me to it: The Hungarian algorithm (the O(n^3) solution to the assignment problem) is the thing that solves your problem as stated.While I'm here, though, I'll also point out another rather amusing approach:representing your formations as the roots of complex polynomials, and interpolating the coefficients.  AFAIK this comes with absolutely no optimality guarantees though.You can also do this kind of stuff with leader-follower networks, or various similar formation control schemes.  One of these is to just pathfind for the center of mass, and to then use an appropriate flocking-type behavior to enforce the formation.  I think this is actually the most likely approach, and I can post some more later about it.   ;  Hey, thanks for answering so fast!I do like maths, but I have to say that the Hungarian Algorithm and any other kind of complex mathematical approach is waaay beyond my present knowledge and understanding.Also, for the hungarian approach I'd first have to calculate the distances from each soldier to each future position just to get into "starting position" for running the algorithm, so to speak. Can you please tell me a bit more about nearest-neighbour queries and flocking behaviours? Also, here is a small graphic showing two standard-behaviours that would occure, just in case: http://www.2shared.com/photo/GWKPsPTu/assignment_problem.html   ;  Hey guys!I want to thank you a lot for pointing out the hungarian algorithm!I invested some time in understanding how it works and how to use it, and then it went faster than I had expected! It's now implemented and works exactly as I pictured it! 1000 Thanks!Friendly Greets,Tenshi   