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.
collision problem in online game (2D)
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.
Author
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.
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).
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).
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.
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.
Author
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:
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]
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]
Author
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!
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!
Try collisioning 2 lines based off his rect that represents his movement against the map(raycasting)
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
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
Author
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
