In my source code, the unit of pathfinding is a grid.

How do I use a navigation mesh cell instead of a grid?

I think I will cast a OBB onto the ground, and use that as a cell,

instead of a polygon as a cell. Is it feasible?

I ask this because I don't know if this is possible for not defining a

cell before the game is started. Instead I create cells on the fly.

In my source code, the agent is able to reverse, dodge and wait

till a corridor is clear. But it only works for regular grids,

still haven't made up my mind on how to turn that into a navigation mesh.

Thanks

Jack

Navmesh (as well as a grid) is a graph and you can use A* to find polygonal path between points. Then you can smooth out the path according to your needs.

As for OBBs. Obviously, you need to use simplified (in any way) mesh to build navmesh. OBBs might work, but you need to handle cases where there is one OBB (obstacle) inside the other one (room) (or you might exclude obstacles from your navmesh at all, if you're sure your collision avoidance system will handle them). Plus it is better to slightly extrude obstacle OBBs and squeeze rooms one. And I would not give up the idea of using polygons. If you have simplified mesh of your level, you can use simple algorithm to merge triangles into concave polygons and use them as navmesh.

As for generating navmesh on the fly. Answer depends on how big and dense your levels are. It might be possible, but I'd do navmesh generation and editing in level editor if possible.

As for dodging, you just check whether you can move agent along specified direction. You raycast from initial position, check if you hit an edge of navmesh polygon. If this edge is passable you continue raycasting in an adjacent polygon until either you hit non-passable edge (then you cant dodge in this direction), either ray ends (dodging is possible). Same goes for other things like waiting till a corridor is clear: you check whether closest agents are in direct visibility

Check this article for some more details (plus more links in the end):

http://www.ai-blog.net/archives/000152.html

For the A* side of things, My personal A* code takes the following args

public Path FindPath(Vector from, Vector to, Func<Vector, bool> isValidMove>)

Where isValidMove is the function used by the path finder to test if a coordinate can be moved to or not. This means my A* is decoupled from the actual thing it navigates over and so I can reuse it no matter how the mesh/grid/whatever being traversed is actually represented, I just need to supply a different test function based on the mesh/grid storage.

You could use similar technique on your AI/Path code so that you minimise changes down the line if/when you decide to switch to navmesh etc