Recast - Open Source Alternative to PathEngine

[koirat]

Sure if you use detour than it might be the best choice. But I'm a Mogre user and i have already made my own pathfinding. As for small dynamic objects I'm using Steering Behaviors as niki suggested.I consider steering B a must have when doing moving with multiple units. One more thing, I have yet got to see the game that is changing it's geometry so radically that you will have to completly rebuild your navmesh. Usually that are some small parts like making new connections between nodes. (open close gates and so on)
But if somebody got such a versatile engine than of course you are right "jacmoe".

[Ident]

If you just have some small moving objects but a generally static level, how about a pathfinding algorithm using recast navmeshes for the 'general path', and a steering algorithm for actually following it?

are you answering to me or to jacmoe? sorry for this stupid question but i dont know since i dont fully understand your answer due to not being used with those words relating to these technologies

[Vectrex]

Usually that are some small parts like making new connections between nodes. (open close gates and so on)

That'd be a pretty sweet feature actually. To pass Recast 2 meshes, one with all dynamic blocking objects open and one all closed. Then have a simple way runtime of telling recast about the state of a particular section. Doors opened/closed mostly, but it could also be rock falls blocking the ai's path etc.
I think 'area's might be useful here?

[koirat]

This might be troublesome since this two meshes would probably generate totally different navigation mesh.
But the solution might be to add some vertical polygons (or just specified edges on a base mesh) that would indicate that no navmesh region can intersect (contain) with them but allow to share edge with different navmesh regions in their position. (this is some messy explenation i will give you an example).

There is a long straight corridor and in the middle is a gate. Navmesh is a long rectangular polygon from begining to the end. When the gate is closed nav mesh is cut in half but since we do not want to disable all this region when gate is closed we need to generate two regions [edit]previously i wrote two nav meshes instead of region (this was my mistake)[\edit] with the connection exactly where the gate is. So when the gate is closed we just disable connection that connects this two sides of the corridor.

[memoni]

Detour has tile navmesh. The idea is the the whole navigation mesh is build from smaller sub pieces, i.e. each tile could be 8x8m. The tile navigation mesh enables quick removing and adding of these tiles and edges which meet at the tile boundaries are automatically linked. This allows stuff like streaming, just swap tiles in and out as the player progresses through larger level, or you can swap tiles when something changes. It does not matter where the tile comes from, you could store two tiles, one of each state of a door/bridge/what ever, or you could even completely recalculate the whole tile.

The can potentially be used the door case too. The cool things about swapping a tile is that you can change the level quite a bit. And it can both add and substract navigable space, where as areas are more a boolean/disable approach. They both have uses, though, and the right choice is up to how you want to build your gameplay.

[memoni]

Nikki, the Detour path smoothing is build so that you can use it to generate good steering velocity towards the target along the path polygon corridor. That is, if you call the findStraightPath() with maxPathSize of 1 or 2, then you will get the point where you should be steering at in order to reach the target. Steering has always some problems when reaching the exact point, so for that reason you usually want the next two steering points and use some logic to get past a point. The string pulling is so fast that you can call it every update to calculate best steering velocity towards your navigation target, that is, if you only need the next couple of points.

Also, if you deviate from your current navmesh polygon it is possible to "patch" the path by adding the new polygon the the beginning of your path poly list. That way you can use steering behaviors too. That is the reason why the path poly list and the path spline are separate. Also many of the query functions return path poly list, or you can generate one from the returned data. I.e. findPolysAround() return data can be used to generate path to any poly it visits using the parent indices.

So the bottom line is that path is not a spline If you have multiple agents, any spline you generate is most likely going to be invalid the next frame.

[koirat]

After looking at your code and code comments, and reading your posts.

I assume:

Smoothing of a path is done inside selected by pathfinding polygons.

So this path might be not the smoothest one, since there is a possibility that the smoothest path will intersect with a region that was not selected by the pathfinding.

Is this correct ?

[memoni]

Yes, that is correct. And it is not a smooth path, it is straight path
Also the pathfinder does not always find the shortest path. This is general navmesh problem, not specific to Detour.

