Plan for Stefan Beffy Moises

Working on the navgraph and pathfinding for the AI project...

Since Justin is very busy at the moment and "on the road" quite often I've taken over his pathfinding code to tweak and optimize it a bit (not necessarily speed-wise since Justin already did a great job and a lot of tweaking and profiling there, but to get it more versatile and flexible for various map types and map "anomalies" :P).
What anomalies you ask? Well, stuff like the following... :)

Large static obstacles



Look at those rocks, they were one of the problem we've encountered while running a Realm Wars test map... the rocks just werent detected, whereas other statics, like trees, were... so the AI would just bump into those rocks since the Navmesh passed right through them... First, I expected a problem in the fact that the rocks are inside the worldbox of other objects (interiors in this case), but then it turned out to be a simple raycast problem - we were scanning from BOT_HEIGHT (size of the AI Player) down to right above the ground to detect obstacles... well, but those rocks were slightly higher than the AI Player and they stuck inside the terrain - ergo, the rayscan would completely take place inside the rock and never detect anything... :P
So a solution would be to scan from high above in the sky down to the terrain (or even below it) - but what if you have something like a bridge (DTS or DIF), and the AI could walk below that bridge?
Well, the solution I came up with is this: using 3 rayscans for each "terrain node filter" (we are running every node through filters to filter nodes that are too steep, below the terrain, below interiors or statics and the player cant stand there, etc.), so for each node, 3 raycasts are performed now:
1) one down from high above scanning for the terrain height
2) one rayscan up from below the terrain to detect anything else above the terrain - then we check the "free space" between terrain and the (bottom of the) object above it... if the bot is able to stand there, we're almost golden
3) finally, we scan from above again to detect interiors or statics and see if anything sticks in the ground, but also is looking out of the terrain which could be a potential obstacle (e.g. rocks or trees)

Now this does look better, doesn't it?



Fences and other bad things



Here is another favourite problem... the bot would find paths that lead right through the left and right parts of such a fence, since the Nodes are linked mainly based on LOS, so Nodes are connected in cases like this although the bot can only pass that fence in the middle part...

Here is what it looks like now:

The trick here is that the fence luckily consisted of three parts... so I was able to treat each part differently - the middle part is treated like any other interior, the algorithm tries to place nodes inside of it and in a dense grid around it - the left and right parts of the fence however are treated as "blockers" - you can set a flag in the mission editor and there will be no nodes generated inside or around the objects and so no links are created either :)

So, as you can see, the level designer has to be careful how he sets things up in the mission and also how critical interiors are build in Quark/Hammer etc.


The impossible path

One mystery Justin was able to solve yesterday are "impossible" paths... due to the concept of our NavMesh, we have partial meshes on roof tops, etc. (which we could remove, but we think it makes sense to keep them, since somebody may want to place some AI entities on roofs and let them attack from there, etc.)
Anyhow, these nodes are kinda "isolated" from the main navgraph nodes and you end up having nodes on some other weird locations from time to time... e.g. on this well:

Now, if the target or start node of the AI is right at that well e.g., it may pick one of those isolated nodes on top of it as the next nearest node and try to path to/from there, which will fail miserably... starting from there, it will come to an end very soon and give up... trying to path to that node is even worse, since it will try to get there forever and will of course never reach it! This was causing some severe lockups and would slow everything down... so since we dont want to remove those "roof type" nodes, we decided to limit the search to a maximum iterations value for now... if it loops through the main pathfinding algorithm for more than X times, we cancel the search and "give up" on that path...

The mysterious subterranean node

EDIT: well, one more thing since this also was a little mystery ;)
When standing right in front of one of the RW towers, the bot seemed to be unable to find any path... so I checked which node it was using as its start node: it was node with ID 3047:



Now, for some weird reason, there seemed to be no node at that spot where the ID was rendered... hm... after flying around a bit in the mission editor, I found it: there was a group of isolated nodes created under the terrain, covering the basement of the tower! duh!
The bot was chosing one of those as starting point, but of course couldnt get anywhere since the nodes there werent really connected to the main graph again!



For now I just remove any interior node that is under the terrain... but I guess we should support support "underground" interiors so maybe I'll add another flag to interiorInstances to keep those nodes or something like that ...

Phew, that was a long .plan and I still could show you some more anomalies and funny pathfinding pics... but I guess I'll do that in the next .plan ;)
So stay tuned! :)