PDA

View Full Version : Path Finding



malolo420
January 19th, 2010, 07:09 PM
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
January 19th, 2010, 07:15 PM
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
January 19th, 2010, 07:46 PM
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
January 19th, 2010, 09:50 PM
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
January 20th, 2010, 07:45 AM
It sucks you cant put way points in the map to help the AI navigate. Sadly Halos fuzzy logic is too fuzzy.

Kornman00
January 20th, 2010, 09:02 AM
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
January 20th, 2010, 10:22 AM
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
January 20th, 2010, 10:34 AM
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
January 20th, 2010, 10:48 AM
I think it uses a method similar to D*, based on personal observations.

Limited
January 20th, 2010, 11:37 AM
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
January 20th, 2010, 12:00 PM
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
January 20th, 2010, 12:17 PM
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
January 20th, 2010, 12:23 PM
Well during command lists they have a certain goal though, same goes for when they are following the player.

Limited
January 20th, 2010, 12:28 PM
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
January 20th, 2010, 12:36 PM
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
January 20th, 2010, 01:10 PM
So placement nodes are added? That changes everything...

L0d3x
January 20th, 2010, 01:24 PM
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
January 20th, 2010, 01:25 PM
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
January 20th, 2010, 02:58 PM
So placement nodes are added? That changes everything...
firing/movement positions have been visable/editable in the scenario for years now lol

Dwood
January 20th, 2010, 03:09 PM
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
January 20th, 2010, 04:32 PM
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
January 20th, 2010, 11:30 PM
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.