MMaps Redux

As continuation to my previous post.

Below attached patch that changes once again the way we store our data.

Basically, we're back having 1:1 relationship between ingame tiles and mmap tiles we extract.

The reason we moved from this design, was problem with the way some polygons were shaped. Long and thin.

Splitting tiles to subtiles solved this problem but introduced couple very unpleasant corner cases, as explained in my previous post.

Below patch tries different approach to exactly same problem. However, it uses 1:1 (ingame:mmap tiles).

Basically, it generates polygons in such a way, that they are shaped just as we want them to be, without using subtiles.

Most modifications are done to the extractor. The core is basically back to old code we used to have loading tiles.

All metrics moved to native unit sizes. This solves all truncation problems. It also makes things much clearer.

See code comments for more info.

Some other generation parameters were tweaked too. I had time to play with those, to truly understand their effect, so some of them modified to give better results.

maxSimplificationError : 2.5-3.0 gives by far the best result in preserving our geometry ( assuming ~0.5 base unit : vertex size) while removing almost all jagged edges. This greatly reduces the number of overall polygons with no side effects. Those small polies are not walkable in 99% of the cases anyway, they just slow us down.

walkableClimb: this one must be less than our agent height. We really, really don't want to allow units climbing over things their height, it just looks wrong.

tileSize: about 20yads is more or less optimal here, but we can push it up for smaller mmap sizes.

EDIT: The bigger number is, the less polygons we have. Up to some limit. But we get more and more "bad" polygons.

This can be nice thing to have as parameter. We can have different sizes for different maps. They can co-exist just fine.

Overall compared to current solution (multiple tiles):

The good:

- Solve mentioned above problematic cases.

- Allow safely using any size as cell size.

- Smaller mmap sizes -> less memory usage.

- Spiral stairs are finally solved, this time for good.

- Much simpler core code. We don't need any extra logic. Basically what we had before.

- Solves visuals at debugging tools.

- Smoother maps, almost no jagged corners.

The bad:

- We won't have compactHeightfield/ContourSet/HeightField in debug info (or atlest I haven't found a way adding those .. yet ... not a big loss)

The ugly:

- It is based on revision 4da57201204, so some useful parts that was added with multi-tile will have to be re-added. Like mmap version, etc.

- You have to extract all mmaps again

- Lots of testing needed.

They say one picture worth 100 words , so... http://i53.tinypic.com/2rot5cw.jpg http://i55.tinypic.com/1zn3j1t.jpg

This should give basic idea what it is all about.

Patch against latest (beb30c28604f11ef27cb) EDIT: http://pastie.org/1342639

Updated a patch a little bit to include some changes we need from multi-tile patch. Shouldn't have real functionality change.

Feedback is always welcome.

Go and test!

https://gist.github.com/726329

Same thing as above, but with a bit of cleanup and some of our more recent features.

edit: that cellSize comes really close to making doors impassable on the maps I've tried. Wouldn't be surprised if some are blocked.

https://gist.github.com/726329

edit: that cellSize comes really close to making doors impassable on the maps I've tried. Wouldn't be surprised if some are blocked.

I guess you meant BASE_UNIT_DIM(0.53333333f).

In order passage not to be walkable, it has to be less than 1.6y and some bad luck to be optimized out.. hm... we might actually have such places, that should be walkable. I'm 99% sure there's minimal walkable size defined in wow. Can be really nice finding it out.

We can always change BASE_UNIT_DIM to 0.333333f - but.. it will double extraction time and other parameters will have to be recalculated accordingly. Namely maxSimplificationError and walkableRadius. Since we still want to keep about the same ration of 0.5y borders, so 2*BASE_UNIT_DIM will have to be used, making actual borders even bigger. Maybe we can use 0.266666f , or something ... needs testing - but in general above applies to it too.

Not sure if it is worth it. Unless we can find some real places where passages are cut due to this metrics.

Barely walkable = good for us, since what really moves on our mesh is point, with zero radius. As long as there's connectivity - we're good, no matter how thin the passage is.

PS: thanks for merging those changes.

EDIT: I did noticed something strange, something I never seen before.

http://i51.tinypic.com/dpyclc.jpg

That screwed polygon is totally fine on polymap but something went wrong on converting to mesh.

Has no affect on pathfinding, but still annoying.

Any ideas?

Some of the doors on map 34 look like they are only 1 voxel: http://img689.imageshack.us/i/tight.png/

EDIT: I did noticed something strange, something I never seen before.

...

Has no affect on pathfinding, but still annoying.

Any ideas?

It's the detail mesh - it won't affect pathing, but it will affect movement with findSmoothPath.

You can fix it be decreasing maxSimplificationError. Experiment with that number a bit... 1.9 seems ok

Some of the doors on map 34 look like they are only 1 voxel: http://img689.imageshack.us/i/tight.png/

