MoveMaps

[evilatwow]

that's 3000^2 pointers at the lowest = 9M ptrs = 27MB per grid w/ a 32bit arch.

Make that 9M pointers = 36 MB per grid as a 32 pointer is 4 bytes

[smellbee2008]

So how many grids can be loaded at time with 3.2.x and 1K+ ppl? +-

To understand my question, I want to know if there is good reason to not develop all-pair paths algorithm.

First it may be memory usage, so I want to know the max that can be for that type of storage(for grid: nodes^2 pointers)

second it may be problem with spawn like objects, they are collision positive too.

So what with them? Deny npcs going through(if the height difference is high enough)?

seocnd problem can be solved with another algorithm that will go through them and change pregenerated all-pair paths : )

but second problem is problem also for A* because it take path from loaded movemaps which does not contain spawnlike objects

[jolan]

@ evilatwow : you are right , is miscalculated it .

@smellbee2008 : I dont know how many grids are loaded in this case for a real server but the worst case is every grids is loaded :-)

spawned GOs are not handled ATM. perhaps later ...

[aming51]

I think the open zones system in mangos need have a change. For example,the around zones onlyl will be active when the player is moving nearby in order to reduce the usage of the CPU and better performance. Once the player is far away from the mobs, mobs will be locked at the moment when the zone where it stand is non-active because the player is moving too far away. This can explain why when other player come across this zone, the mobs will suddenly move to one position(attacking the last player) or go back position.

There are many cases in the movemap system that the mob need to across server zones(or portals) to attack player. We can't accept the mobs finding the path and nerver come back again because the zone it moved to is too far away from the player to be active. So the mob is just locked and nerver come back. This is not the pathfinding system wanted. The zone system needs to upgrade too.

[smellbee2008]

I think the open zones system in mangos need have a change. For example,the around zones onlyl will be active when the player is moving nearby in order to reduce the usage of the CPU and better performance. Once the player is far away from the mobs, mobs will be locked at the moment when the zone where it stand is non-active because the player is moving too far away. This can explain why when other player come across this zone, the mobs will suddenly move to one position(attacking the last player) or go back position.

There are many cases in the movemap system that the mob need to across server zones(or portals) to attack player. We can't accept the mobs finding the path and nerver come back again because the zone it moved to is too far away from the player to be active. So the mob is just locked and nerver come back. This is not the pathfinding system wanted. The zone system needs to upgrade too.

In Trinity, there is a function setActive, solve all that you mentioned, I think mangos should implement it as well

[evilatwow]

I think mangos should implement it as well

Actually I think MaNGOS has that too for quite some time. I remember a post saying that somewhere, where Vladimir even added something like "use it when it is necessary, not for every rabit in the game" :lol:

[caeruleaus]

yes, there is a function to set grids active when there isn't a player in it. The only reason grids aren't always active is because that would be ridiculously cpu intensive. What really needs to be implemented is a way to calculate creature movement in non-active grids and be able to figure out where the creature will be when someone does happen to move near it.

[aming51]

hey, Jolan, any good news about MoveMaps Project? Can you send some pictures here? We will get most excited. :lol:

http://github.com/jolan/MoveMaps/commits/master

It seems this site has not been updated recently. So does it mean the this projcect has finished and can be applyed in Mangos now(just need to optimize the route calculation time< 2ms) ? :huh:

[jolan]

unfortunately, I did not do anything on mmaps lately due to real-life stuff (changed apartment, holidays ...)

that doesn't mean I gave up and that doesn't mean it can be applied to mangos right now.

[smellbee2008]

Ive created better storage system for floyd-warshall pregenerated all-pair-paths that will cost

(((MOVE_MAP_NODES_IN_GRID ^ 2) * 32bits) / 2) of memory. thats twice better then original

((MOVE_MAP_NODES_IN_GRID ^ 2) * 32bits)

Thats for storage of all paths in grid.

Can somebody tell me what is the max and minimum number of movemap nodes in one grid?

New storage system is based on increasing cpu usage minimaly but decreasing memory requirements rapidly:

Old(something like this):

PathNode* AllPairPaths [MOVE_MAP_NODES_IN_GRID] [MOVE_MAP_NODES_IN_GRID];
GetPath (int i , int j)
{
 if( AllPairPaths [i][j] == NULL )
   output(i,j);
 else
 {
   GetPath (i, AllPairPaths [i][j]);
   GetPath (AllPairPaths [i][j], j);
 }
}

