MMaps Redux

faramir118 · August 23, 2010

Ok, new stuff is pushed.

Changes to the core again.

Still need to update VC90 and automake build files.

KiriX · August 23, 2010

Is need re-extract maps and vmaps?

Work well =) One bug - npc correct found path if I attacked them, but then I turn on GM - they return to their spawnpoint without any pathfind =(

faramir118 · August 23, 2010

That's not a bug, I just haven't put pathfinding into HomeMovementGenerator.

This update fixes the some things in recast, most notably the crash that occurred when building Kalimdor with liquids enabled.

Current state:

* Terrain types work

* If a complete path is found, creature will follow path

* If a complete path is not found, default to old movement behavior (run through things)

Otherwise, the creature would just stand there instead of switch targets or evade. Pathfinding during aggro/threat logic will fix this.

* Deleted some simple optimization attempts which, upon further study, could possibly make invalid or unoptimal paths.

* VC90 update will be here in the next couple days, just need to get my work computer up to date.

* Probably need someone to help with automake stuff, since I have no way to test it

You don't need to re-extract maps. Liquids work now, but because of #3 above they don't work in all cases.

KiriX · August 24, 2010

That's not a bug, I just haven't put pathfinding into HomeMovementGenerator.

At youtube video npc return to spawnpoint with using pathfinding. I think that you will add pathfinding into HomeMovementGenerator soon (then it's done ).

And big thanks for the realy great work!!!

Schmoozerd · August 24, 2010

@ faramir:

This is still far in the feature, but I had also some target-selecting problems for some bosses, and I think the correct place to modify is the SelectHostileTarget() function.

I think what we need in the ChaseMovement case is a way to only select units, to which a path is possible, but I wouldn't modify the threat-list

fabian · August 31, 2010

Compile error fix for latest mangos rev:

diff --git a/src/game/MoveMap.cpp b/src/game/MoveMap.cpp
index 9994f23..c337bf7 100644
--- a/src/game/MoveMap.cpp
+++ b/src/game/MoveMap.cpp
@@ -1,7 +1,7 @@

#include "Map.h"
#include "Log.h"
-#include "Utilities/UnorderedMap.h"
+#include "Utilities/UnorderedMapSet.h"
#include "World.h"

inline uint32 packTileID(uint32 tileX, uint32 tileY) { return tileX<<16 | tileY; }

and maybe we can drop this not used variable and fix some warnings:

--- a/src/game/PathFinder.cpp
+++ b/src/game/PathFinder.cpp
@@ -50,10 +50,8 @@ dtPolyRef PathInfo::getPathPolyByPosition(float x, float y, float z)
bool PathInfo::isPointInPolyBounds(float x, float y, float z, float &distance, dtPolyRef polyRef)
{
    float point[3] = {y, z, x};
-    int polyindex;
-
    const dtMeshTile* tile;
-    const dtPoly* poly;
+
    if(!m_navMesh->getTileAndPolyByRef(polyRef, &tile, &poly))
        return false;   // m_pathPolyRefs[i] is invalid

diff --git a/src/game/PathFinder.h b/src/game/PathFinder.h
index 0144ab4..cc53c00 100644
--- a/src/game/PathFinder.h
+++ b/src/game/PathFinder.h
@@ -65,6 +65,8 @@ class PathInfo
        dtNavMeshQuery* m_navMeshQuery;     // the nav mesh query used to find the path
        PathType        m_type;             // tells what kind of path this is

+        const dtPoly* poly;
+
    private:
        inline void clear()
        {

diff --git a/src/game/debugcmds.cpp b/src/game/debugcmds.cpp
index cf0353d..df1d777 100644
--- a/src/game/debugcmds.cpp
+++ b/src/game/debugcmds.cpp
@@ -366,7 +366,6 @@ bool ChatHandler::HandleDebugMoveMapCommand(const char* args)
        // navmesh poly -> navmesh tile location
        dtPolyRef polyRef = query->findNearestPoly(location, extents, &(dtQueryFilter()), NULL);
        const dtMeshTile* tile;
-        const dtPoly* poly;

        if(!poly)
            PSendSysMessage("Dt     [??,??] (invalid poly, probably no tile loaded)");

diff --git a/src/game/Chat.h b/src/game/Chat.h
index bdb12ce..b86e225 100644
--- a/src/game/Chat.h
+++ b/src/game/Chat.h
@@ -651,6 +658,8 @@ class ChatHandler
        void HandleCharacterDeletedRestoreHelper(DeletedInfo const& delInfo);

        void SetSentErrorMessage(bool val){ sentErrorMessage = val;};
+
+    const dtPoly* poly;
    private:
        WorldSession * m_session;                           // != NULL for chat command call and NULL for CLI command

ascent · September 2, 2010

anyone make patch file?

fabian · September 2, 2010

I have 3 merge conflicts with the latest mangos and than one compile error

diff --git a/src/game/MoveMap.cpp b/src/game/MoveMap.cpp
index 9994f23..c337bf7 100644
--- a/src/game/MoveMap.cpp
+++ b/src/game/MoveMap.cpp
@@ -1,7 +1,7 @@

#include "Map.h"
#include "Log.h"
-#include "Utilities/UnorderedMap.h"
+#include "Utilities/UnorderedMapSet.h"
#include "World.h"

inline uint32 packTileID(uint32 tileX, uint32 tileY) { return tileX<<16 | tileY; }

and the other things arefixes for the compile warnings

faramir118 · September 2, 2010

Merged with 10434

faramir118 · September 3, 2010

Added what I hope is a working automake config for Detour.

Can gcc users please test?

nitrogenoxide · September 3, 2010

Fixes compiling Detour/Recast with gcc. Tested compile with gcc 4.4.3 under x86_64. Builds cleanly, didn't do a test run.

Patch is against 17aa80a

diff --git a/configure.ac b/configure.ac
index 1a8cd08..fb6490c 100644
--- a/configure.ac
+++ b/configure.ac
@@ -283,6 +283,7 @@ AC_CONFIG_FILES([
   dep/lib/Makefile
   dep/recastnavigation/Makefile
   dep/recastnavigation/Detour/Makefile
+   dep/recastnavigation/Recast/Makefile
   dep/src/Makefile
   dep/src/g3dlite/Makefile
   dep/src/zlib/Makefile
diff --git a/dep/recastnavigation/Detour/Makefile.am b/dep/recastnavigation/Detour/Makefile.am
index fe6b8dc..46fe3a3 100644
--- a/dep/recastnavigation/Detour/Makefile.am
+++ b/dep/recastnavigation/Detour/Makefile.am
@@ -3,7 +3,7 @@
## Sub-directories to parse

## CPP flags for includes, defines, etc.
-AM_CPPFLAGS = $(MANGOS_INCLUDES) -I$(srcdir)
+AM_CPPFLAGS = $(MANGOS_INCLUDES) -I$(srcdir)/Include

## Build detour as convenience library.
noinst_LIBRARIES = libdetour.a
diff --git a/dep/recastnavigation/Makefile.am b/dep/recastnavigation/Makefile.am
index de13c8b..58d22c9 100644
--- a/dep/recastnavigation/Makefile.am
+++ b/dep/recastnavigation/Makefile.am
@@ -1 +1 @@
-SUBDIRS = Detour
\\ No newline at end of file
+SUBDIRS = Detour Recast
diff --git a/dep/recastnavigation/Recast/Makefile.am b/dep/recastnavigation/Recast/Makefile.am
new file mode 100644
index 0000000..9937f0c
--- /dev/null
+++ b/dep/recastnavigation/Recast/Makefile.am
@@ -0,0 +1,26 @@
+## Process this file with automake to produce Makefile.in
+
+## Sub-directories to parse
+
+## CPP flags for includes, defines, etc.
+AM_CPPFLAGS = $(MANGOS_INCLUDES) -I$(srcdir)/Include
+
+## Build recast as convenience library.
+noinst_LIBRARIES = librecast.a
+librecast_a_SOURCES = \\
+    Source/Recast.cpp \\
+    Source/RecastAlloc.cpp \\
+    Source/RecastArea.cpp \\
+    Source/RecastContour.cpp \\
+    Source/RecastFilter.cpp \\
+    Source/RecastMesh.cpp \\
+    Source/RecastMeshDetail.cpp \\
+    Source/RecastRasterization.cpp \\
+    Source/RecastRegion.cpp
+
+## Additional files to include when running 'make dist'
+#  Source and header files for recast
+EXTRA_DIST = \\
+    Include/Recast.h \\
+    Include/recastAlloc.h \\
+    Include/RecastAssert.h
diff --git a/src/mangosd/Makefile.am b/src/mangosd/Makefile.am
index d8dff41..669f5d9 100644
--- a/src/mangosd/Makefile.am
+++ b/src/mangosd/Makefile.am
@@ -47,8 +47,8 @@ mangos_worldd_LDADD = \\
    ../shared/Auth/libmangosauth.a \\
    ../shared/libmangosshared.a \\
    ../shared/vmap/libmangosvmaps.a \\
-    ../shared/pathfinding/Detour/libmangosdetour.a \\
-    ../shared/pathfinding/Recast/libmangosrecast.a \\
+    ../../dep/recastnavigation/Detour/libdetour.a \\
+    ../../dep/recastnavigation/Recast/librecast.a \\
    ../framework/libmangosframework.a \\
    ../../dep/src/g3dlite/libg3dlite.a \\
    ../../dep/src/gsoap/libgsoap.a
diff --git a/src/shared/Makefile.am b/src/shared/Makefile.am
index 83d2e4e..6c711c6 100644
--- a/src/shared/Makefile.am
+++ b/src/shared/Makefile.am
@@ -17,7 +17,7 @@
## Process this file with automake to produce Makefile.in

## Sub-directories to parse
-SUBDIRS = Auth Config Database vmap pathfinding
+SUBDIRS = Auth Config Database vmap

## CPP flags for includes, defines, etc.
AM_CPPFLAGS = $(MANGOS_INCLUDES) -I$(top_builddir)/src/shared -I$(srcdir) -I$(srcdir)/../../dep/include -I$(srcdir)/../framework -I$(srcdir)/../shared -I$(srcdir)/../../dep/include/g3dlite  -DSYSCONFDIR=\\"$(sysconfdir)/\\"

faramir118 · September 3, 2010

Fixes compiling Detour/Recast with gcc. Tested compile with gcc 4.4.3 under x86_64. Builds cleanly, didn't do a test run.
Patch is against 17aa80a

Does it compile without Recast? Recast isn't necessary for core, and isn't used on Win32

edit: pushed a detour-only version of the above, please test

nitrogenoxide · September 3, 2010

Since you had recast in the libmangos config I had assumed it was necessary, sorry. I'll test it out now

EDIT: Tested 54c1fb7, builds fine, same system specs.

qsa · September 4, 2010

Hey there,

I had some time to play around so I thought it can be nice to contribute. ( its a lie - evil Gotisch put me into this! )

Anyhow, below is attached patch file with following changes:

* integrated pathfinding into HomeMovementGenerator.
* Better interface for PathInfo class.

mostly removing all things that should not be public to their proper place, some const definitions, etc.

* Optimizations

Pretty much cutting the number of new path generations by more than half.

There are multiple cases where we can save some findPath/findStraightPath uses.

For example when creature simply moves along its already generated path - we don't need to recalculate anything. Another case is when creature moves along its path but the target moved away, in this case we don't need to regenerate the entire path, we can keep the majority of the old one, and generating only the suffix. Sub-path of optimal path is optimal.

Overall, at the moment, in most cases full path only generated once and then adjusted. While in some trivial cases, like HomeMovement, both findPath and findStraightPath generated exactly once.

* Code centralization :

previously, poly-path was generated and adjusted in about 4 different functions, now it is in single one. Same goes for all other functionalities.

* General changes :

There are some minor general changes I made.

For example in isSamePoint() func. It used to just take two points and compare they xyz values ( == ), this is wrong in 90% of the time for our code, simply since 1.00001 and 1.0 is the same thing for our resolution, while it is not same point on map.

General, as long as the point is in delta from other point its the same ( used bounding distance for now ).

Removed copyVertex - we have this function in lib.

Added some defines, fixed some compile warnings, some redundant code ( like clean() uses ), etc ...

More or less tested ingame. I haven't notice any changes in behavior of creatures before and after. It doesn't mean there's no bugs

TODO: test under GCC, get some valgrind logs, both memleaks and profile data ( not really related to this patch )

Patch against 2010-09-03 change (54c1fb7ba4) :: http://pastie.org/1138603 updated

Take care.

Toinan67 · September 4, 2010

This is gonna be one of the greatest commit ever. Can't wait

qsa · September 4, 2010

I had to revise the patch a little bit after some testing.

If you get the initial version, please re-download

http://pastie.org/1138603 initial post link updated as well.

Sorry, there was problem with maps w/o move mesh attached.

faramir118 · September 4, 2010

This is a lot of good work. I'm going to commit these changes, probably broken into smaller pieces.

RE: suffix optimization

There are some circumstances where the destination isn't just a small detour from the old path, like teleportation or jumping over gaps/ledges. In these cases, keeping the previous polyRefs could slow down findStraightPath, maybe even create a bad detour in the path. I can't think of a good way to detect this kind of thing, and I don't know how often it happens. Thoughts?

Schmoozerd · September 5, 2010

perhaps naive, but isn't this depending on the movement of the target (players mostly)

If you checked on their movement, if they jump, go into water, teleport, blink, etc and in this case trigger a new calculation of the path of the chaser, it should work well

qsa · September 5, 2010

About poly-path suffix optimization :

It is only heuristics, nothing more.

At the moment I take 80% of the original path and generate the sufix from the last poly to the target then joining them. Then fresh point-path is recalculated ( linear by the number of polygons in path )

This is always converges - if there was valid path, calculating fresh, we will get valid path here too. It may be less optimal.

It work like a magic in most of the time, but there are some corner cases.

Worst case scenario is unit making "U" shaped path.

Now.. how common is that "U" path? well, if you aren't trying to make one, you aren't very likely to notice it. It can be done in some very specific cases. For example ledges.

What can we do?

I was thinking about keeping track of the 3d arc (cone) between the last target position and the new one, the smaller the cone is, the less likely target changed its general direction, the more or the original path we should take. However, there's the old ledge problem - really tinny movement in extreme cases cause really big error.

The other thing, is looking for circles in generated poly-path. This will solve the ledge problem in almost all cases, but, as always we can generate something really nasty here It wont solve wide "U" paths, for example.

The real question is : should we do those? whats the optimal value of the path to take?

The best answer is making some ingame real tests, to figure out how the problem is really common. If it takes it, we can even add some debug variables to gather statistics, how many times each path-finding case was used, etc.

From tests I did while making it, in almost all cases, the longer path you have, the shorter sufix is going to be, it is always short. Simply since the target cannot move too far away in update interval. Even if blinking, you cover 2-4 poly the most, that's on uneven terrain.

I don't think its really major. Dare someone to prove me wrong

In general, there are couple values we may want to optimize in current code.

How ofter do we check for target changes in TargetedMovementGenerator, at the moment? it is set to 10 times a sec.

How close two points should be, to be considered the same point?

What portion of the old path do we take?

Ideas are welcomed.

PS: in general it can be really nice to get some valgrind profiler/memleak logs, if anyone can generate those, I'll be really grateful. Sorry, I don't have *nix environment with all the tools needed.

PSS: thanks.

qsa · September 6, 2010

Every time I have a slow day something comes out of it.

Anyhow, below is another patch with following changes :

* Implementing findSmoothPath. Actually taking it from NavMeshTesterTool and adjusting it to our needs, mehh... close enough .

The good news : it works, giving much nicer, smoother paths. The resolution can be set from defines.

The bad news is that it takes much more resources than the simple findStraightPath did. Not the "not computable" type of "more", but still something to consider when you talking about hundreds of creatures generating paths every moment.

Both options are available, the old and new algo, _USE_SMOOTH_PATH_ define is you're friend here. While on it, you can play with other related defines to figure which works the best.

* Added ResetUpdate(50) to HomeMovementGenerator to make creatures movement bit smoother. Its just temp hack, till we figure how to send the entire path at once. Speaking of which .. read down ... the wall of text.

* Cleared up a little bit sets of m_type, some of them were out of order. It isnt used yet, but may come handy some day.

* Changing abs() to fabsf() in float case, since GCC don't have it overloaded for float while vc does, thus using abs() in vc++ doing what you expect it to, but it will coert (sp? verb form of coercion ) the float to int and return you integer on gcc.
This is really evil bug to have. I wonder if there's similar problem in ,mangos code.

* Fixed little bug involving updateNextPosition() allocating bit more memory than it needs to hold the output point path. Nothing major.

I was also trying to send the entire path at once, using the SMSG_MONSTER_MOVE packet, following the example in Unit::SendMonsterMoveByPath(), but as soon as I send path longer than single point, the movement gets totally screwed.

Either I'm doing something really wrong, or the format we have is outdated.

If anyone have some packet logs with SMSG_MONSTER_MOVE sending multiple points, and not for flight-path, please do post.

Is it even intended to be used for anything but flight-paths?

Some help appreciated on this subject.

Patched against latest (1a564e686) http://pastie.org/1142606

Take care.

Patman128 · September 7, 2010

I was also trying to send the entire path at once, using the SMSG_MONSTER_MOVE packet, following the example in Unit::SendMonsterMoveByPath(), but as soon as I send path longer than single point, the movement gets totally screwed.
Either I'm doing something really wrong, or the format we have is outdated.

If anyone have some packet logs with SMSG_MONSTER_MOVE sending multiple points, and not for flight-path, please do post.

Is it even intended to be used for anything but flight-paths?

Some help appreciated on this subject.

I think I recall seeing this for some creatures in packet logs. I can see if I can find you a good example.

faramir118 · September 7, 2010

Nice work, this is promising. I would think that there is a better way to build a smooth path... those intervals are so inefficient.

Just two things:

* What are you using Recast.h for?
* It's coerce

Schmoozerd · September 7, 2010

A small idea about the abs problem:

perhaps you should ask vladimir about a new platform specific define MANGOS_ABS which replaces all std::abs or abs functions (and works for int and float) ?

Movement in Logs:

Monsters _do_ get a couple of waypoints, but I doubt that they are because of pathfinding, but I had the impression that they are sent due to 'normal' interpolation between waypoints.

However that this can work the MovementGenerator needs the list of the next waypoints, because otherwise it couldn't interpolate

Also the interpolation waypoints are sent in some other format (kind of diffs, they are just parsed there), so that's no surprise they weren't working

I'll give you an example:

http://paste2.org/p/978740

TOM_RUS · September 7, 2010

I was also trying to send the entire path at once, using the SMSG_MONSTER_MOVE packet, following the example in Unit::SendMonsterMoveByPath(), but as soon as I send path longer than single point, the movement gets totally screwed.

Either I'm doing something really wrong, or the format we have is outdated.

If anyone have some packet logs with SMSG_MONSTER_MOVE sending multiple points, and not for flight-path, please do post.

Is it even intended to be used for anything but flight-paths?

Some help appreciated on this subject.

There's a ByteBuffer method for writing packed vectors exists:

       // can be used in SMSG_MONSTER_MOVE opcode
       void appendPackXYZ(float x, float y, float z)
       {
           uint32 packed = 0;
           packed |= ((int)(x / 0.25f) & 0x7FF);
           packed |= ((int)(y / 0.25f) & 0x7FF) << 11;
           packed |= ((int)(z / 0.25f) & 0x3FF) << 22;
           *this << packed;
       }

All points should be written relative to middle of path:

mid.X = (curr.X + dest.X) * 0.5f;
mid.Y = (curr.Y + dest.Y) * 0.5f;
mid.Z = (curr.Z + dest.Z) * 0.5f;

float x = mid.X - waypoint[n].X;
float y = mid.Y - waypoint[n].Y;
float z = mid.Z - waypoint[n].Z;
packet.appendPackXYZ(x, y, z);

And full SMSG_MONSTER_MOVE structure: http://mywowtools.googlecode.com/svn/trunk/WowTools/src/WoWPacketViewer/Parsers/MonsterMoveParser.cs

Some packet examples: http://paste2.org/p/978981

Unkle Nuke · September 8, 2010

Between your recent contributions and faramir's brilliant work, this is going to be one of the most epic commits to the core, once it is finished.

This will be a quantum leap forward in server mechanics that will open up so many other possibilities! I sure hope the two of you will work together to make it possible for NPCs to inhabit transports as your next project.

You have my sincere thanks for the work you've done thus far, faramir and qsa.

Sign In

MMaps Redux

Recommended Posts

Link to comment

Share on other sites

Top Posters In This Topic

Popular Days

Top Posters In This Topic

Popular Days

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Recently Browsing 0 members

Contact Us

Repositories

Important Information