smellbee2008

as you can see

http://img6.imageshack.us/i/image2cne.png/

jolan did a great job and make the movemaps simple so you only need to know in which movezone(square where every point see every other point) the coord is and search way to another movezone where dest coord is. Then you just find path to that movezone and you are 100% sure you have IsInLOS dest point : )

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

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 //

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

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

I want to write should not be.

As stated in here:

http://www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/MyL15.pdf

Floyd-Warshall can be kept in array like this:

nodePointer * pred [NUMBER_OF_NODES][NUMBER_OF_NODES]

so two dimensional array containing pointers to predecesor nodes on path from node X to Y

From that you can take easily path by recursion

quote:

Path ( i, j )
{
 if( pred[i][j] == NULL) // single edge( or inaccesible)
   output( i , j );
 else
 {
   Path( i , pred[i][j] );
   Path( pred[i][j], j );
 }
}

Example:

http://img30.imageshack.us/img30/5787/45877211.jpg

So the memory used will be similar( its number of nodes^2 array) and path computation will be much faster

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

My friend Disassembler told me and idea of loading all pair-paths by Floyd-Warshall or maybe betterJohnsons algorythm on grid loading and then releasing them on grid unload. That shouldnt be so memory using.

How many nodes are in one grid?

And different question, does movemaps support zones like Blades Edge Arena where there are nodes under and on the bridge? And units using pathfind AI must know how to get from the top of the bridge to place under the bridge? Without jumping

Can we see your actual A* path finding algorithm somewhere? Please

//edit::

do we really need dynamic path generation by A*? If we use A* then we must do new generation on every change of destination. that is really a lot of computations

What about pregenerated path datas by Floyd-Warshall or Johnsons algorithm? I mean, generate all paths between all pair of edges before program run and then just call path like GetPath( source,destination,map) which will give us pointer to our desired pregenerated path.

Problem for this is the memory.

Something new with this project? If you need some help let me know please : )

Albrehct de Endrau // freeganja // Tvaroh 216264234