namreeb / namigator Goto Github PK

An intelligent navigation API for World of Warcraft Vanilla, TBC and WotLK

License: MIT License

C++ 65.89% HLSL 0.30% C 31.45% CMake 0.92% Python 1.45%

pathfinding world-of-warcraft high-performance multithreading c-plus-plus

namigator's Introduction

namigator

namigator is a drop-in, high-performance, and nearly feature complete pathfinding system for server-controlled movement of units within a World of Warcraft environment.

Components

namigator is made of three different types of components: applications, shared libraries, and third-party dependencies.

Applications

MapBuilder -- Generates navigation mesh for a given map, or geometrical data for a collection of objects. NOTE: This application can also build a python module.
MapViewer -- A DirectX application to load input data, any mesh data, and allows for testing and debugging.

Shared Libraries

pathfind -- The core pathfinding library. This is the only library you should need to include in your server. NOTE: This library can also build a python module.
parser -- For parsing source terrain data. This library is not needed for navigation functionality. Only for computation. It should not be needed in your server.
utility -- Various generic mathematical and structural utilities used across the other components. You should also not need to include this in your server.

Third-Party Dependencies

stormlib -- Used for extracting source data from its containers.
recastnavigation -- Underlying computational geometry library. Used for mesh generation, pathfinding, and more.
pybind11 -- Optional. Used in creating python modules.
python -- Optional. Used in creating python modules.

Future Plans

namigator is being released because I have lost interest in taking it to the next step myself. I also think it might give other interested people a good start. I have some thoughts on what functionality should be added. This is documented on the issue tracker for the most part. My interest in developing this functionality will probably be proportional to adoption by others. While initially this was a purely academic exercise, I no longer have time to devote to development unless it will be helpful to the larger community.

Caveats

This is something I have developed off and on for nearly a decade. I have never used it, but have tested it fairly thoroughly in a controlled setting. I have also put in a fair amount of effort to understand why common bugs happen and mitigate them (e.g. falling through the world, stuttering, etc.). At this point I do not have time to invest in integrating this library into an existing server. However, if someone else wants to do that, and in doing so discovers some issues, I can probably assist in correcting them. I can also provide some guidance in how to integrate the library. Feel free to contact me privately for this.

Production Testing

To my knowledge, namigator has not yet been integrated into any emulation software. It has therefore not been tested in actual production. There may be unforeseen accuracy or performance issues.

Thread Safety

The thread safety of the map builder and parser should be correct. However the thread safety of the pathfind library is likely not fool proof. Use with caution!

Bots

This software is not designed to honor client-side movement restrictions, and is therefore not natively suitable for use in bots. Though its possible such capability may evolve, I also avoided explicitly supporting this use case. My goal is not to improve the ability of those who undermine the integrity of a server with large scale automation.

Feedback

Please use the issue tracker on this repository to submit issues, feature requests, etc.. Do not use the issue tracker to request help with integration, unless there is a bug causing your problem.

namigator's People

Contributors

Stargazers

Watchers

namigator's Issues

MapBuilder crash when load MH2O

MapBuilder crash when build data of Azeroth for WtoLK.
https://github.com/namreeb/namigator/blob/master/parser/Adt/Chunks/MH2O.cpp#L42
instance.Width and instance.Height are both zero.
It works fine for TBC because header.Mh2oOffset is always zero.

during researching I found the 0x14 offset cause this issue.
https://github.com/namreeb/namigator/blob/master/parser/Adt/Adt.cpp#L98
building success after remove this 0x14 offset.

what's your suggestion?

Create C++ command line program that can smoke test loading/line of sight/etc

When reproducing errors it would be nice to have an upstream program that can be used to verify that the problem is within the library and not in the Python bindings/C API/my application code.

It could make sense to just include this as part of the MapBuilder executable.

I know the MapViewer executable can do this, but it doesn't run on Linux/Mac.

Serpentshrine Cavern

In the middle of the pool from which Lurker is summoned, mobs need to be able to climb out of the water seamlessly onto the platform and back again. No coords needed since you cant miss that part of SSC.

Expose FindRandomPointAroundCircle

https://github.com/recastnavigation/recastnavigation/blob/main/Detour/Source/DetourNavMeshQuery.cpp#L317

https://github.com/layzerar/recastlib/blob/master/python/detour/query.cpp#L460

This would help us a lot with wandering/fear movement generator.

Embedding namigator in another cmake project

When you try to embed namigator into an existing cmake project, the recast source files can't be found.

This is due to the use of the ${CMAKE_SOURCE_DIR} variable in RecastDetourBuild/CMakeLists.txt (Line 40+).

This can be fixed by replacing it with ${CMAKE_CURRENT_SOURCE_DIR}/../

Erode walkable edges only from walls, not cliffs.

