Regular Grid from Recast Mesh

[otty]

Hi Mikko,

is it possible to get a regular mesh abstraction from the polyMesh generated by recast? In particular, i need something like a grid, represented via points within the navigation mesh. For now, i am using the outer edges and the triangle centers to generate a waypoint grid on top of the nav mesh. But this is not very precise. I'd like to use my own pathfinding algorithm, thats why i need something like shown in the picture below ( from killzone).

regards,

Adrian

[Mikko Mononen]

Hi,

You could paint a regular grid on the compact heightfield (i.e. use areas), place nodes at the center of the painted areas, and then use CHFs connectivity to find neighbour links. Short answer, there is no direct way, but with little tinkering you can do it.

--mikko

[otty]

Hi,

glad to hear it is possible. Recast is doing a very ( very! ) good job analyzing the structure of a BSP map for quake 3 arena. Therefore i'd like to stick to it. I already had a look on the compact heightfield, but in the demo it looks very complex. The number of "boxes" derived from the compact heightfield is very huge.

[Mikko Mononen]

Think it as 2.5D image. Once you have the image, you can for example
paint 8x8 "pixel" checker board over it. Now if you place a
vertex/node at the center of each of these checker squares and connect
them to neighbours (use the image connectivity to find neighbours)
then you have coarse grid of vertice/nodes and connections.

Check the debug draw function on how to iterate over the CHF:
http://code.google.com/p/recastnavigation/source/browse/trunk/DebugUtils/Source/RecastDebugDraw.cpp#212

CHFs are build so that it is easy to attach extra data to it.
chf.spanCount tells you how many spans there are. You can then use the
'i' to access the data.

calculateDistanceField() is pretty easy example to follow on how to
access neighbours.
http://code.google.com/p/recastnavigation/source/browse/trunk/Recast/Source/RecastRegion.cpp#31
In the same file you can also find how to do depth first search on CHFs.

--mikko

[otty]

Hey Mikko,

i finally made it ;) It is really impressive, how i can create a very precise waypoint mesh on the top of the recast navigation mesh with the help of the compact height field. Have a look at the screenshot below. It is a very dense mesh. For this map ( medium size ) it has 885 waypoints calculated from a regular grid and the outer edges.

I'm using my own A* algorithm for path finding, because i'd like to use several game specific heuristic calculations for each agent type ( see the red line ? this is an example path with default manhattan distance calculation).

Each waypoint is linked to its closest neighbours, so my A* calculations are damn fast. The precalculation takes its time, but i'm going to save that data within the map file.

thank you Mikko for such a great library as recast is.

regards,

Adrian

[Mikko Mononen]

That looks awesome! Keep us posted on your progress.

--mikko

[otty]

Hey Mikko,

Yeah, i will keep you inform. I'm going to improve the area awareness, like cover, position evaluation for sniper, ambush, etc. Do you know any more good resources for features other game AI systems have? You pointed me to your slides regarding coverplates, that was awesome and really helpful. I'm still not 100% sure which features are worth implementing, and which not. Cover selection is going into the AAS system of mine. As well as special nodes/links for wallwalking/walljumping/vaulting and teleporting/jumppad stuff.

Aigamedev.com is ok, but i don't wanna pay for their articles. Got the free account, but the free articles are more about AI behavior then area awareness. I haven't reached that point yet ;)

regards,

Adrian

[Mikko Mononen]

Hi,

I think your next step is a bit higher level tactical representations
and behaviors. William has bunch of interesting presentations and
links at his site related to that: http://www.cgf-ai.com/ AI Wisdom
books are pretty ok too, although they are getting out dated:
http://www.aiwisdom.com/ AiGamedev is pretty much the best and more
recent game AI source.
A lot of folks are using behavior trees (BT) or some form of
hierarchical state machines (HSM) these days for behaviors. There are
tons of information about them out there. I suggest you to just start
testing things out!

--mikko