Path Finding

[malolo420]

Hey just wondering if anyone knows how the path finding part of the engine for the AI works and how I can use it properly. I don't know why but my AI like to walk into walls and they don't always like to follow command lists.

[Rob Oplawar]

Welcome to the club. I struggled to no end getting my AI in BCE to navigate my geometry. AI in Blam! like nice wide unbroken flat surfaces to navigate. Even when they have it they can't figure it out all the time. I just ended up playing with my geometry until my AI grew a fucking brain. Not sure what else to say.

[Dwood]

If im not mistaken the devs of halo were using the same principles in pathfinding as they used to calculate how the guns shot but its less specific. skarma said the method was like raytracing i think. because of the way it was coded made a huge impact on the style and structures of the game. notice there are no true tunnels/curvy turns in the campaign?

[Rob Oplawar]

If I still cared I might make a few test BSPs to find out what confuses the AI and what doesn't. It's been a decade, tho. It's just too late for me.

[Limited]

It sucks you cant put way points in the map to help the AI navigate. Sadly Halos fuzzy logic is too fuzzy.

[Kornman00]

Well, seeing as how there was never any official (half assed or not) document put out on how to actually implement AI in a Halo 1 scenario (with its underlying geometry), it's kinda crude to judge AI development.

I don't have any reference material near me right now so I can't give any input ATM

[Dwood]

Korn, do you think we could add path points via open sauce? i havent looked at that part of os enough to know how much you had reversed.

[Limited]

Korn, do you think we could add path points via open sauce? i havent looked at that part of os enough to know how much you had reversed.
Depends completely on the type of algorithm used. It may automatically create nodes, but I dunno I doubt it. Or it could just roam around free will and try to discover areas using a number of various techniques.

Game came out in what, 2001? (Xbox).

[L0d3x]

I think it uses a method similar to D*, based on personal observations.

[Limited]

I think it uses a method similar to D*, based on personal observations.
What the hell is D*? I think you mean A*. If you do, your wrong. A* would be totally inefficient in Halo's environment, due to the dynamic objects around and wide spaces.

[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 :neckbeard:

[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.

[Limited]

firing/movement positions have been visable/editable in the scenario for years now lol
:D I remember watching Aztecs AI tut when it came out (like 04/05?) he placed some there.

[Kornman00]

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.
Besides a flag or two that can be applied to a material with a name modifier (ai can't hear through this shit), 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.