Recast has the ability to erode walkable edges for hard mesh poly edges, where hard means that that edge has no neighboring polygon. This serves to improve realism by avoiding having an agent halfway in a wall. However for us, it is not necessary in all cases. If an edge is hard due to steep cliff as opposed to a wall, this erosion should be skipped.

This enhancement will allow pathfinding across the ropes in the Gurubashi Arena to function as intended.

Replace boost python with pybind11

https://pybind11.readthedocs.io/en/stable/benchmark.html
Compile faster, smaller, and almost the same syntax.

Allow using navigation files from locations other than file system

As part of working on the Rust library I would like to be able to have it be possible to use extracted map data from sources other than the filesystem.
Specifically I would like to put the data in an SQLite DB, potentially for speed but also for a cleaner user experience.

I would also like for there to be some way of avoiding the intermediate file system step when creating the map data, but that's easier to work around.

I'm not very well versed in the usage patterns of the navigational data, so I'm not sure what the best way of structuring things would be.

Documentation

Here on wiki? In repo?

Dungeons, query_z & pathing.

Both not working inside dungeons. Probably related to #38.

Loading `SunkenTemple` throws `FAILED_TO_OPEN_FILE_FOR_BINARY_STREAM`

Namigator attempts to load the output path + /Nav/Map.nav in a BinaryStream which doesn't exist.

I suspect it's because of a missing map name here.

Changing
auto const nav_path = m_dataPath / "Nav" / "Map.nav"; to
auto const nav_path = m_dataPath / "Nav" / m_mapName / "Map.nav";
allows Namigator to load the map.

I will send a PR for this since it's such a small change and if it turns out to be wrong you can just deny it.

MapBuilder and C API can not handle uncreated directories 2 steps deep

If we assume that /tmp exists, and you run MapBuilder and point it to /tmp/test1 it will correctly create the directory and proceed with extraction.
If you point it to /tmp/test1/test2 it will fail with Builder initialization failed: filesystem error: cannot create directory: No such file or directory [/tmp/test1/test2] and an unknown exception for the C API.

I already have a PR for this.

Add ability to detect if gameobjects/maps should be built

Currently running the mapbuild_build_bvh and mapbuild_build_map functions don't test if the output files already exist.
It would be nice to have a (C API) way of testing whether it is necessary to build gameobjects/maps.

This could be either an external function in the C API or built into the current functions.

Replicable charge-fall in Tanaris

Had this on my notes:

charge falling:
tanaris: several level issue on small mountain
@todo tweak build params, check with recast demo
-8827.41, -2251.02, 17.97, 0.51
-8817.45, -2246.18, 20.93, 0.47

Path finding context

The user must be able to create a path find context to configure certain behaviors, such as:

Water behavior (can walk on land? can swim?)
Obey maximum slope of ADT geometry?
"Spline mode" where only the final hop of a path requires a precise Z value?
"Human-like mode" where movement heuristics are applied to make the movement appear more natural (eroding edges to not hug the walls, smooth turns)?
Shortcuts (flight masters, hearthstone, teleportation spells, etc.)

Not all of these features need necessarily be implemented for the initial release, but a forward-compatible context structure should be created that can support them when they are introduced.

Doodad/M2 line of sight

