Sign in to follow this  
graveyard filla

collision problem in online game (2D)

Recommended Posts

hi, im working on a multiplayer action / RPG, 2D using square tiles. i use the mouse for movement in the game to help save on bandwith and make it easier to sync. anyway, when a player clicks, his character walks in a strait line to where the user clicked untill he either hits a wall / another character / clicks somewhere else. when he clicks, he sends the server where he clicked and a timestamp. when the server gets this, he does the same calculation for the strait line, finds out how much time has passed with the timestamp, and then i make up for lost time by moving to pos + (velocity * time_passed) (essentially he "jumps" to make up for lost time, so that everyone is on the same spot on all clients and the server). he sends the packet to all clients in his area and they do the same. this puts the characters in the same spot on all clients and the server. i also use the same system for guns / projectiles. anyway, heres the problem. when i do that initial "jump", i don't know how to make sure that the jump wont send me through a wall or another character or anything. i know this is probably easy but im just mathmatically retarded. thanks a lot for any help. [Edited by - graveyard filla on December 6, 2004 1:32:01 AM]

Share this post


Link to post
Share on other sites
It would seem much simpler for all players to send their data - like their position and current state - to the server, and for the server to appropriately send data to all players in a given area. This would save on bandwidth.

And having your player calculate their movements packet by packet and then sending a packet whenever their state changes would be much simpler. It would also allow you to check for collisions on the client end.

However, with your method, the best way to do it is check and see if the tile being clicked on is movable or not. ditto for the first tile in the movement series.

Share this post


Link to post
Share on other sites
Quote:
Original post by andrewk3652
It would seem much simpler for all players to send their data - like their position and current state - to the server, and for the server to appropriately send data to all players in a given area. This would save on bandwidth.

And having your player calculate their movements packet by packet and then sending a packet whenever their state changes would be much simpler. It would also allow you to check for collisions on the client end.


sorry, i think your misunderstanding me. the player sends the server where he clicked when he clicks to move. the server updates his simulation and then relays the packet to all other clients in his area and they do the same. i don't see it using any less bandwith then this... sorry if im misunderstanding you.

Quote:

However, with your method, the best way to do it is check and see if the tile being clicked on is movable or not. ditto for the first tile in the movement series.


im sorry but i don't follow. why would the tile being clicked on be effected? the initial "jump" i make should usually only effect maybe the tile im standing on or if the lag is bad a tile adjacent to the tile im standing on. i think i have to draw a line from where i currently am to where the end of the "jump" is, and if the line goes through something solid, i move to the edge of that object. i'm just not sure how to draw this line and find what it intersects with at what positions.

Share this post


Link to post
Share on other sites
Firstly if you plan on having many people play your game don't follow andrewk3652 as that way makes it immensly easy to cheat - always have the client just request things which the server then actually carries out!

As for making sure characteres dont' jump walls etc there are a number of ways. The easiest though is probably just to do multiple checks. If 1 second has passed and your maximum time step is 100ms, then move your character as if it 100ms had passed and re-check. Do that 10 times and it'll be the same as executing one big step of 1 second except that you can be sure you haven't jumped over anything. You can also do more advanced things like useing swept bounding boxes but multiple checks is easy to impliment (just put a loop round your current check to split it up) and its simple to debug. If speed becomes a problem look into something better but it'll probably work fine.

Share this post


Link to post
Share on other sites
a few thoughts:

1) code time and velocity into your collision detection. That's doable but probably not what you want. If all you use it bounding boxes though, it really would be rather simple. (notice i said "rather" :-)

2) don't jump. Instead of factoring in the time delta, you simply ignore it. You will notice this as a delay in the actions of the character which is probably not what you want, but it would work.

3) try preemptive movement on the client with server corrections. That is, if client presses UP, move the player on the screen up immediately (for instant reaction) and also notify the server of the UP movement. The server then sends back it's "check". If the server and client don't match at that point, you can "snap" the client character back to where he should be. You'll have somewhat jerky movement, but instant reaction from input.

