Scaffold Level Editor(blog.littlepolygon.com)
137 pointsby mwkaufma9 days ago10 comments
  • mwkaufma9 days ago
    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.
    • charlietran9 days ago
      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.

      • mwkaufma9 days ago
        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).

        • dcrazy9 days ago
          Given a long enough path, does this lead to enemies always flying through the center of “windows”?
          • kaibee9 days ago
            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).

            • taeric8 days ago
              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?

          • mwkaufma9 days ago
            They did in my janky initial impl, but in the current version waypoint interfacing "windows" are now quads.
    • squiggy229 days ago
      I have such an appreciation for write ups like this. Reminds me I'm not a real programmer at all.
  • enbugger9 days ago
    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!
  • keyle9 days ago
    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

  • dcrazy9 days ago
    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. :)
  • 9 days ago
    undefined
  • aschearer9 days ago
    Great write up, very interesting. Shame y’all couldn’t get funding even after Day of the Devs! Hang in there, game looks cool.
    • mwkaufma9 days ago
      Last year was rough for indie funding because of interest rates. Luckily, Absolute Nothing Economically Destabilizing Is Happening This Time (O___o).
  • rdw9 days ago
    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.
  • Esras9 days ago
    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.

  • LarsDu889 days ago
    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.
    • dcrazy9 days ago
      UE still has BSP for blocking out levels: https://dev.epicgames.com/documentation/en-us/unreal-engine/...
      • mwkaufma9 days ago
        It's a bit legacy, since it's just used to tesselate PhysX/Chaos trimesh collision, rather than doing true BSP collision in game :/
        • 9 days ago
          undefined
    • mwkaufma9 days ago
      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.

      • LarsDu889 days ago
        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.

        • mwkaufma8 days ago
          Target is switch/steam deck, and I have hard profiling numbers on fully decked scenes, so your suspicions are inaccurate.
      • LarsDu889 days ago
        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

        • mwkaufma8 days ago
          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.
  • OccamsMirror9 days ago
    This is very cool. I would pay for this.