According to Asura, Lost Rigger Cove (http://wowwiki.wikia.com/wiki/Lost_Rigger_Cove) has M2 trees which should not block line of sight, and other M2s which are parts of the structure which should. This is probably a good spot to look for flags relating to whether LOS is enforced for a given doodad instance.

Add documentation for C API

I plan on doing this myself, but there are a few things that I would like to ask so I'm opening it as an issue instead in order to potentially help people in the future.

The wiki mentions that game object processing should always happen before map processing. What would happen if this was done out of order?
"BVH generation" is not very descriptive of what happens at a business logic level, would it make sense to instead call it "Game Object processing"?
What does the "Game Object CSV" do, how is it made, and is it required/recommended?
What is the difference between pathfind_load_adt and pathfind_load_adt_at? When would it be recommended to use these instead of just pathfind_load_all_adts.
What is actually returned by pathfind_get_zone_and_area? From my own wow_messages work I have created an enum that I call Area which seems to contain both "zones" and "areas". What is the difference between these and are the different values documented anywhere?
For pathfind_find_heights and pathfind_find_path, is there an internal limit on the amount of values that are possible?

Deadlock issue

From @devw4r on Discord:

Map 0 ADT [42,33] X -5605.57319977779 Y -544.1348024689524' ? Namigator is locking the core forever when doing that query

Wrong WMO liquids parsing from alpha data

Stormwind.

Undercity.

Tile unload

Expose tile unloading in pathfind and python API.

Include MH2O data in unit tests

Title

Bugged WMO in Outlands

Map: Expansion01
ADT: (18, 37)
WMO: world\wmo\outland\floatingrocks\nagrand_rockfloating_waterfalls.wmo

The WMO instance data says that doodad set number 1 is used, but there is only one doodad set and the list is zero based (so the one set is number 0 not 1).

Correct behavior over hills

When pathfinding over hilly ADT terrain free from obstacles, we likely need intermediate points on the path to give the unit proper elevation along the way.

Building `Kalimdor` for 1.12 prints `Doodad not found`

When building Kalimdor the following is output:

Doodad world\wmo\outland\rubble\outlandrubble02.mdx not found
Doodad world\wmo\outland\rubble\outlandrubble01.mdx not found
Doodad world\wmo\outland\rubble\outlandrubble03.mdx not found

This used to be a THROW_MSG (commented out) but now it's just a std::cerr print.
Is this "supposed" to happen or is it a bug?

SHA256sums of MPQs:

0bb2d6d370d825353eff5d9282c545a1b61980baaa5b7b65b1a7521e0ee8e27a  /home/asd/Downloads/Data112/backup.MPQ
f648e4fae190abcb25749ddbe96454e7e0de7e9c7e955983ed9d0e73b6986009  /home/asd/Downloads/Data112/base.MPQ
d9d5a290bdad848e177e2731c7ef221a1d7a6793e2c94e431488dd40816101e2  /home/asd/Downloads/Data112/dbc.MPQ
511189160f091eeb9d7ee8c473c1422b7f1fadbd9b65bfbf7d0a2a344103312d  /home/asd/Downloads/Data112/fonts.MPQ
6545dfbb3ef21a8b7f36b577419494cc292fec35585f9a1511d6c8b692b83191  /home/asd/Downloads/Data112/interface.MPQ
13aee674db39fc605c8aabf964eda0bb7895c6f026fed6c508bf2f9d155db0f9  /home/asd/Downloads/Data112/misc.MPQ
a7aa78c234bbdd450e00434e5939aa1a02383df1971cddcbfa181d68e9ab45a2  /home/asd/Downloads/Data112/model.MPQ
84f506c9f049f1e35f6d0f7b2e6643d28856888680ae2593436be8b9a058aad6  /home/asd/Downloads/Data112/patch-2.MPQ
a9ad25c9a32600dd3c71f97a0f95f9b9b629a9995988b928975c8871f1197683  /home/asd/Downloads/Data112/patch.MPQ
6ba131da952aae8d1e061b54468fd6e5d2ef78616540e2746ed21255d6b959a7  /home/asd/Downloads/Data112/sound.MPQ
a1564120452cd75c4c7b2002a668b12250a35dab658816a33b591ebb23004f52  /home/asd/Downloads/Data112/speech.MPQ
68fda6fb4f57051a47a0a56ff1757d73ee5c2a870774ba60ee8b52d7b36bc61d  /home/asd/Downloads/Data112/terrain.MPQ
7e5996d2a0a2de03c79dcf9ab78f3fce66264688eee56ca6dbc51c8ce4433dac  /home/asd/Downloads/Data112/texture.MPQ
9933d9ca23d481647880c9798dc7c225cd926f51026d148f09cd5251fc56edb7  /home/asd/Downloads/Data112/wmo.MPQ

Deathknell doorway

From TrayZ @ Warmane

Map 0, (1926, 1548, 88)

Pathing works into the structure, but not out of it.

Zangarmarsh

1028.198 8472.511 58.678 map id 530

Pathing to top and from top of tower is tricky.

another tower with tricky PF just nearby

1034.793 8264.557 32.389 map id 530

Loading `BlackRockSpire` for 1.12 trips assertion

Loading BlackRockSpire for vanilla trips the following assertion:

.//vendor/pathfind/Tile.cpp:58: pathfind::Tile::Tile(pathfind::Map*, utility::BinaryStream&, const std::filesystem::__cxx11::path&, bool): Assertion 'quadHeight == 0 || quadHeight == 1' failed.

SHA256sum of generated files:

7b48817c573db9d9bfc697728b0e059e6c1ba86d855d51fbaf18d0001a391cda  BlackRockSpire.map
367bb1b45dc73a067fb4290d0d95961f6cab8181b059446316804c3ec06b2571  BlackRockSpire/Map.nav

quadHeight = 120 for all maps.

Let me know if you need backtraces or any further info.

Backtrace from Rust (ignore anything below pathfind_new_map:

__pthread_kill_implementation (no_tid=0, signo=6, threadid=140737352607872) at ./nptl/pthread_kill.c:44
44      ./nptl/pthread_kill.c: No such file or directory.
(gdb) bt
#0  __pthread_kill_implementation (no_tid=0, signo=6, threadid=140737352607872)
    at ./nptl/pthread_kill.c:44
#1  __pthread_kill_internal (signo=6, threadid=140737352607872) at ./nptl/pthread_kill.c:78
#2  __GI___pthread_kill (threadid=140737352607872, signo=signo@entry=6) at ./nptl/pthread_kill.c:89
#3  0x00007ffff7842476 in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#4  0x00007ffff78287f3 in __GI_abort () at ./stdlib/abort.c:79
#5  0x00007ffff782871b in __assert_fail_base (
    fmt=0x7ffff79dd150 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n",
    assertion=0x55555565a7c0 "quadHeight == 0 || quadHeight == 1",
    file=0x55555565a6b0 "./pathfind/Tile.cpp",
    line=58, function=<optimized out>) at ./assert/assert.c:92
#6  0x00007ffff7839e96 in __GI___assert_fail (
    assertion=0x55555565a7c0 "quadHeight == 0 || quadHeight == 1",
    file=0x55555565a6b0 "./pathfind/Tile.cpp",
    line=58,
    function=0x55555565a750 "pathfind::Tile::Tile(pathfind::Map*, utility::BinaryStream&, const std::filesystem::__cxx11::path&, bool)") at ./assert/assert.c:101