Share this post


Link to post
Share on other sites
Quote:
Original post by kaysik
As for making sure characteres dont' jump walls etc there are a number of ways. The easiest though is probably just to do multiple checks. If 1 second has passed and your maximum time step is 100ms, then move your character as if it 100ms had passed and re-check. Do that 10 times and it'll be the same as executing one big step of 1 second except that you can be sure you haven't jumped over anything. You can also do more advanced things like useing swept bounding boxes but multiple checks is easy to impliment (just put a loop round your current check to split it up) and its simple to debug. If speed becomes a problem look into something better but it'll probably work fine.


what do you mean by maximum timestep here? also how do i decide which is a good value for it? i need it to be as precise and consistant as possible.

Quote:
Original post by leiavoia
a few thoughts:

1) code time and velocity into your collision detection. That's doable but probably not what you want. If all you use it bounding boxes though, it really would be rather simple. (notice i said "rather" :-)


could you explain what you mean here? and yes, im just using bounding boxes and square tiles for collision.

Quote:

2) don't jump. Instead of factoring in the time delta, you simply ignore it. You will notice this as a delay in the actions of the character which is probably not what you want, but it would work.


well, that won't work too well. the game is action-y and theres real time projectiles flying through the air - i need it to be as synced as possible to reduce errors as well as possible.

Quote:

3) try preemptive movement on the client with server corrections. That is, if client presses UP, move the player on the screen up immediately (for instant reaction) and also notify the server of the UP movement. The server then sends back it's "check". If the server and client don't match at that point, you can "snap" the client character back to where he should be. You'll have somewhat jerky movement, but instant reaction from input.


im a little confused here. there is already immediate reaction. let me try to explain better how movement is done:

-the player clicks somewhere on his screen. (theres no arrow key movement) now on his machine his character starts walking to where he clicked, moving in a strait path. he will continue moving untill he collides with a wall, a person, or clicks to move somewhere else.

-when the player clicks, he sends to the server "this is where i clicked at time T". the server calculates velocity just like the client did and then he "jumps" that client on his simulation (vel*dt) pixels, as to make up for latency.

-the server now sends this message to all the clients in the area of the client whos moving. these clients do the same thing the server did - set the position and velocity of the client who moved.

using the mouse for movement makes it pretty easy to sync movement and its also very low bandwith. i just need to figure out how to detect collisions in between where i am and where i will be after i make the "jump".

thanks again for anymore help.

Share this post


Link to post
Share on other sites
then go with option #1 - start researching the Separation of Axis algorithm. What that does is compare two polygons (boxes in your case) for collision and also reponse, but you can throw in time and velocity as well for perfect collisions. Check out oliii's code and tutorials called "polycoly". It's what i'm using for my project currently.

Share this post


Link to post
Share on other sites
Quote:
Original post by graveyard filla
Quote:
Original post by kaysik
As for making sure characteres dont' jump walls etc there are a number of ways. The easiest though is probably just to do multiple checks. If 1 second has passed and your maximum time step is 100ms, then move your character as if it 100ms had passed and re-check. Do that 10 times and it'll be the same as executing one big step of 1 second except that you can be sure you haven't jumped over anything. You can also do more advanced things like useing swept bounding boxes but multiple checks is easy to impliment (just put a loop round your current check to split it up) and its simple to debug. If speed becomes a problem look into something better but it'll probably work fine.


what do you mean by maximum timestep here? also how do i decide which is a good value for it? i need it to be as precise and consistant as possible.


Most games have a maximum upper frame length (typically rendering up to 60 frames per second or something like that). In the provided example, if each of your frames was a tenth of a second (i.e frames per second = 10) and you received a message with a delay of 1 second, you would want to simulate the "missing" frames when you're accounting for that delay. Since you're missisng ten frames, you'd simulate ten frames in turn. No jumps involved.

As for choosing a frame length, whatever looks smooth. 10 is too small in most cases. If you make each frame too short (lots of frames per second) then you'll be doing a lot of needless work, since the player won't be able to notice anyway. I think animated movies run at 24 frames per second.

