MMaps Redux

[Toinan67]

I totally agree with UnkleNuke, what you're doing is really amazing. I wish I could be "fan" of some MaNGOS contributors

faramir and (recently) qsa FTW. Huge thanks.

[KiriX]

What is this:

diff --git a/src/shared/vmap/MapTree.cpp b/src/shared/vmap/MapTree.cpp
index 5e34061..8ea449f 100644
--- a/src/shared/vmap/MapTree.cpp
+++ b/src/shared/vmap/MapTree.cpp
@@ -386,7 +386,7 @@ namespace VMAP
#ifdef VMAP_DEBUG
                        if (referencedVal > iNTreeValues)
                        {
-                            [color="DarkGreen"]DEBUG_LOG("invalid tree element! (%u/%u)", referencedVal, iNTreeValues);[/color]
+                            [color="Red"]DEBUG_LOG("invalid tree element! (%u/%u)", referencedVal, iNTreeValues);[b][u]dd42b44[/u][/b][/color]
                            continue;
                        }
#endif

Typo? =)

[KiriX]

Some testers say that after latest commits too much memory leak...

[Toinan67]

Some testers say that after latest commits too much memory leak...

Your players see the mem leak? x)

[Konctantin]

Your players see the mem leak? x)

As if to debug

Some testers say that after latest commits too much memory leak...

is not the players

[KiriX]

Your players see the mem leak? x)

I didn't say anything about players. I said about testers who use this patch at his server...

[FeRkEl]

jeah but players are in some case the testers, i wondered a short time too :-)

how can u find out about mem leaks?

[DaViper]

jeah but players are in some case the testers, i wondered a short time too :-)

how can u find out about mem leaks?

I don't know yet on Windows or Linux but on the Mac they have a tool just for that, plus it's free.

[Toinan67]

I didn't say anything about players. I said about testers who use this patch at his server...

Ok ! Usually when people talk about "testers" it's players, so I had some troubles understanding how players could see mem leaks oO

[Unkle Nuke]

It's easy! You just look for puddles on the ground with lots of ones and zeroes floating around in them, but I think you need Gnomish Engineering to use the special goggles for spotting them

[qsa]

Another wall of text, that about 4 users will read. Hey! my pleasure guys.

Below attached another patch which continues my work on the subject.

• * Smooth path generation from my previous patch. Just read post #333.
  * Silly crash in generator at case of slightly invalid input. Happens when using any of the "--" options without its parameters.
  * Store our point path in Path<> class instead of that flat array. This class exist for ages and provides pretty much everything we need, making some things much simpler and intuitive.
  * Fixing and using Unit::SendMonsterMoveByPath() thanks to TOM_RUS and his detailed info on the structure.
  

This allows us to send the entire path to the client in single packet in HomeMovementGenerator making the code there much, much simplier and movement smoother. Also used to send _partial_ path in TargetedMovementGenerator when we have long paths generated.

I won't make this wall of text even longer, check the code or try it ingame.

• * Some minor, random changes ...
  

patched against 1a564e68647a39 :: http://pastie.org/1147846

About memory leaks : older version may have some, even tho I can't point at one.

This one, I actually checked. There are no related to pathfinding. Atleast not for the common thing I checked.

I did found some other things is anyone interested.

there's memory leak in Aura::HandleAddModifier() and some read/write violations on loading of WMOAreaTableEntry.

Here's partial log : http://pastie.org/1147043

generated by edu version of purify. (sorry, no testing environment with valgrind at the moment).

What I got by making my pathfinding test, so I guess that HandleAddModifier, is nasty one.

Take care.

[faramir118]

Made a few revisions to qsa's first contribution, please check them over and give me some feedback.

In the meantime I'll work on adding the new stuff!

[Curious]

Another wall of text, that about 4 users will read. Hey! my pleasure guys.

The number of thanks make you wrong And be aware that your work is much appreciated. As said before this will be a epic commit (if it ever make it to master).

@ faramir : As for now what is still to be done ? pathfinding in liquid ? mob who are allowed to walk/swin in specific area (lava/water....) ?

