   Waypoints and history / RTS unit navigation
  Hopefully this makes some sense, I''m rather tired (long day at work).Anyway, my problem is I''m attempting to comprehend a reasonable way for moving a _lot_ of units around somewhat efficiently. For example, say I have a server that computes movement for a bunch of units, and it takes care of calculating waypoints for these units and keeping track of where they are at given times.Given that scenario, does anyone know of any methods, or have any interesting ideas that would allow the server to bypass continually updating and moving the little units around each simulation tick? Perhaps storing a short history of waypoints for the units, and the times that it takes them to get from waypoint to waypoint, as well as the time that they actually hit the waypoint? Which would allow you to rollback to any specified time (as far back as the history goes, at least), and get that unit''s position?I''m just bouncing around ideas, and I''d love a little adverse input on the topic.. One of the problems I can see with my waypoint method is that units may collide with other units at given times, so I''d either be required to still do the game ticks for collision, or see if unit''s paths intersect in the same time region..Mkay, I think it''s time for bed.. Any comments appreciated! Even if you want to tell me I''m a crazy man Thanks,   Klowner________________http://dugnet.com/klown 
  Providing that no interaction involving units happens (no collision, attacks or anything else) then your system will work perfectly. Straight line motion is easy to predict. It''s doubtful though that in a game no interaction will happen, and when it does the complexity will grow exponentially.MarkFlatspace is here: The ultimate space adventurehttp://www.lostinflatspace.com;  Although I havn't been involved in any major stuff, I've thought of something similar, for the purpouse of reducing rounding errors using integer math for movement, for the slow time MMORTS I plan to make .My method is pretty simple... x,y,t.x/y are the coordinates of the unit at the last updatet is the absolute time of the last update.Changes to path due to reaching waypoints or collisions, or collision checks if using a finer grained scale (since the new x/y would need calculation anyways, might as well cache the result) update the x/y/t.Current x/y can be simply extrapolated from:V-- aka object x/y vars.x = oldx + mxy = oldy + mywhere: V-- program set constantmx = dt * dx / scalemy = dt * dy / scalewhere:dt = time - t (old time)dx = change in _x_ over _scale_ units of _t_.dy = change in _y_ over _scale_ units of _t_.aka, dx/dy would be found by:    V-- of objectdx = (targetx-x)*speed/distancedy = (targety-y)*speed/distancewhere:distance = sqrt((targetx-x)*(targetx-x) + (targety-y)*(targety-y))-Mikeedit: code tags   [edited by - MaulingMonkey on February 19, 2004 6:01:01 PM]