Share this post


Link to post
Share on other sites
so essentially, i would do this?

when i get a "client clicked over here to move" packet, i extract the data from the packet and call this function:

void Player::Process_Movement(float dest_x, float dest_y, Uint32 timestamp)
{
//set our new destination coordinate
current_dest_x = dest_x;
current_dest_y = dest_y;

//calculate velocity
xVel = current_dest_x - (xPos+(width/2));
yVel = current_dest_y - (yPos+(height/2));
float diff = sqrt((float)yVel*yVel + xVel*xVel);
float invlen = 1.0f/diff;
xVel *= (invlen*200);
yVel *= (invlen*200);

//how much time has passed since the user actually clicked to do this action?
Uint32 dt = RakNetGetTime() - timestamp;

//we will do steps in 10 millisecond increments
Uint32 timestep = 10;

//while we haven't done a time step as big as our DT
while(timestep < dt)
{
//how many seconds have passed since this timestep?
float secs_passed = (float)timestep * 0.001f;

//move our character this far
xPos += (xVel * secs_passed);
yPos += (yVel * secs_passed);

//if we are colliding with anything in this spot, we can stop testing for collisions
if(Collision_Detection_And_Reaction_With_The_Map_And_Other_Characters())
break;

//advance another 10 MS
timestep+=10;
}
}







so, how does that look? most notably the end of it, where i try to do the timestep thing, is where i'm not sure i did it right or not.

thanks again everyone.

[Edited by - graveyard filla on December 6, 2004 3:18:48 PM]

Share this post


Link to post
Share on other sites
Er...ms_passed is an undefined variable. Other than that, your use of "timestep" as an incremented variable feels weird; a name like "makeup_time" or something might be more appropriate. Make certain that your update of xPos and yPos is correct (since I don't know what ms_passed is, it's hard to say). But that looks reasonable.

Share this post


Link to post
Share on other sites
whoops, i meant to put "secs_passed" instead of "ms_passed". does it look right now? =).

also, what do you think is a good value for the timestep? err, makeup time variable? i have it here as 10, but i think that might be too low. i don't want to go too low as im trying to have this as optimized as possible, since its run on a server with possibly many clients connected, and that Do_Collision_Detection_And_Reaction() function will have to loop through all the characters in my area plus do map collision. however i don't want to use a value too big that i jump past things. the current width of characters is 17 pixels and the height is 37 pixels. tiles are 32x32 pixels. thanks for anymore help.

Share this post


Link to post
Share on other sites
I'm supprised nobody has mentioned dragging a line from old position to the current position. This way you can order the collisions that have happened along the line, which gets rid of the jumping through object/wall problem.

Share this post


Link to post
Share on other sites
hey X-out, that was what i thought the solution to the problem was. i thought it would involve drawing some sort of line type thing. however, i have no clue how to do that as i'm mathmatically retarded. however, im very happy to figure out this method which requires no special math [smile]. i'd still like to hear out your method though as i said i want this to be as optimized as possible.

Share this post


Link to post
Share on other sites
Ok you can pick up line intersection algorithms here:
http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/

The idea is that for all moving objects you drag the lines as said above, (you can factor in the radius/box of your entites to make a capsule,) then you can test the intersection of those lines to see if they collided. For non moving geometry you'll need to setup some classes/functions/whatever to test if the line intersected them, for example LineBox/LineSphere intersections. The math isnt horrendous, and the toughest part is there allready on that link ( the line/line test).

Share this post


Link to post
Share on other sites
from a quick glance your code looks right - but just one seggestion. If your max time step is 10ms, and the time delta is 11 right now you'll make two updates both of 10ms which will appear as if 20ms has passed when it was only 11.

At the end of your while loop instead of having:

timestep+=10;

have something like:

if ((dt - timestep) > 10)
timestep += 10;
else
timestep += dt - timestep;

so that your first loop will calculate for 10ms and your 2nd loop will only calculate 1ms instead of another 10.