[Toinan67]

Yes, imagine a crowd of fans screaming your names. That's what the "thanks" are

[vladex]

@Courious, just read the faramir's first post , there is a log of what needs to be done and what is already done.

[TOM_RUS]

• * Fixing and using Unit::SendMonsterMoveByPath() thanks to TOM_RUS and his detailed info on the structure.
  

According to http://mywowtools.googlecode.com/svn/trunk/WowTools/src/WoWPacketViewer/Parsers/MonsterMoveParser.cs Unit::SendMonsterMoveByPath() should look like this, or you will broke taxi fly paths:

   if(flags & SplineFlags(SPLINEFLAG_FLYING | SPLINEFLAG_CATMULLROM))
   {
       for(uint32 i = start; i < end; ++i)
       {
           data << float(path[i].x);
           data << float(path[i].y);
           data << float(path[i].z);
       }
   }
   else
   {
       // destination
       data << path[end-1].x;
       data << path[end-1].y;
       data << path[end-1].z;

       // all other points are relative
       float mid_X = (path[start].x + path[end-1].x ) * 0.5f;
       float mid_Y = (path[start].y + path[end-1].y ) * 0.5f;
       float mid_Z = (path[start].z + path[end-1].z ) * 0.5f;

       for(uint32 i = start; i < end-1; ++i)
           data.appendPackXYZ(mid_X - path[i].x, mid_Y - path[i].y, mid_Z - path[i].z);
   }

[Toinan67]

qsa works too much! -> http://pastie.org/pastes/1147846

[qsa]

TOM_RUS : thanks once again. I wrongly assumed they are the same without checking. Patch updated in post #351.

faramir118: Sorry for that sufix->suffix typo.

in 0d8929c64 :

I think that change around line 315 , setting PATHFIND_INCOMPLETE is redundant, we are checking it in PathInfo::updateNextPosition() again. Knowing it early won't give us anything, since we move along point-path and not poly-path. While having less set-points makes things easier to debug.

Around Line 399, checking getTileAndPolyByRef() is redundant. It is already checked in getPathPolyByPosition(). If there's invalid poly, startPoly or endPoly is already 0. So, I dont think we need that hulk (-370,22 +382,33).

I may be wrong about those two. Rest looks good.

Toinan67: I'm not into that, sorry. I didn't meant it to sound like it turned out to be.

[Toinan67]

Sorry of what? I didn't get it.

Don't be sorry of anything, we should all be thankful to you and faramir for this amazing work. You are one of the reasons why I found this project so great.

However, I have a question (maybe a bit offtopic). Currently I don't understand anything to this "mmaps" thing (even if I know it's awesome ), but I'd like to have a few explanations about it : can someone give me a link or something that could help?

[Curious]

@Courious, just read the faramir's first post , there is a log of what needs to be done and what is already done.

Yeah...sry. Used to watch this thread almost avery days make me forget to check the main post.

@faramir : how did you send the movement to creature before sending the whole path ? you were calculating the next point to go at evry clock cycle ?

About nix build someone was working on that, and i thought it had finished.... Did changes make his work useless ?

@Toinan : i think the best place to start would be recast if you get recast right, you'll have the base to understand how it is applied to MaNGOS.

[vladex]

@Toinan : 2 words, movement maps .

@Qsa and @faramir thanks to both !! this is amazing .

[faramir118]

I think that change around line 315 , setting PATHFIND_INCOMPLETE is redundant, we are checking it in PathInfo::updateNextPosition() again.

We can know the path type using just the poly path... it can go wherever, just makes more sense (to me) to update type as soon as the path has changed.

Also, I think setting type should be this:

if (polyPath.lastPoly == endPoly)
   pathType = PATHFIND_NORMAL;     // path is complete
else if (polyPath.Length == MAX_PATH_LENGTH || queriedNodes == MESH_MAX_NODES)
   pathType = PATHFIND_INCOMPLETE; // path is assumed to be incomplete
