Quote: If you really want to get a general idea of things, you should view the "The Integration of AI and Level Design in Halo" presentation.
Bungie used the A* algorithm in Halo. D* is more so for real-world robotics where the underlying terrian is an unknown factor.
Static pathfinding data is built from the BSP. Therefore the AI has a meaningful representation of the terrain. From there, the designer can place objects in the world which can act as "obstacles". Pretty much all obstacles in Halo 1 can be considered static besides units.
The pathfinding is initialized from the respected BSP data and bsp surface indices which act as the source and desintation. From this a node based system is created for the AI, which (my ordering may be wrong on this but the entire process shouldn't) then factors in current obstacles then finally they can "smooth" the path. Dynamic obstacles wouldn't matter unless they present themselves during the execution of movement from NodeX to NodeY.
Replanning of the whole path wouldn't needed, only between nodes. If the game had large dynamic objects, this case wouldn't be as effective (as the obstruction could be affecting X amount of nodes). The only objects really dynamic in the world are Units, which the largest instance you'll find of is the Pelican or Covie dropship.
So we have the terrian pathfinding which is static and thus can be precalculated into nodes (to precompute distances from say a wall) then we have 3D obstacles represented by spheres or pills. To map this 3D data to the 2D pathfinding, a "disc" is created from a sphere which can be inputed into the path finding.
Think about how a shadow works. The disc is the 2D representation of that sphere. Since the only obstacle avoidance in Halo 1 was going around objects (jumping, climbing, etc not introduced until Halo 2 and required much more spatial information) this made the system very simple. From that disc, a smoothed path can be computed between the nodes.
But then another layer is introduced as the designer also has firing/move positions at their disposal to better customize the AI in the encounter/squads. Since AI was very centralized in Halo 1 and didn't really track the entire level, a designer can place firing positions to define where they're at when they're in a certain state. Say they're in an attack state, they can have positions K, N and Q to hold. Since the positions are bit-mapped based, a single position can be used for multiple states (ie during attack and during cover). The movement positions can also weigh in on the grand scheme of things with timing and also specific animation to use while in the movement.
So not only is it on the designer to properly create 3D geometry which can consumed into pathfinding data, they also have to properly setup and convey how the AI encounter is suppose to behave in an area. Conveying by toggling bits in each state's respected firing position bit-map.
There are debug options which can visualize all this information. Just research the engine's script functions/globals.
In a follow-up post he hits on the most important part;
Besides a flag or two that can be applied to a material with a name modifier (ai can't hear through this s***), you don't have a say in how that static pathfinding data is calculated
Bungie would have had the perks of having documented contraints and figures of how to build their levels so there wouldn't be any pathfinding issues. That and the original programmers.
And, no I don't know what the commands are to display all that data.