Hi.., Basically, what i'm currently doing, is i generate automatically a series of navigation points that are spread around in the heightmap. This navigation points are then connected to each other( depending on the distance, and line of sight between each point). The AI bots then navigate in this grid of points with a A* algorithm. Well, this is working allright, but somehow the movements don't seem natural. I was checking how far cry is doing it, and they seem to use navigation areas ?? The mapper simply assigns a area where the ai can walk around, and they simply walk in that area.., any ideias how is this done ? Limiting the area of the ai is one thing, but the ai still needs to generate target points somehow, or how to avoid obstacles, trees, rocks, etc., they can't possibly be doing this in realtime, raycasting everything the ai does. thanks, Bruno

If the mapper assigns the area, then what's the problem? All you have is a set of adjacent polygons corresponding to walkable areas. You can pathfind between them using A* and you can move within them using steering behaviours or any other simple obstacle avoidance scheme. Large obstacles can be used to split the areas into several smaller ones if you need.

The farcry AI manual explains in pretty good detail how they auto-generate it. Essentially they place vertex points at obstacle world positions to create a mesh of the terrain. Triangulate this mesh, then run it through a step where each edge of the triangles does 2 raycasts in each direction. This is to detect the space available on each edge and give a rough indication that takes the obstacle size into account. In the case of large irregular shaped obstacles that this may not work well with, mappers can place convex no-walk zones, where the vertices of these zones would also be used in the triangulation phase. After reading it, it sounds like a relatively simple concept to implement. I don't believe they went into much detail on how they handle overlapping areas, though I don't think that would necessarily be a difficult part to extend.

What you should look at is Delaunay Triangulation.

If you check a Far Cry map with the nav mesh displayed, you'll see that each vertices are right under obstacles. From that, an "obstacle width" is baked in the edge of the triangle using ray casts. The results are so-so.

An improvement you can do, is generate a set of surfaces representing the collision volumes, substract that to the world surface, and then run a delaunay triangulation on the remaining surface. Using this method, any point lying on the nav mesh is valid and can be walked to.

Cheers

Eric

Another way is to select walkable surfaces, subdivide them into smaller triangles. Mark the resulting triangle mesh based on the free space (height and distance to obstackles), then try to simplify it by coalescing adjacent triangles with the same type into bigger ones. The result is a walkable mesh with small enough triangles that allow linear motion between adjacent waypoints (triangle centers) with taking care of the object height and width. (height to avoid hitting the ceiling, width to avoid bouncing into walls). Smaller objects could use the same mesh while having access to more places, because they can walk on triangles marked for smaller objects. The whole algoritm can be run when the map editor saves the results, and has zero overhead during runtime. Except the pathfinding between the triangles and the interpolator code that moves the objects between triangle nodes. The algorithm can be extended to allow a certain class of mobile objects to walk on walls and other non horizontal sufaces or even other types of terrain. (by having both a size and an object class field for each triangle) The triangles can be reduced to a point (node) graph on load or during the map save.

Viktor

I would use a navigation lattice comprised of lines with imbedded attributes on how to traverse the terrain. Optimizing the path with a time sliced probing system close to the characters feet (rotating probe one per 10 characters.). One of the attributes would be strict so the character won't deviate from the path when on a cat walk or next to lava.

Well there's a multitude of methods for navigation representations - nav meshes, navpoints and all of that. We autogenerate a navmesh based on the physics mesh representation of the terrain and objects on the map -- which is probably overkill for most games, but some kind of autogeneration of navigation data is recommended, I'd say.

Now regardless of your actual representation you'll get a somewhat coarse view of the walking (a path consisting of a poly-line), and you'll need to smooth that in order to get the "natural" walking you want (not walking to a point, turning 45 degrees, walking 2 meters, turning a bit again, etc). And as I understand it, your problems are really much more about pathfollowing than pathfinding/navigation.

Thanks guys :)
Stary, i think you are right, if i could smooth the paths i think it would be more real, instead of making hard turns everytime..,
Do you guys know how could i smooth the paths ?
I supose i need to generate a curve somehow, between the origin and the destiny point ? But thinking of it, can;t be between the origin and the destiny, maybe between the destiny and the destiny + 1 or something ?

thanks,
Bruno

I don't know the details of how our smoothing works, but here's my thoughs:

The difficult thing is not to make it smooth, but to make it smooth while keeping it in only allowed areas. I assume some b-spline-like curve (but not entirely spline, since that'd miss all the target points). You could try hermite interpolating the points, the results could be good enough.

Quote: Original post by Stary
I assume some b-spline-like curve (but not entirely spline, since that'd miss all the target points).

Catmull-Rom spline.