In ABx a Player or NPC can move autonomously from one point to another. For example, a Player can click on a point on the Terrain, the client calculates where the mouse pointer hits the terrain with a raycast and tells the server to move to this coordinate.
To make this happen, the server performs three steps: (1) Find a path to the destination, (2) avoid obstacles on this path and (3) if there is some dynamic object on the way the actor would collide with, slide along the bounding box of this object. Also NPCs use the same method to, e.g. move into skill range or attack range.
1. Finding path
ABx uses Recast/Detour for path finding. It uses a navigation mesh, which is basically a grid with fields describing whether or not you can step on it (the green fields).
The API of Detour is quite simple, it boils down to:
- Find the nearest field (Actors can step on) to the starting point.
- Find the nearest field to the end point.
- Find a path from the first and the second field.
If a path was found, Detour returns a series of points forming the route.
2. Avoiding obstacles
The navigation mesh is built without taking buildings and other static objects into consideration. But this doesn't mean we can just walk through them. If there is an obstacle on the route to the destination, the server tries to find a way around on the fly.
When the game realizes that there is an obstacle between the current position and the next waypoint, it inserts a new waypoint which is close to the object.
Of course there is no guarantee that the new route is without obstacles, so the game tries different solutions until one is found, or, if none was found, the character is stuck and stops moving.
I'm not quite sure if it wouldn't be better to build the navigation mesh with static objects. On the other hand, obstacle avoidance must always be performed, because it should also avoid other moving objects, like other players or NPCs.
3. Collision sliding
If the character still collides with another object, it tries to go around it by sliding along the bounding box of the object.
This works nice for axis aligned bounding boxes (AABB), but not so great for oriented bounding boxes (OBB) yet.
Conclusion
There may be better ways to do this, but this works more or less and is not too difficult. I think this is one of the more difficult parts of this project.
I assume the obstacles that you're talking about in Section 2 & 3 are smaller than the ones that have carved out portions of your navmesh in the example in Section 1. Is that right?
That, combined with the mention in Section 2 “The navigation mesh is built without taking buildings and other static objects into consideration”, my initial reaction/suggestion would be: Don't do that.
If your navmesh already reflects the nature of the static world geometry, why doesn't it also reflect the static nature of other static objects in the world? Is there some particular reason that you ignore those objects when building your navmesh?
The immediate benefit would be that for static things, whatever pathing algorithm you have working for your navmesh example in Section 1 would immediately “just work” when updated with navigation information from the other static objects.