Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
So I know the Valve model for networking in FPS games involves rolling back to the time of the player's shot to perform raycasts in the past. What do you do in this case about broadphase/spatial decomposition?
Say I have something like a Dynamic AABB tree. Do I keep copies of the tree I made for the past 60 frames in some sort of rolling buffer? Or, when I rollback to frame t-n, do I just re-insert every dynamic object in the tree (seems expensive)?
Just curious what is generally recommended for this, as my raycasts are getting pretty expensive without a proper broadphase step. Thanks!
Say I have something like a Dynamic AABB tree. Do I keep copies of the tree I made for the past 60 frames in some sort of rolling buffer? Or, when I rollback to frame t-n, do I just re-insert every dynamic object in the tree (seems expensive)?
I didn't know the technique Valve used, but many data structures handling collision detection of dynamic objects needs to be rebuilded every frame. I.e. I use a sweep'n'prune which rebuilds its three ordered arrays by using insertion sort. So, it would not have any performance impact to keep the last 60 frames. Other data structures will have some advantages and disadvantages, but considering that Valve games have at max 32 players (for NPC it isn't really that important), most data structures should be rebuild in a single frame without issues.
Therefor I would say: keep copies in a rolling buffers sound good.
Any suggestion for a data structure? I tried using quadtrees stored in-place in an array, and doing a memcpy from one buffer to the next each frame, but doing everything in-place was pretty difficult and ended up being costly. I've been looking at persistent data structures but it seems a bit overkill, and I'm not sure how to cut it off at a maximum history length.
I'm working in C# so I'm trying to avoid a lot of garbage collection overhead, and I don't want to rebuild my spatial decomposition each frame from scratch.
You can have two trees; one for static things that don't move, and one for dynamic things that move. Then, when doing collision detection, check the dynamic one against the static one, and then check the dynamic one against itself. When you need to rewind time, re-build the dynamic tree (really, for each node, move it in the tree to its new location.) Yes, that means processing for each dynamic (moving) object. How many of those do you have? In the Valve model, there's seldom more than 32 moving players, and it doesn't do server-side perfect collision for random debris (barrels, etc.)
You can have two trees; one for static things that don't move, and one for dynamic things that move.
Then, when doing collision detection, check the dynamic one against the static one, and then check the dynamic one against itself.
This is actually a little easier for me because I'm only allowing dynamic-static collisions (players pass through each other). So for each dynamic object, I just check it against all the static.
When you need to rewind time, re-build the dynamic tree (really, for each node, move it in the tree to its new location.)
Yes, that means processing for each dynamic (moving) object. How many of those do you have? In the Valve model, there's seldom more than 32 moving players, and it doesn't do server-side perfect collision for random debris (barrels, etc.)
I'd like to target 40-ish or some more, so this might still be a little costly. Then again, it's a 2D game with far simpler dynamics. I'll try the full-move and rebuild approach, maybe with tree rotations, and bench it against a persistent data structure approach. Thanks!
Ah, sorry. I restrict to dynamic-vs-static for collisions, but raycasts can intersect with both dynamic and static objects.
Application: 2D spaceship shooter game, ships fly through each other, projectiles (modeled with ray/circle casts) can hit both ships and static geometry.
I bet you can raycast against 40 dynamic objects in a few microseconds, with no tree needed. Test each dynamic object's bounding sphere against the ray; for those where that works, do a more detailed test. For the static geometry, you can use the tree/hash-grid/whatever, and not re-calculate it.
