Hi everyone,
In a fit of nostalgia, I decided I wanted to try my hand at creating an AI to play an old HL1 mod called “Natural Selection” - a marines-vs-aliens asymmetrical mix of RTS and FPS elements - since nobody plays it any more and there isn't a good bot already available that is actually fun to play.
The challenge with this game is movement: player capabilities can vary drastically. Marines generally play like a regular FPS character: they can walk, jump, climb ladders, crouch and swim. However, they can also obtain jetpacks which enable them to fly for short periods of time. Aliens on the other hand can transform into different forms which give them radically different movement sets depending on the form: some forms can climb walls and walk along ceilings, some can fly, some can use huge leaps to reach high/distant areas, and each one can vary drastically in size as well.
One approach I thought might work was to use the Recast library to voxelize the map geometry and build a heightfield, and then use that to generate a series of single-sided 3D convex hulls. Each triangle within the hull can be tagged with information such as the surface angle of the real-world geometry it represents, what kind of surface it is etc. The AI can navigate between convex hulls using “portal” triangles, which close holes in the hull where there isn't any real-world geometry and thus represent doorways and openings.
On paper, it seems like a good solution: non-flying AI can navigate along the triangles within the hull just like a regular navmesh, except that they can discard certain triangles as options if the surface angle is too steep and they don't have wall climbing, or ignore this check if the triangle is marked as a ladder and so on. Reachability between hulls can be pre-calculated so the AI can discard entire hulls if they're not deemed reachable for an agent with their movement capabilities. Flying AI can navigate easier knowing that every point within a hull is directly reachable from anywhere else inside the hull so they can navigate from one “portal” triangle to another directly.
Has anything like this been done before? Was wondering if there were any previous examples of someone using a heightfield to generate a set of convex hulls, and what fundamental challenges I might be missing that could make this unviable.
