MoveMaps

[ionstorm6]

[jolan]

I'm sorry but it would be difficult for me to debug mmap-viewer for w32 because I dont have a 3d capable VM installed right now.

I cant generate 000_25_32.mmap because I do not have starting points for this one. can you send me 000_25_32.txt and 000_25_32.mmap ?

[ionstorm6]

I don't have a 00_25_32.txt, where should it be?

Well here is the .mmap http://localhostr.com/files/267873/000_25_32.zip

[jolan]

00_25_32.txt is in the StartCoords folder.

there is no move zone in your file, either it was generated with an old version of the generator or there was an error when you generated it. can you provide the output of its generation ?

[jolan]

Several people (2 actually) asked me what's the progress with movemaps, so I think it's time to give a small status update.

about when it will be done : I really can't tell, I dont always have time to devote to it. I progress slowly.

what's done :

mmap data is correctly generated : as I described it , it's rectangular move zones connected by portals. portals are correctly connected to nearby zones, including zones in adjacent grids. move zones are stored in an R*Tree which allows fast lookup (about 3 microsec. a lookup). a path generation starts by 2 zone lookups in order to get the starting and the ending zones.

the Path Generator is not 100% perfect but works resonably well. there is still some bits to take care of but it have been tested inside a sigle grid (larger paths will need mmap load manager). it's an A* algorithm. a path takes about 5ms to generate for paths inside a given grid.

what needs to be done :

there is still some things to eventually take care of in mmap generation : some zones are completely contained in other zones and this is not handled. I dont know if its desirable to include them as these are usually terrain glitches.

dependencies update : maps where changed since ralf started it, and I think g3d libs too, I didn't watch closely. right now I still use old 0.12 maps and vmaps generated with rev 6989. thats before DiSlord enhanced maps.

those who took a look at some parts of the code know there is some garbage to clean. (my favorite one being : + printf("#### graaa ####\\n"); ) , destructors are not implemented, I'm not very good at memory management.

mmap generation and mmap use must be separated. everything is in the same classes. functions and data that are only used for mmap generation have nothing to do in a pathfinder system.

load / unload manager : similar to grid loading in mangos

once these stuff are done, movementgenerators could be enhanced to use pathgenerator (with still the classical code as a fallback)

a batch to generate and connect mmaps. I use a php script to generate mmaps but it might not be a good solution for windows systems.

VC++ build files.

an exemple of path, with and without vmaps :

[Derex]

Looks nice

[Homenixx]

mooooolaaa ;-)

[XTZGZoReX]

That's some damned nice progress there. If you need a hand in memory management, just poke me.

[jolan]

thanks for the offer.

I think generation / usage separation will perhaps modify the way destructors will have to be implemented so it's a thing that should be handled then.

[subhuman_bob]

a path takes about 5ms to generate

...which is about 2 million CPU cycles (assuming an "average" CPU speed of 2.5 GHz)

I don't mean to belittle the work being done here, but want to point out to all the people going "I want this naow!!" that if it was in your server now, it would barely run.

[XTZGZoReX]

If anything, movement pathing should _definitely_ have its own thread and mob movement, as well, would have to be threaded. That's the only real way we can efficiently implement it in MaNGOS as it is.

People who intend to use movement pathing in the future surely also must be aware of how heavy it will be...

[jolan]

you are right subhuman_bob, 5ms is slow; honestly I expected better results when I began this. I think (hope) there is room for optimisations.

if it cant be optimized, a thread is an option, even a separate server as long as the latency is low. data exchanges would be quite small.

[subhuman_bob]

Jolan, don't take my post the wrong way. I did not mean to be negative about the work that is being done at all.

you are right subhuman_bob, 5ms is slow; honestly I expected better results when I began this. I think (hope) there is room for optimisations.

if it cant be optimized, a thread is an option, even a separate server as long as the latency is low. data exchanges would be quite small.

The first step is to make it work- you're on your way to that point. After it works, no doubt many improvements to speed and memory usage will be found.

The entire reason for my post was because I have no doubts that very soon we'll be hearing "Why isn't this committed?" "Can a dev commit this?" "I want to use this NOW!!!" etc, etc

[jolan]

Jolan, don't take my post the wrong way.

I didn't

[XTZGZoReX]

Well, I think if it's a seperate process, we should as a first step make realmd<->worldd intercommunicate first .

[throneinc]

Sound promising, GJ.

[Derex]

The generation of path can me implemented asynchronous. So that more than one bacground threads can generate paths (using the same mmaps data), and return the results to mangos thread.

If you have problems with memory, or crashes, I can also take a look, when I have free time.

[smellbee2008]

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.

[jolan]

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

it's in src/mmap/PathGenerator.h (github)

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

I think we can keep the generated path in memory for long paths in order to re calculate the end of the path if the destination object moves. it's more memory vs more cpu so it mays be configurable, and I dont like eating too much memory.

other algorithm may be suitable, I focus on A* but someone else could try another one...

[smellbee2008]

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

[jolan]

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.

well , grids are kept loaded for a while, the more the players, the more grids get loaded at the same time, and remember there is an option for keeping grid in memory forever. that said perhaps movezones wont consume that much memory, I didnt check that.

feel free to try these algo, and lets compare results

How many nodes are in one grid?

about 3000-4000 zones, with a variable ammount or portal in each. that's not hat much and I expect to achieve faster path generation.

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

yes that's supported.

portals are one-way, so if we ever want to allow mobs to jump down, and use a different path to go back, it will be possible. I dont know if it will be usefull.

[smellbee2008]

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

[jolan]

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

yes, as long as the grid is active.

Keeping complete map pairs should be much bigger

I think. that would be hundreds of Mb per grid.

[smellbee2008]

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

[jolan]

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

thats still a lot IMO but maybe it would be better that 2ms per path (the time I get right now).

maybe you could write your own pathgenerator_floyd.h so we can test.