MoveMaps

[Gotisch]

ah really? i though it was written somewhere how to generate, anyway there is file CreaturesToCoords.py just put it in a folder and a folder called StartCoords then edit configureation (database info) and run file it wil generate StartCoords from your database

here i uploaded the ones i generated you should be able to use them: http://rapidshare.com/files/362545930/StartCoords.tar.gz

[Gotisch]

Hey, i'm having trouble to get the correct coordinates for the map/vmap data to generate the navmesh for example position in x=-9454.2724, y=72.769554,z=56,717453 is in my extracted vmaps/maps x[43.54] y[-9459.35] z[56.96]. that y and x are echanged isnt really a problem but there is still big discrepancy i mean 72 vs. 43.54 \\o/

to convert the vmap data i am currently using

Vector3 vertex = tbarray[i].vertex(j).getVector3() + pSm.getBasePosition();
convertedvertex = Vector3(-((64*533.333333333/2 + vertex.z) - 64*533.333333333),
                           -((64*533.333333333/2 + vertex.x) - 64*533.333333333),
                           vertex.y);

and the map data i dont convert at all just x/y/z

does anyone have any info on this? im not even sure where i found that conversion for vmaps anymoer

[tehavatar]

Just check the mangos+vmaps git repo, there should be some source examples you can look at.

[Gotisch]

its ok actually i think i was to asleep when i wrote that code, i just rewrote the whole coordinate conversion and now they match.

[Gotisch]

first: sorry for doublepost

second sorry for the huge images tinypic doesnt support reencoding apparently

On Topic: I have now completed my first draft of a movemap implementation. Though i went another way then the initial posters of this topic: i just let detour generate the navigation mesh. For this i used the already present Tile spationing of the gridmap and just passed data according to that to detour and let it generate the mesh. Depending on the ammount of data there is for a tile, size varies between 16kb / 1mb per tile.

You can find the code in this commit and the following 3 or 4: http://github.com/gc/mangos/commit/7941a0c0590ca9e4902b0b13e8b04c0d75a676ab

please don't post questions asking how to install things in comments on that github repo. this is development forum after all not "download and use this i will provide support" form.

This is a tile with content and size up to 1mb:

This is a tile without content and size only 16kb (and probably will never get loaded):

The general implementation is such that on loading vmaps and maps i just load the NavMesh too. And i added a method

Position getNextPositionOnPathToLocation(const float startx, const float starty, const float startz, const float endx, const float endy, const float endz);

to the Map class that will allow to get the next point to walk to in a straight line to reach the end point from the start point on the shortest correct path.

Then i added code inside TargetedMovementGeneratorMedium<T,D>::_setTargetLocation(T &owner)

To not walk to the target directly but the generated point (from pathfinding)

