Building the NavMesh out of .adt's

[Bananenbrot]

Hi there, hope you still know me... quite some time since my last post.

I lately was (actually am) busy with my exam and stuff, however, I got my navmesh project 'finished' in a manner, that I have a good starting point for some real bot programming. So only a post for showing some results, maybe I will add something like 'what steps to take' later, but I think there are also plenty enough (sophisticated) posts about that topic already.


I initially wanted to settle the whole application to QT for better GUI creation (too lazy to write a DirectX/OpenGL library myself :P), already implemented signal/slot system and for taking advantage of the Q... C++-library.

That forced me to get into the OpenGL-API, which was for my understanding... well, very differently from DirectX.

By the way, I got to know of some sort of C++ SDL lib: Simple and Fast Multimedia Library (SFML), which I would choose the next time for building OpenGL-apps.

What actually took the most time was that I had to get a goot BVH-Tree implementation, both for object-clicking and later for using in the recast-algo. I tested about 5 (zillion) different ways to build the hierarchy, and read some articles on GD.net and white papers... BVH, BSP, Octree, ..., very interesting stuff, but my project hasn't really gained any progress of it :P
Well, after I realized, that the recast way of doing it (array with skip-branch-values) is to be favored instead of an OOP way with virtual functions ( :roll: ) , I played around with it a bit; how to arrange the tree nodes to fit them into the whole concept, ...

When I had the BVH-tree running I was really relieved^^ The remaining steps where done in the last 4 weeks:

- enable clicking/object selection, which was simple with BVH-tree and a good Ray-AABB intersection algo (maybe some sort of overkill ^^)
- implement recast algo, the ray implementation came in handy here
- enable 'SceneObject'-deletion
- enable mesh-selection/-deletion
- (jump links, teleports, doors)
- save mesh

When I wanted to start implementing editing jump links, I realized, that it would be totally overkill for my current bot framework (which is... a pile of dirt), so I deferred it for later improvements, when I really have the need of an accurate navmesh.
There were (are) some minor problems:

- the WMO liquid parsing is still not correct
- water is handled sloppy: simple removed RC_WALKABLE flag in each cell -> border applies also to 'shore' areas
- because SW generated 71k verts with 1/6 cellsize, some mesh members had to be changed from unsigned short to unsigned int
- good old displaylists didn't allow me to apply some kind of global alpha for the wow mesh (actually wanted to fade in and out the mesh with the mouse wheel), I tried with an own simple vertex shader, but the z-Ordering got in my way

The mesh has to be 'compiled' (I alredy had the term 'build NavMesh' in use before I dug into the dt-stuff) into a dtNavMesh before saving, maybe I add a pathfind-testing tool to it later for a visible purpose of that button. There will be a Meshes-folder generated in the application directory, where all meshes will be saved under their .adt name, with .rnm (Recast Nav Mesh) ending, for example Azeroth_30_48.rnm.

The application is by far not perfect^^ Unfortunately, if any of the 8 adjacent .adt's doesn't exist, you'll get a nice MessageBox. I tested it only for few .adt's in Eastern Kingdoms, some simple in Northrend (don't know what happens to phasing right now) and in Kalimdor. You might try some in Outlands, but I honestly didn't check many of all those .adt's out there.
I built a whole editor around it, because I wanted to be able to edit and... optimize^^ the generated navMesh: Notice the patches under/in trees, some unnecessary roof meshes, the whole big area under SW...
Navigating is simply stolen from RecastDemo, I liked the smoothed moving :P, that is, move with wasd and RMB, speed up with shift, go up and down with space and x.
The only time when you may edit the input wow mesh, is when you extracted it. you'll notice this look'n'feel thingy bb under your cursor, click to pin the box and press delete for deletion.
Then you'll build the mesh; prior to that you may adjust your settings under the 'recast settings' tab. The values for cellsize and cellheight are meant reciprocal (value = 3, then cs = 1/3.0f), some other values are actually divided by 10, i was simply to lazy to add slots for adjusting the string representations of the values.
After building, you can delete one or more polygons by holding ctrl while selecting, you may even select all connected polygons by holding shift. Toggle visibility of the wow mesh with the wheelbutton of your mouse.

I was not too concerned about performance, however I implemented simple, no need to be synchronized, multi-threading based on physical cores in the recast algo. Each core will be told to generate the mesh for 256 / corecount mcnk tiles. With my Core2Duo E6400, I had the whole SW navmesh (center, (30,4) generated in ... 66 secs with cellsize changed to 1/6, which is a good resolution considering the mcnk sizing. There may be a lot room for improvement^^
It even takes nearly 6 seconds to generate the wow mesh for that .adt, maybe I'm doing too expensive bounds checksfor the models or something like that. Didn't get the Bounding boxes in the m2 and wmo grp files working.

After editing for example (36, 49), I could have cut down the filesize from 1,2 mb to 1 mb (woot!), I haven't yet tried for .adt's like the aforementioned 'benchmark' (30,4 to optimize.. there are many of those patches on roofs, under SW, inside walls, ...

I haven't implemented deserializing yet, but I think it will work, if the serializing code in the recast samples is correct (which I honestly believe^^).

Lastly I have to admit, even though I used some nice RAII, somewhere there are still memory leaks, but they are marginal and shouldn't be troublesome.

There are many possible ToDo's (such as learning how to implement realistic lighting ..) for later on, I will now go back to C# and rebuild/improve my bot framework :P

I hope everybody (who is on Windows) may run it without critical errors... but you will need the VC++ 10 redistributable, if you haven't already installed VS 10. Hopefully, you won't be bombed with newbish exceptions and shipping errors :/

Bin drop

To conclude, some pictures (of an older version, notice the changed GUI)





EDIT: fixed typo's

[Flowerew]

Really nice work. Also the time you invested to make it a little editor is quite honorable. I currently have no chance to test it but it looks great for a start. You should consider batch building for the navmesh, typing in > 1000 adt coords for something like EK is a little time consuming +rep to you

[Bananenbrot]

Thanks,
my first idea was to do some kind of batch building in a console application... but I ran some examples in RecastDemo and decided to do it this way for now. That was because of the reasons I already mentioned; I liked to clean up things like under SW, etc.

I of course will do batch building in a later version, when I really need all mesh tiles and have the algo fitted for my needs.

[namreeb]

We use a console app and perform a flood fill to remove the unreachable polygons.

[Bananenbrot]

you mean some kind of what I do to select the adjacent polygons?
I get the selected polygon and insert the index into a std::set. Then I have a deque with a helper class to determine, which Polys were traversed and at which neighbour index I jumped to the next to avoid endless recursion.

The main thing why I didn't want to implement that, was because I might want to insert jump links later on. Flood filling (if it's as easy as I'm doing it) would delete those jumpable polygons.

However, at the moment I don't care for any jump links so I will going with that, thanks.

EDIT: for those who care: confused std::list with std::set sry^^

[namreeb]

The solution to that is to have more than one starting point for the flood fill. The first point will take care of the vast majority of the continent, but you'll need some others. For example, Thunder Bluff will need it's own. One solution is to use the set of locations of all flight masters/transports/etc.