MoveMaps

[wow4]

i think you can post some ideas to get me into this, i will try and find out how it works

everything I have found on how to do this is in this thread I downloaded stuff from the first post and was messing with it don't know if that the right thing I need?

[Gotisch]

...to generate the mmaps too you have to comment out the

return true;

after

debugGenerateObjFile();

and you can comment out debug blabla if you just want to generate the mmap files.

the message needs to have at least 10 chars

[Woweur]

This is generation for all creatures inside a grid to player position so also pathes of different length. (range dont matter it just gets all creatures in grid that way) Is this good/bad? i feel that 400 pathes in 60ms is acceptable for at least small servers ~500 players or such since not everyone will aggro and run away from mob at same time

I think it's better to handle a calcule in thread for that.

[ilija]

1.after you use the patch

2.Make a folder called mmaps in your mangos folder.

3.Download this mmap http://rapidshare.com/files/36805003...32.mmap.tar.gz Gotisch made.

4.If you are on windows you will need something like winrar to open the .tar.gz than you should see a file named 0004932.mmap in it

5.put the map file in the folder start mangos go to the fishing trainer by goldshire than type .damage 1 on him or any other npc in that area than jump over a fence the npc will go around to get to you!

If you say it will go around it , so you can just jump over and he never get you , lol

[69straight]

How is this project faring? I find it very intriguing, I would love to see this eventually fully integrated and supported by MaNGOS/MaNGOS Dev Team, Keep up the good work, and I myself (even though I'm not known) will do what I can do if I progress further I will post here

[faramir118]

First, I'm just going to suggest we move this to a new thread. The original topic is a few years old, and I feel we've departed from the original spirit, seeing as Gotisch is using recast+detour. Would be easier to explain what this does, what we want it to do, track progress on a todo list, and keep a link to current versions of code and/or mmaps.

Anyway, on to constructive discussion:

for the gridmap im doing sort of a bruteforce approach querying height/waterlevel every 2 meters.

You'll have to check to make sure you're only removing the ground that's under the water, and not ground that is on a lower floor. Take dalaran for instance: there is water on the top floor, but walkable floors below it. And way below that (but maybe not in same grid?) there's the surface of northrend.

If you say it will go around it , so you can just jump over and he never get you , lol

The implementation of the pathfinding using detour is more important - if it's done poorly, there won't be a point to even create navmeshes with recast because people won't want slow, inefficient, or crappy pathfinding!

Don't worry though, there are ways to fix it. We just have to tweak recast navmesh creation parameters.

• * agent step height
  Defines the height of objects that agents are allowed to step up to. This will be tricky to get right, should be about the same as player jump height
  * navmesh height above the terrain mesh
  Would allow mobs to ignore low obstacles like rocks, logs, fences, etc.
  Short doorways might become impassable, would have to tweak agent height to compensate.
  On the other hand, it might make agents ignore objects that they shouldn't
  

I think it's better to handle a calcule in thread for that.

I vote no, until MaNGOS has a built in thread pool. Read on if you want to know why.

There are two ways to handle multi threading:

• * block on a synchronized object until the pathfinding thread signals
  

1. 
   
2. * makes debugging harder
   A crash in one thread may be caused by another thread, which is hard to track down
   * offers no performance benefit
   You suspend one thread and start another. This takes just as long as if you had done it in the current thread (technically it can take longer because of thread priority scheduling, context changes, etc)
   

* defining a callback function for the pathfinding thread to call

• * makes debugging harder
  Same as above
  * only offers performance benefits if you have a multiprocessor system, and only if you execute the callback function on a thread other than the pathfinding thread (unless all threads are part of the thread pool)
  * complicates code
  it is hard to correctly implement (preventing concurrent access, avoiding/detecting deadlock and race conditions, etc)
  

[OneB1t]

http://github.com/gc/mangos/commits/master

[przemratajczak]

I assume mmap assembler is reserved for author ;-) ?

[faramir118]

I don't have a lot of time at the moment, so this will be relatively short.

All the work I did was to optimize the pathfinding.

My goal was to reuse a path as often as we could, so that we don't have to generate them that often. See Map::UpdatePath for the specifics. There should be plenty of comments.

First, the code.

This is a patch for mangos commit 9638. (also works for 9648)

