Building the NavMesh out of .adt's

[Bananenbrot]

Hey,

well... I finally started to code my own bot since 3 months. I actually planned it in my short time using ppather being fascinated of it. That was when I decided to learn C#/C++ basics and to programmatically pick them up while programming the bot. It went all pretty and fine, about 3-4h a day reading tutorials, book, ... since then. Finally I got by bot running (literally) along waypoints with a for now I believe somewhat stupid function, which does not work always, but that I leave out for later^^

Interesting seems the idea to build a navmesh for me, so I got busy following the guide of dejavu11's blog (MPQNav). I know, the project is outdated (at least the code in each blog entry), but I got it working with checking the WoWDev site rebuilt by MaiN. The code in the SVN is working for wotlk by the way, refined with a console and the currently not right implemented MpqTool.
I decided to rewrite it a bit, I extracted the .adt parsing work in a single .dll (MPQExtractor), turned the coordinate system (I rather took the ingame X,Y,Z system) and gave it a different OOP structure (static ADT functions, no more *Manager classes) so that it fits more my ... taste :P As I haven't already experimented much with naming conventions, I used the leading underscore for private variables... the this.* looks simply plain ugly to me^^
The code isn't the esthetic optimum for most of you, but it's a practice for me and works in the current state, so why change it

Now the reason why I post (long prelude for that ) is that I'm stuck with what I will do next. There are many questions for now:

How can I extract the NavMesh of it?

MPQNav was intended to implement QuadTrees and test each vertex for being walkable... I might implement that too, but I don't know what to do then.

Maybe I could have them in a List and based on that run A* on them?

I don't think storing each single vertex isn't a good idea, but I don't really know how to extract them to Polygons like for example on Game/AI: Fixing Pathfinding Once and For All without "handwork".

And for now the last question is how to maybe get a vertex editor out of an XNA view similar to MPQNav's (and to mine MPQBrowser, which I think I don't need to share here, because it has similar or less functionality) to fullfill that handwork?

There are many other questions swirling around in my head, but I think based on those questions I might find the path :P

My MPQExtractor.dll: File-Upload.net - MPQExtractor.zip

EDIT:
Here are some pictures for those who are interested (Redridge):


with/without M2 bounding volumes:

[namreeb]

Take a look at this:

http://www.mmowned.com/forums/wow-me...n-process.html

You might also want to checkout how RecastAndDetour does it, here:

recastnavigation - Project Hosting on Google Code

Basically if you can store your mesh as a series of polygons (proper polygons, not limited to triangles), you can make the mesh relatively small. Our mesh for all of Azeroth is 180Mb.

[Bananenbrot]

At first thanks for your reply,

Yeah I already knew these threads and about recast (great work by the way^^).. I'm currently playing with it and looking for a good tut (just got invited at aigamedev.com). My current problem is to feed recast with the vertices in the right format... maybe it becomes clearer for me in a few hours^^
Even if I feed it with my vertices in the correct way, is recast able to find out which vertices are walkable (too precipitous)? How did you map WMO's/M2's? did you recast each single mapobject for itself and mapped it into your mesh? Maybe I simply should get my hands dirty and trying...

EDIT: looked into the .obj files of recast... If I'm correct, there are vertices prefixed with v, then followed by 3 floats not written in binary format(4 bytes per float) but in ... stringformat (don't know how to call that...). They are sperated by blanks. Each vertex is followed by 2 bytes (0x0D 0x0A <-- just figured out that it's a newline with carriage return -.-).
The second half of the .obj file is the indexlist (1 2 3 | 2 3 4 and so on), prefixed with f and blanks between them. Indices are again seperated by the 2 bytes.
Now I realize that progging a parser is easy, the proof is the pudding (dictionary ftw :P).

[berserk85]

I'm using a scene graph structure to grab all wow mesh (Scene graph - Wikipedia, the free encyclopedia) ...
When i call Map::GetMesh() i get all mesh merged and transformed ...

You should use rcMarkWalkableTriangles for slope check ...

[Bananenbrot]

I got ported my vertices into the .obj format and played around a bit with the demo tool...
Too bad that there's no file extractor so that I have to work with the source code :P
There are only few tuts for recast and detour (at least for the API) so at the moment I have some problems to make out a point from where to start...
Are the scene graphs similar to the Quadtrees on the MPQNav blog? I still haven't implemented them because I cannot imagine how it would help me right at the moment^^

Another question: Did you got your data for agent heigt/width, climb and max slope from trial and error or can I look them up anywhere, being a file or in process memory?
Currently I'm using the same settings as on the MPQNav blog, which don't seem to bad for me...

EDIT: Just found the main.cpp file (yay), I'm too impatient

EDIT2: Okay, thanks Apoc..

[Apoc]

Max walkable climb is 50deg
Unit radius is roughly .6f and unit height being roughly 2.1f. (Just use the 2.1f [which is for Taurens] to make sure you can compensate for any class. Just because gnomes are tiny little things, their collision box is only roughly 1.6f high IIRC. All units have roughly the same width. (Hell; even rabbits from what I've found)

[berserk85]

Tnx Apoc ^^ I was searching for that info ^^ ...
For the radius ... is not better set it to 0 and have a better NavMeshFit (how Mikko says) ??

@Bananenbrot :
Quadtree is a Binary space partitioning method (http://en.wikipedia.org/wiki/Binary_space_partitioning), you can use that for mesh subdivione ... Scene graph is different

http://dl.dropbox.com/u/1470350/WoWExtractor.7z this is my mesh reader ...
I use it in my project ( Astrad ) . You can use it with a simple file or with libmpq (I'm using it with libmpq).

PS:Sorry for my English

[namreeb]

If you set your radius to zero, you will get mesh polys which shouldn't be there (narrow passageways and such).

[Bananenbrot]

Thx for showing that to me
I have real problems with the cmd commands used to install libmpq (don't laugh at me -.-)
It's not the first time that I've been messing around with strange installations (wtf does ./configure?!).. maybe you know a tut for that or explain it in short here (cannot be so hard cause INSTALL says 'easy')

Anyways, seems that I'm now porting my extractor to C++ code...

[audible83]

Look at the extractor that Bersek posted. It is fast, well written and works.

[Bananenbrot]

Ok, then I use his source. Actually thought of a little practice in C++ for me :P
I got to know what ./configure does btw. Didn't heard about automake and autoconf before^^

[berserk85]

I suggest to you to use libmpq from mangos source (is win32 ported and has cmake) ...

[lanman92]

./configure is generally a Unix/Linux compiling step

[Bananenbrot]

I spent my half day at looking into Linux/GNU to figure that out^^
When I tried to ./configure, make, make install ... with MinGW and MSys, I had errors compiling ZLib because of the missing mmap .. macro? in windows (which acutally has the CreateFileMapping dunction for that). I loaded the setup.exe for win, but when I tried to ./configure libmpq, the header of zlib could not be found (configuring bzip2 went well when I figured out how to)... Currently I'm working on the C++ wrapper (if you want so) around the 0.3.0 version of libmpq included in mangos as berserk adviced. I think soon I figure out how to combine it with the extractor. As I've not much experience with these stupid named CRT functions it's a little practice for me and maybe I will write an own mpq extractor (far in the future).

A more topic related question along the way as I haven't much time spent with the recast API: can I map different vertices or triangles with values to weight water and later way textures?

[namreeb]

A more topic related question along the way as I haven't much time spent with the recast API: can I map different vertices or triangles with values to weight water and later way textures?

Not yet, no. Mikko is planning on adding this feature, however.