BaK's Rambling...

[Bak]

Continuum does black magic when it draws other player's ships on your screen. The timers for all the players are not synchronized very well, so if you just draw the ship with your best prediction, it jumps back and forth as either of the players' latency jumps back and forth (which happens often).

 

So how does the drawing continue to look smooth? Continuum cheats. The way I did it in Discretion, and the way I think it's done in Continuum, is that it adjusts each player's velocity so that their ship will work it's way to the correct position over time, rather that instantly resetting the position to the best prediction (which would make it jump on your screen). Want proof? Fly next to a player in Continuum that's drifting through space. Match his speed. If you look at him he'll be drifting faster and slower as Continuum adjusts his velocity for you. Black magic!

 

Anyways the code to do it in Discretion is below. There's two settings you can adjust, which are

 

[OtherShips]

;;; The amount of time in milliseconds we must "tweak" the velocity before the player's position is

;;; exactly what we predict it should be

;;; too low = bad because suffers from latency jerkiness

;;; too high = bad because we may never catch up to their real position (and have to reset more)

Prediction Velocity Adjust Time = 300

 

;;; The distance, in pixels, the player's drawn position is allowed to stray from what we predict the real position is

;;; note that it never stays this far for more than a few fractions of a second because the velocity adjustment corrects it

;;; too low = bad because we reset often which causes jerkiness

;;; too high = bad because the player's position may not be drawn accurately

Prediction Reset Distance = 40

 

During my tests it actually looks better in Discretion than in Continuum, but I'm not 100% this is always the case since when I run both side by side the fps on the non-selected one drops to ~10fps. I'll need to get another computer to test it if still looks good at high fps. I suspect that by modifying the settings it can look reasonable.

 

s->vel.x = xvel;
s->vel.y = yvel;
s->display = true;
s->rot = sm->frameToRot(frame, s);
	
// look at the timestamp and compute the predicted "correct" position for the player
int millDif = 10 * (((net->getServerMilliseconds()/10) & 0x0FFFF) - pi->getValue("timestamp"));
// millDif is positive, how much later it is than when the event occured
	
// predicted correct positions
int newx = xpos * 10000 + (xvel * millDif);
int newy = ypos * 10000 + (yvel * millDif);
	
// these are how much we are "off" by
int dx = (newx - s->loc.x)/10000;
int dy = (newy - s->loc.y)/10000;
	
// resetDist is in pixels
u32 maxDistSq = resetDist * resetDist;
u32 distSq = dx * dx + dy * dy;
	
// if we're drawing too far away from the predicted position, jump the player to the correct spot
if (distSq > maxDistSq)
{
s->loc.x = xpos * 10000;
s->loc.y = ypos * 10000;
}
else
{	// otherwise cheat with the velocities to fix the player position smoothly			
	
// s->vel = pixels/10sec, velAdTime = ms, newx/s->loc.x = 10000*pixels
if (s->loc.x / 10000 != newx / 10000)
	s->vel.x += ((newx - s->loc.x)) / (velAdjustTime);
	
if (s->loc.y / 10000 != newy / 10000)
	s->vel.y += ((newy - s->loc.y)) / (velAdjustTime);
}

[tcsoccerman]

that's the kind of coding you show off with lol.

[jake13jake]

I'm having a hard time figuring out what all the 10,000s are for. Generally I'd use something similar as a cop-out of a rounding situation (where there is generally a far more elegant solution). However, if it has some particular meaning, I'd set it as a constant.

 

I'm taking that s is the ship, and rot is the ship's rotation, though it would be more clear if the variable names were more verbose.

No idea what pi is. No idea what the bitwise-and is for, though I know if it weren't there you could get rid of the 10* and /10. I'm !@#$%^&*uming that millDif is in units of milliseconds.

 

Since maxDistSq and distSq are only used once, I'd just calculate them in the conditional statement, Either that or give them verbose names, because then it would have the reason of being there for people to understand the code.

 

Unless this is integer division, I have honestly no clue why there's division in this statement:

(s->loc.x / 10000 != newx / 10000)

 

s->vel.x = xvel;
s->vel.y = yvel;
s->display = true;
s->rot = sm->frameToRot(frame, s);
	
// look at the timestamp and compute the predicted "correct" position for the player
int millDif = 10 * (((net->getServerMilliseconds()/10) & 0x0FFFF) - pi->getValue("timestamp"));
// millDif is positive, how much later it is than when the event occured
	
// predicted correct positions
int newx = xpos * 10000 + (xvel * millDif);
int newy = ypos * 10000 + (yvel * millDif);
	
// these are how much we are "off" by
int dx = (newx - s->loc.x)/10000;
int dy = (newy - s->loc.y)/10000;
	
// resetDist is in pixels
u32 maxDistSq = resetDist * resetDist;
u32 distSq = dx * dx + dy * dy;
	
