Download

Flying AI Pathfinding?

I’m wondering how easy it would be to add pathfinding for basic flying monsters.

For example, Cacodemons from DooM.

We have the pathfinding for walking enemies, but flying seems like it needs a node based system rather than a navmesh.

NavMesh would certainly not work for Flying AI’s, a NavMesh requires a geometric plane. in UE4 at the moment there’s no such thing as a “Flying AI Pathfinding”.
I had conducted some research a while back as were tasked with implementing something like this for our engine. Implementing such thing is actually quite complex, there’s a reasonable amount of research paper, but being able to integrate that in an engine while retaining overall performance is not an easy task. One thing I’d like to point out is the generalization of a NavMesh. For 3 dimensional pathfinding a Navigation Volume can be used, this is pretty much what Havok AI makes use of and what they showed at the 2011 GDC https://www.youtube.com/watch?v=_hkjcpmqK90 now of course, a Nav volume is very computationally expensive, quite frankly I doubt the required data can even be generated at run-time, as it usually requires a long pre-processing stage. On top of that you’d also have to change the steering behaviour and pretty much everything else, the A* algorithm and such can be retained however. We went with tons of approaches including using an octree, a visibility graph and lots more. :slight_smile:

A few links you might find helpful, you may probably find more ways to implement such thing by searching online
http://www.red3d.com/cwr/steer/gdc99/

http://anarchy.cn/manual/12/HavokSdk_ProgrammersManual/bk06ch02s04.html

Personally I’d advice you to use waypoints or anything else instead of attempting to implement something like that, best of luck!

UT had flying vehicles, and I’m guessing UT4 will too. I wonder if bots will be able to use them. Now that I think about it, I’m not 100% I remember bots ever using the flying vehicles.

The simplest solution I have is placing a bunch of waypoints in the level for flying AI only. The waypoints will link to each other if they are in line of sight. Things like doors will be ignored in line of sight checks. Then I use A*. This is something that can easily work at runtime, especially when you have procedurally generated levels.

It’s a good thing I plan on having very simple monster AI since I’m making what can basically be called a DooM clone in a way. I just need the flying monsters to float over towards the player and attack. I could even use navmeshes and have them float above the ground, but it’s going to look pretty strange if a flying monster needs to use the stairs to get to me instead of hovering upwards heh.

There are at least two ways I can think top of my head. Simple and not so efficient (but probably sufficient for simple stuff), and complex, and more efficient.

The first idea, is that every tick you sweep sphere/box traces around your flying pawn, and check for obstructions/enemies/etc. If you pawn find that path in X units is obstructs, you tell it, to find another light point or to chase enemy.

For path finding, you just find random point in space, and make pawn move towards it. After reaching this point, you find another random point and so on. you can make it more smooth/predicable, by finding point in in overlapped shapes, like Box or sphere, or by manually checked it next point is within tolerable angle from last point. It’s very simple and not so intensive, since you will be looking for new only every so often (depends on how fast your pawn reaches nav points).
This approach is entirely procedural, but can be really daunting to set it right. For simple games, math is pretty straight forward, and there shouldn’t be much of an issues. For complex levels, you will have to do alot of checking to make sure AI behave properly.

Another way, is to make volume, which will cluster your level into 3d grid. Each point in grid can contain information about navigation (like, blocked), and then you AI can either trace trough them, or you can write graph traversal trough tree. to search optimal path. How exactly you will do it, depends on your case. Tracing might be actually easier if not faster, for small amount of pawns (and you won’t see much of performance hit).

The solution with nav points is also acceptable, for small levels. Combined with first approach it would reduce checking complexity, since there would set path for navigation.