else
   pathType = PATHFIND_NOPATH;     // path doesn't reach dest, search didn't exeed limits => definite fail

Without knowing if the A* open set reached MESH_MAX_NODES limit, we can't determine for sure if there is no path.

However, I don't think it's is possible without some modifications to detour.

Around Line 399, checking getTileAndPolyByRef() is redundant. It is already checked in getPathPolyByPosition().

Nice find!

If we ever handle runtime navmesh modification, we will already be making sure we're not traversing parts of the mesh that have changed.

We should also overload isPointInPolyBounds() so that we re-use the tile and poly from getPathPolyByPosition().

re: SendMonsterMoveByPath

You or someone should submit this as a patch separately. Probably need to come up with a better/cleaner way to handle movespeed and travel time calculation though.

[qsa]

We can know the path type using just the poly path... it can go wherever, just makes more sense (to me) to update type as soon as the path has changed.

Also, I think setting type should be this:

...

Without knowing if the A* open set reached MESH_MAX_NODES limit, we can't determine for sure if there is no path.

However, I don't think it's is possible without some modifications to detour.

It's exactly the check I made after building point-path in the new patch. Actually, when I think about it... It doesn't matter which check we keep, after poly-path build or point-path. Simply since if there's poly-path, there must be point path.

It sounds logical, but we have to make sure findStraightPath/findSmoothPath cannot fail given valid poly-path. If it can, keeping the check after point-path is build is a must, making one after poly-path totally redundant.

About MESH_MAX_NODES limit: I don't think we need to. As documentation of all those functions states, if it fails for some reason to find full path, it will return the closest point to destination.

I think we need to think more about those definitions and how we should processed in every case. For example, if we conclude there is no possible path at all, should we move at all? maybe come as close as we can and try again? things like that.

Nice find!

If we ever handle runtime navmesh modification, we will already be making sure we're not traversing parts of the mesh that have changed.

I don't think we should ever change the meshes.

Just a thought on mesh-changing (totally unrelated to current subject): We "need" it for dynamic objects, right?

I was thinking more in direction of generating the maps with those objects in the first place and marking those polygons. Then, when we generating the filter for our path, adding/removing those flagged polygons, just like with other marked polygons ( water, etc ). Flag can be something as complicated as including specific guid's of objects we want to include depending on their current visibility status.

Same goes for vmaps.

But as I see it, it is pretty far away from us no offense. Right now polygon status cannot change, making old poly-references valid.

We should also overload isPointInPolyBounds() so that we re-use the tile and poly from getPathPolyByPosition().

Sure, why not, we can pass them into isPointInPolyBounds() to clean up the code abit and save some getTileAndPolyByRef() calls, even tho they are trivial.

Pretty good idea. I'll change that next patch.

re: SendMonsterMoveByPath

... Probably need to come up with a better/cleaner way to handle movespeed and travel time calculation though.

We can always add function into Path<> class to calculate it, given speed.

Will save us 2 lines at call

Maybe we can integrate all this path system into DestinationHolder class. Instead of patching it into every MovementGenerator. Just a thought.

Toinan67: I have no idea what exactly you are asking for, general idea how it works, or how our implementations works or ...

Here's some general info to get some idea what it is all about.

http://www.ai-blog.net/archives/000152.html

You can search/ask for more once you know what you know what exactly you like to know about.

[faramir118]

About MESH_MAX_NODES limit: I don't think we need to. As documentation of all those functions states, if it fails for some reason to find full path, it will return the closest point to destination.

I think we need to think more about those definitions and how we should processed in every case. For example, if we conclude there is no possible path at all, should we move at all? maybe come as close as we can and try again? things like that.

This touches on another subject: The aggro logic will need to be able to create paths, select a complete one, then store it where the movement generator can access it:

• * Store the path in Unit class (easy way)
  * Store the path in a PathPool class
  Creatures could ask the PathPool for a path to their target.
  The PathPool could check to see if a path has already been found which has similar start and end locations, modify it with prefix/suffix heuristics, and return it.
  If no suitable path exists, PathPool just builds one from scratch.
  This would work very efficiently in a lot of cases - in most instances monsters are in a tight group (similar start position) going toward the tank (exact same end position).
  

