A whistle-stop tour of some game-engine collision/pathfinding background, how modern engines work, how old engines work, and how I'm applying a mixed-approach in my game.
Excellent article, and I appreciate how you gave an overview of solutions that didn't make sense for you but were otherwise important to know about.
Could you expand on how your pathfinding works for both ground-based and flying enemies? I've been trying to wrap my head around how to handle this on my own game, and trying not to invent a wholly separate solution for enemies than can avoid obstacles vertically.
The scaffolding is built from convex volumes, and I know which cuboid faces are "walls" and which are "windows" so I link the windows into a graph where the shared-faces are waypoints and do A*, using straight-line distance as the cost function.
Big obstacles are just built from the scaffold itself, and small obstacles are avoidable by just doing "whisker-traces" to veer around them (the navigation path is a movement hint used to calculate accelerations, not followed strictly).
Yes, but that's why ~~good~~ fun enemy AI for games is both an art and a science.
My approach is that the path from the pathfinding algorithm is just a known good solution. The path the agent gets back from the algorithm doesn't have to be just a list of Vector3's for the window centers. It could get back a list of each window quad instead, and then aim for a random point in the next quad shifted by the distance between the two quads. You can also do some raycasts from each agent occasionally to do local-avoidance-type behavior (which you'll likely have to do anyway so that enemies spread out a bit and avoid non-static geometry).
Note that there is also TrenchBroom [1]. An editor which you can then use to create levels and import them in UE4/5 [2], including textures and collisions.
I created my HN account to comment on the post announcing the release of the Descent 3 source code last year. So of course I immediately recognized the similarity to Descent 1 and 2’s cube-based level design, and was pleased to see the screenshot of DLE. :)
I was always inspiring the level editor in Cube 2: Sauerbraten (http://sauerbraten.org). This seems like an alternative to BSP approach which was more popular at the time. But I think this game's octree-based solution has more potential than just the render and raycast logic implemented in the engine. You could potentially make the entire level fully destructible and keep it optimized at the same time. The level building was also fun when I was teenager. No game allowed to edit levels with other players connected to the server and that was working in 2004!
Thanks, Max! I've personally never been able to wrap my head around BSP; I appreciate your diagrams explaining everything, and I am optimistic about the new engine. It's crazy how much faster it can be; really drives home how much extra stuff Unreal is doing that your game may not need.
Thanks for sharing! I was thinking how this is a good example of the kinds of things that you can do with a game engine that already exists, as opposed to having to write everything yourself.
Also a nice mention of octrees' use outside of voxels.
Isn't this kind of like simply putting the data structures from the first Unreal Engine (which I believe used BSP), into the latest one? For the game you appear to be building, this appears to be rather unnecessary, even for authoring purposes. Even the Nintendo Switch 1, which is being phased out, might not necessarily benefit enough performance-wise to overhaul these core systems.
It's not a BSP, it's volumetric data (this is in the actual article). Just off the bat I get aerial navigation "for free" without having to hand-place regions, and a secondary collision-query for bullet-hell that's much faster than Chaos, which was a huge perf regression in UE5 from PhysX (which already wasn't great).
Additionally, there's productivity + rapid iteratoin. Trying to build interiors with Unreal's built in drag-out-an-actor-at-time interface is too laborious, and the built-in automations (Construction Scripts, Blutilities, PCG) are impedance-mismatched for constructing interiors quickly.
I don't think I quite understood what you are trying to accomplish that is distinct from what 90s BSP engines like Unreal 1, Quake 2, and Source were doing?
Are you trying to do convex spatial partitions for 3d pathfinding in the air?
I did an indie VR starfighter game Rogue Stargun (https://roguestargun.com) and quite honestly intermittent navigation raycasts from the enemy ship AI is sufficient for this sort of stuff.
The bullets all run on the main thread on mobile hardware and so does all the AI. It's not optimized and I have yet to witness CPU bottlenecks being the main cause of frame drops.
Your game looks simple enough and is on the PC platform... I suspect you may be optimizing for the wrong thing.
How is it that you are running into cpu limitations for raycasts in a bullet hell game with UE5 to the extent you built this?
I wrote a VR game that has hundreds of bullets running at 72 fps on Quest 2. Never went multithreaded and never actually encountered FPS drops due to CPU limitations
A whistle-stop tour of some game-engine collision/pathfinding background, how modern engines work, how old engines work, and how I'm applying a mixed-approach in my game.
I have such an appreciation for write ups like this. Reminds me I'm not a real programmer at all.
Excellent article, and I appreciate how you gave an overview of solutions that didn't make sense for you but were otherwise important to know about.
Could you expand on how your pathfinding works for both ground-based and flying enemies? I've been trying to wrap my head around how to handle this on my own game, and trying not to invent a wholly separate solution for enemies than can avoid obstacles vertically.
The scaffolding is built from convex volumes, and I know which cuboid faces are "walls" and which are "windows" so I link the windows into a graph where the shared-faces are waypoints and do A*, using straight-line distance as the cost function.
Big obstacles are just built from the scaffold itself, and small obstacles are avoidable by just doing "whisker-traces" to veer around them (the navigation path is a movement hint used to calculate accelerations, not followed strictly).
Given a long enough path, does this lead to enemies always flying through the center of “windows”?
Not OP but hobby gamedev here:
Yes, but that's why ~~good~~ fun enemy AI for games is both an art and a science.
My approach is that the path from the pathfinding algorithm is just a known good solution. The path the agent gets back from the algorithm doesn't have to be just a list of Vector3's for the window centers. It could get back a list of each window quad instead, and then aim for a random point in the next quad shifted by the distance between the two quads. You can also do some raycasts from each agent occasionally to do local-avoidance-type behavior (which you'll likely have to do anyway so that enemies spread out a bit and avoid non-static geometry).
They did in my janky initial impl, but in the current version waypoint interfacing "windows" are now quads.
Note that there is also TrenchBroom [1]. An editor which you can then use to create levels and import them in UE4/5 [2], including textures and collisions.
[1] https://trenchbroom.github.io
[2] e.g. https://www.youtube.com/watch?v=41HZzy-nJDU
I created my HN account to comment on the post announcing the release of the Descent 3 source code last year. So of course I immediately recognized the similarity to Descent 1 and 2’s cube-based level design, and was pleased to see the screenshot of DLE. :)
I was always inspiring the level editor in Cube 2: Sauerbraten (http://sauerbraten.org). This seems like an alternative to BSP approach which was more popular at the time. But I think this game's octree-based solution has more potential than just the render and raycast logic implemented in the engine. You could potentially make the entire level fully destructible and keep it optimized at the same time. The level building was also fun when I was teenager. No game allowed to edit levels with other players connected to the server and that was working in 2004!
That's a cool reference, thanks for showing me. Similar energy to Q1K3 https://phoboslab.org/log/2021/09/q1k3-making-of
Great write up, very interesting. Shame y’all couldn’t get funding even after Day of the Devs! Hang in there, game looks cool.
Last year was rough for indie funding because of interest rates. Luckily, Absolute Nothing Economically Destabilizing Is Happening This Time (O___o).
Thanks, Max! I've personally never been able to wrap my head around BSP; I appreciate your diagrams explaining everything, and I am optimistic about the new engine. It's crazy how much faster it can be; really drives home how much extra stuff Unreal is doing that your game may not need.
Thanks for sharing! I was thinking how this is a good example of the kinds of things that you can do with a game engine that already exists, as opposed to having to write everything yourself.
Also a nice mention of octrees' use outside of voxels.
This is very cool. I would pay for this.
Isn't this kind of like simply putting the data structures from the first Unreal Engine (which I believe used BSP), into the latest one? For the game you appear to be building, this appears to be rather unnecessary, even for authoring purposes. Even the Nintendo Switch 1, which is being phased out, might not necessarily benefit enough performance-wise to overhaul these core systems.
It's not a BSP, it's volumetric data (this is in the actual article). Just off the bat I get aerial navigation "for free" without having to hand-place regions, and a secondary collision-query for bullet-hell that's much faster than Chaos, which was a huge perf regression in UE5 from PhysX (which already wasn't great).
Additionally, there's productivity + rapid iteratoin. Trying to build interiors with Unreal's built in drag-out-an-actor-at-time interface is too laborious, and the built-in automations (Construction Scripts, Blutilities, PCG) are impedance-mismatched for constructing interiors quickly.
I don't think I quite understood what you are trying to accomplish that is distinct from what 90s BSP engines like Unreal 1, Quake 2, and Source were doing?
Are you trying to do convex spatial partitions for 3d pathfinding in the air?
I did an indie VR starfighter game Rogue Stargun (https://roguestargun.com) and quite honestly intermittent navigation raycasts from the enemy ship AI is sufficient for this sort of stuff.
The bullets all run on the main thread on mobile hardware and so does all the AI. It's not optimized and I have yet to witness CPU bottlenecks being the main cause of frame drops.
Your game looks simple enough and is on the PC platform... I suspect you may be optimizing for the wrong thing.
How is it that you are running into cpu limitations for raycasts in a bullet hell game with UE5 to the extent you built this?
I wrote a VR game that has hundreds of bullets running at 72 fps on Quest 2. Never went multithreaded and never actually encountered FPS drops due to CPU limitations
UE still has BSP for blocking out levels: https://dev.epicgames.com/documentation/en-us/unreal-engine/...
It's a bit legacy, since it's just used to tesselate PhysX/Chaos trimesh collision, rather than doing true BSP collision in game :/