Share this post


Link to post
Share on other sites
hey guys,

i have been trying to implement this system, but am having problems.

if i set the step time interval to 10 MS, then it won't work sometimes. that is, on my local client, i will collide with the character, but on the remote machine, the character will keep walking. the problem is the "jump" is making me jump past the character.

so, im going crazy trying to debug this, so i set the interval to 1 MS. now, with 1 MS steps, NOTHING should get through. however, it seems to completely backfire on me. now, on the local client i will keep walking, and on the remote client i will detect a collision and get stuck up against the character! basically, the complete opposite is happening. i don't know what im doing wrong. i tried 5 MS but im getting mixed results...

PS - keep in mind that it works 90% of the time in both situations. its just not 100% accurate. i am really just trying hard to have it not work and it doesnt work. like im standing on the very very edge of a character and then moving, just to test to make sure its 100% accurate, but when im on that tiny tiny edge of the character, it doesnt work (e.g. on one client i collide but on another i don't, and keep walking)... could the in-accuracy possibly be because im dealing with floats?

here is the code:

void Other_Player::Im_Moving(Uint32 timestamp,float x,float y, float dest_x,float dest_y)
{
current_dest_x = dest_x;
current_dest_y = dest_y;

xPos = x;
yPos = y;

// calculate slope
xVel = current_dest_x - (xPos+(w/2));
yVel = current_dest_y - (yPos+(h/2));

//find the distance between dest and source
float diff = sqrt((float)yVel*yVel + xVel*xVel);

// normalize and set velocity
float invlen = 1.0f/diff;//((float)dy*dy + dx*dx);

xVel *= (invlen*200);
yVel *= (invlen*200);

//find how long ago this event truly happend
const Uint32 dt = RakNetGetTime() > timestamp ? RakNetGetTime() - timestamp : 0;


//if there was a dt (this should always be true except rarely when there is 0 ping)
if(dt > 0)
{
//we will do steps in 10 millisecond increments
const int STEPTIME = 1;

//save our starting position
const float old_x = xPos;
const float old_y = yPos;

Uint32 timestep = STEPTIME;

bool hit_obstacle = false;

//while we haven't done a time step as big as our DT
while(timestep < dt)
{
//how many seconds have passed since this timestep?
float secs_passed = (float)(timestep) * 0.001f;

//set our position to what it would be at, at this time
xPos += (xVel * secs_passed);
yPos += (yVel * secs_passed);

////if we are colliding with anything in this spot, we can stop testing for collisions
////this function should set our new X/Y position after the collision reaction
if(Collision_Mediator::Run_Collision_Check(this))
{
//bail out!
hit_obstacle = true;
break;
}

//advance another 10 MS (if possible)
if ((dt - timestep) > STEPTIME)
timestep += STEPTIME;
else
timestep += dt - timestep;

//re-set to our original position so our movement doesn't accumlate
xPos = old_x;
yPos = old_y;

}//end while(timestep < dt)

//if we didn't hit an obstacle, that means our position got re-set, so lets move our full step
//since now we know its legal!!!
if(!hit_obstacle)
{
float secs_passed = (float)dt * 0.001f;
xPos += (xVel * secs_passed);
yPos += (yVel * secs_passed);
}

}//end if(dt > 0)
}







thanks a lot for any help!

EDIT: i forgot to add, that "Collision_Mediator::Run_Collision_Check(this)" is doing the collision detection / reaction for this character. it will step through all the other characters on the map and then do bounding box collision and reaction.

[Edited by - graveyard filla on December 9, 2004 5:05:07 PM]

Share this post


Link to post
Share on other sites
ok, i just can't get this to work. i've tried values from 1 through 15 and none of them work properly. between 1 and 12 the collision prediction is "too" accurate, and i predict a false collision on my end where on the other clients (who was making the move) machine i made it through. starting at values around 13, the value is too big and i "jump" over an obstacle on my end but on the remote machine i collide with the object. i just can't find a happy middle.

also, i tried switching my BB collision detection to cast to int's, so that's not the problem. i also tried having my STEPTIME value to be == the time it took in MS for the last frame to go, e.g. the time_passed variable i use in all of my movement (however converted to milliseconds from seconds), to simulate a standard "step". i was thinking maybe since i was using a value too small, i was colliding with a piece of a character i would normally jump over. however, even this doesn't work! i even tried only moving at my time_passed for the first, initial step (since through tracing through the code, i find its the very first step that is predicting the false collision), this too does not work. note: my time_passed in MS was ranging from 8 to 16...

does anyone have any idea what im doing wrong, or failing that, an alternative solution? thanks a lot for any help!

Share this post


Link to post
Share on other sites
Hello.

Seems like the best way to deal with a situation like such is to conduct a swept intersection test. Basically, you know the player’s initial bounding box, the updated bounding box (player’s bounding box plus player’s velocity multiplied by time passed) and any number of obstacles may lie between these two boxes.
Your tiles are square? What you need to do is transverse through each impassable tile that lies inside the bounding box that encases the player’s initial and updated box and do a swept test to determine if that tile’s box intersects the swept bounding box. If a collision occurs, record the time and continue to test the other tiles. You need to test all blocked tiles and determine which one was hit first.
This may seem difficult but most of the necessary code can be plucked straight from the internet or can be found right here on GameDev.net (forum searches are useful in such situations). Google brought up this article as the first result – it discusses and gives code for swept aabb (axis-aligned bounding box) vs swept aabb. It is not exactly what you need but it could be used if absolutely necessary (by passing the tile’s box as both the initial and updates position of the second box to the sweep function). I’d suggest you recode it yourself but you did note that you are ‘mathematically retarded’. :P

However, I would suggest NOT employing this method, or any other method described in this thread. I’ve been keeping an eye on your game for a short while now and I think I understand what you are trying to achieve with your movement / projectile system.
Instead of having the character move in a direct line towards the position that the player clicked, halting when an obstacle is reached, why not employ a pathfinding method such as A* (A-Star – thing of games such as Diablo/any RTS) so as that your characters navigate successfully and smoothly from one position to another?
The problem I see with your current method is that it may be annoying to have to manually navigate around obstacles because the corner of the character’s bounding box may get anchored on the corner of a tile, causing unnecessary stress and difficulty.
There are some advantages to using pathfinding besides from the obvious already mentioned:
-Seems like your tile map is already designed well to support a pathfinding algorithm.
- No need to do collision detection! Just calculate the character’s path when the player gives the move command and never worry about hitting walls etc.
- Player’s movement is confined to the tilemap (8 directions): this may be a good or bad thing – I know you want to be able to doge projectiles etc – maybe include keyboard movement as well to as that player’s can aim at an enemy with the mouse and dodge incoming gunfire at the same time?
- You can find 100s of pre-coded A* algorithm classes on the internet.
Anyhow, if interested I suggest you Google and read any of the many tutorials (or head over to the AI forum). This movement system may (or may not) benefit your game.

Ehh… apologies… I know you were not asking for design suggestions.

Hope this helps,
Jackson Allan

Share this post


Link to post
Share on other sites
hi jack,

thanks a lot for the reply. currently twix is helping me figure out how to do this mathmatically by casting rays (THANKS ALOT TWIX!!). however, to be honest, i might wind up going back to my way, simply because its hard for me to understand this whole ray casting business, and i'd rather have code i understood in my game. (also, im coding a fairly large game completely by myself, so time is a factor with everything, and time spent trying to learn this code (which could be long and frustrating, because as i said, im mathmatically challenged) could be better spent doing something else). however, if i tare out my hair for the next week and still can't figure out why my current method is not working properly, ill probably just stick with twix's method.

about your suggestion, i have actually done this in the past, before i brought the game into multiplayer. collision was removed, and i had pathfinding do collision for me. there are several reasons why i don't want to do this though..

1) it was _REALLY_ hard for me to get the movement to work. that is, once i calculated my path, have the player walk this path. i went through absolute hell getting it to work. in fact, it was much harder for me to get the guy to walk his path, then it was for me to calculate the path using A*. you would think this would be the opposite, but.. anyway, in the end, the movement was kludgy and i didn't like it much.