I don't think we should ever change the meshes.

Just a thought on mesh-changing (totally unrelated to current subject): We "need" it for dynamic objects, right?

I was thinking more in direction of generating the maps with those objects in the first place and marking those polygons. Then, when we generating the filter for our path, adding/removing those flagged polygons, just like with other marked polygons ( water, etc ). Flag can be something as complicated as including specific guid's of objects we want to include depending on their current visibility status.

Same goes for vmaps.

I had come to the same conclusion, but wanted to leave options open if we can't solve this issue at mmap generation:

How do you make it so that recast doesn't see a door as an immutable obstacle? Perhaps flag all triangles that it touches, then remove the door?

Other cases will be simple, like the bridge in Gundrak - just flag the walkable surfaces like normal.

And currently there are only 6 bits of area flags to work with (for the input mesh). We can safely increase this, generator only uses 40mB on average.

[qsa]

This touches on another subject: The aggro logic will need to be able to create paths, select a complete one, then store it where the movement generator can access it:

• * Store the path in Unit class (easy way)
  * Store the path in a PathPool class
  Creatures could ask the PathPool for a path to their target.
  The PathPool could check to see if a path has already been found which has similar start and end locations, modify it with prefix/suffix heuristics, and return it.
  If no suitable path exists, PathPool just builds one from scratch.
  This would work very efficiently in a lot of cases - in most instances monsters are in a tight group (similar start position) going toward the tank (exact same end position).

We can try something like that. There are two options as I can think of right now.

First is for creature or search for other close-by creatures and adopt their paths with needed adjustments. This is pretty much what you were talking about in first bulletin, if I understand correctly.

2nd one, is to store paths at grid ( or something similar ). store them at start location.

Then when creature gets to some coordinate, it can query the "location" if it "knows" the way to XYZ.

I don't sure I understand your PathPool idea and how it is going to help us. If it is something like table of (from: map, xyz to: xyz, path) it is terrible idea. It is almost like pre-making path grid. Maybe we can optimize it to store only last K generated paths, hoping creatures move in packs - but then we are back to first idea. Otherwise searching in that pool will take longer than generating new paths.

But before we do any of those, we need to be really sure we can actually gain anything out of it. I mean, if looking for close-by creatures takes about the same time as generating medium path - we better forget about it and focus on optimizing the path-search algo

I personalty incline towards the "get neighbor's path" solution - since it sounds like most common case. Storing path for single creature ... the next time it will use it only maybe after respawn and that's too not very likely.

All above valid for long paths only, anything under ~10-poly-long shouldn't even be considered - short paths are generated about instantly.

Maybe we can wait with those ideas, just for now - since we have no idea how well, even our current, next to trivial solution, preforms under pressure.

Maybe we wont have to do anything too complicated. Complicated things => complicated bugs

I had come to the same conclusion, but wanted to leave options open if we can't solve this issue at mmap generation:

How do you make it so that recast doesn't see a door as an immutable obstacle? Perhaps flag all triangles that it touches, then remove the door?

Other cases will be simple, like the bridge in Gundrak - just flag the walkable surfaces like normal.

And currently there are only 6 bits of area flags to work with (for the input mesh). We can safely increase this, generator only uses 40mB on average.

Bits aren't the problem. Having 4~ bits for dynamics we can hash all our objects to those 16 cases. I mean, its not like we have anywhere 16 different dynamic objects along any single path. Having remote objects with same poly-marked values wont affect different paths.

About the way to generate those "special" polygons in the first place : I don't understand well enough how the generation works ( yet ), so I rather not say something stupid/impractical. But it sounds like something that can be done.

On a bit different subject: do you think we should implement pathfinding into WaypointM ovementGenerator too?

It can sure make making those database path much simpler and shorter, but ...

Sorry for "bit long" post, but the better things are planed, the easier it is to make them happen.