Path Finding

[L0d3x]

D* is a dynamic version of A* if I remember correctly, I learnt about it in my AI classes last year.

http://en.wikipedia.org/wiki/D*_search_algorithm

[Limited]

Oh, didnt know that was called the D*.

"This has the advantage that each expanded node refers to the next node leading to the target and knows the exact cost to the target (after expansion)."

Okay, you have the exact cost to the target, yet you still need a heuristic to the start target, so kinda removes the advantage?

I still dont think Halo uses D*, because AI dont necessarily need a goal to reach. They just mill around, somewhat aimlessly.

[L0d3x]

Well during command lists they have a certain goal though, same goes for when they are following the player.

[Limited]

Well during command lists they have a certain goal though, same goes for when they are following the player.

With objectives yeah I suppose. Its one reason why they dont sync in MP because they all run off in different ways (roaming) instead of going to a single goal.

[Kornman00]

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.

[Limited]

So placement nodes are added? That changes everything...

[L0d3x]

D* is more so for real-world robotics where the underlying terrian is an unknown factor.

Ah yes, we used it for one of our lego mindstorms projects in CS.

And thank you for that information

[Dwood]

So placement nodes are added? That changes everything...

How would one know what those placement nodes are when reversing?

e: Look for some special flags I guess.

[Kornman00]

So placement nodes are added? That changes everything...

firing/movement positions have been visable/editable in the scenario for years now lol

[Dwood]

firing/movement positions have been visable/editable in the scenario for years now lol

He means outside of normal firing positions. ie ones used to calculate the pathfinding in the bsp... so we dont have to modify the geometry to get bots to do what we want them to.