2) my pathfinding algo was _SLOW_. like very slow. i tried to optimize it, but i failed. i even split it into chunks over frames - that is, if it was taking too long, i saved my current state in the search and kept on doing other things. but even this was unacceptable. like my pathfinding algo would literally take 3 - 20 frames, 2 milliseconds each frame to calculate. this is just way un-acceptable. i tried using different methods, but A* was just really hard to wrap my head around and i couldn't get it working fast.

3) this is the main reason why i don't want to do it. the server must replicate the exact movement that the client is doing, to keep the game in sync and to have the server have a world state. for now, its extremely simple and fast. just calculate a strait path and send him on his way. however, if i wanted to use pathfinding for movement, this would be way to slow. the server would have to constantly be calculating short path's for all of the clients every time they clicked. this would bog down the server real fast.

in a perfect world, i would be able to make a pathfinding algo that was lighting fast, fast enough for the server to handle calculating it for all the clients. however, i don't even think it would solve this problem. when the server got the "the player clicked here, at time T" packet, he would have to calculate the shortest path, and send him on his way - however, the server would still have to make up for lost time using the timestamp, and give the player a "jump". this means i would still be having this exact problem. furthermore, that "jump" will no longer be in a completely strait direction (remember shortest path != strait line), so then i would have to come up with a way to "jump" along my own path, which would further complicate the problem.