#7  0x00005555555d84bf in pathfind::Tile::Tile (this=this@entry=0x5555558ef690,
    map=map@entry=0x55555569ed50, in=...,
    navPath=filesystem::path "/tmp/outputtest/Nav/BlackRockSpire/Map.nav" = {...},
    load_heightfield=load_heightfield@entry=false)
    at ./pathfind/Tile.cpp:58
#8  0x00005555555d53cb in std::make_unique<pathfind::Tile, pathfind::Map*, utility::BinaryStream&, std::filesystem::__cxx11::path const&> () at /usr/include/c++/11/bits/unique_ptr.h:961
#9  pathfind::Map::Map (this=this@entry=0x55555569ed50,
    dataPath=filesystem::path "/tmp/outputtest" = {...}, mapName="BlackRockSpire")
    at ./pathfind/Map.cpp:265
#10 0x000055555556dae4 in pathfind_new_map (data_path=<optimized out>, map_name=<optimized out>,
    result=0x7fffffffdddf "")
    at ./pathfind/pathfind_c_bindings.cpp:13
#11 0x000055555556d2e0 in namigator::pathfind::{impl#0}::new::inner (data_path=..., map_name=...)
    at src/pathfind.rs:39
#12 0x000055555556d058 in namigator::pathfind::PathfindMap::new<&std::path::Path> (data_path=...,
    map_name=...) at src/pathfind.rs:61
#13 namigator::vanilla::{impl#0}::new::inner (data_path=..., map_name=...) at src/util.rs:35
#14 namigator::vanilla::VanillaMap::new<&std::path::Path> (data_path=..., map=<optimized out>)
    at src/util.rs:39
#15 namigator::vanilla::{impl#0}::build_gameobjects_and_map::inner (data_path=..., output_path=...,
    map=<optimized out>, threads=<optimized out>) at src/util.rs:86
#16 0x000055555556bd53 in namigator::vanilla::VanillaMap::build_gameobjects_and_map<&str, &str> (
    data_path=..., output_path=..., threads=26, map=<optimized out>)
    at /home/daniel/gitas/namigator-rs/namigator/src/util.rs:89
#17 namigatortest::main () at src/main.rs:11

WMO walkability flag

According to this post there is a flag to determine whether a triangle in a WMO is walkable.

ADT is based on the triangle normal, WMO and WDT are based on triangle flags.

I believe it's the MOPY chunk you are after, 0x40 is considered "unwalkable" and IIRC 0x80 filter would give you the navigation mesh (but it's low detail and shouldn't be used for client side movement).

Unable to create BVHs for version 1.12

As talked about on Discord, figured I would open an actual issue.

The 1.12 client does not have a locale directory or any MPQ files with it in the name, so it fails to find any data files.

This is checked in the MpqManager here.

Remove boost

Right now we are using boost only for boost::python. This is a pretty heavy lift just to benefit from the syntactic sugar that boost gives us. Also at the time of writing this, the Windows tests simply cannot run because cmake finds python 3.10 (despite us installing python 3.9), and the FindBoost package of cmake currently available on the github windows runner does not support 3.10 when integrating with boost.

Building Azeroth map for 1.12 SEGFAULTs (nullptr dereference)

Building the Azeroth map for 1.12 segfaults when building the map at around 60 percent. This happens even on threads == 1.

Seems to happen during MHDR at ADT x=30, y=45 (more info in the backtrace below).

gdb backtrace:

0x000055555560a7ca in std::__shared_ptr<std::vector<unsigned char, std::allocator<unsigned char> >, (__gnu_cxx::_Lock_policy)2>::operator bool (this=0x0) at /usr/include/c++/11/bits/shared_ptr_base.h:1300
1300          { return _M_ptr != nullptr; }
(gdb) bt
#0  0x000055555560a7ca in std::__shared_ptr<std::vector<unsigned char, std::allocator<unsigned char> >, (__gnu_cxx::_Lock_policy)2>::operator bool (this=0x0)
    at /usr/include/c++/11/bits/shared_ptr_base.h:1300
#1  0x000055555560a74a in utility::BinaryStream::buffer (this=0x0)
    at ./utility/../utility/BinaryStream.hpp:34
#2  0x0000555555609e53 in utility::BinaryStream::GetChunkLocation (this=0x0, chunkName="MHDR",
    startLoc=0, result=@0x7fffa33fb888: 1)
    at ./utility/BinaryStream.cpp:156
#3  0x0000555555609e20 in utility::BinaryStream::GetChunkLocation (this=0x0, chunkName="MHDR",
    result=@0x7fffa33fb888: 1)
    at ./utility/BinaryStream.cpp:146
#4  0x000055555559ee3d in parser::Adt::Adt (this=0x7fff9910f130, map=0x55555597c500, adtX=30, adtY=45)
    at ./parser/Adt/Adt.cpp:75
#5  0x00005555555d4d4b in std::make_unique<parser::Adt, parser::Map*, int&, int&> ()
    at /usr/include/c++/11/bits/unique_ptr.h:962
#6  0x00005555555d3123 in parser::Map::GetAdt (this=0x55555597c500, x=30, y=45)
    at ./parser/Map/Map.cpp:231
#7  0x000055555558594f in MeshBuilder::BuildAndSerializeMapTile (this=0x555555a07760, tileX=479,
    tileY=719) at ./MapBuilder/MeshBuilder.cpp:926
#8  0x000055555559c434 in Worker::Work (this=0x55555597ac10)
    at ./MapBuilder/Worker.cpp:57
#9  0x000055555559cedc in std::__invoke_impl<void, void (Worker::*)(), Worker*> (
    __f=@0x55555597ac90: (void (Worker::*)(Worker * const)) 0x55555559c174 <Worker::Work()>,
    __t=@0x55555597ac88: 0x55555597ac10) at /usr/include/c++/11/bits/invoke.h:74
#10 0x000055555559ce2f in std::__invoke<void (Worker::*)(), Worker*> (
    __fn=@0x55555597ac90: (void (Worker::*)(Worker * const)) 0x55555559c174 <Worker::Work()>)
    at /usr/include/c++/11/bits/invoke.h:96
#11 0x000055555559cd8f in std::thread::_Invoker<std::tuple<void (Worker::*)(), Worker*> >::_M_invoke<0ul, 1ul> (this=0x55555597ac88) at /usr/include/c++/11/bits/std_thread.h:253
#12 0x000055555559cd44 in std::thread::_Invoker<std::tuple<void (Worker::*)(), Worker*> >::operator() (
    this=0x55555597ac88) at /usr/include/c++/11/bits/std_thread.h:260
#13 0x000055555559cd24 in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (Worker::*)(), Worker*> > >::_M_run (this=0x55555597ac80) at /usr/include/c++/11/bits/std_thread.h:211
#14 0x00007ffff7cdc2b3 in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#15 0x00007ffff7894b43 in start_thread (arg=<optimized out>) at ./nptl/pthread_create.c:442
#16 0x00007ffff7926a00 in clone3 () at ../sysdeps/unix/sysv/linux/x86_64/clone3.S:81

SHA256sums of files:

0bb2d6d370d825353eff5d9282c545a1b61980baaa5b7b65b1a7521e0ee8e27a  backup.MPQ
f648e4fae190abcb25749ddbe96454e7e0de7e9c7e955983ed9d0e73b6986009  base.MPQ
d9d5a290bdad848e177e2731c7ef221a1d7a6793e2c94e431488dd40816101e2  dbc.MPQ
511189160f091eeb9d7ee8c473c1422b7f1fadbd9b65bfbf7d0a2a344103312d  fonts.MPQ
6545dfbb3ef21a8b7f36b577419494cc292fec35585f9a1511d6c8b692b83191  interface.MPQ
13aee674db39fc605c8aabf964eda0bb7895c6f026fed6c508bf2f9d155db0f9  misc.MPQ
a7aa78c234bbdd450e00434e5939aa1a02383df1971cddcbfa181d68e9ab45a2  model.MPQ
84f506c9f049f1e35f6d0f7b2e6643d28856888680ae2593436be8b9a058aad6  patch-2.MPQ
a9ad25c9a32600dd3c71f97a0f95f9b9b629a9995988b928975c8871f1197683  patch.MPQ
6ba131da952aae8d1e061b54468fd6e5d2ef78616540e2746ed21255d6b959a7  sound.MPQ
a1564120452cd75c4c7b2002a668b12250a35dab658816a33b591ebb23004f52  speech.MPQ
68fda6fb4f57051a47a0a56ff1757d73ee5c2a870774ba60ee8b52d7b36bc61d  terrain.MPQ
7e5996d2a0a2de03c79dcf9ab78f3fce66264688eee56ca6dbc51c8ce4433dac  texture.MPQ
9933d9ca23d481647880c9798dc7c225cd926f51026d148f09cd5251fc56edb7  wmo.MPQ

