gdalgorithms-list

[Algorithms] Network prediction algorithms specific to racing?

[Megan F. <sha...@gm...>]

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?

-- 
Megan Fox
http://www.shalinor.com/

Re: [Algorithms] Network prediction algorithms specific to racing?

[Jason H. <jh...@st...>]

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?
>
>    

Re: [Algorithms] Network prediction algorithms specific to racing?

[Megan F. <sha...@gm...>]

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
<jh...@st...> 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&#174; 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
Megan Fox
http://www.shalinor.com/

Re: [Algorithms] Network prediction algorithms specific to racing?

[Blair H. <thy...@ch...>]

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

<http://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 <sha...@gm...> 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
> <jh...@st...> 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&#174; 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
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> >
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
> >
>
>
>
> --
> Megan Fox
> http://www.shalinor.com/
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Network prediction algorithms specific to racing?

[Jason H. <jh...@st...>]

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 
> <http://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 <sha...@gm... 
> <mailto:sha...@gm...>> 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
>     <jh...@st... <mailto:jh...@st...>>
>     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&#174; 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
>     > GDA...@li...
>     <mailto:GDA...@li...>
>     > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>     > Archives:
>     >
>     http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>     >
>
>
>
>     --
>     Megan Fox
>     http://www.shalinor.com/
>
>     ------------------------------------------------------------------------------
>     Download Intel&#174; 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
>     GDA...@li...
>     <mailto:GDA...@li...>
>     https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>     Archives:
>     http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Network prediction algorithms specific to racing?

[Darrell B. <db...@su...>]

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:jh...@st...] 
Sent: 16 April 2010 07:25
To: gda...@li...
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 <sha...@gm...>
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
		<jh...@st...> 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&#174; 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
		> GDA...@li...
		>
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&#174; 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
		GDA...@li...
	
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
		Archives:
	
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t
		


	
	
------------------------------------------------------------------------
------
	Download Intel&#174; 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
	GDA...@li...
	https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
	Archives:
	
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t

Re: [Algorithms] Network prediction algorithms specific to racing?

[Jamie F. <ja...@qu...>]

Jason Hughes wrote:

[snip]

> 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.

We used this on PS1 for a racing game (which wasn't released) back in 
'98; although the hint was per track quad rather than in a texture. The 
track was divided into strips of quads, and each quad had a vector 
associated with it that the AI used as a hint for what it should be 
doing. Worked fine in the end, but testing and debugging was a pain, as 
you'd have to first find a problem (test and test until a car hits 
something that misbehaves), work out which vector(s) gave bad hints, 
then tweak them... then test and test and test to see if the problem had 
gone away.

The plus side: it was fast; we had 30 racing cars on that little old PS1.

Jamie

> 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 
>> <http://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 <sha...@gm... 
>> <mailto:sha...@gm...>> 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
>>     <jh...@st... <mailto:jh...@st...>>
>>     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&#174; 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
>>     > GDA...@li...
>>     <mailto:GDA...@li...>
>>     > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>     > Archives:
>>     >
>>     http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>     >
>>
>>
>>
>>     --
>>     Megan Fox
>>     http://www.shalinor.com/

Re: [Algorithms] Network prediction algorithms specific to racing?

[Stuart C. <sca...@to...>]

The approach I've used on a few games in the past is to imagine a point out in front of the car that represents a location where some other authoritative machine says it should be some period of time from now, with rope attached to the steering of the car that pulls it towards that point at a fixed distance. With infreqent updates you might get the vehicle trying to cut corners or do other weird things, but for the most-part it worked pretty well with variable lag.

If you've got a proper tyre friction model, just be careful to turn the wheels towards where you want to steer rather than relying on a force from some point on the car to pull it into line.

Stuart

-----Original Message-----
From: Megan Fox [mailto:sha...@gm...] 
Sent: Friday, 16 April 2010 7:51 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Network prediction algorithms specific to racing?

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 <jh...@st...> 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&#174; 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-l
> ist
>



--
Megan Fox
http://www.shalinor.com/

------------------------------------------------------------------------------
Download Intel&#174; 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
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Network prediction algorithms specific to racing?

[Jon W. <jw...@gm...>]

If you do physical simulation of each entity on each client, then you can
"interpolate" the assumed control inputs, rather than the position/state of
the vehicle. You can assume that the player will want to turn into turns,
accelerate on straights, etc. When you find out that you predicted the
controls wrong, you apply a delta-control to the follow-on input controls
(allowing super-natural acceleration/braking for the sake of "catching up").
There is some risk that you'll end up oscillating if you over-compensate, so
there has to be a balance between compensating quickly and dampening the
response.

An alternative is to delay all the remote players by X amount of time, so
that you actually have their input when it comes time to simulate them, but
then you're out of "extrapolation" and into "lag compensation" territory.

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Thu, Apr 15, 2010 at 1:34 PM, Megan Fox <sha...@gm...> 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?
>
> --
> Megan Fox
> http://www.shalinor.com/
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>