anyway, my goal in this project is to completely avoid pathfinding 100%. i don't plan on doing it for any of the enemy AI at all. im going to come up with some sort of pre-calculated pathfindign scheme to help enemies walk around wall corners and stuff. however, i remember playing UO (a MMORPG) back in the day, and im pretty sure they didnt use pathfinding. monsters would get caught up against walls and stuff, and you could just run around to the other side of a building if a monster was chasing you, and he would get stuck there. i do want some semi-complicated AI though, so in the long run, im either going to have to come up with a very clever pre-calculated pathfinding scheme, or come up with a lighting fast A* algo. even if i do chose the latter, i don't plan on using the A* for player's movement, since that isnt as nessasary as having half decent AI. (and i need to conserve on CPU power as much as possible)

btw, i dont apologize; i love getting alternative solutions and appreciate any help.

lastly, a really huge cookie goes go anyone who can spot out what in the hell im doing wrong. just read my last 2 post's, i describe what im doing and show the code. nothing has changed...

thanks again!

[Edited by - graveyard filla on December 10, 2004 10:20:18 PM]

Share this post


Link to post
Share on other sites
why dont you do it the other way, have the server broadcast the postion information to the client, do all pathfinding on the server and have no A* on the client?

that could work quite well...

user clicks on postion:
say lag is 70ms, server receives and sends back position info to client per frame, run the client 2 frames lagged, thus 70ms is lessend to about 25ms and interpolate between the 2 buffered frames... appearence: client thinks he/she is moving smoothly and no one really knows the better, advantage: client cant exploit A* to cheat...

Share this post


Link to post
Share on other sites
well, i don't want to calculate A* on the server, because it will be too slow. however even if i did, doing it the way you describe is probably a bad idea. first, a player's movement won't be instantaneous, but more importantly, the server will have to send the player the path, which is wasting bandwith. if i were to use A*, i would have the client calculate it on his end as well as the server. if the client wanted to cheat, he could go ahead and hack his client to give himself special path's - this wouldn't do anything but screw the hacker. because the server knows where the client *should* be, the server will know where he should be at all times, as will other clients. what happends is, the cheater is totally out of sync. he *thinks* that he is walking to wherever he wants, but the server knows his real location based on the input given. the result is the cheater is totally out of sync. he wont be able to pick up items or attack things because he'll be getting "you are not in range" messages, even though on his end he appears to be in range. someone could come along and attack the cheater, and he would be screwed, since the cheater probably will be in some weird location and not even be able to see whos attacking him, and he will never be able to sync himself back to where he should be. furthermore, i could detect if a client ever clicked somewhere off his screen, and then kick/ban him...

