[11917] Movemaps

This first post will focus on the core implementation. It may need lots of discussion, so other topics can be covered later.

I am going to apologize in advance for a post which is simultaneously really long and overly brief or simplistic.

[h]Table of Contents[/h]

• How it Works
  I want to initially just give an overview how pathfinding has been integrated into the core
  Read this first, then look at some code before continuing on (a diff between mmaps_rewrite HEAD and cee28237f73a)
  
• Pathfinding Control
  How pathfinding can be configured in the core, and how that impacts different people in the mangos community
  
• Future Work
  any known or outstanding issues
  

[h]How it Works[/h]

I won't go into the details of Recast or Detour, those libraries are a bit beyond the scope of this post. If you want to know more about those, I recommend looking at Mikko Mononen's blog.

A prerequisite to understanding how mmaps works is knowing how the movement system works currently:

• SilverIce's move spline system
  Keep movement-related state and communicate this state to the client. At the risk of over simplifying, there are two entry points:
  

1. 
   
2. MoveSplineInit::MoveTo builds a straight line, A -> B path
   
3. MoveSplineInit::MovebyPath takes an arbitrary sequence of points
   

[*]Movement generators

The logic engines which determine where to go and how to get there. They sit on top of the move spline system, providing it with a destination point (for MoveTo) or a path to follow (for MovebyPath).

mmaps supplements this system with a new class, the PathFinder - as qsa says, it is the real mmaps implementation, and everything which calls it is just usage examples.

This class has the following capabilities:

• Using Detour, generate a new path which 1) avoids obstacles (don't walk through objects/terrain) and 2) follows terrain (don't fly off the ground)
  
• Store enough state to determine if a previously-generated path is valid, whether it needs to be updated, or if it needs to be recalculated from scratch.
  

In practice, PathFinder is used in the following ways:

• MoveSplineInit::MoveTo now internally uses PathFinder to generate a path to the destination. This gives nice looking paths anywhere the spline system is used, and also frees the caller from doing any pathfinding work.
  
• MoveSplineInit::MovebyPath can take a path which was generated by PathFinder.
  This is recommended for when maintaining the path is important, such as a moving destination (see TargetedMovementGenerator). Maintaining PathFinder outside of the move spline system allows you to avoid expensive pathfinding operations which are unnecessary; for example, when the destination moved byt the rest of the path is unchanged
  

If you want more specific details on how PathFinder works, please look at the code first. The constructor and the calculate function are a great starting point, and there are lots of comments in the code. After that, I can answer any questions you may have.

[h]Pathfinding Control[/h]