Building `GnomeragonInstance` for 1.12 trips assert

When building GnomeragonInstance the following backtrace happens:

__pthread_kill_implementation (no_tid=0, signo=6, threadid=140737352534080) at ./nptl/pthread_kill.c:44
44      ./nptl/pthread_kill.c: No such file or directory.
(gdb) bt
#0  __pthread_kill_implementation (no_tid=0, signo=6, threadid=140737352534080) at ./nptl/pthread_kill.c:44
#1  __pthread_kill_internal (signo=6, threadid=140737352534080) at ./nptl/pthread_kill.c:78
#2  __GI___pthread_kill (threadid=140737352534080, signo=signo@entry=6) at ./nptl/pthread_kill.c:89
#3  0x00007ffff7842476 in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#4  0x00007ffff78287f3 in __GI_abort () at ./stdlib/abort.c:79
#5  0x00007ffff782871b in __assert_fail_base (fmt=0x7ffff79dd150 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", assertion=0x5555556aa120 "chunkX >= 0 && chunkY >= 0 && chunkX < MeshSettings::ChunksPerAdt && chunkY < MeshSettings::ChunksPerAdt",
    file=0x5555556aa0d0 "./namigator/utility/MathHelper.cpp", line=108, function=<optimized out>) at ./assert/assert.c:92
#6  0x00007ffff7839e96 in __GI___assert_fail (assertion=0x5555556aa120 "chunkX >= 0 && chunkY >= 0 && chunkX < MeshSettings::ChunksPerAdt && chunkY < MeshSettings::ChunksPerAdt",
    file=0x5555556aa0d0 "./namigator/utility/MathHelper.cpp", line=108, function=0x5555556aa078 "static void math::Convert::WorldToAdt(const math::Vector3&, int&, int&, int&, int&)") at ./assert/assert.c:101
#7  0x0000555555610ee6 in math::Convert::WorldToAdt (vertex=..., adtX=@0x7fffffffd5c4: 30, adtY=@0x7fffffffd5c8: 33, chunkX=@0x7fffffffd5cc: 16, chunkY=@0x7fffffffd5d0: 0)
    at ./namigator/utility/MathHelper.cpp:108
#8  0x00005555555c928c in parser::(anonymous namespace)::UpdateBounds (bounds=..., vertex=..., adtChunks=std::set with 265 elements = {...}) at ./namigator/parser/Wmo/WmoInstance.cpp:39
#9  0x00005555555c9590 in parser::WmoInstance::WmoInstance (this=0x555555e0a550, wmo=0x555555c413e0, doodadSet=0, nameSet=0, bounds=..., transformMatrix=...) at ./namigator/parser/Wmo/WmoInstance.cpp:68
#10 0x00005555555d4d80 in std::make_unique<parser::WmoInstance, parser::Wmo const*, unsigned short&, unsigned short&, math::BoundingBox&, math::Matrix&> () at /usr/include/c++/11/bits/unique_ptr.h:962
#11 0x00005555555d2c4d in parser::Map::Map (this=0x555555c2beb0, name="GnomeragonInstance") at ./namigator/parser/Map/Map.cpp:207
#12 0x000055555558b2d8 in std::make_unique<parser::Map, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&> () at /usr/include/c++/11/bits/unique_ptr.h:962
#13 0x00005555555825a4 in MeshBuilder::MeshBuilder (this=0x555555a1dd80, outputPath=filesystem::path ".", mapName="GnomeragonInstance", logLevel=0) at ./namigator/MapBuilder/MeshBuilder.cpp:462
#14 0x0000555555560fc5 in std::make_unique<MeshBuilder, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, int&> ()
    at /usr/include/c++/11/bits/unique_ptr.h:962
#15 0x000055555555efa7 in main (argc=9, argv=0x7fffffffe188) at ./namigator/MapBuilder/main.cpp:241

SHA256sums of MPQs:

0bb2d6d370d825353eff5d9282c545a1b61980baaa5b7b65b1a7521e0ee8e27a  /home/asd/Downloads/Data112/backup.MPQ
f648e4fae190abcb25749ddbe96454e7e0de7e9c7e955983ed9d0e73b6986009  /home/asd/Downloads/Data112/base.MPQ
d9d5a290bdad848e177e2731c7ef221a1d7a6793e2c94e431488dd40816101e2  /home/asd/Downloads/Data112/dbc.MPQ
511189160f091eeb9d7ee8c473c1422b7f1fadbd9b65bfbf7d0a2a344103312d  /home/asd/Downloads/Data112/fonts.MPQ
6545dfbb3ef21a8b7f36b577419494cc292fec35585f9a1511d6c8b692b83191  /home/asd/Downloads/Data112/interface.MPQ
13aee674db39fc605c8aabf964eda0bb7895c6f026fed6c508bf2f9d155db0f9  /home/asd/Downloads/Data112/misc.MPQ
a7aa78c234bbdd450e00434e5939aa1a02383df1971cddcbfa181d68e9ab45a2  /home/asd/Downloads/Data112/model.MPQ
84f506c9f049f1e35f6d0f7b2e6643d28856888680ae2593436be8b9a058aad6  /home/asd/Downloads/Data112/patch-2.MPQ
a9ad25c9a32600dd3c71f97a0f95f9b9b629a9995988b928975c8871f1197683  /home/asd/Downloads/Data112/patch.MPQ
6ba131da952aae8d1e061b54468fd6e5d2ef78616540e2746ed21255d6b959a7  /home/asd/Downloads/Data112/sound.MPQ
a1564120452cd75c4c7b2002a668b12250a35dab658816a33b591ebb23004f52  /home/asd/Downloads/Data112/speech.MPQ
68fda6fb4f57051a47a0a56ff1757d73ee5c2a870774ba60ee8b52d7b36bc61d  /home/asd/Downloads/Data112/terrain.MPQ
7e5996d2a0a2de03c79dcf9ab78f3fce66264688eee56ca6dbc51c8ce4433dac  /home/asd/Downloads/Data112/texture.MPQ
9933d9ca23d481647880c9798dc7c225cd926f51026d148f09cd5251fc56edb7  /home/asd/Downloads/Data112/wmo.MPQ

Transport support

Transports have their own coordinate system. A couple of questions which need answers:

Can you be feared, blink, or charge on to or off of a transport?
Is the behavior the same between boats/zeppelins and elevators?

Skettis

The whole Terokkar forest - skettis zone is a bit of a rough spot. Mobs are supposed to path onto those treehouses and whatnot. There isn't a specific place where it broken, but generally its not working as its supposed to. Tobschinski had huge issues with this.

Precise z values query for a given (x, y)

Retail sniffs of splines show that the first and last hop on a path have extremely precise values for Z. Intermediate hops can be less accurate. This is probably because for start and stop a more expensive query is used. Currently I plan to use Detour's detail mesh for the intermediate hops and a custom high precision query for the start and stop.

Retail sniff examples (from Azeroth / map 0):

[0] Waypoint: X: 1111.479 Y: -1818.246 Z: 63.10447 actual z: 63.043503	z - actual = 0.060967
[1] Waypoint: X: 1112.965 Y: -1830.395 Z: 62.19612 actual z: 61.473637	z - actual = 0.722483
[2] Waypoint: X: 1113.965 Y: -1837.395 Z: 61.44612 actual z: 61.092140	z - actual = 0.35398
[3] Waypoint: X: 1114.715 Y: -1841.145 Z: 60.94612 actual z: 60.915379	z - actual = 0.030741

[0] Waypoint: X: 1111.479 Y: -1818.246 Z: 63.10447 actual z: 63.043503	z - actual = 0.060967
[1] Waypoint: X: 1112.965 Y: -1830.395 Z: 62.19612 actual z: 61.473637	z - actual = 0.722483
[2] Waypoint: X: 1113.965 Y: -1837.395 Z: 61.44612 actual z: 61.092140	z - actual = 0.35398
[3] Waypoint: X: 1114.715 Y: -1841.145 Z: 60.94612 actual z: 60.915379	z - actual = 0.030741

It is probably the lack of the high precision stop values that ultimately cause players falling through the world following server-controlled movement (from charge, blink, etc.).

query_z wrong inside caves

Example 1: Map 0 ADT 50, 31 -9849.028, 134.545, 5.815 query_z returns a list of three identical values of 35.582
Example 2: Map 0, ADT 48, 32 -8617.701, -147.215, 87.239 query_z returns a list of three identical values of 145.589

Heavier weight on water-flagged mesh polygons

Must weigh mesh polys which require swimming to traverse them more heavily (proportional with swim speed versus run speed).

Correct MPQ load order

Some files exist in multiple MPQs. To get the right data, we have to get the load order correct. This issue will serve as a placeholder for all specific issues that getting this wrong can cause.

Examples:

