Jump to content

MMaps Redux


Guest auntieMangos

Recommended Posts

"Another wall of text, that about 4 users will read."

"Sorry for "bit long" post,"

No, really, here are many guys who take glimpses at the code, but don't really know what the code is about, but these "long, stupid, boring" texts are the most intersting things around in mangos forums at all, because they show where the _problems_ are, and what solutions could be used, that's by far more intersting then a "added patch for recent rev" post.

So, what I am saying: Keep up these long posts, they are intersting for all of us who are interested in design questions ;)

And btw thank you for your work, mmaps are both important and interesting!

Link to comment
Share on other sites

  • Replies 1.2k
  • Created
  • Last Reply

Top Posters In This Topic

This touches on another subject: The aggro logic will need to be able to create paths, select a complete one, then store it where the movement generator can access it:...

Why does the Aggro logic have to select a Path? If by Aggro Logic you mean the AI, its job is: to decide which Target to attack, if Target is in range attack him, if not set goal for movementgenerator to the Target (and lots of other high level stuff).

Job of Movementgenerator is to decide how to get form current location to location of target and do the actual movement, or not?

Link to comment
Share on other sites

Someone suggested this (it was many pages back, sorry for not giving credit):

When a monster aggros, mangos core finds and aggros all nearby creatures.

Tie into that mechanism, and generate a path for all of them at once.

Just some things to look out for:

  • * Need to check the filter that was applied to the path, just in case a walking-only creature is grouped with a swimming creature.
    * Need to copy path, not use the same one.

This should reduce the number of paths that need to be generated, is selective, and means we don't have to create a cache/pool mechanism.

Link to comment
Share on other sites

On a bit different subject: do you think we should implement pathfinding into WaypointM ovementGenerator too?

It can sure make making those database path much simpler and shorter, but ...

If I may say so, waypoints will need pathfinding too : we would have a cpu loss with the path generation between 2 waypoints, but it's _only one time_. When the path is generated, we won't have to modify it : it will be just "move at this exact point".

As you said, waypoints tables will be _much_ simpler, we won't have to add thousands of wp to follow the ground level and slopes.

And btw thanks for the link you gave me, qsa. I strongly recommend it to everyone :)

Link to comment
Share on other sites

Why does the Aggro logic have to select a Path?

An example is the best answer:

Bob is a melee-only creature.

Bob enters combat.

If Bob cannot reach a target, it is not an attackable target.

Bob must evade+reset when he has no attackable targets.

The evasion code is tied to aggro, in Unit::selectHostileTarget()

By the time Bob MovementGenerator is active, we are already finished with selectHostileTarget() and can't see if another target on the threat list is reachable if there is no path (and can't enter evade mode if there are no reachable targets).

Link to comment
Share on other sites

I think not, the AI only needs to know, if a enemy is "reachable"

The one enemie case is (main points):

MoveLoS -> AttackStart -> MoveChase -> Creates the path

SelectHostileTarget -> AttackStart

For multiple enemies case I suspect the most generic case will be:

MoveLos -> AttackStart -> MoveChase -> Create path (to first victim)

collect more enemies

SelectHostileTarget: check if target is 'reachable' before selecting it, if not, try the next target.

if no target is reachable:

select targets that might be reachable for a spell (like fireballs) (I think such a spellId should be taken from DB)

if no targets available, select most-aggro enemie, start evade mode timer, perhaps chase to the nearest place possible

Link to comment
Share on other sites

sorry for editing my post makes yours seem a bit out of context :).

but to see if a enemy is reachable, the function calls isInAccessablePlaceFor() which at the moment only does:

if(IsInWater())
       return c->canSwim();
   else
       return c->canWalk() || c->canFly();

here it should check if there is a path from creature to target.

Link to comment
Share on other sites

An example is the best answer:

Bob is a melee-only creature.

Bob enters combat.

If Bob cannot reach a target, it is not an attackable target.