[koirat]

I have got this bug.
For this mesh with settings as on a picture. (radius 0.3)
http://www.storage.to/get/iD7RyJFk/testlevel2.rar

[memoni]

Koirat, I'll take a look at that. Faster way to get bugs noticed is post an issue at http://code.google.com/p/recastnavigation/

First batch of the Linux fixes are in SVN now. It would be awesome if someone could verify that they actually compile better There is no linux make file yet in svn, though.

[koirat]

This is more like a Navigation mesh problem than recast question. It's open question for everybody. (i do not know how recast is doing this)
How would you determine what navigation node the agent is on (given the position of an agent). Or what is the closest node to an agent, when agent is outside of a navigation mesh ? (except of brute force methods).

[KungFooMasta]

I've been reading through the library some more, it seems all the magic happens in the handleBuild function. Few questions:

1. What is a span? According to rcCreateHeightfield:

Code: Select all

bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
						 const float* bmin, const float* bmax,
						 float cs, float ch)
{
	hf.width = width;
	hf.height = height;
	hf.spans = new rcSpan*[hf.width*hf.height];
	vcopy(hf.bmin, bmin);
	vcopy(hf.bmax, bmax);
	hf.cs = cs;
	hf.ch = ch;
	if (!hf.spans)
		return false;
	memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
	return true;
}

And the definition:

Code: Select all

// Heightfield span.
struct rcSpan
{
	unsigned int smin : 15;			// Span min height.
	unsigned int smax : 15;			// Span max height.
	unsigned int flags : 2;			// Span flags.
	rcSpan* next;					// Next span in column.
};

What does

Code: Select all

new rcSpan*[hf.width*hf.height];

mean? I'm not familiar with this syntax, x * [y].

Spans are later used to filter triangles that cannot be walked on. What does the data of the span represent? Is there a span per triangle?

2. According to the process outlined in handleBuild:

Step 1. Initialize build config.
Step 2. Rasterize input polygon soup.
Step 3. Filter walkables surfaces.
etc.

Rasterization is when you convert the triangle data into renderable data, so you can draw the triangles, right? Shouldn't step 2 and 3 be switched? Otherwise the polygon sections you see drawn don't truly represent all walkable areas..

3. Has anybody made an Ogre adaptation of the demo? ie using Ogre::ManualObject in the rasterization process?

[jacmoe]

I did. It was fairly straightforward because the debug drawing is all in immediate mode. Just convert it to use an Ogre::ManualObject, and that's it.
Was surprised at how easy that was.
Sadly, I was a bit sloppy when I did my last Windows reformat, and forgot that I had some stuff in my home directory.. Stupid Visual Studio insisting on creating projects there by default.. Normally I keep all my code on a different disc. So I don't have any code to share. Well..

[KungFooMasta]

I read through the code a bit more, thought I would provide the high level algorithm used:

1. Create mesh
2. Load mesh data from .obj
3. send mesh verts, tris, normals, min/max bounds to Sample class
4. Sample class builds the nav mesh (several step process)

4.1. Set parameters used to build nav mesh (cell size, height, walkable slope, etc.)
4.2. Create flag for each triangle to mark it as walkable or not
4.3. Rasterize the triangles, which populates the Spans (??)
4.4. Filter ledge spans (?? - ".. remove unwanted overhangs caused by rasterization")
4.5. Filter low height spans (?? - "Remove walkable flag from spans which do not have enough space above them for the agent to stand there."
4.6. Create Compact heightfield - data allowing quick lookup, neighbors between walkable cells calculated.
4.7. Build Distance field, preparing to break walkable areas into regions
4.8. Partition into regions without holes
4.9. Create contours
4.10. Create polygon mesh from contours
4.11. Create detail mesh from polygon and Sample config
4.12. Create Detour StatNavMesh from polygon and detail meshes

5. Use StatNavMesh to get paths

I still don't know what a Span is, I thought it was the difference in height between one cell and the next, but I think a triangle can have a list of Spans.. and then there are Compact Spans..

I'm trying to understand the process because I'd like to have a good pathing solution in place for the RTS game I've been working on, which has scenarios where you can take down trees creating more paths. I guess the easiest way to accomplish this is to create new regions or contours underneath the trees as they're removed, but it will take some effort to understand the data format and how to update it.

[koirat]

As i know rts games use rather hierarchical grid based approach (or similar) to pathfinding. And disabling and enabling nodes in this method is rather easy and straightforward.
May I ask why you decided to go with navigation mesh, are you doing something that fancy, excluding trees issues?

Code: Select all

  hf.spans = new rcSpan*[hf.width*hf.height];

Probably an array of pointers to object of type rcSpan.

Take a look at function declaration. rcHeightfield is a type.

Code: Select all

bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
                   const float* bmin, const float* bmax,
                   float cs, float ch)

