Navigation System design process

[ostapus]

small contribution for discussion
MEGAUPLOAD - The leading online storage and file delivery service - adt to obj exporter to play w/ recast demo.
you will need vc# (w/ xna 3 installed) to compile/change adts you want to export (in program.cs). code is nasty but it works though

now my questions :
what optimal settings you've found for recastdemo ?
- cell size/heigt
- agent settings
- region
- polygonization
and i would appreciate if you explain why those ones fits better (besides simple shuffling them).

thanks

small bug: replace AddModel function in CModel.cs with following to fix

public void AddModel(CModel model)
{
if ( !CModelManager.models.ContainsKey(model.name) )
{
CModelManager.models.Add(model.name, model) ;
modelsGroup.Add(model);
}
else
{
CModel mm = CModelManager.models[model.name];
modelsGroup.Add(mm);
System.Console.WriteLine("Model {0} already exists in the list", model.name);
}
}

[ostapus]

<edit> any info on dynamic objects in wow memory ?

[lanman92]

Maybe look back at Unknowned posts on parsing the M2 list?

[ostapus]

thanks, i remember someone (Unknowned) posts info on it.. This forum needs to do something with search function.

[namreeb]

You can also search google by appending "site:mmowned.com" to your query. I have found that much more efficient.

[FenixTX2]

Just an update: I have begun the portal identification code.
[SPOILER]

[/SPOILER]

How are you identifying these portals? I'm looking at this problem right now. Current idea is to find all tiles along each edge of a mesh. Then find portals which are perpendicular to the mesh edge. These portal points will be grouped into 'exit portals' for that mesh. After that I path find from each point within a portal group to every other point in each of the other portal groups (removing any portal groups which cannot reach any other portal group...although I may change this to removing any portal group whose tiles do not reach further than 1 tile depth into the mesh). This leaves me with a list of basic exit and entry points for a nevmesh and a cost for routing between them...I'll add flight points as entry/exit points too with costs based on travel time between each flight point later.

[streppel]

wow...this thread is sooo awsome

[FenixTX2]

I've made some progress towards identifying entry and exit points for a mesh. Example shows portals for one side of 30_48 (stormwind)

[Apoc]

As far as the 'portal' stuff goes, you can effectively ignore it. R+D had somewhat poor support for tiles. It is much better now; and is the default way to handle things. Detour will automatically build the portal information when you load new tiles.

[MaiN]

As far as the 'portal' stuff goes, you can effectively ignore it. R+D had somewhat poor support for tiles. It is much better now; and is the default way to handle things. Detour will automatically build the portal information when you load new tiles.

No it won't. Detour has always built what you refer to as portal information.
I think FenixTX2 is trying to create a macro-mesh for long path finds, to find out which tiles to load pre-pathing. Instead of doing that, what I did was to let Detour request a tile to be loaded in the A* search itself. I check if a polygon lies on the border of a tile; if it does, I load the adjacent tiles. This works well (with a few other modifications you will be able to generate paths from Booty Bay to Light's Hope Chapel or Moonglade to Silithus).
If you aren't, then you don't need to identify the 'portals'; Detour stitches the tiles together, as long as you get the borders perfect (pass information about neighbour tiles to Recast in the mesh process; add border*cs to the outer bounds etc.).

[Apoc]

No it won't. Detour has always built what you refer to as portal information.
I think FenixTX2 is trying to create a macro-mesh for long path finds, to find out which tiles to load pre-pathing. Instead of doing that, what I did was to let Detour request a tile to be loaded in the A* search itself. I check if a polygon lies on the border of a tile; if it does, I load the adjacent tiles. This works well (with a few other modifications you will be able to generate paths from Booty Bay to Light's Hope Chapel or Moonglade to Silithus).
If you aren't, then you don't need to identify the 'portals'; Detour stitches the tiles together, as long as you get the borders perfect (pass information about neighbour tiles to Recast in the mesh process; add border*cs to the outer bounds etc.).

When we were working on 'portals' was when R+D barely had support for tiled meshes. (It was basically a complete 'world mesh') I'm well aware of what it does now. -_-

[DrGonzo]

I've got my own implementation parsing adt's and using recast and I've noticed that some paths go underground in some places (as much as 6f). I'm not using the inner 8x8 verts of the 9x9 for terrain, would using those extra detail verts fix the issue?

[namreeb]

To clear up the confusion, there are two types of portals. First, there are the portals that Detour identifies as basically shared edges between tiles. These are used for pathfinding across tiles. The concept I described earlier in this thread was taking the same concept and expanding it, giving us a 'hierarchical pathfinding' situation. That is, you take a grid of arbitrary tile size (1 tile, or 2x2 tiles, 3x3, etc.), discover the portals connecting this "tile chunk" to its neighbors, and use this information to dictate which of detour's mesh tiles to load prior to executing Detour's stock pathfind.

To demonstrate this, visit the Kynapse site here: Autodesk - Autodesk Kynapse

If you watch the demonstration video, and skip to about 3:00, it describes their mesh system. If you skip to 4:28 the author describes hierarchical pathfinding.

I can't remember if I updated this thread or not, but this approach was abandoned. The reason for creating this system was to achieve a robust tile management that was also memory efficient. It turned out that even with a very large "tile chunk" (I think I tried up to 5x5), the chunk portal data got larger than the tiles themselves. On some boundaries I had up to 300 portals, and to produce optimal paths you have to store some sort of heuristic between each portal and its neighbors. Things got out of hand very quickly.

A more simple approach would be to load all tiles within a given radius of the agent, and expand that radius as necessary to encompass the target destination. Granted there is the possibility of missing the optimal path by doing this, but assuming you're also using gryphons, hearthstone, etc., I think the impact of this is minimal.

Edit: To answer your question, FenixTX2, I was doing more or less what you appear to be doing, but I also combined adjacent/connected squares to reduce the data size.

[homer91]

is it possible to use Kynapse with a custom bot?

[ostapus]

No it won't. Detour has always built what you refer to as portal information.
I think FenixTX2 is trying to create a macro-mesh for long path finds, to find out which tiles to load pre-pathing. Instead of doing that, what I did was to let Detour request a tile to be loaded in the A* search itself. I check if a polygon lies on the border of a tile; if it does, I load the adjacent tiles. This works well (with a few other modifications you will be able to generate paths from Booty Bay to Light's Hope Chapel or Moonglade to Silithus).
If you aren't, then you don't need to identify the 'portals'; Detour stitches the tiles together, as long as you get the borders perfect (pass information about neighbour tiles to Recast in the mesh process; add border*cs to the outer bounds etc.).

interesting approach, did you have to modify FindPath function to implement it ? How perfomance wise ? For a long path, say from BB to very Chapel - did you hit limitation on loaded tiles ?

thanks