// if we're drawing too far away from the predicted position, jump the player to the correct spot
if (distSq > maxDistSq)
{
s->loc.x = xpos * 10000;
s->loc.y = ypos * 10000;
}
else
{	// otherwise cheat with the velocities to fix the player position smoothly			
	
// s->vel = pixels/10sec, velAdTime = ms, newx/s->loc.x = 10000*pixels
if (s->loc.x / 10000 != newx / 10000)
	s->vel.x += ((newx - s->loc.x)) / (velAdjustTime);
	
if (s->loc.y / 10000 != newy / 10000)
	s->vel.y += ((newy - s->loc.y)) / (velAdjustTime);
}

[»CypherJF]

I agree - no "magic numbers" please!

[Bak]

<_< good point.

 

internally the ship's location is stored as 10000th of pixels. if it's not done this way, when the ships are moving very slowly they'll stop moving completely as you can't move a whole pixel in one frame iteration (and movement looks sloppy). Rounding won't work for this reason. I should make it a constant though... any name suggestions?

 

pi is the packet instance... pi->getValue("timestamp") is the timestamp we just received in the packet. The reason for the binary & is that in the player packet, the timestamp is stored as a 16 bit value, whereas when you do a timer sync it's 32 bits... continuum is re!@#$%^&*ed I know.

 

distSq and maxDistSq are verbose names.. distance squared and maximum distance squared... it's the pythagorean theorem without the square root which is unnecessary for just comparing distances.

 

everything is integer division, "(s->loc.x / 10000 != newx / 10000)" is checking whether the pixel of the Ship* (which we are drawing), is the same as the predicted actual pixel position.

[»CypherJF]

pixel movement threshold ?

[Drake7707]

so if i get this right you're lineair interpolating the velocity to converge to the correct location ?

 

also

 

if (s->loc.x / 10000 != newx / 10000)

if (s->loc.y / 10000 != newy / 10000)

no reason to divide by 10000

[Bak]

sort of, except that I'm not really interpolating just modifying the velocity to the correct location.

 

(5/3 == 4/3) but (5 != 4)

[rootbear75]

kinda cool Edited May 5, 2008 by rootbear75

[Drake7707]

oh are those integer divisions

[Samapico]

c/c++ divisions are always integer divisions (when dealing with integers, anyway)

[Bak]

don't mix c and c++ code in the same executable -nt

[»D1st0rt]

what if you compile them both to machine instructions first

[Dr Brain]

internally the ship's location is stored as 10000th of pixels. if it's not done this way, when the ships are moving very slowly they'll stop moving completely as you can't move a whole pixel in one frame iteration (and movement looks sloppy). Rounding won't work for this reason. I should make it a constant though... any name suggestions?

 

Maybe this is a silly question, but why not store them as 1/8192 of a pixel? Right and left shifting is much, much, much faster than multiplication and division, at least on Intel machines. I'm jumping in on this in the middle, so if there's a good reason to keep it at 10000, ignore me.

[Bak]

it's convenient when you have to move things around, as speeds are in pixels / 10 seconds, so you can just take milliseconds * velocity to get the change in position. Although that's a pretty silly reason since you could convert from pixels / 10 seconds to pixels / 8.192 seconds when you load the settings. It probably is an optimization I could make at some point.

 

Integer multiplication should be pretty quick since you can do many things in parallel, division is probably a slowdown.

[»doc flabby]

Its unlikely after compiler optimisation it would make much difference imo.

[Dr Brain]

Its unlikely after compiler optimisation it would make much difference imo.

 

The machine instruction itself is what is slow. Division is a complicated multistage algorithm in the ALU. No compiler can change that. A complier might optimize a division to a right shift if it could prove that the divisor was power of two, but that's not the case when it's 10000.

 

True, there may still be little difference in terms of performance, but for something that is happening several times hundred times a second in a large zone, it's better to be fast.

[»doc flabby]

Yes that is true, integer divisions (on the processor) are slow. However multiplication is fast. A very commen optimisation by most compliers convert integer divisions by a fixed number (eg x /10000) in source into integer multiplication instructions which are fast. this is what i'm refering too. You can check this by creating a simple c program which does a division and then dis!@#$%^&*ble it

 

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
 int x,y;
 x= 0;
 y = 0;
 printf("\n Enter an Number:  ");
 scanf("%i",&x);
 int ans = x / 10000;
 printf("\n Answer / 10000 = %i\n", ans);
 system("PAUSE");
 return 0;
}

Dis!@#$%^&*mbly for optimized exe of code above

 

As you notice there are NO IDIV instructions. The division is carried out using MUL (multiply)