Very confusing naming convention IMHO.

At first i thought it was a "placement new" lol.

I'm guessing here because I haven't check the code.

[KungFooMasta]

are you doing something that fancy ?

Yah. I don't want the limitations of the standard Tile-based RTS system, with defined height levels and square cells. Its one of the key differentiators I'm going for.

Probably an array of pointers to object of type rcSpan.

Oh I get it now.

Code: Select all

new int * [5]; 

Allocating an array of pointers, duh.. lol.

I agree the naming convention causes a lot of confusion. You really have to dig into the code to realize cs is Cell Size, and cs is Cell Height, for example. The extra key presses to spell out variables in a meaningful way is definately worth it IMO.

[jacmoe]

I think you'd be interested in the area generation code:
http://digestingduck.blogspot.com/2009/ ... gress.html
Seems to be perfect for your RTS game.

I also noticed your post at the Recast Google Group, where you wanted a more modern and object-oriented style:

I hate namespaces, hence not using them One of my earlier versions
(Recast is something like version 4) used more class based approach,
but most of the pipeline does not map well to classes. It is more like
series of transformations or filters to data. I would like to make the
toolkit even more towards that kind of functional style.

I also want to differentiate between the data that is used to generate
the mesh versus the actual runtime data.

So the current toolkit structure is just a series of function calls.
You can track how the data flows between the functions and write your
own to mangle with the data in between. Or you can just choose to use
some parts of the code. That's the reason I like to call it a toolkit,
its series of useful functions which happen to work well together.

I think it's refreshing to work with a library which is practical and functional, and very easy to wrap.

[hd_]

Wow, this is brilliant! I never even knew about this kind of thing before. Exactly the kind of thing I will need in some future projects

[koirat]

Once again about it's naming convention. I just realized that prefix "rc" comes from Recast and "dt" probably Detour. Anyway it's still confusing for newcomers. Since I'm mosty c# programmer I'm used to start names with uppercase for Type names and Functions and lowercase for variables. So RCSpan RCHeightfield would be my choices for type naming.

[jacmoe]

Is it really suitable for newcomers, I ask..
I very much prefer someVariable naming conventions, but it's a matter of taste.

If you think it's difficult, get some more mileage..

[koirat]

I also prefer someVariable naming conventions i just don't like someType naming conventions.
I also use camel notation for variables.
Read my post i was talking about first character.
I'm using big letter for RC -> uppercase R since it is starting type name. You can change uppercase c to lowercase, I made this mistake since it's a Recast not ReCast, and uppercase S for Span since it's starting new word.

[jacmoe]

Right.
I think it's because rc and dt is meant to be some sort of namespace-like prefix; 'rc' is the library and the rest is the typename.
If you view it that way, it ought to make sense.

[koirat]

OK I'm closing this thread

[jacmoe]

Nah - I am just splitting hairs -

[KungFooMasta]

Thanks for the blog link Jacmoe! Very interesting. After understanding more how the library works, I think its well suited to be a set of useful functions that manipulate data. Although I'll never agree with not needing a namespace, that just seems primitive and lacking in organization.

Unfortunately from the Ogre Terrain thread, it seems there is no easy way to get the triangle/vertex data from the Ogre Terrain class. It seems every Terrain system I move to has to have work done to get all the necessary data, whether its for collisions, or for pathing. What a pain.