anyway, i'm pretty sure i have figured out what the problem is. however, i'm completely stuck in solving this problem. here's the problem:

when i have the STEPTIME variable set to 10, the client won't predict the collision accurately, and on his end, the client who moved will "jump" the corner of the character, and keep on moving. however, on that clients local version, there was no "jump", so he collided with the character. so on the client who tried to move's computer, he will have collided. but on the other computer, he will see the client move to where he clicked. (e.g., he would have "jumped" over that tiny tiny 2 pixel edge that the other client got stuck on)

if i set the STEPTIME to 5, the client will predict the collision - but he will do it TOO accurately. that is, when he goes step by step to predict to make sure the character doesn't "jump" over anything, he predicts a collision that will happen at 5 milliseconds. however, on the character who did the moving, he won't predict this, and will keep moving. but why? because on the local machine, the time_passed since the last frame will be something like 7 or 8 or 9 MS. the result is that the guy who tries to move won't collide, since he's moving a few pixels further (his "step time" is == the time it took to go through a frame, like any other time based movement, so his "step time" is ~8, while the guy who is trying to predict the collision is stepping him at 5).

also, i tried doing this (which i thought for sure would solve the problem) - whenver a player moves, even if its on his own local machine, we do "step by step" collision to make sure he won't "jump" over anything. so i set this to 5 MS steps just like i do with the other step by step collision (in fact; they both use the same function). however, even this doesn't work. i don't know why, but its just not... also, i had to do this anyway, because if a player's computer chokes for a second, and his time_passed variable is huge, he will be sent through walls / completely off the map. this is a problem with time based movement, so i thought i would kill 2 birds with one stone, fix the problem with time based movement AND fix my bug. however, its not working. EDIT: what i mean by "not working", is when 2 players collide they seem to get "stuck" to each other sometimes and i have to keep clicking to get "out" of it. also, it seems to be even more in-accurate as far as syncing goes. i might just be doing something wrong though.

so, now what? i mean, how do i do this? i have to somehow make sure that all clients are running at the exact same frame-rate, so that on one machine they don't jump over but on another they do. however obviously this is not possible. i can't lock the frame-rate either, because then people who are under the frame-rate will be totally screwed and out of sync. i hope someone understood my problem. its kind of hard to explain, but it's pretty strait forward problem. i just can't figure out how to do it, to make it completely accurate on both machines.. any help is greatly appreciated. if you need a better explanation, please just let me know and i'll make pictures and stuff. i'm going to try twix's method tonight, but im pretty sure it will suffer from the same problem..

thanks again.

[Edited by - graveyard filla on December 11, 2004 10:55:31 PM]

Share this post


Link to post
Share on other sites
Your problem is quite common in client-server predictions.

What Coutnerstrike, Quake3, and other derivatives do is like this...

first, the entities.

1) CPlayer
----------
that's the player controlled on a local machine. It's linked to the input system of a machine. (inputs).

2) CClientPlayer
----------------
That's the representation of a player (Either a remote player from another machine, or a local player CPlayer), its animation, graphics and sounds. (outputs).

3) CServerPlayer
----------------
that's the player on the server machine. It receives inputs from CPlayers, and convert them into CClientPlayer update packets.

the process of updating the path of a player.

- every frame, CPlayer process inputs. and using those inputs, It does a physics simulation on it's local CClientPlayer (colliding with other players, NPCs, environment, ...). Therefore, the CClientPlayer will move around and collide with things. It also stores the inputs, the timestep upsed for the physics simulation, the time the simulation started, and the resulting position calculated into a small packet (CPacket).

- At a given update rate (cl_rate), it will bundle packets of inputs it processed and that hasn't been sent yet to the server. So it sends a list of input packets (CPacket[4] for example) CPacketList.