There's no problem with those passes. Just like I explained in previous post.

We don't care how thin they are. Just try that place in game, you'll see that the movement there is just fine.

It's the detail mesh - it won't affect pathing, but it will affect movement with findSmoothPath.

You can fix it be decreasing maxSimplificationError. Experiment with that number a bit... 1.9 seems ok

maxSimplificationError is too good to lower it.

I wasn't able to understand why they are generated by Recast.

But, I did 2nd best thing : hack-fixed them.

Add anywhere before running dtCreateNavMeshData and after meshes are merged.

   // little ugly hack to prevent unexpected polygon angles
   // TODO: find why they are generated in the first place.
       for (int k = 1; k < iv.polyMeshDetail->nverts; ++k)
       {
           float* v1 = &iv.polyMeshDetail->verts[k*3];
               float* v0 = &iv.polyMeshDetail->verts[(k-1)*3];
           if(fabsf(v1[1]- v0[1]) > 300.0f)
               v1[1] = v0[1];
       }

Will have to do for now

hey,could someone post a download link for the new hi-res mmaps please? its takeing me ages to redo them again .

Thanks.

Did some more testings and tweaking, and this is what came out.

http://pastie.org/1347195

BASE_UNIT_DIM lowered to 0.266666f. This gives us much better results. All those corners, passes and doorways are much nicer now. Came with a price, longer extraction times, but meh ... you don't switch client version too often.

Some other parameters were tweaked a little bit too.

I also added check, to prevent generating maps without any actual geometry, those flat tiles.

Saves some disc space. Their chances to be loaded on runtime are slim, but still.

Some little changes here and there, etc.

I was thinking about making BASE_UNIT_DIM parameter, something like hiResHeight we have, but then, I came to conclusion it will only create mayhem. People having different version of maps, making different reports, etc.

So, my next though, following same logic, was removing hiResHeight option altogether.

Any objections?

If no problems will be found, I'll push it soon enough.

One more though: Noticed that in some portions of the extractor code we use "int" and in others+core "uint32". Can't it cause problems? Lets say, on 64bit system int is 8 bytes, while uint32 is still 4. Can this sort of thning happen with ACE defines? it sure looks so. Do we really care?

Best regards.

Uh, this Baby gettin better than i ever dreamed off!

Thanks Dudes! :cool:

I also added check, to prevent generating maps without any actual geometry, those flat tiles.

Saves some disc space. Their chances to be loaded on runtime are slim, but still.

I didn't see this part in diff

So, my next though, following same logic, was removing hiResHeight option altogether.

Any objections?

At the very least, it should be the default. No problems removing lowRes

One more though: Noticed that in some portions of the extractor code we use "int" and in others+core "uint32". Can't it cause problems? Lets say, on 64bit system int is 8 bytes, while uint32 is still 4. Can this sort of thning happen with ACE defines? it sure looks so. Do we really care?

It shouldn't impact anything. All of the things we write to file in the extractor is read using the same type in the core (assuming extractor is run on the same arch and os as core ). If I missed something, we should fix it.

One more though: Noticed that in some portions of the extractor code we use "int" and in others+core "uint32". Can't it cause problems? Lets say, on 64bit system int is 8 bytes, while uint32 is still 4. Can this sort of thning happen with ACE defines? it sure looks so. Do we really care?

It shouldn't impact anything. All of the things we write to file in the extractor is read using the same type in the core (assuming extractor is run on the same arch and os as core ). If I missed something, we should fix it.

Hello,

I think you should use uint32, uint16, int32... everywhere like in the core. Personally I generate map, vmap... on my Win7 32bit and transfer the files to a Linux x64, and I think I am not the only one who does this.

If you don't want to include core files that define them, you can use stdint.h which also exists in Win platform by including this: http://pastebin.com/cEt9Ph7P. But then you would have to use uint32_t, int16_t...

Neo2003

I think you should use uint32, uint16, int32... everywhere like in the core.

That is problematic, because Recast and Detour would need a lot of modifications

Pushed new tile format, some additional changes, cleanup.

You will have to extract all maps fresh. This time it will take longer.

So, it can be good idea, if you have multi-core systems, to parallelize things by simply extracting different maps in different instances on the extractor simultaneously.

If I remember right, someone was about to make bash+batch script for us. Something nice, which detects number of CPUs and balances load of extraction accordingly. Guess I was imagining ... ehh, I'll get there one day.

I also added check, to prevent generating maps without any actual geometry, those flat tiles.

Saves some disc space. Their chances to be loaded on runtime are slim, but still.

I didn't see this part in diff

Just a little, very basic check. Around line 1021 (MapBuilder.cpp)

We may want some real logic there. Since most, if not all instance maps are filled with junk tiles.

For example, places like map 33 - two actual tiles out from ~22.

General formula can be really hard to come by, but it can be good idea. Saving us alot of time.