You need the mmap created by Gotisch. Easiest place to test it is at the house near this guy.

My tests were thorough, but I can't promise that this is stable.

Next, the results. If these videos look choppy, please don't worry about it being the pathfinding. I've got 2 instances of WoW, MySQL, mangos, 2 instances of visual studio, camtasia capture, and some other crap open. On a laptop.

(At the time of posting, the videos are still being processed by youtube)

• *
  
  Short video where you can see the pathfinding in action.
  *
  
  A little more involved, just showing off.
  

A good start, but there's more to be done:

• * Testing!
  * HomeMovementGenerator seems to pause for a second on some of the path vertices, definitely needs looked at.
  * Could really do with some memory management. I'm really not that good at dynamic memory, or C++ for that matter.
  * More abstraction. I feel that we can get it to the point where a MovementGenerator makes one call to get the next destination's x,y,z
  * A few comments in the code have some ideas, just can't remember them.
  * Other stuff
  

[ilija]

Does this patch use alot of cpu usage?

[frostzhenya]

People prompt please!!! How to generate these charts mmaps (if it is possible describe in Russian)

[Gotisch]

My goal was to reuse a path as often as we could, so that we don't have to generate them that often. See Map::UpdatePath for the specifics. There should be plenty of comments.

The recast docs say this is a very cpu intensive operation and that they should be buffered if possible:

startPoly = navMesh->findNearestPoly(startPos, mPolyPickingExtents, mPathFilter, 0);
endPoly = navMesh->findNearestPoly(endPos, mPolyPickingExtents, mPathFilter, 0);

if we already use a path object maybe we can just save those two polygons in it too.

A good start, but there's more to be done:

• * Testing!
  * HomeMovementGenerator seems to pause for a second on some of the path vertices, definitely needs looked at.
  * Could really do with some memory management. I'm really not that good at dynamic memory, or C++ for that matter.
  * More abstraction. I feel that we can get it to the point where a MovementGenerator makes one call to get the next destination's x,y,z
  * A few comments in the code have some ideas, just can't remember them.
  * Other stuff
  

if i can add to this todo list:

• * Navmesh:
  Check if its possible to use TileMesh. i.e. Can we use just one dtnavmesh object and make "533*533" tiles, from which for each path calculation we load 3 adjancent tiles into memory.
  tbh. i asked author of tool here about tilesize, but i dont really understand his answer: http://groups.google.com/group/recastnavigation/browse_thread/thread/14c338dd04285250
  if its possible to have an unlimited number of tiles, but only a certain number of tiles loaded into the navmesh, maybe we should use tiled navmesh.
  problem is, how cpu intensive is loading tiles into the navmesh?
  Solving this will solve all cross-tile pathfinding problems.
  

also i agree about moving to new thread.

[Darkhunter]

what all do I need for it ? and can somebody make patch for MaNGOS rev. 9608 ?

[przemratajczak]

thanks for sharing mmaps assembler, but GridMapManager.h/GridMapManager.cpp is missing in uploaded source

[faramir118]

Does this patch use alot of cpu usage?

At this point, yes. Granted that someone is playing in the one small area that has the navmesh.

We're still working on it, so there will be a lot of performance improvements to come.

The recast docs say...

What docs are you talking about? All I have been able to find is the comments in the headers, and a few comments in the code.

this is a very cpu intensive operation and that they should be buffered if possible

This creates a problem, because I was using findNearestPoly to determine whether or not they had left the previously-calculated path - buffering ruins that.

I can work on finding a less-expensive way, but I think it will require storing a few additional things in the PathInfo. Once we settle on something that is fast, we'll definitely need to optimize memory usage.

Right now, our memory usage for PathInfo:

• * 204 bytes for path (208 on x64)
  * 4 bytes for path length
  * 4 bytes for current index
  * 12 bytes for positions (start, end, next dest)
  * 4 bytes for navMesh pointer (8 on x64)
  

TODO:

• * convert to dynamic memory allocation for the path, we'll save a lot of space. I'm terrible at this, will need some help
  * convert path length to unsigned char, that's still plenty long
  * get rid of current index, it's not being used right now
  

we should use tiled navmesh

Yes, we should

I need to read the code to fully understand what he was saying in his response. From just his response, this is what I understand:

larger tiles => more polygons per tile => need more space in polyRef for poly id number => less space available in polyRef for tile id number => fewer possible tiles (because you reduce the number of available ID numbers)

or:

smaller tiles => less polygons per tile => need less space in polyRef for poly id number => more space available in polyRef for tile id number => more possible tiles

I don't know how his code handles this, will have to look at it.

[ilija]

I want to help with this project only im at learning fase of c++ (damn those pointers shit (x->y = *x.y , why should you use that damn , why just not x f; and then x.f , really dont understand that part , explain if you can but that is offtopic)

[xeross155]

I want to help with this project only im at learning fase of c++ (damn those pointers shit (x->y = *x.y , why should you use that damn , why just not x f; and then x.f , really dont understand that part , explain if you can but that is offtopic)

Just keep an eye on the pointers thread (Dunno if you created that), in the meantime try to stay on-topic.

This indeed seems like a promising new direction for MoveMaps, however I so suggest you make a new thread if you haven't done so yet.

[lecails]

Is there a sql file ?

ERROR:Error in creature_template_addon table, probably sql file format was updated (there should be 9 fields in sql).

I have 7 fields what is the two field added ?

[faramir118]

Sorry, another long post...

Check if its possible to use TileMesh. i.e. Can we use just one dtnavmesh object and make "533*533" tiles, from which for each path calculation we load 3 adjancent tiles into memory..

I think I figured it out.

Each dtPolyRef is 32 bits, and is broken down into three parts

• * salt: 10+ bits
  Used to determine if the mesh has been altered, as in an obstacle has been added or removed. If salt changes, you should probably recalculate your path.
  * tileID: 1+bits
  The identity number of the tile that this polygon belongs to.
  * polyID: 1+ bits
  The identity number of this polygon.
  

Now, the maps have been broken up into grids already:

• * 64x64 array, or 4096 cells
  * each grid cell is 533.333333f wide, 533.333333f deep
  

edit: read hunuza's post below, I'm bad at math and calculators

if you want to match the navmesh tiles to a map grid, then we'll need 4096 tiles, which means 2^11 bits for tileID.

This leaves 2^11 bits for polyID, allowing 4096 polygons per tile.

s = salt bit, t = tile bit, p = poly bit, spaces just make it easier to read/count (note: actual encoding might be different, I just am making an example)

ssss ssss sstt tttt tttt tppp pppp pppp
\\ 10 bits  /\\  11 bits   /\\  11 bits  /
            \\4096 tiles/  \\4096polys/

It will be interesting to see if 4096 polygons is sufficient for all tiles.

for each path calculation we load 3 adjancent tiles into memory

Since the loading and unloading of grids is already done, you would just need to add the tile loading code to what already exists for grids. Then as mangos loads grids, tiles are loaded into the navmesh for us. When (if) a grid is unloaded, mangos unloads the tile also.

problem is, how cpu intensive is loading tiles into the navmesh?

I don't think it would be terribly CPU intensive, but there would be some disk IO involved that would make it slow. It is a concern, but I don't see a way around it at the moment.

The recast docs say this is a very cpu intensive operation and that they should be buffered if possible:

I've done a bit of digging in the detour code...

• * findNearestPoly
  looks at every single polygon in the tile, and returns the nearest one even if the position isn't inside that polygon.
  waste of CPU when I only care about the polygons in the path
  'nearest' polygon is risky, for instance if player jumps off a cliff it might to return the cliff edge and not the polygon player will land on
  * findStraightPath
  gives shortest path, in coordinates
  assumes that the path is reachable from startPos and endPos
  * moveAlongPathCorridor
  gives next coordinate on the path that is reachable from startPos, as well as which polygon that coordinate is on
  returns nearest point on portal edge, so path will be longer than it needs to be
  * distancePtPolyEdgesSqr
  returns true if a point lies within a polygon (ignores up/down, so point can be above/below polygon)
  

Two ways to avoid findNearestPoly:

• * If I can get the right results from moveAlongPathCorridor, great!
  * If not, I'm prepared to write some code that uses distanctPtPolyEdgesSqr to find if the start and end polygon are on the previously-calculated path, then use findStraightPath to get the next coordinate to travel to
  

As for progress, I've just been working on abstracting the pathfinding code. A peek at my changes:

// change to class so it goes on the heap
class PathInfo;

// moved to make more abstract/convenient
PathInfo* WorldObject::GetPathTo(WorldObject* targetObject);
PathInfo* WorldObject::GetPathTo(float x, float y, float z);
void WorldObject::UpdatePath(PathInfo* path);

// easier to implement/read code
void TargetedMovementGeneratorMedium<T,D>::_setTargetLocation(T &owner)
{
   ...
   i_path = owner->UpdatePath(i_path);

   float x, y, z;
   i_path.GetNextPosition(x, y, z);
   i_destinationHolder.SetDestination(x, y, z);
   ...
}

I so suggest you make a new thread if you haven't done so yet.

Been a busy week, and my weekend will be as well. As soon as I get some free time, I'll write up something nice and make a new thread!

[faramir118]

Is there a sql file ?

No, haven't altered any sql. I can't think of any reason that we'd ever need to either!

[hunuza]

if you want to match the navmesh tiles to a map grid, then we'll need 4096 tiles, which means 2^11 bits for tileID.

This leaves 2^11 bits for polyID, allowing 4096 polygons per tile.

s = salt bit, t = tile bit, p = poly bit, spaces just make it easier to read/count (note: actual encoding might be different, I just am making an example)

ssss ssss sstt tttt tttt tppp pppp pppp
\\ 10 bits  /\\  11 bits   /\\  11 bits  /
            \\4096 tiles/  \\4096polys/

It will be interesting to see if 4096 polygons is sufficient for all tiles.

Maybe I got something wrong, but 2^11 = 2048 not 4096, so we would need 12 bits for tileId, which would leave us with 32-10-12=10 bits or 2^10=1024 polygons per tile.

[faramir118]

Oops! Must have fat-fingered my calculator.

hunuza is right, its 12 bits for tileID and 10 for polyID.

Is that better or worse than before? Seems that for most maps it wouldn't matter, but maps that have a lot of floors may have a lot of polygons?

[Gotisch]

the thing i was wondering about is if this tile limit is all tiles, or just tiles loaded into navmesh at some point. if its just the number of tiles that can be loaded at once, we can add more poligons per tile, just making sure we do not load to many tiles at once.

[Linencloth]

'nearest' polygon is risky, for instance if player jumps off a cliff it might to return the cliff edge and not the polygon player will land on

It shouldn't return the polygon which the player will land on.

The reaction of a mob needs to be determined by it's InhabitType. If it canFly(), then it should countinue chasing the player mid-air, otherwise it should suspend moving.

An other problem comes here, what should be implemented first: on offical a mob will not start evading for about 5 seconds from the moment, when there isn't any available path to the player, but it continues using spells which can reach the chased target. Creature::IsOutOfThreatArea is going to return true by Unit::isInAccessablePlaceFor, which will result in an instant target switch, or evade.

At the moment, it is only theory, but it will cause easily exploitable bugs when the pathfinding will be implemented fully.

Sorry for interrupting the brain storming, but i think it is easier to get rid of it in the development stage.

[faramir118]

...SNIP...

Sorry for interrupting the brain storming, but i think it is easier to get rid of it in the development stage.

No apologies necessary. Discussion is open to all!

The logic for grounded mobs will probably take a few tries to get right, but it seems doable at this point. Clamping them to the navMesh would be fast and easy, and we can make sure that mobs are confined to the path polygons. This would prevent them from walking up into the air or off cliff edges.

Flying mobs will be easier, there are fewer checks that need to be made. It will be interesting to see that in action though, because they'll fly towards the ground, behave like someone that's walking, and then fly back up once they've gotten around the obstacle. Who knows, it may be better to just let flying monsters continue to go through obstacles?

The cliff scenario may have been the wrong one to post

There are other scenario's that are worse, like a player being thrown into the air. There's a chance findNearestPoly returns a polygon in a room above the current floor or something, so we'll waste CPU cycles finding a path there, and then waste even more cycles when the mob realizes that the player is still in the room.

So, it's risky. And because it's CPU intensive itself, I'd like to use findNearestPoly only when we have no other way of finding out where something is on the navMesh.

And having a delay during that initial evasive period seems beyond the scope of pathfinding... sorry