New(something like this):

// id of node in grid up to 0xFFFF
uint32 AllPairPaths [MOVE_MAP_NODES_IN_GRID / 2][MOVE_MAP_NODES_IN_GRID];
GetPath(int i , int j)
{
 uint32 word = NULL;
 if( i & 1)
   word = (AllPairPaths [(i >>1)+1][j] & 0xFFFF);
 else
   word = ((AllPairPaths [(i >>1)][j] & (0xFFFF << 4)) >> 4);
 if(word == NULL)
   output(i, j );
 else
 {
   GetPath( i ,word);
   GetPath(word, j);
 }
}

every odd i is saved as 16bit LOW WORD

every even i is saved as 16bit HIGH WORD

maybe there are mistakes now, dont know

// Albrecht de Endrau // freeganja // Tvaroh //

[darkstalker]

So if we will be using A* runtime path finding we need to keep movemaps in memory, dont we?

Keeping complete map pairs should be much bigger

With A* you'll need to compute the entire paths before moving the agent, and recalculate everything when target moves/on collision (A* with local repair). Its slow and expensive on big problems.

You can use realtime search algorithms like LRTA* and calculate paths on the fly with a low cost (but reduced solution quality). This needs storing the heuristic value for each node in the search space (the "memory" of the algorithm).

[smellbee2008]

Jolan is working on making movemap generation better and cleaner and also on A* runtime algorhytm.

I am working on pregenerated paths for every pair of nodes by floyd-warshall algorhytm that will be only loaded to memory on server startup and GetPath function will handle all pathfinding then, by simple recursion so the cpu usage is tiny as it can be for path finding

A* = average memory usage and big cpu

pregenerated all-pair-paths = low cpu, huge memory

[Gotisch]

is there github/svn for your work too?

[DasBlub]

is there github/svn for your work too?

http://github.com/jolan/MoveMaps/commits/master

<10 characters>

[False.Genesis]

found a draft for a less memory consuming algorithm then LRTA*, look here: http://ircl.cs.ualberta.ca/files/webfm/lrts/pubs/bulitko09aiide.pdf - this may possibly help you.

[darkstalker]

this can be useful too (RTAA*): http://idm-lab.org/bib/abstracts/papers/aamas06.pdf

[spalc]

Hi man. Sorry bad engl.

For extract vmap i use vmapextract_v2.exe vmap_assembler.exe from mangos REVISION_NR "6989" and client 3.0.3

use Generator.exe 0 51 29 1 and i has crash ( null point access error )

pNode.valueArray no valid

  void
 MoveMapContainer::countMoveMapBoxesAndNode (AABSPTree<MoveMapBox*>::Node& pNode, int& nBoxes, int& nNodes)
 {
   nBoxes += pNode.valueArray.size (); //  pNode.valueArray no valid
   ++nNodes;

   if (pNode.child[0] != 0)
     {
       countMoveMapBoxesAndNode (*pNode.child[0], nBoxes, nNodes);
     }
   if (pNode.child[1] != 0)
     {
       countMoveMapBoxesAndNode (*pNode.child[1], nBoxes, nNodes);
     }
 }

How fix it?

[jolan]

I didn't try it with 3.x maps/vmaps yet. it's still for old 2.4.3 files

[alexluana]

any news?

With respect,

Axel

[rad_d]

Hi,jolan. Sorry for my bad English.

I have a question about move map layer:

is the same z-coordinate for all points on the layer or not?

[rad_d]

Sorry for my stupid question.I understand!!!

i'm dealing with it first time

[bubbie]

Heey,

I was wondering if this project is still on the move or not

Atm this seems the only way to make sure pet's/npc's don't go through walls/floors etc.

If there is a different way pls send me a link

Thanks,

Bubbie

[aming51]

Heey,

I was wondering if this project is still on the move or not

Atm this seems the only way to make sure pet's/npc's don't go through walls/floors etc.

If there is a different way pls send me a link

Thanks,

Bubbie

You can have a look at:

http://www.trinitycore.org/forum/movement-maps-t6878.html

And very interesting test:

[rad_d]

Hi

could someone give me all I need for 2.4.3 client to extract vmaps

[xingbarking]

Interesting Job, guys