Jump to content
Posted 19 April 2012 - 11:29 PM
Posted 20 April 2012 - 07:16 AM
Posted 20 April 2012 - 09:51 AM
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI
Posted 20 April 2012 - 06:31 PM
Posted 21 April 2012 - 01:27 AM
Thank you IADaveMark. I have thought about this situation, but even poly B is generated as you say, this problem is still exsit. Or it would be an easy way to do some algorithem base on an appropriate generation?
Poly B in that example is horribly inappropriate anyway. It shouldn't connect to the top and bottom walls at all. Instead, the corners of the blue boxes should be connected to each other making area B represent the area between them.
That allows you to simply mark poly B as being off-limits for agents that can't use it.
You might want to take a look at the Recast and Detour library, which provides automatic generation of navmeshes. A part of the parametric structure that you populate to generate the navmesh includes a member for agent radius and another for agent height, which affect the generation of the navmesh. A solution to the problem of agents of multiple sizes is to generate multiple navmeshes, and roughly classify the agents into a fixed number of size categories equal to the number of navmeshes. This way, you don't have to complicate the actual pathfind with additional logic to cull polygons based on agent size.
Always shrink your navmesh for agent size.
We have tested this problem at work and we found that generating several navmeshes - as JT suggest - is far more efficient (less memory AND less cpu cost) than generating one navmesh that supports several agent radii.
Posted 21 April 2012 - 11:04 AM
Posted 22 April 2012 - 07:45 AM
CoH's solution seems nice. If you dont need the information to be so dense, you can use a quadtree instead of a dense grid. That would reduce the memory, and the cost of pathfinding, line-of-sight checks, etc.
Im not sure why your string pulling is so expensive, it should be very cheap to do on a grid, as all you need to do is intersecting a vector with axis-aligned lines. If you are sure your maths are optimal, then there is also the fact that you dont need to smooth the whole path at once. You really only need to smooth up to the next "corner", its useless to smooth a whole path that is likely to change.