Re: Network prediction algorithms specific to racing?
"Darrell Blake" <[email protected]> Fri, 16 Apr 2010 10:07:19 +0100
| Newsgroups | gmane.games.devel.algorithms |
|---|---|
| Message-ID | <[email protected]> |
I recently worked on a peer to peer cart racing game and we experimented with dead reckoning and 2nd order polynomial interpolation but in the end we found that simple linear interpolation gave us the smoothest results in most cases. We sent packets with compressed data for the position and orientation and because the data was small enough we got away with sending 15 packets per second so the error margin was always quite small. Also, if we'd used a delta compression method we could probably have increased the send rate too. Interestingly enough, we looked at compressing the position based on track location but our tracks were fully 3D (loops, upside-down track, jumps etc.) so with the extra information that would have been required we didn't actually save that much more than if we just compressed the cartesian coordinates. If you know the dimensions of the track and therefore all the possible positions a racer can be in then you can compress within a certain range of values which brings the data size down too. Darrell ________________________________ From: Jason Hughes [mailto:[email protected]] Sent: 16 April 2010 07:25 To: [email protected] Subject: Re: [Algorithms] Network prediction algorithms specific to racing? Interesting. A set of track space coordinates, unfortunately, does not map continuously nor uniquely onto the cartesian world space, however. Except with a drag strip. :-) Even an oval would have a discontinuity at the checkered flag. Shortcuts, branches, or even places where an object might move jump between levels (fall off an upper deck to a lower one) would be severe and unpredictable discontinuities in that space. That severely impinges on the usefulness for prediction. (Aside: I recently ran into this problem when implementing a spline following camera system that indexes the spline directly based on the position of the hero character. Due to curvature of the spline, there are multiple valid associated camera positions associated with a single world-space point.) It does occur to me that it may not be possible to mathematically map uniquely into track space easily, but an artist could very well use a good UV layout tool to create a giant flowing UV shell that could at least create a fairly good coordinate space for the whole track. Positive in U means heading straight along the track, V would be the lateral axis. There would definitely be discontinuities when branches met, or when the player left the track (sometimes), but it could be done with existing tools in human-aided fashion. The very same mapping could also use that for helping AI drive, come to think of it. It's effectively an artist-generated influence map at that point. JH On 4/15/2010 6:47 PM, Blair Holloway wrote: Shawn Hargreaves wrote on his blog about having a track-space coordinate system in MotoGP: blogs.msdn.com/shawnhar/archive/2009/12/30/motogp-ai-coordinate-systems. aspx If you were to have the player's position and velocity transmitted in track space coordinates instead of world space, you'd be able to do dead reckoning in that space entirely - i.e. reckon forward based on the player's local track velocity rather than their world space velocity. As long as the player is on the track and not, say, driving perpendicular to it, the player would always interpolate along the track, even on corners. Corners are likely to be, quite literally, one of your corner cases, due to players needing to slow down to corner correctly - something the reckoning/interpolation would need to take into account. Additionally, if the player is driving fast diagonally across the track, there may be cases where he would be reckoned outside of the track, in which case you might need to detect those cases and switch to a world space prediction method. - Blair On Fri, Apr 16, 2010 at 7:50 AM, Megan Fox <[email protected]> wrote: At present, we have a fairly terrible scheme that amounts to no real rectification or prediction AND a dead-space that allows out-of-sync conditions to get around how jumpy it would be without it. Not so good. I was pulled off my other tasks and re-assigned to make it not suck / take it to polished instead of prototype, basically. My suspicion is that dead reckoning (ie. like you say, simple extrapolation from last known pos/vel) will be "ok", but that it will tend to not produce the smooth arcs I'd like to see in a cart racer. I'm also not convinced that a second or third degree prediction from sampling the prior positions would be anywhere near usable if the player ever deviated from smooth arc driving. So, just thought I'd see if there were any particular known-better-case solutions, given that it's a well-trodden domain. On Thu, Apr 15, 2010 at 3:25 PM, Jason Hughes <[email protected]> wrote: > I guess there are two aspects of this: prediction and visual rectification. > > We've been doing a networked basketball game recently, where one team is > entirely controlled remotely. Even with fairly high latency, slow > moving objects (like players) will look okay using a smooth > rectification algorithm, but they're a little delayed from real-time. > High velocity objects (ie. bullets or ballistic objects) are pretty > easy to sync as well, provided they are not controlled or intelligent. > The main issues we've had thus far involve rectifying the ball physical > state after a collision with a player, since that's often incorrect and > delayed. Luckily, most collisions in basketball games result in the > ball being grabbed, so this isn't always an issue. For reference, our > simple rectification code is X = Lerp(X, X', f), where f could vary > depending on the latency and current error. Spline rectification would > be nicer, and we might implement that, though it may be overkill for us. > > I haven't tried prediction beyond simple linear extrapolation based on > the last single sample (position, velocity, orientation). 1st order > prediction would likely close most of the gaps for generally smooth > functions like position and orientation, but for velocity, I'm not sure > it would help in our case, since the velocity is basically joystick > angle for us and is generally discontinuous. > > Sorry I can't be more help with racing specifically. Out of curiosity, > what have you tried and how did it work? > > Thanks, > JH > > Jason Hughes > President > Steel Penny Games, Inc. > Austin, TX > > > On 4/15/2010 3:34 PM, Megan Fox wrote: >> I'm currently fiddling with dead reckoning for a racing game I'm >> working on, but this seems like a specific enough domain that there >> ought to be specific-to-racing prediction approaches. We have a >> fairly good idea of what the player is doing (trying to stay on the >> track), and that would seem to give more data that isn't really being >> exploited with standard approaches - but googling isn't turning up >> much. >> >> Do such algorithms exist? Or, in practice, are the same approaches >> used in FPSes et al still the ones to use here? >> >> > > ------------------------------------------------------------------------ ------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t > -- Megan Fox http://www.shalinor.com/ ------------------------------------------------------------------------ ------ Download Intel® Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. http://p.sf.net/sfu/intel-sw-dev _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t ------------------------------------------------------------------------ ------ Download Intel® Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. http://p.sf.net/sfu/intel-sw-dev _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t ------------------------------------------------------------------------------ Download Intel® Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. http://p.sf.net/sfu/intel-sw-dev _______________________________________________ GDAlgorithms-list mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list