Sunday, August 07, 2005


Looking around at
different ways to steer computer-generated characters, I came upon OpenSteer.

I really wish I knew C++ and OpenGL.

Anyway, be sure to check out the different types of steering behaviors. They are all based on simple goals (Seek, Flee, Wander, etc.) and by combining them together you could get some pretty awesome movement.

This is related to my post on creating simulated organisms.

I wish I had the know-how to apply a Sims-like template (needs, desires, fears) to create a herd of, say, sheep and then use steering behaviors to get them to:

1. Find food.
2. Move as a herd.
3. Perform defensive and fleeing in response to predators.
4. Reproduce.
5. Adjust their behavior in response to changing environments.
6. Be sheep-like (whatever that really means)

Watching a flocking simulation with avoidance programmed in, I'm still boggled how games can have characters that walk into walls. Or tables, chairs, other detritus. It's like the characters were given no way of gauging obstructions and creating a path around them.

Any programmers want to comment on why this implementation is so difficult? I would guess that it could have to do with 3-d environments. Very curious.


Chris said...

Flocking can be controlled with a few simple principles (cohesion, avoidance, alignment). See Boids for a good demonstration and explanation of an individual actor model.

Pathing, on the other hand, gives actors certain paths on which they may travel from point to point. Paths can be explicitly defined, or can be defined as a set of geometric limits (essentially, allow the actor to move within the bounds of a polygon, or to an adjacent polygon where the bounds meet or overlap). Consider that the actor will likely traverse graphs of polygonal areas, each area possessing a cost, summed and modified by proximity to the destination.

Pathfinding is the most difficult and computational intensive task to perform. Basically, you're looking for the lowest cost path from the current point to the destination within the legal bounds. Adding different costs to terrains makes the algorithm more complication (ie, it takes longer to swim than it does to walk; is it it cheaper to swim across the lake or to walk around it?). As a result, in many cases MMOs ignore or mostly ignore pathfinding. In UO, it wasn't uncommon to trap a mob behind cleverly constructed barriers. Almost everyone who played EQ can remember particular places where a mob would either get stuck while pathfinding, mobs would walk through walls, or would take a very long route in order to attack the player character. In WoW, some mobs can't be hit if a path can't be determined. Damion Schubert, in a comment on TerraNova, mentioned that the majority of Shadowbane's server CPU time is spent pathfinding, collision, line-of-sight, and cheat detection. Moving pathfinding and line-of-sight computations to the player's computer is infeasible as it is an insecure environment.

For more information on pathfinding, read Bryan Stout's article at GamaSutra.

Johnny Pi said...

Wow. Thanks for the links. That Gamasutra article was great, can't believe I missed it (though it is an article from way before I signed up at the site).

I guess my problem, then, was that I was kind of equating the flocking algorithms and pathfinding. I can definitely see similarities and areas of overlap, but it's pretty clear now that there are many, many things to consider about each method.

I wonder if anyone has cobbled any kind of hybrid methods.

I know that HL2 requires you to place nodes to help the AI with pathfinding, but you can set a radius in which they have have limited agency up to a certain distance from the node.

My problem with their system is that when NPCs plot a path and select their next node, that node becomes locked - so if there aren't enough nodes placed then NPCs can move around awkwardly, even if it looks like they should be able to share space (a wide hall with only one node for NPCs will only admit one at a time, even if it's wide enough to accomodate them). At least, that's my understanding of the system.

I can definitely see the difficulties with MMO development. That's a monster I don't even want to think about, not until I've completed at least one lame space invaders clone. Then I'll think about it, and decide, "No effing way."

I'll have to consider this further.