If we manage to check it before extracting anything.

I think you should use uint32, uint16, int32... everywhere like in the core.

That is problematic, because Recast and Detour would need a lot of modifications

Unfortunately, both of you are right. Both Faramir and Neo.

We do have to think about some solution.

Easiest, will be just converting Recast+Detour from native sizes. But, it will make future syncs, updates really painful.

But, currently I don't see any other option. Beside doing nothing, that is ...

Maybe we can suggest it for commit for Mikko's repo.

One thing I noticed today: we have like 3 different sets of definitions for things like MMAP_VERSION, MmapTileHeader, etc. Those should be in some separate file included by all involved.

So, I guess, this makes it 2 TODO items. Beside the usual testing.

Then, its time to think, what do we want next.

If I remember right, someone was about to make bash+batch script for us. Something nice, which detects number of CPUs and balances load of extraction accordingly.

I tried a Java thing, just a couple dozen lines, but there was some really weird issue.

MoveMapGen would hang at some point, so I tried to attach the VS debugger. All I got was an error:

windbg also had problems, it won't load symbols for the hung process

I was thinking more in direction of bash script that does something as simple as :

MoveMapGen 0&

MoveMapGen 1&

MoveMapGen 530&

MoveMapGen 571&

MoveMapGen --skipContinents true&

You can get reporting, distribution based on number of CPU's, etc. But this basic thing will do just fine for a start.

Compile and extract on win7 x64, now at map 585.

A question, for example, how about Jeklik on the wall at map 309, x -12289, y -1382, z 146 (ZG) ?

Thanks

A question, for example, how about Jeklik on the wall at map 309, x -12289, y -1382, z 146 (ZG) ?

What about him?

He starts in a place where there isn't a path to players.

Technically, he turns into a bat so he should fly somehow...

Brings up a point (one mentioned before) that some mobs probably should cheat, like bosses and guards.

I wouldn't say there is need for cheeting, this rather could use some advanced scripting for such bosses, like prevent Evading (caused by unreachable targets) and to add special ways to move (like flying, teleporting)

Hope to not waste your time, this one, map 571, x 4064, y 2097, z 154. Mobs here does not follow you on the gray rocks, they have no path to reach you when aggroed.

Thanks

He starts in a place where there isn't a path to players.

Technically, he turns into a bat so he should fly somehow...

Brings up a point (one mentioned before) that some mobs probably should cheat, like bosses and guards.

We most defiantly should not allow cheating by default.

Just like Schmoozerd said, script should handle this case, since obviously it is scripted event.

Script can "cheat" by using something as simple as :

target->GetMotionMaster()->MovePoint(0, x,y, z, false);

Last optional parameter allows skipping pathfinding in movement.

I was thinking to add in our "canFly" check not only check for static inhabit type, but also auras, but then, I figured, that there are no real fly auras. Only things like mounts and levitate, but they are not really related to actual pathfinding.

Jek'lik's movement is part of the scripted event. He jumps/flies down to a static point before attacking the target.

Jek'lik's movement is part of the scripted event. He jumps/flies down to a static point before attacking the target.

boss_jeklik.cpp doesn't have anything like this, I think it just falls back to typical MoveChase

We should create an 'mmap compatible' version of SD2. There are probably other corner cases like this one... it would be nice to have them fixed ahead of the time mmaps gets accepted. You know, years from now after all the testing

I really doubt that these are many cases

This is like evading evading timers, generic ideas about target selecting depending on reachability - basicly stuff that has lots of time to be taken care of!

ie the example with the bat is quite easy: this boss most likely will need a flying flag for the point when he is flying down, and that's the only thing you need to check in your code

If this flag isn't used (yet) in the script, then I am sure that someday someone will fill in a bugreport at sd2 such that it get's the needed attention

Jek'lik's movement is part of the scripted event. He jumps/flies down to a static point before attacking the target.

boss_jeklik.cpp doesn't have anything like this, I think it just falls back to typical MoveChase

We should create an 'mmap compatible' version of SD2. There are probably other corner cases like this one... it would be nice to have them fixed ahead of the time mmaps gets accepted. You know, years from now after all the testing

Of course it doesn't, whoever wrote the script just left that out. I described how he is supposed to work.

