jolan

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

for you info, ascent implemented it long ago. unfortunately AFAIK their licence is not compatible with mangos one. maybe a chinese wall approach would allow us to implement it.

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.

If I understand correctly, you want to stop Update*Visibility when the player is not actually moving, and you add a timer in order to update only after the interval the client usually sends packet when moving straight forward.

then modifying Player::SetPosition to check if x,y,z changed seems a better solution to me . you could pass an arg to tell if Update*Visibility are needed (if x,y,z changed) and force this flag to true in Unit::SetVisibility and i think in Traveller<Player>::Relocation too.

or you can check before and after player->Relocate() in Map::PlayerRelocation()

then you wouldn't need neither extra var in player* nor getMSTime() and you would have better speed / accuracy.

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

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.

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.

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.

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

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

I didn't

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.

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.

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 :

pointers are much more efficient to move around.

function doSomething(Player thePlayer); // will copy the Player struct each time it is called, will delete it when it returns, will not modify the original Player if the function modify (or call a member function modifying) thePlayer

function doSomething(Player* thePlayer); // none of the above

so the second version is faster and use less memory.

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 ?

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 ?

you have to launch it from cmd-line, with correct arguments (mapid, x and y of a generated file)

what is the output in cmd-line ?

Ok, there have been requests for source code.

the code is still somewhat bad and full of debug traces but here it is :

git clone git://github.com/jolan/MoveMaps.git

it's still for the original version of maps/vmaps, it needs an update.

I'm now implementing mmap-connector, a tool that links grids to nearby grids.

Hi, Derex and Jolan. How about the project? i just wana.

I'm still continuing it but I'm still lacking time.

By the way could the movement of mobs can be fixed by collision detection?:lol: just a suggestion.

no because collision detection takes too much CPU and it would not handle holes, big slopes etc.

jolan where I can download the sources of your "box style" map generator, as I saw on screenshots.

Can you share them for me? I have a lot of free time to work with mangos.

It's not ready yet, lots of experiments / bad code to clean before releasing it.

There will be modification to do that are not related to the new code, eg updating the original code to the current mangos version, which can be done now ...

adding it to mangos is not done, there is more work to do at the generator side before.

it's an new feature so yes, it will increase CPU usage.

I'm still on it, I dedicate the few time I have to continue it, but progress is slow due to my free time.

move zones are generated, in-layer zone to zone portals too, R*Tree with point lookup and point with height delta lookups are ok. save and load of the tree needs to be done (stored as an array right now)

gave up layer's connexion points to make layer to layer portals, wrote my own lookup routines, needs more work.

grid to grid portals need to be done.

the generator is very slow right now, will need optimisation.

path generator needs to be done.

a scene before my work :

a scene with zones and portals :

the same from above w/o vmaps and mmaps :

Yea, I have pushed to serverwide branch - it is for current mangos master , I can move it to some other branch if you want ?

do what you want, as long as ppl know which branch to pull ...

ok. I used serverwide-master and serverwide-0.12 for different client revs. you pushed into serverwide, so I think it's for master branch ? I dont think it's a problem.