I know this is suboptimal solution, because it will generate the path from the beginning at every node on the way, wether the goal location changed or not. On the other hand if the target (player) moves a lot paths have to be generated anew anyway. ( i also added to settargetlocation a check wether there is currently movement and if so dont change goal, so that the path will only be generated once a node is reached. settargetlocation gets called _alot_ apparently in mangos (even if player doesnt move at all).

Anyway that is basically current setup. Here are two movies a made while testing it: http://www.youtube.com/watch?v=XNQOTJpLuuA (dunno if i am allowed to post movies to ingame content, if not please remove).

Now there are multiple problems i am facing:

• * Pathfinding across grids:
  Is not implemented at all. The current system has fallback, that if no path is found it just goes back to standard mangos way: straight to target. This is really suboptimal since its realy ugly, but unless there is valid way to generate path accross grids is the only practical way, else people could flee from mobs by just crossing from one grid to another. Any ideas on this? One thing i can think of is to increase the actual grid size further then 533² while still keeping that number for grid calculation, this would result in overlapping navmeshes, and so the problem would maybe become negligible. Also lets stay focussed here that things like long path generation in the world are very... uncommon most of the time the path to be generated will have 3-4 nodes max! Just around a corner or such. The path generated in the screenshot is imo very unrealistic, since no player will aggro a mob from that distance (outside of instance).
  * Gameobjects have holes:
  This is a problem maybe someone with more knowledge about how vmaps work can help me with. you can see it well on following image:
  
  This is naxxramas instance (the instance is actually floating in the air above an unused map) and maybe for instances only 1 navmesh should be generated, containing the main wmo. But it shows the problem, each room seems to be present in the vmap but somehow the corridors between them are missing. I have same problem with all big wmos, stormwind for example each "zone" is cut of from the other. Is there a way to get these corridor information from vmap, if yes how?
  * Some gameobjects are inside out. Mostly threes but as you can see on image above mushrooms too. Does anyone know how to identify those models in the .vmap data, so that i can reverse them?
  * Other problem you can see on that image above is huge waste of memory for generation of paths on space that is not used by anybody.Question is when should navmesh not be generated or saved? initial project checked for NPC's at that location, but imho we need to think of pets too, they shouldnt walk wrongly just because we didnt want to generate paths where npcs aren't spawned. Anyone any ideas on that?
  * Thread safety. From what i read on recast mailing list, the pathfinding itself is not thread save. Since each map in mangos is used only by 1 thread at a time this is not a problem (or is it?). only problem i can think of is instances. Currently each instance gets its own navmesh, to save memory this could be changed. On other hand, since there are doors in instances for example and one could mark door area as non walkable on navmesh while door is closed, maybe own navmesh per instance is even wanted?
  * Speed:
  I did some speed tests on a per grid basis:
  

  [21:55:46]Joined Channel: [1. General - Shattrath City]
  [21:55:46]Joined Channel: [2. Trade - City]
  [21:55:46]Joined Channel: [3. LocalDefense - Shattrath City]
  [21:55:46]Joined Channel: [4. GuildRecruitment - City]
  [21:55:56]Generating MoveMap Path for all creatures around player In range:10000.00
  [21:55:56]Found 386 Creatures.
  [21:55:56]Generated 386 pathes in 0 seconds 60835 µs
  [21:56:30]Generating MoveMap Path for all creatures around player In range:1000000.00
  [21:56:30]Found 386 Creatures.
  [21:56:30]Generated 386 pathes in 0 seconds 62467 µs
  

  
  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.
  

So if anyone could help me with ideas or code suggestions for those problems it would be greatly appreceated

[hunuza]

Your work is promising. Keep up the good work

[vladex]

Exelent work ! i hope mangos will implement it soon enough

[przemratajczak]

for me it generates always one path per creature which is stright way from creature to attacker (like on clean mangos). maybe i missed something

[vladex]

can you update it for rev 9613 or higher please ?

[Gotisch]

for me it generates always one path per creature which is stright way from creature to attacker (like on clean mangos). maybe i missed something

you need to have generated a navigation mesh for the zone you are in of course here is one for for grid 49 32 on map 0 its near the field where first defias bandits i think are in human startarea

http://rapidshare.com/files/368050038/0004932.mmap.tar.gz

location one is border of the field where defias are in human startarea, you can test nicely with the fences. location 2 is a house near lake basically first house on left if you take path out from human startarea

[przemratajczak]

that's what i thought, started to read already detour documentation

EDIT: wow. looks damn good

[darkstalker]

i still think that navigation map should be generated at runtime (probabilistic roadmap comes into mind), so you dont have to use any additional data, libraries or anything. To do that would be needed:

1. When a grid is loaded, generate N random samples of terrain using vmaps near creature spawn zones (aggro radius?), that samples are made at floor level.

2. For each of those points, find the K nearest points and test if they're in line of sight. If they are, connect them into the graph

3. when a creature moves, calculate shortest path to target using the calculated graph, if the average distance between a straight line and the path is above a treshold, move the creature by the path, otherwise move in straignt line

well, just an idea.

[faramir118]

I know this is suboptimal solution, because it will generate the path from the beginning at every node on the way, wether the goal location changed or not. On the other hand if the target (player) moves a lot paths have to be generated anew anyway.

I would store the path in the unit. When it needs to recalculate because target moved, do pathfinding from the end of the previous path, add new path on to the end of previous path, then call dtNavMesh::findStraightPath().

This should be faster, because the new path is most often going to be a very short, straight line. findStraightPath will then straighten out the path, removing any excess nodes.

Worst case would be teleporting mobs, like Arugal in Shadowfang Keep - you would lose a bit of performance, because you generate a whole new path, then findStraightPath has even more work to do.

• * Pathfinding across grids:
  Is not implemented at all.
  

Try these:

• * dtNavMesh::connectExtLinks()
  * dtNavMesh::connectIntLinks()
  

Gameobjects have holes

I don't know about maps or vmaps, but if nobody replies we can use:

• * dtNavMesh::connectExtOffMeshLinks()
  * dtNavMesh::connectIntOffMeshLinks()
  

[Gotisch]

I would store the path in the unit. When it needs to recalculate because target moved, do pathfinding from the end of the previous path, add new path on to the end of previous path, then call dtNavMesh::findStraightPath().

Yes i wouldnt know where to implement this though, should it go in creature AI? movementhandler?

Try these:

• * dtNavMesh::connectExtLinks()
  * dtNavMesh::connectIntLinks()
  

problem here remains to find those connections, although probably can just check all nodes in navmesh if they touch the border or something like that

I don't know about maps or vmaps, but if nobody replies we can use:

• * dtNavMesh::connectExtOffMeshLinks()
  * dtNavMesh::connectIntOffMeshLinks()
  

Also here remains problem how to automatically find out where such a connection should be?

I have also checked mailingliste of detour a bit more and maybe it would be better to just create one big Tiled_NavMesh then those connection between 533*533 zones would be handled automatically i think. I think autor of detour released new version just few days ago that allows easier loading of tiled meshes, so might be worth looking into.

i still think that navigation map should be generated at runtime (probabilistic roadmap comes into mind), so you dont have to use any additional data, libraries or anything. To do that would be needed:...

Well i dunno the map is 99% static it seems waste of cpu to generate a navigationmesh on the fly.

edit:

Also i found way around those insideout object like trees. I shall call it double buffering!

Instead of

Triangle t = Triangle(toconvert[0],toconvert[1],toconvert[2]);
globalTriangleArray.append(t);

or

Triangle t = Triangle(toconvert[2],toconvert[1],toconvert[0]);
globalTriangleArray.append(t);

Which lets one half or the other work, i do

Triangle t = Triangle(toconvert[2],toconvert[1],toconvert[0]);
Triangle t1 = Triangle(toconvert[0],toconvert[1],toconvert[2]);
globalTriangleArray.append(t,t1);

Which creates the doulbe of triangles. but since those are only created for navmesh generation and that only in the first step i think the impact is negligible. (or am i wrong?)

Also i added removal of all tiles in gridmap that are below water (gonna work on vmap under water now) now navmesh looks like this

http://rapidshare.com/files/368138336/recastmmaps.tar.gz

in above tar.gz are 2 files, one is recastdemo modded to load mmaps files if present in meshes folder

second more interesting is movemaps project i edited to create generator for .obj and .mmap. all code is nearly inside viewer folder, i dont even know if the rest compiles. 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.

[faramir118]

I've thought it over, and this is the best I can come up with for the pathing algorithm:

• * Create Map::findPath(source, destination), should return entire path
  * Create Map::findStraightPath(path), should pull string
  * Current path stored in TargetedMovementGeneratorMedium
  * i_DestinationHolder stores current destination node
  

So, pseudo code for what TargetedMovementGeneratorMedium<T,D>::_setTargetLocation(T &owner) would do:

if (path)
   // path exists because _setTargetLocation is being called from Update
   source = path.EndNode
   destination = target.position
   path.append( Map::findPath(source, destination) )
else
   // path does not exist, start from scratch
   source = owner.position
   destination = target.position
   path = Map::findPath(source, destination)

if(!path)
   // need to handle case where path doesn't exist

// clean up and shorten path, set destination
Map::findStraightPath(path)
i_destinationHolder.SetDestination( traveller(owner), path.StartNode )

I would really like to see this in action, I just don't have the resources to bring up a test server at the moment.

As for pathing between Tiles, a TiledNavMesh would work. I haven't looked at how the path is formed with Tile links, and I'm concerned that the link itself is used as a node in the path. This would create some very awkward paths.

For the above reason, I am favoring overlapping tiles.

This forces you to keep track of which Tile your path is for (and paves the way for one mmap per dungeons instead of one mmap per instance). You can add logic to setTargetLocation to detect when you have moved into a new mmap, and start a new path with new data.

Potential pitfalls:

• * A too-small overlap will limit the distance creatures can path. This can manifest in a few different ways:
  

1. 
   
2. * creature may not see a path to the character at all, such as when the stairs up to the character are just across the tile boundary.
   * overlap is small and players are moving fast, player might move out of overlap area before creature enters it - creature won't be able to find path to player
   

* A too-large overlap will waste resources.

Some potential distances are Aggro range, creature follow range, update interval * max player speed

In any case, I think dungeons should be one big Tile.

[faramir118]

Also i added removal of all tiles in gridmap that are below water (gonna work on vmap under water now)

Can you get the water surface polygons? It would be awesome if you could flag them (with rcPolyMesh.flags) so that we have an easy way of finding fishable water, for instance.

[Gotisch]

I've thought it over, and this is the best I can come up with for the pathing algorithm:

• * Create Map::findPath(source, destination), should return entire path
  * Create Map::findStraightPath(path), should pull string
  * Current path stored in TargetedMovementGeneratorMedium
  * i_DestinationHolder stores current destination node
  

So, pseudo code for what TargetedMovementGeneratorMedium<T,D>::_setTargetLocation(T &owner) would do:

if (path)
   // path exists because _setTargetLocation is being called from Update
   source = path.EndNode
   destination = target.position
   path.append( Map::findPath(source, destination) )
else
   // path does not exist, start from scratch
   source = owner.position
   destination = target.position
   path = Map::findPath(source, destination)

if(!path)
   // need to handle case where path doesn't exist

// clean up and shorten path, set destination
Map::findStraightPath(path)
i_destinationHolder.SetDestination( traveller(owner), path.StartNode )

I would really like to see this in action, I just don't have the resources to bring up a test server at the moment.

Yes this looks nice i will try to implement something like this when i have some time, probably only after weekend though. maybe we need to make it even more generic since HomeMovementgenerator could work of it too. atm i hacked around in it

http://github.com/gc/mangos/commit/88343b8983920a7c9c4a953fe7782ac0b4945d83

so if there was baseclass to handle all movement along navmesh would probably work better.

About seeing it in action, i have public testserver running with navmeshs enabled, if you are interested you can pm me.

As for pathing between Tiles, a TiledNavMesh would work. I haven't looked at how the path is formed with Tile links, and I'm concerned that the link itself is used as a node in the path. This would create some very awkward paths.

For the above reason, I am favoring overlapping tiles.

This forces you to keep track of which Tile your path is for (and paves the way for one mmap per dungeons instead of one mmap per instance). You can add logic to setTargetLocation to detect when you have moved into a new mmap, and start a new path with new data.

Potential pitfalls:

• * A too-small overlap will limit the distance creatures can path. This can manifest in a few different ways:
  

1. 
   
2. * creature may not see a path to the character at all, such as when the stairs up to the character are just across the tile boundary.
   * overlap is small and players are moving fast, player might move out of overlap area before creature enters it - creature won't be able to find path to player
   

* A too-large overlap will waste resources.

Some potential distances are Aggro range, creature follow range, update interval * max player speed

In any case, I think dungeons should be one big Tile.

I aggree with dungeons i think its a simple hook in MapInstance class. and overwrite the relevant functions there. Now just need to find out if detour can handle it.

I also think overlap is best way to go, although i hade huge memory increase with 50 meters overlap on each side. before it was like 1,1mb and afterwards 1.7mb but i added that double triangle thing at same time, maybe that was responsible.

Can you get the water surface polygons? It would be awesome if you could flag them (with rcPolyMesh.flags) so that we have an easy way of finding fishable water, for instance.

Well i can only get water from the gridmap. Vmap don't save any water information sadly i see i the source its on a sort of todolist. and for the gridmap im doing sort of a bruteforce approach querying height/waterlevel every 2 meters. but marking triangles should be possible.

[wow4]

Here is Gotisch's work in a patch file I made for MaNGOS rev.9619

http://filebeam.com/c9592e7f60ad896da960bced37c3646a

It does build: Build complete: 13 Projects succeeded, 0 Projects failed, 0 Projects skipped - Visual Studio x64 Win64 Command Prompt

But i have not had the time to test it running yet, so feel free to try it and post what happens

edit: Ok I just tested it works! :cool: this is Epic... no.. Legendary! lol

[vladex]

NIce thanks wow4

[vladex]

i actually see no diference ... after i compiled with the patch +other addons , maybie the others disabled it ? or overwritten it ?

[ilija]

Guys , could you please explain what this exactly is ?(i think it is improved vmaps) and how to use it?

[wow4]

i actually see no diference ... after i compiled with the patch +other addons , maybie the others disabled it ? or overwritten it ?

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!

[vladex]

thanks for the help, are there any ways to generate more mmaps ? last time i generated .obj files but not mmaps

[wow4]

thanks for the help, are there any ways to generate more mmaps ? last time i generated .obj files but not mmaps

I was working on doing that last night but I keep getting errors idk whats going wrong if I find what I am doing wrong before someone else I will post on how to make them step by step

[vladex]

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