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).
I'd also ask if this isn't somewhat accurate for how people would do things? We have specific rules that we have internalized on what side of a road to drive on. But, absent those rules, it isn't uncommon to just drive down the center of the road. Largely expected on many surface streets that don't have brightly painted lanes and large shoulders.
To that end, you could always encode the rule of what side of a window to aim for? Something you probably want to do if you are going to be aiming for bidirectional agents going through them?
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!
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. :)
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
Can't tell you wo a profile, but I assume your content was as complex as a full byzantine shooter map. I've also got large enemy squads, so there's an M×N issue.
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).
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).
I'd also ask if this isn't somewhat accurate for how people would do things? We have specific rules that we have internalized on what side of a road to drive on. But, absent those rules, it isn't uncommon to just drive down the center of the road. Largely expected on many surface streets that don't have brightly painted lanes and large shoulders.
To that end, you could always encode the rule of what side of a window to aim for? Something you probably want to do if you are going to be aiming for bidirectional agents going through them?
They did in my janky initial impl, but in the current version waypoint interfacing "windows" are now quads.
I have such an appreciation for write ups like this. Reminds me I'm not a real programmer at all.
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
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
TrenchBroom caused a renaissance in Quake 1 mapping community, bringing tons of new mappers:
https://www.quaddicted.com/
As well as dumptruck_ds tutorials:
https://www.youtube.com/watch?v=gONePWocbqA&list=PLgDKRPte5Y...
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. :)
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.
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.
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 :/
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.
Target is switch/steam deck, and I have hard profiling numbers on fully decked scenes, so your suspicions are inaccurate.
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
Can't tell you wo a profile, but I assume your content was as complex as a full byzantine shooter map. I've also got large enemy squads, so there's an M×N issue.
This is very cool. I would pay for this.
Wishlist! https://store.steampowered.com/app/3038700/Nightshift_Galaxy...
Those are some good missile effects right there.
I wrote about those, too: http://blog.littlepolygon.com/posts/missile/