004012F0  /$ 55			 PUSH EBP
004012F1  |. B8 10000000	MOV EAX,10
004012F6  |. 89E5		   MOV EBP,ESP
004012F8  |. 83EC 18		SUB ESP,18
004012FB  |. 83E4 F0		AND ESP,FFFFFFF0
004012FE  |. E8 7D050000	CALL divide.00401880
00401303  |. E8 F8000000	CALL divide.00401400
00401308  |. C745 FC 000000>MOV DWORD PTR SS:[EBP-4],0			  ; ||||
0040130F  |. C70424 0030400>MOV DWORD PTR SS:[ESP],divide.00403000  ; ||||ASCII 0A," Enter an "
00401316  |. E8 DD050000	CALL <JMP.&msvcrt.printf>			   ; |||\printf
0040131B  |. C70424 1530400>MOV DWORD PTR SS:[ESP],divide.00403015  ; |||ASCII "%i"
00401322  |. 8D4D FC		LEA ECX,DWORD PTR SS:[EBP-4]			; |||
00401325  |. 894C24 04	  MOV DWORD PTR SS:[ESP+4],ECX			; |||
00401329  |. E8 C2050000	CALL <JMP.&msvcrt.scanf>				; ||\scanf
0040132E  |. C70424 1830400>MOV DWORD PTR SS:[ESP],divide.00403018  ; ||ASCII 0A," Answer / "
00401335  |. 8B4D FC		MOV ECX,DWORD PTR SS:[EBP-4]			; ||
00401338  |. BA AD8BDB68	MOV EDX,68DB8BAD						; ||
0040133D  |. 89C8		   MOV EAX,ECX							 ; ||
0040133F  |. F7EA		   IMUL EDX								; ||
00401341  |. 89C8		   MOV EAX,ECX							 ; ||
00401343  |. C1F8 1F		SAR EAX,1F							  ; ||
00401346  |. C1FA 0C		SAR EDX,0C							  ; ||
00401349  |. 29C2		   SUB EDX,EAX							 ; ||
0040134B  |. 895424 04	  MOV DWORD PTR SS:[ESP+4],EDX			; ||
0040134F  |. E8 A4050000	CALL <JMP.&msvcrt.printf>			   ; |\printf
00401354  |. C70424 2F30400>MOV DWORD PTR SS:[ESP],divide.0040302F  ; |ASCII "PAUSE"
0040135B  |. E8 88050000	CALL <JMP.&msvcrt.system>			   ; \system
00401360  |. C9			 LEAVE
00401361  |. 31C0		   XOR EAX,EAX
00401363  \. C3			 RETN

 

I've attached the exe if you need to verify

divide.exe

[Dr Brain]

That's ok. I prefer AT&T syntax from my compiler writing days. I didn't realize one could make that optimization, but it's pretty nifty.

 

movl	-8(%ebp), %ecx
movl	$1759218605, %edx
movl	%ecx, %eax
imull   %edx

 

Even then, a right shift will be faster than multiplication, but it won't be as marked as the difference from division.

[Snrrrub]

Bak, in this part:

 

if (distSq > maxDistSq)
{
s->loc.x = xpos * 10000;
s->loc.y = ypos * 10000;
}

 

you don't want to use xpos and ypos - instead, you want:

 

if (distSq > maxDistSq)
{
s->loc.x = newx;
s->loc.y = newy;
}

 

I had released virtually identical code in 2002: http://daccel.cvs.sourceforge.net/daccel/S...amp;view=markup

 

You should consider looking at the code I have already made available - it might prove useful.

 

-Snrrrub

[Bak]

cool thanks.

 

yeah there's something else I need to add like when the velocity is 0 I think continuum doesn't do prediction and just places the player on their correct spot... Weird behavior now when people stop in safe zones you can see discretion trying to adjust the velocity to make him get on the correct spot, maybe I just need to fine tune the parameters.

[Bak]

I'm working on it ok... there's lots of stuff i needed to adjust to get discretion modules working on ASSS server... most notably I'm working on getting server-side weapons in so players can actually get hit (also no cheating!). Anyways the big problem is discretion modules are made to be for one arena, whereas a server must handle multiple arenas. I have just about every module done... still gotta fix one or two and we should have a online playable version out with server-side weapons.

[»doc flabby]

I will look forward to seeing the result of your work with interest.

I'm facing the same issues, epescially with server synconisation.

http://www.gamedev.net/reference/articles/article1370.asp

 

I think HL2/CS:Source handles this by rolling back the game state and seeing if when you originally shot the bullet it would have hit its target, taking into account movement of the target whilst the bullet is in motion.

[Bak]

find the bug:

 

Particle* p = (Particle*)amalloc(sizeof(Particle*));

 

...

 

 

where's that bullet to the head emoticon, can't believe I'm stupid enough to do that... twice in one file at that

 

show all emoticon's doesn't work... http://forums.invisionpower.com/index.php?app=tracker&showissue=15558

[Samapico]

sizeof(Particle)