World\maps\Azeroth\Azeroth_33_28.adt exists in world.mpq and common.mpq. common.mpq contains the correct version.
DBFilesClient\AreaTable.dbc exists in enUS\locale-enUs.mpq, enUS\patch-enUS.mpq, and enUS\patch-enUS-2.mpq. Not sure which is correct but locale-enUS.mpq is definitely wrong.
world\wmo\outland\floatingrocks\nagrand_rockfloating_waterfalls.wmo exists in expansion.mpq and expansion1.MPQ, and expansion1.MPQ contains the correct version

Pet pathing behavior

This will probably not be handled by the API, but this is a useful video anyway:

https://youtu.be/lXe_ChXstEQ

Use std::filesystem::path instead of std::string for paths

This is now more standard.

Slave Pens

(@Guid,1,-261.6143,-675.7715,10.54156,0,0,0,0,0,0,0,0,0,0,0,0),
(@Guid,2,-246.7325,-683.1629,15.52901,0,0,0,0,0,0,0,0,0,0,0,0),
(@Guid,3,-238.0786,-686.4232,18.47306,0,0,0,0,0,0,0,0,0,0,0,0),
(@Guid,4,-227.7346,-690.909,22.02582,0,0,0,0,0,0,0,0,0,0,0,0),
(@Guid,5,-217.9532,-695.7503,26.76936,0,0,0,0,0,0,0,0,0,0,0,0),
(@Guid,6,-208.0547,-701.3806,34.94818,0,0,0,0,0,0,0,0,0,0,0,0),
(@Guid,7,-204.0264,-702.2903,37.2308,0,0,0,0,0,0,0,0,0,0,0,0),
(@Guid,8,-199.4935,-705.5977,37.80273,0,0,0,0,0,0,0,0,0,0,0,0);

The area underwater in map 547 - slave pens, is fishy (pun intended) because it causes quagmirran to run zig zag instead of straight out of water. Note: with these coords he should never leave the ground. This is sniffed retail coords data so should be applicable to namigator too.

Indoor/outdoor query

Must be able to query whether a given (x,y,z) is indoors or outdoors

Cross platform build

Make sure compilation works under Linux, FreeBSD. ARM?

Building maps for 1.12 trips assertion

When attempting to build the Azeroth map for 1.12 with the following files:

0bb2d6d370d825353eff5d9282c545a1b61980baaa5b7b65b1a7521e0ee8e27a  backup.MPQ
f648e4fae190abcb25749ddbe96454e7e0de7e9c7e955983ed9d0e73b6986009  base.MPQ
d9d5a290bdad848e177e2731c7ef221a1d7a6793e2c94e431488dd40816101e2  dbc.MPQ
511189160f091eeb9d7ee8c473c1422b7f1fadbd9b65bfbf7d0a2a344103312d  fonts.MPQ
6545dfbb3ef21a8b7f36b577419494cc292fec35585f9a1511d6c8b692b83191  interface.MPQ
13aee674db39fc605c8aabf964eda0bb7895c6f026fed6c508bf2f9d155db0f9  misc.MPQ
a7aa78c234bbdd450e00434e5939aa1a02383df1971cddcbfa181d68e9ab45a2  model.MPQ
84f506c9f049f1e35f6d0f7b2e6643d28856888680ae2593436be8b9a058aad6  patch-2.MPQ
a9ad25c9a32600dd3c71f97a0f95f9b9b629a9995988b928975c8871f1197683  patch.MPQ
6ba131da952aae8d1e061b54468fd6e5d2ef78616540e2746ed21255d6b959a7  sound.MPQ
a1564120452cd75c4c7b2002a668b12250a35dab658816a33b591ebb23004f52  speech.MPQ
68fda6fb4f57051a47a0a56ff1757d73ee5c2a870774ba60ee8b52d7b36bc61d  terrain.MPQ
7e5996d2a0a2de03c79dcf9ab78f3fce66264688eee56ca6dbc51c8ce4433dac  texture.MPQ
9933d9ca23d481647880c9798dc7c225cd926f51026d148f09cd5251fc56edb7  wmo.MPQ

Namigator fails with:

parser/Adt/Adt.cpp:339: parser::Adt::Adt(parser::Map*, int, int): Assertion `mclqBlock->RenderMap[y][x] != 8' failed.

My best guess is that x = 4 and y = 3, although this might not be entirely correct.
My debugger was not able to connect within a reasonable time, and printing out the values through std::cout had weird behavior. Calling exit(1) when mclqBlock->RenderMap[y][x] == 8 consistently produced those values.

Make temporary obstacles and serializing of heightfield optional

This will save considerable RAM and disk space at the expense of having no support for temporary obstacles.

Better string pulling to polish final path

Quoted from oiramario:

when agent move from A to B will fall off to conner. map id 532(Karazahn).