• Developers have control over the use of pathfinding via two parameters to functions which lead to PathFinder calls: generatePath and forceDest
  

  [*]Scripters can use the new unit UnitState UNIT_STAT_IGNORE_PATHFINDING. Creatures with this flag will default to A -> B movement.

  It would be trivial to implement additional UnitStates for other functionality, such as forceDest

  [*]DB devs only have the inhabittype mechanism to control pathfinding. If a creature only has land inhabit type, PathFinder will not generate a path through water (except shallow areas, I think it was 1.5 yds for max depth). Some people have requested flags for the database like the new UnitState flags.

  [*]Admins/GMs can use the mangosd.conf settings to enable/disable server-wide pathfinding and also to disable pathfinding on specific maps.

  There is also a ".mmap on|off" command to toggle server-wide pathfinding

  [h]Future Work[/h]

  mmaps is complete, as far as generating usable paths for units to follow.

  However, there is some unfinished and unstarted work due to lack of time/motivation, tediousness, or unimplemented dependencies. In some cases, more design/value discussion is needed before committing to a certain feature/implementation.

  • offmesh connections
    Some of Blizzard's collision meshes erroneously contain small gaps or holes which prevent generating a contiguous navmesh.
    Offmesh connections fix this by linking two arbitrary navmesh locations to each other.
    They need to be created manually, and any contributions by the community are welcome. Also, currently they are only added to the navmesh through the generator - a way to add/remove them at server runtime would be nice.
    
  • Aggro system integration
    When targets are unreachable they are dropped from the threat list - mangos needs an explicit RemoveFromThreatList function for this, current implementation is a bit 'hacky'.
    Also, it has been heavily discussed whether monsters should be able to target only creatures that they can reach. Current implementation is a 'lazy' one - rather than generate paths to all creatues in aggro list until a reachable one is found, we generates only one path to one creature in aggro list per update cycle - if that creature is unreachable, we drop the target and repeat the process the next cycle.
    
  • Evade timer implementation
    Currently, evasion happens immediately. There are some very specific things that creatures do when they can't reach any targets (complicated behavior, but easy to implement the basics first and build onto it)
    
  • Better destination
    

    A      @
    XXXXXXXXXXXXXXXXXX
    X
    X     Z
    B     C#
    
    monster = @, player = #, obstacle = X
    nice path:   @ -> A -> B -> C
    actual path: @ -> A -> B -> Z

    
    (code boxes are bugged, so here's a working version)
    Because the destination Z is found before we call PathFinder, we end up with a path that looks really bad from a player's perspective.
    It would be better to generate the path directly to #, but stop when we reach C. This will look better, and also eliminate the expensive GetNearPoint call, as B -> C is constrained/clamped to the terrain as part of the pathfinding.
    

  • Shared paths
    We might be able to save cpu if one path could be generated for multiple units. Most paths are short, so amount of benefit is questionable (possibly minimal gain after factoring in path copy, validation, and (maybe) modification).
    Anyway, it would be accomplished most easily via AssistDelayEvent - pass a generated path to the constructor, and during AssistDelayEvent::Execute we copy it to the assistant(s) via overloaded AttackStart.
    
  • reimplement smooth path
    While the majority of PathFinder is our original implementation/logic, the piece which builds the actual terrain-clamped point path (the 'smooth path') is not. It works, but the implementation is not very straightforward, and seems at first glance to be inefficient.
    
  • dynamic mmaps
    Handling dynamic vmaps presents a lot of challenges, but dynamic mmaps is potentially worse. There are facilities to handle dynamic navmeshes, but picking the right one (then implementing it, and integrating it into mangos) would be a lot of work.
    
  
  
• generatePath=true enables path finding, but is defaulted to false. false will cause movement to be simple A -> B line. true has been used in the core where it makes sense to do so.
  
• forceDest makes reaching the destination guaranteed. Currently, if there isn't a complete path to the destination the resulting path leads to the reachable spot nearest the destination. Some behaviors require that a unit always reach its destination, such as pets following their owner - forceDest=true helps enforce this behavior. It is defaulted to false.
  

Thank you very much for all involved Mikko,Gotisch,Lynx3d,Faramir118 and aspecialy to Schmoozerd for finally pushing this wagon few last steps!

Thanks to all the testers, namely Undergarun for adopting early and sticking with us; providing invaluable benchmarks/test results.

PS: just posting something silly so it wont get forgotten; follow the comments : https://github.com/faramir118/mangos/commit/53ed5f371e887039902547ea680a1375219232e4 and https://gist.github.com/1678609

Edit by Schmoo: Also worth to not forget:

- http://getmangos.eu/community/post/141107/#p141107

- http://getmangos.eu/community/post/141028/#p141028

Little something for http://getmangos.eu/community/post/141028/#p141028

Limiting those can sure save some CPU cycles.

https://gist.github.com/1818568

About https://github.com/faramir118/mangos/commit/53ed5f371e887039902547ea680a1375219232e4

Version 2 of initial idea, bit prettier, should have same functionality (not actually tested).

https://gist.github.com/1818550

@cyberium: cashing can be nice, but I'm afraid net very efficient in our case. You can do a simple experiment: just save start and end locations in hash map, then lookup every calculation to see how many hits you get, if its under ~10% of searches, it ain't worth it.

About IsReachable: Need to check it.

The thing with IsReachable() is bit different, it will work only after path is calculated, that's why it ain't exported via public API.

Thank you very much for this summary post.

You didn't add any installation/ "where is the patch" instructuctions, I think a post to post1 of the mmaps redux thread will be fine

As I can see the patch is about 150k lines, I won't read this till tomorrow

So, infact I directly jumped to the step for 'future work'

* Offmesh connections

Well, this is stuff no project (db, core, scripting) handles yet, so without any other good points I guess we can keep this as part of the mangos project directly, with the goal that reasonable 'custom' corrections can be "reviewed", and maybe shipped with a default_offmesh.txt file. (Probably at least in the beginning you and qsa will have biggest word on mainting this file's content)

Do I understand correctly? If it is changed it will require some time-consuming rebuilding?

In this case I would agree that some more dynamic approach for this would be nice to have, but still candy.

* Aggro system

I think I will push something like http://paste2.org/p/1400454 (take just as basis) 'soon', most interesting might be the function currently named IsSecondChoiceTarget - dunno if not maybe this should be moved to unit class, and also be used for taunters.

Would then likely also be a place where we could add the reachable-path-exists check.

Opinion would be appreciated.

This also might remove the pressure to remove the unreachable units from the threat list, but would simply order them to lower priority

* Evade

Well, it seems from many sources that our current implementation (evade on range) should be replaced with (evade after timelimit without action) anyways, so this might then be a huge simplification anyways.

Sorry, I've grown lazy after 1200+ posts in the other thread...

The code is located in the mmaps_rewrite branch in my github repository

And because I'm lazy, I also like to let git do all the work...

You can get my branch like this:

git remote add -f faramir118 git://github.com/faramir118/mangos.git

After that, you can look at the mmaps-only changes (pipe this command to a file to generate a patch):

git diff $(git merge-base faramir118/mmaps_rewrite master) faramir118/mmaps_rewrite

• offmesh connections
  Yes, rebuilding the mmap files just for offmesh connections is very time consuming (especially since not much work is actually done).
  It can be lessened with a really good how-to on the use of the mmap generator, but not very user friendly.
  
• aggro system
  This part needs some work, regardless of how it involves mmaps. I will read your changes once I am home.
  IIRC, testing for mmaps on retail showed that unreachable targets were dropped from the threat list.
  
• evade
  That would make things simpler.
  However, I believe that there are some cases where evasion isn't on a timer - don't bosses reset much faster than regular mobs?
  

First thing I noted:

IN src/game/MoveMap.cpp
+    // ######################## MMapFactory ########################
+    // our global singelton copy
+    MMapManager *g_MMapManager = NULL;

Why not use the default mangos way with Singleton?

IIRC, there isn't any particular reason why we use this factory rather than singleton. We simply followed how vmaps work with regards to map/grid lifecycle management.

Related to your changes in SelectHostileTarget

I think it might be a good idea to move the "GetMotionMaster()->operator->()->IsReachable())" check into Unit::IsSecondaryChoiceTarget added in commit 51d2766d57ad

I think the best choice will depend on the final way we'll implement monster's agro reset. (evade mode)

But your suggestion goes to the right direction Schmoozerd.

Tiny observation:

I usually compile on 64bit debug mode ( VC100)

So I switched to the mmaps_rewrite branch, and get this error

LINK : fatal error LNK1181: cannot open input file '\\dep\\lib\\Win32_Debug\\Detour.lib'

With 32bit release compile was alright

try compiling detour first, in win32_debug mode

Tiny observation:

I usually compile on 64bit debug mode ( VC100)

So I switched to the mmaps_rewrite branch, and get this error

LINK : fatal error LNK1181: cannot open input file '\\dep\\lib\\Win32_Debug\\Detour.lib'

With 32bit release compile was alright

https://gist.github.com/1678748

should fix this issue

I rebased a little bit: https://github.com/Schmoozerd/mangos/commits/mmaps_rebase

(author information and commit messages are crap, but these are temporary commits)

I reextracted them on an older quad-core with 3 CPUs used for mmap-Gen, and it took about 2.5hours

So this is not too bad at all

For some tests you might go and just extract a few smaller maps in the beginning

In case anybody wants to do some last-minute tests ...

Edit: Maybe not so last minute:

On *nix I (and at least another person) cannot compile contrib/mmap. Fails with:

[  5%] Built target Detour
[ 12%] Built target Recast
[ 24%] Built target zlib
[ 91%] Built target g3dlite
[ 92%] Building CXX object CMakeFiles/vmap.dir/some/mangos/src/game/vmap/BIH.cpp.o
In file included from /some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/config-lite.h:24,
                from /some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/Basic_Types.h:46,
                from /some/mangos/contrib/mmap/../../src/framework/Platform/Define.h:24,
                from /some/mangos/src/game/vmap/BIH.h:26,
                from /some/mangos/src/game/vmap/BIH.cpp:19:
/some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/config-macros.h:28:26: error: ace/config.h: File or Directory not found
In file included from /some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/os_include/os_signal.h:217,
                from /some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/os_include/sys/os_wait.h:27,
                from /some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/os_include/os_stdlib.h:28,
                from /some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/Basic_Types.h:60,
                from /some/mangos/contrib/mmap/../../src/framework/Platform/Define.h:24,
                from /some/mangos/src/game/vmap/BIH.h:26,
                from /some/mangos/src/game/vmap/BIH.cpp:19:
/some/mangos/contrib/mmap/../../dep/ACE_wrappers/ace/os_include/os_ucontext.h:40: error: conflicting declaration 'typedef int ucontext_t'
/usr/include/sys/ucontext.h:244: error: 'ucontext_t' has a previous declaration as 'typedef struct ucontext ucontext_t'
make[2]: *** [CMakeFiles/vmap.dir/some/mangos/src/game/vmap/BIH.cpp.o] Fehler 1
make[1]: *** [CMakeFiles/vmap.dir/all] Error 2
make: *** [all] Error 2

commit 5ebd86136a5510a968f70994834ad034858903c6

Author: Schmoozerd <[email protected]>

Date: Mon Jan 30 19:13:13 2012 +0100

Remove old binaries for extraction

Builds with these on Arch Linux x86_64

cmake ../ -DPREFIX=/opt/mangos -DPCH=1 -DACE_USE_EXTERNAL=1 -DDEBUG=1 -DTBB_USE_EXTERNAL=1

gcc 4.6.2 20120120

ace 6.0.8

intel-tbb 4.0_20111130

Regards

Skirnir

[EDIT] Builds as well without external libs.

[EDIT2] Oh nvm you were talking about contrib ... should not post if coffee <= 0

[EDIT3] It is rather stupid, but MaNGOS is missing ace/config.h that is all. Copy it from a full MaNGOS installation into the ACE_WRAPPER/ace/ folder and compilation works. Missing this "config.h"-file breaks contrib vmaps stuff as well.

Thank you very much.

I still fail to compile vmap_extractor and assembler[Edit: Was told by Skirnir how to solve it], but the MMapGen is working now

But I fear this will be pretty complicated to fix, because the ace/config.h depends highly on the settings of how mangos is compiled, and hence might be around in different versions within different built-trees, but if no cmake genious will show up, I guess a small note in a readme.linux should do the trick.

(Generating mmaps on linux is fairly important I think, because this allows to recreate offmesh changes on-the-fly for a test-server)

A small special feature:

I think we should limit valid points for RandomMovement to consider the length of a created path.

Just noted on UDB that the images of bosses like 31584 have some pretty cool random movement in dalaran

Sorry for being slow to respond, lots of work stuff recently...

contrib/mmap with -DACE_USE_EXTERNAL works for me after some copy paste (untested with 'internal' ace):

https://gist.github.com/1721754

When compiling contrib/mmap, MoveMapSharedDefines.h seems to have a bad include for DetourNavMesh:

In file included from /Users/a/Projects/mangos/mangos/contrib/mmap/src/TerrainBuilder.h:24,
                from /Users/a/Projects/mangos/mangos/contrib/mmap/src/MapBuilder.h:26,
                from /Users/a/Projects/mangos/mangos/contrib/mmap/src/generator.cpp:20:
/Users/a/Projects/mangos/mangos/contrib/mmap/../../src/shared/../../src/game/MoveMapSharedDefines.h:23:62: error: ../recastnavigation/Detour/Include/DetourNavMesh.h: No such file or directory

All other files under src/game include "../../dep/recastnavigation/Detour/Include/DetourNavMesh.h", so MoveMapSharedDefines.h is probably wrong in general.

Thank you very much. Added in Revs 11901 to 11919

Also special thanks to qsa and all the other involved.

This is extremely great that mmaps are finally within MaNGOS, your work is very appreciated!

The patch from your post #15 I did not include, I think there will be some good input about *nix problems anyways, but it just is the time to get things rolling.

Yeeeeesssssss!!!!!

Thanks to all of you!.

extraction mmaps is very long Could someone tell me how many M0 or G0 can hold it? thank you for your answers

@Jethro What do you mean with M0 or G0?

mmaps extraction is rather long, expect 8 hours/ numCpu (numCpu <= 4)

MMap Extraction

Extracting mmaps takes very long, especially the continents take > 1 hour

If you start on windows in Git-Bash, you won't see changes now and then, just be patient.

Also you can look into the log-files for changes

You can skip a few (or all) mmaps (continents are the biggest by far), and just add them whenever you want to

Whats the recommended server spec with mmaps enabled?

Whats the recommended server spec with mmaps enabled?

I think we'll have more input soon about big server owners

Can some one load the extrated files up to some host that we can download the finished mmaps thx if some one do this.

ooo yeah...this is it...looong waited moment... make wow servers look offlike... even scripting will get more awesome..

Thank you schoomozerd