k8vavoom: no good thing ever dies! (2023, Dec 22 build)

in Doom, any movement is done by the series of "mircoteleports". i.e. to move something, it is teleported to the destination, then the engine checks if the object is not stuck in a geometry. if it stuck, the engine tries to find the "best" wall to slide along, and does some trickery.

there are many problems with this approach; the most prominent one is that you can't move with high velocities (because the object could skip some walls while doing "teleport check"). that's why, for example, ZDoom has "FastProjectile" actor class. that class has it's own movement implementation: it splits one long movement to many small steps, and "microteleports" by a smaller amount, hoping to not miss anything along the way. later, some sourceports implemented such "split-teleporting" for all mobjs, because CPUs are much faster now, and it's better to stay safe than to expect modders to always use proper actor class. ;-)

now, there is another approach to collision detection, called "continuous collision detection", or CCD for short. it works in a completely different way: instead of "teleport and check" approach, CCD checks all possible obstacles along the way, one by one. it checks if the moving object can reach and hit that obstacle, and if it can, CCD code calculates exact hit point. this way the object will never miss any wall, no matter how high its velocity is.

"but why Carmack didin't used CCD in Doom?" you may ask. there are several reasons. first, Carmack simply didin't knew that it is possible back then. he figured out the correct algorithm for that at Q3 development time. Q1 was using separate "augmented" BSP trees for different AABB sizes, for example. only in Q3 Carmack finally realised how to implement that properly by using the same BSP tree that is used for rendering, and for any AABB size.

and second, mobjs in vanilla Doom have limited speeds, so doing "microteleporting" was simply much faster, because it is O(1) blockmap check, and BSP CCD is O(log n), or even worser.

yet today we have mods, and mod authors often using fast projectiles with small radius. for such projectiles, CCD looks like a better approach. also, i simply wanted to implement CCD for Doom. ;-)

another problem is that Doom BSP is "inverted". Quake BSP holds solid space in leafs, but Doom BSP holds empty space instead. checking collision with convex solid volume is easy and cheap, but there is no good algo to do that for "inverted BSP".

i tried several implementations, but neither was good enough. they all worked, more-or-less, but each had some fatal flaws. the current one is still not ready for "production use", but it is way closer to it. it is the first time i was able to use it for player movement without stucking (almost), or jumping onto very high ledges. and it doesn't require any additional info besides what the engine already has. i.e. it is using the same BSP that is used for rendering, and there is no need to augment subsectors or lines/segs with additional planes. this is the first time when i feel that i'm on the right path.

of course, don't expect it in the next k8vavoom build; this is just R&D work i'm doing all the time. i don't think that it is possible to completely replace Doom coldet code without rewriting huge parts of AI and physics. also, CCD algo completely ignores things for now, so you can't collide with a monster, or pick up some ammo.

yet having fast and universal "trace box" API could be handy to implement various other things. if (when ;-) i solve problem with things, it could be used for tracing fast projectiles. it could also be used for chasecam, bot pathfinding, and many other interesting things. also, if someday i manage to make it good enough to completely replace "microteleporting", it will open a way for adding Quake-like 3d moving meshes (think of 3d polyobjects, but without restrictions at all).

don't hold your breath, tho, it's still very early R&D, and may never happen at all. i simply love to tell you about some things i'm experimenting with, so you won't think that small amount of commits into the main k8vavoom repo means that i'm doing nothing. ;-) i have more than one such R&D Doom project, and some of those already helped to improve the engine.