1>------ Début de la génération : Projet : shared, Configuration : Release Win32 ------
1>Extract revision
1>Le journal de génération a été enregistré à l'emplacement "file://c:\\Users\\Nemesis\\Desktop\\Emulateur Serveur en Développement\\Emulateur V 0.0.3\\Master\\win\\VC90\\shared__Win32_Release\\BuildLog.htm"
1>shared - 0 erreur(s), 0 avertissement(s)
2>------ Début de la génération : Projet : mangosd, Configuration : Release Win32 ------
2>Édition des liens en cours...
2>Detour.lib(DetourAlloc.obj) : .netmodule ou module MSIL compilé avec /GL trouvé ; redémarrage de l'édition de liens avec /LTCG ; ajoutez /LTCG à la ligne de commande de l'édition de liens pour améliorer les performances de l'Éditeur de liens
2>   Création de la bibliothèque .\\mangosd__Win32_Release\\mangosd.lib et de l'objet .\\mangosd__Win32_Release\\mangosd.exp
2>game.lib(Chat.obj) : error LNK2001: symbole externe non résolu "protected: bool __thiscall ChatHandler::HandleMmap(char *)" (?HandleMmap@ChatHandler@@IAE_NPAD@Z)
2>game.lib(Chat.obj) : error LNK2001: symbole externe non résolu "protected: bool __thiscall ChatHandler::HandleMmapTestArea(char *)" (?HandleMmapTestArea@ChatHandler@@IAE_NPAD@Z)
2>game.lib(WaypointMovementGenerator.obj) : error LNK2001: symbole externe non résolu "public: void __thiscall Unit::SendMonsterMoveByPath<struct PathNode,struct PathNode>(class Path<struct PathNode,struct PathNode> const &,unsigned int,unsigned int,enum SplineFlags,unsigned int)" (??$SendMonsterMoveByPath@UPathNode@@U1@@Unit@@QAEXABV?$Path@UPathNode@@U1@@@IIW4SplineFlags@@I@Z)
2>game.lib(PointMovementGenerator.obj) : error LNK2001: symbole externe non résolu "public: void __thiscall Unit::SendMonsterMoveByPath<struct PathNode,struct PathNode>(class Path<struct PathNode,struct PathNode> const &,unsigned int,unsigned int,enum SplineFlags,unsigned int)" (??$SendMonsterMoveByPath@UPathNode@@U1@@Unit@@QAEXABV?$Path@UPathNode@@U1@@@IIW4SplineFlags@@I@Z)
2>game.lib(TargetedMovementGenerator.obj) : error LNK2001: symbole externe non résolu "public: void __thiscall Unit::SendMonsterMoveByPath<struct PathNode,struct PathNode>(class Path<struct PathNode,struct PathNode> const &,unsigned int,unsigned int,enum SplineFlags,unsigned int)" (??$SendMonsterMoveByPath@UPathNode@@U1@@Unit@@QAEXABV?$Path@UPathNode@@U1@@@IIW4SplineFlags@@I@Z)
2>game.lib(HomeMovementGenerator.obj) : error LNK2001: symbole externe non résolu "public: void __thiscall Unit::SendMonsterMoveByPath<struct PathNode,struct PathNode>(class Path<struct PathNode,struct PathNode> const &,unsigned int,unsigned int,enum SplineFlags,unsigned int)" (??$SendMonsterMoveByPath@UPathNode@@U1@@Unit@@QAEXABV?$Path@UPathNode@@U1@@@IIW4SplineFlags@@I@Z)
2>game.lib(WaypointMovementGenerator.obj) : error LNK2001: symbole externe non résolu "public: void __thiscall Unit::SendMonsterMoveByPath<struct TaxiPathNodePtr,struct TaxiPathNodeEntry const >(class Path<struct TaxiPathNodePtr,struct TaxiPathNodeEntry const > const &,unsigned int,unsigned int,enum SplineFlags,unsigned int)" (??$SendMonsterMoveByPath@UTaxiPathNodePtr@@$$CBUTaxiPathNodeEntry@@@Unit@@QAEXABV?$Path@UTaxiPathNodePtr@@$$CBUTaxiPathNodeEntry@@@@IIW4SplineFlags@@I@Z)
2>..\\..\\bin\\Win32_Release\\mangosd.exe : fatal error LNK1120: 4 externes non résolus
2>Le journal de génération a été enregistré à l'emplacement "file://c:\\Users\\Nemesis\\Desktop\\Emulateur Serveur en Développement\\Emulateur V 0.0.3\\Master\\win\\VC90\\mangosd__Win32_Release\\BuildLog.htm"
2>mangosd - 8 erreur(s), 0 avertissement(s)
3>------ Début de la génération : Projet : script, Configuration : Release Win32 ------
3>Édition des liens en cours...
3>   Création de la bibliothèque .\\script__Win32_Release/mangosscript.lib et de l'objet .\\script__Win32_Release/mangosscript.exp
3>Incorporation du manifeste en cours...
3>Le journal de génération a été enregistré à l'emplacement "file://c:\\Users\\Nemesis\\Desktop\\Emulateur Serveur en Développement\\Emulateur V 0.0.3\\Master\\win\\VC90\\script__Win32_Release\\BuildLog.htm"
3>script - 0 erreur(s), 0 avertissement(s)
========== Génération : 2 a réussi, 1 a échoué, 9 mis à jour, 0 a été ignoré ==========