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

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