[Tool] Navmesh Creator

[caytchen]

As for tile size, the problem I had with Recast was that with large tiles you can get long and skinny mesh polygons. This can give you some non-optimal paths because of the string pulling algorithm being used in Detour at the time. This may or may not still be the case, but currently I am experimenting with MCNK sized tiles.

This happens if you use monotone partitioning, which is fine for small tile sizes but its practically useless for large tiles. See this blog post Digesting Duck: Monotone Regions
To "fix" that, watershed partitioning can be used, which is the default now anyway, I think.

(I noticed you've been looking to build your own Recast. Could you elaborate on the simplifications and improvements that can be made when specializing on WoW? I remember pendras thread, but I never understood why his system would perform magnitudes faster than Recast)

[ostapus]

Anyone can check for me kalimdor_37_23 map. On following pictures the players coordinates are "Mount Hyjal,4581.5273,-2959.8936,1066.5474" and that location happening to be under the stair. and that stair is actually doesn't look good to me (the next one further is looking ok though). My nav implementation stucks everytime over there. Is this something wrong with my model importing (the other models are looking ok) or ...

pictures:
http://ostap.us/5/p1.jpg
http://ostap.us/5/p2.jpg
http://ostap.us/5/p3.jpg

the coordinates from above reported from the in-game player's position in "stuck" place.

[namreeb]

This happens if you use monotone partitioning, which is fine for small tile sizes but its practically useless for large tiles. See this blog post Digesting Duck: Monotone Regions
To "fix" that, watershed partitioning can be used, which is the default now anyway, I think.

(I noticed you've been looking to build your own Recast. Could you elaborate on the simplifications and improvements that can be made when specializing on WoW? I remember pendras thread, but I never understood why his system would perform magnitudes faster than Recast)

It happens with watershed partitioning just the same. In fact my experience has been it is less prevalent when doing monotone partitioning. But Mikko's implementations are geared towards a dungeon style universe with long, narrow corridors.

As for what the motivation is for doing your own, there are three major elements.

1. I felt I would need to understand every element of this process if I wanted to extend the process to do 3d navigation properly.
2. As stated before, some of the algorithms used by R+D while they work in WoW are not ideal.
3. In response to one of your questions, yes it does go faster.

As for why pendra's implementation went so fast, I believe it is a combination of his access to a server designed for computational geometry related number crunching, the fact that his code was highly parellel, and being WoW specific does allow you to skip some serious number crunching. Most notable, you do not have to rasterize the entire terrain. In fact, you need only rasterize doodads and WMOs. When I wrote my height field generation class, I wrote it so I could easily switch between height map interpolation and rasterization for the terrain and liquid data, so I could see what the speed up is. It was a few months ago, but I'm pretty sure that by skipping the un-needed rasterization I saw the height field generation take about 60% of the time it had taken prior.

Also, Mikko rebuilds and iterates over his data structures a few times more than are necessary for the purposes of maintaining a compact form in your data structure. The idea is Mikko wants you to be able to read (from a file, socket, whatever) an entire mesh in one read operation. Reorganizing things into this form takes time. Look at the differences between the height field and what Mikko calls the compact height field.

Lastly, Mikko's code has a lot of bells and whistles that are simply not applicable. And it makes keeping current with his library a real pain in the butt. Especially when you are making changes to it to add things that are WoW specific. I had to keep a txt file in the SVN repo (and in the project itself for convenience sake) that itemized the changes to make once a new R+D revision had been inserted into our project.

Edit: I think I came off a bit too critical of Mikko's code. That is not my intention. I would not be anywhere without R+D as a reference. I think the drawbacks are relatively minor and completely necessary when writing something like this in a generic way as he has done.

Anyone can check for me kalimdor_37_23 map. On following pictures the players coordinates are "Mount Hyjal,4581.5273,-2959.8936,1066.5474" and that location happening to be under the stair. and that stair is actually doesn't look good to me (the next one further is looking ok though). My nav implementation stucks everytime over there. Is this something wrong with my model importing (the other models are looking ok) or ...

pictures:
http://ostap.us/5/p1.jpg
http://ostap.us/5/p2.jpg
http://ostap.us/5/p3.jpg

the coordinates from above reported from the in-game player's position in "stuck" place.

I don't quite understand. Are you saying that you cannot get the RecastDemo app to select the top of the stairs as the player position, only the terrain underneath it?

[ostapus]

Namreeb,

i am trying to say (sorry for my english), that the lower slope of that porch is missing, however in game - there is nice slope, the in game coordinates reported by staying on that slope somehow points inside the model (as you can see on pictures). so i was asking if someone can check their generated maps/geometry mesh for this specific place.

thanks

[MaiN]

Anyone can check for me kalimdor_37_23 map. On following pictures the players coordinates are "Mount Hyjal,4581.5273,-2959.8936,1066.5474" and that location happening to be under the stair. and that stair is actually doesn't look good to me (the next one further is looking ok though). My nav implementation stucks everytime over there. Is this something wrong with my model importing (the other models are looking ok) or ...

pictures:
http://ostap.us/5/p1.jpg
http://ostap.us/5/p2.jpg
http://ostap.us/5/p3.jpg

the coordinates from above reported from the in-game player's position in "stuck" place.

http://dl.dropbox.com/u/4368377/WoW/Kalimdor_37_23.jpg
Looks fine for me.

[ostapus]

Thanks MaiN,

going to dig wmo part.

[amadmonk]

Looks like Mikko is looking into 3D nav a lot lately too, namreeb. CF Digesting Duck: Loosely Ordered Mega Navigation Grids

Even if you're not actually based off of R+D these days, it might be educational to follow his thinking. I think that this idea of smaller "tiled" meshes fits a lot better with bot design, since the unwieldiness of giant "mega" meshes is one of the biggest problems I've faced trying to incorporate pathfinding into my bots, and since smaller tiles give a lot more opportunity for dynamically recalculating a mesh when navigability changes occur. Since I don't grind outside of instances, a lot of the optimizations that go into outdoors pathfinding are less than useless for me -- they obfuscate the data without benefiting me much. So, I'm curious to see where Mikko takes this new line of thought...

[dook123]

Hopefully someone can answer this but what is the best solution to solve the size issue with the exported wow maps in R+D?

Ive used WoWMapper to export a full map, say Kalimdor_14(the map of orc starting zone all the way to orgrimmar).
I have modified R+D for usage in my project and when it tries to create the navmesh for this map it runs out of memory. I also tested this using the unmodified demo with same results.

I was thinking of generating the navmesh for each tile in this map, combining them and then saving them. Im not sure if this is a good approach or even possible...

[namreeb]

Looks like Mikko is looking into 3D nav a lot lately too, namreeb. CF Digesting Duck: Loosely Ordered Mega Navigation Grids

Even if you're not actually based off of R+D these days, it might be educational to follow his thinking. I think that this idea of smaller "tiled" meshes fits a lot better with bot design, since the unwieldiness of giant "mega" meshes is one of the biggest problems I've faced trying to incorporate pathfinding into my bots, and since smaller tiles give a lot more opportunity for dynamically recalculating a mesh when navigability changes occur. Since I don't grind outside of instances, a lot of the optimizations that go into outdoors pathfinding are less than useless for me -- they obfuscate the data without benefiting me much. So, I'm curious to see where Mikko takes this new line of thought...

You can hardly scold me for not viewing a post he made just a few hours ago! That said, I actually had already read it (though it wasn't there when I made my previous post in this thread). I follow his blog religiously. My concern for this approach, which I believe is called a 2.5D nav mesh, is that there simply would be too much data to make it practical.

Edit: Yup, I asked that question on his blog and he just responded that that is indeed 2.5D. That approach can theoretically give you workable 3d navigation. You basically stack one tile on top of the other and another one on top of that, and then figure out a way to jump from one to the other. Too be accurate, you'd have to put let's say one tile per meter. That means to encompass a building like a cathedral you'd need to mesh the same ADT a few hundred times.

Hopefully someone can answer this but what is the best solution to solve the size issue with the exported wow maps in R+D?

Ive used WoWMapper to export a full map, say Kalimdor_14(the map of orc starting zone all the way to orgrimmar).
I have modified R+D for usage in my project and when it tries to create the navmesh for this map it runs out of memory. I also tested this using the unmodified demo with same results.

I was thinking of generating the navmesh for each tile in this map, combining them and then saving them. Im not sure if this is a good approach or even possible...

First, I assume by Kalimdor_14 you actually mean Kalimdor_14_yy.adt. Secondly, R+D shouldn't be running out of memory. You've probably got your cell size too low so its being waaay too precise. And as for one tile per adt, that is how I used to do it and it worked fine.

[ostapus]

Need help again (resolved my previous issue, it was indeed WMO rotation taken/stolen from wowmapper project). Now i am looking for help with M2 placements. As i understand from wiki, M2s which should be drawn refered in MCRF chunk of ADT/MCNK but offset i've got is always 0. If i am trying to draw interior's WMO M2s based on MODD chunk , there are too much junk M2. Anyone can provide some details on WMO's doodas proper handling ?

thanks

[caytchen]

MCRF chunk of ADT/MCNK but offset i've got is always 0.

Look into the _obj files for each ADT.

[ostapus]

caytchen, can you provide another hint for me please because i am still missing interior's doodas ( i think).
modf.info.doodadSet for each wmo instance points to N doodas set being used in this wmo (found cases where # of doodas sets is less than reference, is that valid exception ?)
i am reading doodas sets in wmo root file, each set is defined by firstindex in modd file and # of entries starting from firstIndex.
next, during wmo processing i am doodas defined in doodas set[modf.info.doodadSet].
am i missing something ?

[caytchen]

caytchen, can you provide another hint for me please because i am still missing interior's doodas ( i think).
modf.info.doodadSet for each wmo instance points to N doodas set being used in this wmo (found cases where # of doodas sets is less than reference, is that valid exception ?)
i am reading doodas sets in wmo root file, each set is defined by firstindex in modd file and # of entries starting from firstIndex.
next, during wmo processing i am doodas defined in doodas set[modf.info.doodadSet].
am i missing something ?

If you're only looking for WMO doodad sets, just do it as you laid out in your post: take the doodadSet from the WMO instance info, check if you actually have an doodad set for that index (there are some cases, as you said, where doodadSet is bigger than the actual number of doodad sets you have, just ignore those cases), and then just insert all doodads in the set when you're processing the WMO instance.
Just remember that interior doodads are transformed both by their parent WMOs transformation and their own.

[dook123]

http://img189.imageshack.us/img189/1...st5attempt.jpg

Yeah, some settings changed and better results. I would like to be able to figure out the best settings possible and calculate them on the fly per map.

Any suggestions on tile size and cell size according to map size? or should the tile size and cell size be the same for all wow maps?

[ostapus]

If you're only looking for WMO doodad sets, just do it as you laid out in your post: take the doodadSet from the WMO instance info, check if you actually have an doodad set for that index (there are some cases, as you said, where doodadSet is bigger than the actual number of doodad sets you have, just ignore those cases), and then just insert all doodads in the set when you're processing the WMO instance.
Just remember that interior doodads are transformed both by their parent WMOs transformation and their own.

thanks.
doing exactly as you/me said and still missing doodas. Particular case is
WORLD\\WMO\\KALIMDOR\\OGRIMMAR\\ORCHOVELORGRIMMAR.WMO - hut on the left of orgimar front gates, kalimdor_40_29. In the game this wmo has interior (shelf, couple barrels), but it has 0 doodasSet. However if i am drawing doodas referenced in MODR chunks - those doodas are present there + bunch of junk doodas. Same story if i render all doodas from MODN chunk of wmo instance - proper ones + bunch of junk.
However, this wmo has 5 doodas sets defined, and those are correct ones.. but why doodas set # in modf is 0?


---------- Post added at 10:44 AM ---------- Previous post was at 10:43 AM ----------

http://img189.imageshack.us/img189/1...st5attempt.jpg

Yeah, some settings changed and better results. I would like to be able to figure out the best settings possible and calculate them on the fly per map.

Any suggestions on tile size and cell size according to map size? or should the tile size and cell size be the same for all wow maps?

yes, you can't dynamically change cs/ts, for each navmesh init you have to feed tiles with same cs/ts size. basically you decide once on cs and stick to it.