Bob must evade+reset when he has no attackable targets.

The evasion code is tied to aggro, in Unit::selectHostileTarget()

...

This isn't how it works on retail (should we stick to it?)

They use "best effort" algorithm. "Bob cannot reach a target" -> he doesn't evade, he gets as close to the target as he can and waits till better opportunity arrives ( target moves where he can reach him).

This is pretty logical considering cases like : you mount up, fly just over the heads of creatures, they follow you till you land ( on the ground ), or out of their range.

Aggro mechanism has nothing to do with paths themselves, as I see it.

Therefore I don't think we need to know if there's full/valid path to the target as soon as isInAccessablePlaceFor() or similar.

Link to comment
Share on other sites

There was a discution somewhere in this thread.

On retail, if mob can reach you he will wait for a amount of time in combat mode, then evade. I suspect this wait timer is reinitialized whenever the target move (the path even incomplete to the target as change). I don't think a player could kill mobs without being hit in return.

Link to comment
Share on other sites

There was a discution somewhere in this thread.

On retail, if mob can reach you he will wait for a amount of time in combat mode, then evade. I suspect this wait timer is reinitialized whenever the target move (the path even incomplete to the target as change). I don't think a player could kill mobs without being hit in return.

On offy the path finding is not optimal at all and may fail easiely, then bliz desided to prevent hack: if a creature can't reach you in a simple manner, it becomes immunized to damages then reset health and return to spawn point. With navmeshes, I am sure this will occur a lot less than on offy. I think it's not a necessity here to make the navigation as bugged as on offy, at least not on purpose.

Moreover, I am very impressed by the progresses made here. It you look back 1 year in past, we where loading maps and vmaps objects then using a start point to put a point on the ground, then using ray of light to draw the next one... until the grid was full of points... in a BSP-Tree.. And when we did the meshes, we connected the points to make triangles in such a complex tree that it was impossible to make a usage of the data. Now you have a nav-mesh using polygons... I would be pleased to see the same on offy :P

Last note on this (this is maybe done, I did not look at the sources) don't forget to put the high available on top of each polygon attached to the polygon, then the navigation system may know where for example under a small bridge a npc can go and a vehicle cannot. This is also usefull later for flying mobs since you can extend the meshes to "3D" by extruding the polygons in Z direction.

Link to comment
Share on other sites

Just finishing up implementing the smooth path patch on my repo.

I noticed some recalculations in TargetedMovementGenerator::_setTargetLocation() due to GetContactPoint()/GetClosePoint() changing the destination position. Probably something we want to handle better, maybe set the endPosition equal to the target creature's exact location, then stop short?

Link to comment
Share on other sites

Just finishing up implementing the smooth path patch on my repo.

I noticed some recalculations in TargetedMovementGenerator::_setTargetLocation() due to GetContactPoint()/GetClosePoint() changing the destination position. Probably something we want to handle better, maybe set the endPosition equal to the target creature's exact location, then stop short?

If you talking about flying/unreachable target, then it is solved in last patch.

Since GetContactPoint() return ground level, if target was flying (and you cannot), it was always out of range, thus it every update loop tried to calculate new path and failed every time.

Anyhow, here's another patch with following additions :

  • * Everything from posts #333 , #351
    * removed PathInfo::isPointInPolyBounds, this is redundant code, check new PathInfo::getPathPolyByPosition implementation.
    * Pathfinding integration into WaypointMovementGenerator, in between the points.
    * Partially "solving" pathfinding for flying creatures. Non-flying creatures will follow you on the ground till out of range ( if you are flying ). If you landed and there's no path, shortcut will be used.

It isn't the best solution, we'll have to implement evade on last case, but it is "testable".

patched against 1a564e68647a39 :: http://pastie.org/1151815

Take care.

Link to comment
Share on other sites

I would move one commentar in PathFinder.h and there is a little typo: NODE must be NOTE:


diff --git a/src/game/PathFinder.h b/src/game/PathFinder.h
index 8340cd5..01d1875 100644
--- a/src/game/PathFinder.h
+++ b/src/game/PathFinder.h
@@ -109,8 +109,9 @@ class PathInfo
        bool isPointInPolyBounds(float x, float y, float z, float &distance, dtPolyRef polyRef);

        void BuildFreshPath();
+
+        // NOTE: startPos, endPos is in Y, Z, X format!
        void BuildPath(dtPolyRef startPoly, float* startPos, dtPolyRef endPoly, float* endPos);
-        // NODE: startPos, endPos is in Y,Z,X format!

        void updateNextPosition();
        void shortcut();

Link to comment
Share on other sites

don't forget to put the high available on top of each polygon attached to the polygon, then the navigation system may know where for example under a small bridge a npc can go and a vehicle cannot. This is also usefull later for flying mobs since you can extend the meshes to "3D" by extruding the polygons in Z direction.

Hm, recast doesn't have this built in. Instead, it only builds polygons which have a specified vertical clearance above them.

I suppose it could be done with some modifications, as it might allow for easier 3D navigation (flying and swimming). I'll add it to the end of the list ;)

If you talking about flying/unreachable target, then it is solved in last patch.

No, I think it was caused when GetClosePoint selects a point that doesn't lie on/near the path due to obstacles. As the monster follows the path, GetClosePoint eventually picks a point that is nearer to the path, but far enough from the old dest point that targetMoved is set to true. A good example is the last room in scarlet monastery armory - the initiates all recalculate their path when they circle around the player to get to the stairs in the back of the room.

Setting the destination point to the target's actual location will provide a better result.

This would require that the PathInfo class handle angle and offset values, instead of TargetedMovementGenerator.

Do you think this kind of change is worth it?

I also did a bit of testing with ACE_High_Res_Timer, with smooth paths, on a 2.4 ghz core 2 duo.

Most of the time it was less than 300 microseconds to build a path, but I saw a few around 600.

Updates that didn't require changing the poly or point path were 2-3 microseconds.

@qsa

I've made some changes to your code...

  • * clarified that m_pointPathPointer is an index to the point currently being travelled to, it should be >= 1
    * set m_type in BuildPath
    * changed path send algorithm in TargetedMovemengGenerator, a bit simpler
    * in SendMonsterMoveByPath, check unit flags to determine if unit is on a taxi (instead of splines)

I'll push the changes when I wake up in the morning..

Link to comment
Share on other sites

Hm, recast doesn't have this built in. Instead, it only builds polygons which have a specified vertical clearance above them.

Well...that's exactly what is needed, isn't it? :o

I also did a bit of testing with ACE_High_Res_Timer, with smooth paths, on a 2.4 ghz core 2 duo.

Most of the time it was less than 300 microseconds to build a path, but I saw a few around 600.

Updates that didn't require changing the poly or point path were 2-3 microseconds.

This seems to be quite low but :