- You can add redundancies as well, if you suffer packet loss. So you send several CPacketList instead of one. That can double or triple your bandwidth, but this is the upstream on the client, so it can take it. And of course, you can tweak that as much as you want (something cl_dupcommandpacket 2, for packet loss up to 50%).

- OK, now the server receives a list of commands from a client. Using each CPacket (time the commamnd was simulated on the client, frame time, inputs), it also does a physics simulation, on its CCserverPlayer entity. Each time, it compares the position it calculated, with the position predicted on the client.

- If the positions calculated on both machines are the same, then the server continues the simulation with the remaining command packets. Once all the command packets positions have been verified, it sends a validation message, with a timestamp, to say that the player's posiiton is valid at a time.

- if the positions diverge, it sends a correction message, with a time stamp and the correct position to the player. The player then corrects it's position accordingly.

- The positions can diverge mostly when the player collides with other moving entities (like remote players, NPCs, ect). This is what you see when in Counterstrike you collide with other moving players. You jitter slightly, since the position from remote players is rather unpredictable and innacurate.

- there are also things like prediction, where you have to predict positions of entities forward in time, and interpolation, to smooth out the movement of players. You can also see it in counterstrike, when players with high ping seems to teleport from place to place rapidly (I've seen it), which brakes the prediction since the lag pushes the prediction too far ahead in time.

Share this post


Link to post
Share on other sites
Here's the way I would do it:

When the player clicks, it sends the (local) character walking in the desired direction and speed, then sends his target (x,y) & velocity to the server.

The server does a collision test along the line from origin(x,y) to target(x,y) to see where the character must stop. The algorithm is simple, something like;

dx = xdest - xstart
dy = ydest - ystart

xtiles = dx / tile_width
ytiles = dy / tile_height

step = xtiles / ytiles
y = start_tile_y

for x = start_tile_x to (start_tile_x + xtiles)
y_inrc = 0
for y = y to (start_tile_y + ytiles)
if ++y_incr > step then break innermost loop

if !walkableTile( x, y )
final_x = x
final_y = y
stop algorithm

of course, this algorithm I just made up now, so there's probably much more effective ones, the important thing is that you sweep the path and see where, if at all, the player collides with something.

Now you've got the (final_x,final_y) where the character must stop (regardless of where the player actually clicked). Now, caluclate the players position with regard to lost time and send that (or final_x, final_y if the adjusted position is larger) together with the velocity and (final_x, final_y) as target position to all clients.

As far as I can see, that would solve your problem of teleporting through walls.

alternatively, if you trust the clients to do collision detection. You only need to sweep (velocity * delta_time) number of tiles forward, with velocity in tiles/time_unit of course, instead of the whole path to save some CPU.

Share this post


Link to post
Share on other sites
@oliii,

thanks for the reply. however, this is a problem which can be solved without having to acknowledge the fact its a client / server game. the physics in my game are extremely simple, and all collision is simple 2d bounding box's. the way i have design the network layer, the game should run in good enough sync for me to not have to send corrections about character collision detection. (projectiles is another story..).

@Luctus,

thanks for the reply. i think i understand your algo. im kind of doing that exact thing now, i think.

anyway, i'm still having trouble getting this to work. im about to say screw it and just let the bug sit there for awhile. im getting frustrated and maybe checking on it later with a fresher head is a good idea. this is one of those bugs where you have to really try to reproduce to make happen. not only that, but its not a huge disaster. the game will re-sync as soon as the client clicks to move again..

theres only one problem, i really DO need to do something about the time based movement. the problem is what if a player's computer chokes up and his time_passed that it took to do a frame was big, and it sends him flying through a wall or completely off a map? i need a way to make sure this won't happen. i thought doing step-by-step collision when moving each frame would solve this, along with solving my original problem (which would kill 2 birds with one stone) but i can't get it to work (the player seems to get stuck up against another player when they collide).

thanks everyone for all your help.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this