600 microsec = 0.6 millisec => 0.6% of the map update interval just for one creature. Let's hope we won't have 170 creatures building a path at the same time ! (If i'm wrong just tell me)

Link to comment
Share on other sites

Well...that's exactly what is needed, isn't it? :o

It isn't. If I understood properly, it builds the polygons only if a fixed clearance is available, meaning that you pass a "hardcoded" value to recast and then it produces the polygons that fit this value. On top of this it should also attach to each polygon the real clearance available above it so that there is only one polygons graph created. With this extra info, different path could be built for different object's high, depending on the clearance required.

Link to comment
Share on other sites

I have a problem when compiling

5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(110) : warning C4996: 'strcat': This function or variable may be unsafe. Consider using strcat_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(79) : see declaration of 'strcat'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(120) : warning C4996: 'wcscat': This function or variable may be unsafe. Consider using wcscat_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(245) : see declaration of 'wcscat'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(178) : warning C4996: 'strcpy': This function or variable may be unsafe. Consider using strcpy_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(74) : see declaration of 'strcpy'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(188) : warning C4996: 'wcscpy': This function or variable may be unsafe. Consider using wcscpy_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(252) : see declaration of 'wcscpy'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(222) : warning C4996: 'strdup': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _strdup. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(207) : see declaration of 'strdup'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(266) : warning C4996: 'strncat': This function or variable may be unsafe. Consider using strncat_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(144) : see declaration of 'strncat'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(279) : warning C4996: 'wcsncat': This function or variable may be unsafe. Consider using wcsncat_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(268) : see declaration of 'wcsncat'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(320) : warning C4996: 'strncpy': This function or variable may be unsafe. Consider using strncpy_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(157) : see declaration of 'strncpy'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(329) : warning C4996: 'wcsncpy': This function or variable may be unsafe. Consider using wcsncpy_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(275) : see declaration of 'wcsncpy'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(513) : warning C4996: 'strtok': This function or variable may be unsafe. Consider using strtok_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(166) : see declaration of 'strtok'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_string.inl(524) : warning C4996: 'wcstok': This function or variable may be unsafe. Consider using wcstok_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\string.h(280) : see declaration of 'wcstok'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_stdlib.inl(140) : warning C4996: 'getenv': This function or variable may be unsafe. Consider using _dupenv_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\stdlib.h(447) : see declaration of 'getenv'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_stdlib.inl(152) : warning C4996: '_wgetenv': This function or variable may be unsafe. Consider using _wdupenv_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\stdlib.h(653) : see declaration of '_wgetenv'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_stdlib.inl(163) : warning C4996: '_itoa': This function or variable may be unsafe. Consider using _itoa_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\stdlib.h(465) : see declaration of '_itoa'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_stdlib.inl(176) : warning C4996: '_itow': This function or variable may be unsafe. Consider using _itow_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\stdlib.h(640) : see declaration of '_itow'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_stdlib.inl(242) : warning C4996: '_mktemp': This function or variable may be unsafe. Consider using _mktemp_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\io.h(206) : see declaration of '_mktemp'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_stdlib.inl(253) : warning C4996: '_wmktemp': This function or variable may be unsafe. Consider using _wmktemp_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\wchar.h(320) : see declaration of '_wmktemp'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_stdlib.inl(310) : warning C4996: 'putenv': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _putenv. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\stdlib.h(864) : see declaration of 'putenv'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_unistd.inl(59) : warning C4996: 'access': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _access. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\io.h(303) : see declaration of 'access'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_unistd.inl(131) : warning C4996: 'chdir': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _chdir. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\direct.h(127) : see declaration of 'chdir'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_unistd.inl(156) : warning C4996: 'rmdir': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _rmdir. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\direct.h(129) : see declaration of 'rmdir'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_unistd.inl(377) : warning C4996: 'getcwd': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _getcwd. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\direct.h(121) : see declaration of 'getcwd'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_unistd.inl(983) : warning C4996: 'swab': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _swab. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\stdlib.h(865) : see declaration of 'swab'
5>d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\dep\\ACE_wrappers\\ace/OS_NS_unistd.inl(1127) : warning C4996: 'unlink': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _unlink. See online help for details.
5>        D:\\Programy\\Microsoft Visual Studio 9.0\\VC\\include\\stdio.h(301) : see declaration of 'unlink'
2>SV_Semaphore_Simple.cpp
5>Creating library...
2>SV_Semaphore_Complex.cpp
5>Build log was saved at "file://d:\\mangos\\faramir118-mangos-v0.16-dev1-1496-g0d8929c\\faramir118-mangos-0d8929c\\win\\VC90\\framework__Win32_Release\\BuildLog.htm"
5>framework - 0 error(s), 24 warning(s)

I downloaded http://github.com/faramir118/mangos

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue. Privacy Policy Terms of Use