MMaps Redux

[Unik2psc]

compilation error:

eps/TaxiHandler.Tpo -c -o TaxiHandler.o ../../../src/game/TaxiHandler.cpp

../../../src/game/TargetedMovementGenerator.cpp: In member function 'void TargetedMovementGeneratorMedium<T, D>::_setTargetLocation(T&, bool)':

../../../src/game/TargetedMovementGenerator.cpp:114: error: no matching function for call to 'min(uint32&, long unsigned int&)'

../../../src/game/TargetedMovementGenerator.cpp: In member function 'void TargetedMovementGeneratorMedium<T, D>::_setTargetLocation(T&, bool) [with T = Player, D = ChaseMovementGenerator<Player>]':

../../../src/game/TargetedMovementGenerator.cpp:269: instantiated from here

../../../src/game/TargetedMovementGenerator.cpp:114: error: no matching function for call to 'min(uint32, long unsigned int)'

../../../src/game/TargetedMovementGenerator.cpp: In member function 'void TargetedMovementGeneratorMedium<T, D>::_setTargetLocation(T&, bool) [with T = Creature, D = ChaseMovementGenerator<Creature>]':

../../../src/game/TargetedMovementGenerator.cpp:281: instantiated from here

../../../src/game/TargetedMovementGenerator.cpp:114: error: no matching function for call to 'min(uint32, long unsigned int)'

../../../src/game/TargetedMovementGenerator.cpp: In member function 'void TargetedMovementGeneratorMedium<T, D>::_setTargetLocation(T&, bool) [with T = Player, D = FollowMovementGenerator<Player>]':

../../../src/game/TargetedMovementGenerator.cpp:339: instantiated from here

../../../src/game/TargetedMovementGenerator.cpp:114: error: no matching function for call to 'min(uint32, long unsigned int)'

../../../src/game/TargetedMovementGenerator.cpp: In member function 'void TargetedMovementGeneratorMedium<T, D>::_setTargetLocation(T&, bool) [with T = Creature, D = FollowMovementGenerator<Creature>]':

../../../src/game/TargetedMovementGenerator.cpp:352: instantiated from here

../../../src/game/TargetedMovementGenerator.cpp:114: error: no matching function for call to 'min(uint32, long unsigned int)'

make[3]: *** [TargetedMovementGenerator.o] Błąd 1

make[3]: *** Oczekiwanie na niezakończone zadania....

cat /proc/version

Linux version 2.6.32.2-xxxx-grs-ipv4-64 (---) (gcc version 4.3.2 (Debian 4.3.2-1.1) ) #1 SMP Tue Dec 29 14:41:12 UTC 2009

ACE libary external. ( --with-debug-info --disable-builtin-ace).

--- Edit:

diff --git a/src/game/TargetedMovementGenerator.cpp b/src/game/TargetedMovementGenerator.cpp

index 85eb3be..e060152 100644

--- a/src/game/TargetedMovementGenerator.cpp

+++ b/src/game/TargetedMovementGenerator.cpp

@@ -22,6 +22,7 @@

#include "Creature.h"

#include "DestinationHolderImp.h"

#include "World.h"

//+#include <algorithm>

//#include "ace/High_Res_Timer.h"

#define SMALL_ALPHA 0.05f

@@ -111,7 +112,12 @@ void TargetedMovementGeneratorMedium<T,D>::_setTargetLocation(T &owner, bool upd

if (m_pathPointsSent < 2 || startIndex == 1 || i_recalculateTravel || owner.IsStopped())

{

// send 10 nodes, or send all nodes if there are less than 10 left

- m_pathPointsSent = std::min(uint32(10), pointPath.size() - startIndex);

+ #ifdef WIN32

+ m_pathPointsSent = std::min(uint32(10), pointPath.size() - startIndex);

+ #else

+ m_pathPointsSent = ((uint32(10) < (pointPath.size() - startIndex)) ? uint32(10) : (pointPath.size() - startIndex));

+ #endif

+

uint32 endIndex = m_pathPointsSent + startIndex;

// dist to next node + world-unit length of the path

Maybe ?

[DJNefast]

no pb on x64 on linux & VS 2008

[faramir118]

lazy compiler... try this:

m_pathPointsSent = std::min(uint32(10), uint32(pointPath.size() - startIndex));

[qsa]

Had some slow days, had some time to make few changes.

• No more shortcuts :
  Basically, the path classification was remade, actually using path types.
  One of the key idea, is to use actual end position in addition to given end location.
  Those can differ if provided end position is not reachable. The old code just used to
  make a shortcut to destination, the new one will come as close as it can instead.
  If actual end and given end are close enough for NPC to attack, its all fine,
  if not, it will come as close as it can, and evade after 2sec.
  NPC will also evade on errors and such.
  I had to add variable into unit class to allow evading calls from movement generators,
  simply since it is pretty bad idea calling one generator from inside another.
  We may want to move it to Creature class instead, simple since players cannot evade.
  When I think of it, we may have problem with generating paths for players. Test case can be nice here.
  Had to add some logic on how the actual reachable position is calculated. Most of it done in
  BuildPolyPath().
  The only thing is missing right now is support for swimming. But we don't have liquids data ready yet, so no biggie.
  
• Rearranging code:
  If I had to change so many things, I figured its about time to arrange the code little bit better.
  Some functions renamed, others removed - all in favor centralizing and clear code.
  Now BuildPolyPath() responsible for all poly logic. From getting the polygons to generating the poly-paths.
  BuildPointPath() former known as updateNextPosition() will generate point paths.
  BuildFreshPath() was removed - it has no unique functionality.
  Also removing redundant public debug functions.
  
• changed some defines :
  Things like MAX_POINT_PATH_LENGTH/MAX_PATH_LENGTH had to be changed from their astronomical values.
  Path sized 2048 points with 6y intervals will give you maximal path length of ~12k - this is about the size of Outlands.
  We need to calculate optimal values there, but this is better than before. Also saves some memory.
  
• Added some debug prints, you can enable them using PRINT_DEBUG_INFO define.
  
• Changed how getPathPolyByPosition() work. It will use closestPointOnPoly() giving much better results with
  minimal performance penalty.
  
• BuildPointPath() can generate either findStraightPath or findSmoothPath depending on given parameter.
  It will come handy for things like charge.
  
• Couple memory leaks in debug command and some silly crash.
  
• Lots of small changes all over the place.
  

Basically : try it.

Patched against (213e909001) :: http://pastie.org/1199623

Suggestions, bug reports and test results are always welcomed.

There's one issue I did notice : some flying creatures will get some bumpy movement after being stunned/knockbacked

or casting. If I remember right, it was there before this patch, but it isn't on clean mangos.

Can be nice finding the source of this issue.

Testing is needed. Lots of it. While I did some (alot) on my own while writing the code, there're just to many cases to cover on my own.

PS: to the above posts : you can explicitly specify template parameter in calls : e.g. : std::min<uint32>(10, pointPath.size()) .

thus the parameter will be coerced to uint32.

PSS: Thanks in advance.

[faramir118]

Busy with work and class, but I'll look at the diff and merge it as soon as I get an opportunity!

edit:

I started work on WMO liquids, but got extremely sidetracked.

Managed to figure out how to find auras that liquids should apply, but it only works for ADT liquids (aka liquid from .map, not from .vmap):

• Wintergrasp Water for Lake Wintergrasp
  
• Magma for Obsidian Sanctuary
  

If anyone wants to take this up as a separate core mod, I can start another thread with the relevant details and hand it off so I don't get distracted anymore

[petbat]

Works with 10581

* Tested patching and compile

[faramir118]

Still not much time to fully test, working on other stuff.

I have concerns about evading from within movement generators:

• Alice(player) attacks Eve(monster), does some damage
  
• Bob(player) stands somewhere Eve can't go, like on a roof
  
• Bob uses ranged taunt on Eve
  
• Eve paths to Bob, stops at end of path
  
• Eve can't reach Bob, so evade timer is started
  
• Bob randed attacks Eve, and Alice melee attacks Eve
  
• Eve either evades due to evade timer, or dies from players attacking
  Eve's movement generators has no way to know she can attack Alice instead
  

Some other changes look good, but separating them is slow.

[qsa]

Still not much time to fully test, working on other stuff.

I have concerns about evading from within movement generators:

....

Some other changes look good, but separating them is slow.

The example given is right, this case should not be handled from movement generators, but aggro/target selection code instead.

Aggro mechanism controls and calls target movement generator, therefore if this case arrives it should do the necessary calculations.

But!, if target selector decides that unit have to move to target, its up to movement generator to get it there and evade if needed.

What I'm really saying here, is that additional logic should be added to target selector - but in addition to ability to evade from movement generator ( what we currently have ).

This additional logic is something to be done, for now, evading when there's no path to the target is only the first step.

I think we should handle the evading and similar stuff in SelectHostileTarget.

Same answer as to above - We;ll have to add some logic there, but we cannot cut the current mechanism, maybe change it a little bit.

* add a param to not evade by default (ie for a boss like gothik where the encounter starts the first few minutes without any enemy in accessible place

...

This is not needed at all - as I said, target selector controls/calls target movement generator - before npc moves to attack ( fight starts ) movement generator is not called at all.

Its the same thing when creature can cast spell on the target ( casters AI ) if it can cast, it will cast from far away, target movement generator is not involved here again, so creatures wont "just evade" when they shouldn't.

I think there's some misconception here, with where exactly this evade code is used.

Creatures will evade ONLY when AI tells them to get somewhere and they cannot.

I hope, I cleared this out, if not, feel free asking.

PS: anyone had some time to do actual testings? don't be shy ...

PSS: faramir : I have another pack of changes ready, charge effects and extractor unix compatibility, but that's only after those are added. Saying, so people wont work on those.

[Toinan67]

PS: anyone had some time to do actual testings? don't be shy ...

[...]

extractor unix compatibility

[qsa]

PS: anyone had some time to do actual testings? don't be shy ...

[...]

extractor unix compatibility

You can run current under wine just fine, or just extract under win machine and transfer.

[faramir118]

I think we should plan this all now, so that everybody is on the same page. This is going to be a long post.

Current mangos implementation updates MovementGenerator before it calls SelectHostileTarget:

Creature::Update()
   Unit::Update()
       process events (might die here, damage aura or something)
       MotionMaster::UpdateMotion()
           active MovementGenerator::Update() (1)
   if (not evading) UpdateAI()
       Unit::SelectHostileTarget() (2)

Calling evade at (1) means we don't properly look for other attackable targets, because it prevents the AI from updating.

Currently, mangos master calls evade at (2), only when it has targets but can't attack them (for example, mob that can't swim vs player that is in water).

IMHO, it should happen the other way around - SelectHostileTarget before MovementGenerator::Update. This is how I think it should work, and has been my long-term plan for a while:

Creature::Update()
   if (not evading) UpdateAI()
       Unit::SelectHostileTarget() (3)
           Unit::isInAccessiblePlaceFor()
               verify target is reachable with pathfinding
   Unit::Update()
       process events (might die here, damage aura or something)
       MotionMaster::UpdateMotion()
           active MovementGenerator::Update()

Now evade is only called from (3). We are always giving Creatures a chance to pick a target (ie, not forcing them to evade when they have other options).

This can be optimized a bit by moving the event processing into Creature::Update. That way if the creature dies from an event, we don't waste cpu cycles finding a path to something the creature won't get to attack.

My rationale (and other random stuff) about why this way is good:

• Creature::Update() no longer wastes an update on the wrong target when it should have switched due to threat/taunt/death/whatever.
  bonus bug fix
  
• We can guarantee that we evade only if there are 0 reachable targets
  (reachable is an ugly word, thanks to ranged attacks and spells - not a huge problem, just something to be aware of)
  
• As Schmoozerd said, we can add a param to SelectHostileTarget for ignoring pathfinding.
  This will help ensure that bosses don't reset due to a faulty navmesh or something. Could also help with maps that have problems, like SFK's spiral staircase.
  
• For 100% retail behavior, where monster follows for a while before evading:
  SelectHostileTarget should save the best target, regardless of reachability
  If it doesn't find a reachable target, it should move toward the best target and start the evade timer
  if it later finds a reachable target, it should reset the evade timer
  if the evade timer reaches 0, evade (duh)
  

Feedback (or criticism) welcome!

[qsa]

After thinking about it, I think it should stay the way it is in current mangos.

First, I will try to explain why I think, your idea wont work well ( atleast under current layout ).

We generate path under MovementGenerator. From what I understand, if we change the scheme to what you suggest, we will have to either generate paths as soon as isInAccessiblePlaceFor, and then somehow copying them to movement master, or generating those path more than once. This is totally unacceptable performance wise.

If we keep the current scheme, after we generate the path in (1), we get to (2) - there we can check the type of the path. If we can select better target, set new target for next MovementGenerator update.

We do "skip" one iteration here, but thats totally expendable when you compare it with generating extra paths ( checking reachability ).

Eventually we will select "the best target", it may take few extra update calls, but it will take overall less path calls.

Keep in mind that if we will try to calculate paths to all feasible targets on same update we're creating bottleneck. Spreading those calls is much better choice.

I think we should only modify Unit::SelectHostileTarget() to check current path type - if it isn't complete => try to select different target. No targets at all => evade ( after they came as close as possible etc .. ).

Just my thoughts, Ideas are welcomed. The more time we spend on planning, the less time we'll spend dealing with problems.

About the temp evade solution I have in my patch : for now its better than nothing. Can always be removed when better implemented.

It has nothing to do with actual pathfinding code, it just prevents loops when target is not reachable.

I still think it should be added for now.

[Schmoozerd]

hmm, I can see what you are referring too - though this is mainly a question of saving/ accessing, the actual work that is to be done is always the same.

And the logic is in my view clear, that the selecting of the target should be handled in SelectHostileTarget

But I don't know anything about movement generators, so I just wanted to give some input (I come from the AI direction)

(A small note: there is no principle problem to check if we do have combatMovement for a mob in SelectHostileTarget, I already prepared a patch to move this to generic CreatureAI)

[faramir118]

For qsa's way:

update cycle 1:
   Creature::Update()
       Unit::Update()
           MotionMaster::UpdateMotion()
               MovementGenerator::Update()
(1)                 evadeWhenCan()
   (call stack eventually goes back to Creature::Update)
       unit is not evading yet, so UpdateAI()
           SelectHostileTarget
(*)             pick new target using pathfinding, set evadeWhenCan to false
(*)                 AttackStart()
(*)                     MotionMaster.MoveChase()

update cycle 2:
   Creature::Update()
       Unit::Update()
(2)         m_evadeWhenCan is true, so CreatureAI::EnterEvadeMode()
   nothing else matters, we are in evade mode (new MovementGenerator, leave combat, etc)

The stuff with (*) is not implemented yet.

Without it, everything between (1) and (2) is guaranteed to not matter (except if creature dies to aura damage).

So it can be made to work, but only if you generate and validate paths in SelectHostileTarget - this is functionally the same as what I proposed.

However:

From a design-oriented viewpoint, I feel that deciding to enter evade mode should solely be the responsibility of AI. Evade mode has a lot of implications besides just movement. MovementGenerator should only generate movement. It is a more logical separation of functionality, IMHO.

somehow copying them to movement master

This is easy, just store path in Unit instead of MovementGenerator.

Keep in mind that if we will try to calculate paths to all feasible targets on same update we're creating bottleneck.

I don't know how often this will actually happen...

In most cases, players are solo and monsters will just reset (or attack the pet if there is one).

In raids, players are always right in the fight. I can't think of any realistic scenarios where more than one or two extra paths will need to be generated. Is it big enough problem to base design decisions on?

As a proof of concept, your implementation works well. I have no problem adding it as long as there are concrete plans for an agreed-upon, proper implementation!

[qsa]

For qsa's way:

update cycle 1:
   Creature::Update()
       Unit::Update()
           MotionMaster::UpdateMotion()
               MovementGenerator::Update()
(1)                 evadeWhenCan()
   (call stack eventually goes back to Creature::Update)
       unit is not evading yet, so UpdateAI()
           SelectHostileTarget
(*)             pick new target using pathfinding, set evadeWhenCan to false
(*)                 AttackStart()
(*)                     MotionMaster.MoveChase()

update cycle 2:
   Creature::Update()
       Unit::Update()
(2)         m_evadeWhenCan is true, so CreatureAI::EnterEvadeMode()
   nothing else matters, we are in evade mode (new MovementGenerator, leave combat, etc)

The stuff with (*) is not implemented yet.

Without it, everything between (1) and (2) is guaranteed to not matter (except if creature dies to aura damage).

I see no problem calling all those while we move in direction of something we consider "non-optimal" target. All the code in-between (1) and (2) should run anyway. If the creature dies, or whatever, we wont have to continue anyhow, already set evade flag wont change anything. Maybe the unit can cast spells while on its way, who knows ...

So it can be made to work, but only if you generate and validate paths in SelectHostileTarget - this is functionally the same as what I proposed.

No, By the time it gets to SelectHostileTarget, MovementGenerator already made path. There's no reason generating anything new here.

However:

From a design-oriented viewpoint, I feel that deciding to enter evade mode should solely be the responsibility of AI. Evade mode has a lot of implications besides just movement. MovementGenerator should only generate movement. It is a more logical separation of functionality, IMHO.

somehow copying them to movement master

This is easy, just store path in Unit instead of MovementGenerator.

That's right, "design-oriented viewpoint" - MovementGenerator deals with the movement, AI deals with the aggro.

That what I was saying all along.

That's why I'm against generating paths in SelectHostileTarget.

We can check the type of already generated path inthere, but not dealing with path logic.

Thats why we cannot store paths in Unit too. In addition to the fact it is wont be used by anything but npc's which use targetmovement generator ( its maybe 1% of all units in any given moment).

Keep in mind that if we will try to calculate paths to all feasible targets on same update we're creating bottleneck.

I don't know how often this will actually happen...

In most cases, players are solo and monsters will just reset (or attack the pet if there is one).

In raids, players are always right in the fight.

Another reason why we shouldn't add any heavy code dealing with this corner case.

EDIT: I took another look at the pseudocode you added for my suggestion, and it isn't exactly what I had in mind.

All 3 stars can be replaced with "select different feasible target" - no path generating involved there. Just checking what type the current path has.

And (1) can/should be removed ( after (*) added ).

PS: sorry for such late edit.

[faramir118]

I'm looking for 100% guarantee that we pick a reachable target, assuming that there is one. I'm not convinced yet that what you propose (no pathfinding during target selection) is going to accomplish that. Even after several iterations, how can we guarantee it will settle on one reachable target? How can we guarantee correct behavior when there are 0 reachable targets?

The MovementGenerator isn't aware of the big picture, and less-than-ideal circumstances may cause problems:

In the previous example, assume that Alice and Bob (and for the sake of argument, 8 other players) are on the roof. Eve's movement generator will reject each target in turn, but never all at the same time.

SelectHostileTarget is already dealing with the big picture. It already makes decisions based on location of the potential target, and pathfinding is a (really complex) extension of that functionality.

AI should use whatever information it has at its disposal to make the best choice possible. Categorically denying information based on cost is possible, but in this situation I think the cost is reasonable most of the time.

I know it's potentially costly to generate paths in SelectHostileTarget, but in most cases it should only generate (or update) one path. I think that it will take special circumstances (exploits, bugs in pathfinding, bad navmesh, etc) to create a true bottleneck. It would be better to catch and handle these root causes. For example: count the number of incomplete paths generated in SelectHostileTarget - if there are more than 5, log an error with information about what map, location, creature, etc.

Additionally, we can give a time slice budget to SelectHostileTarget. If it goes over, just use whatever target was best so far. Many video games do this so that other important tasks, like rendering the scene, get time to finish.

In addition to the fact it is wont be used by anything but npc's which use targetmovement generator ( its maybe 1% of all units in any given moment).

Probably 99% of units which call SelectHostileTarget use TargetedMovementGenerator:

SelectHostileTarget calls AI()->AttackStart(). All core AI implementations of AttackStart() call MoveChase.

I'm not familiar enough with scriptdev2's AI implementations to know what to do to allow them to skip pathfinding. I'll post more on this after I look into it.

[Schmoozerd]

there is a "big" class of mobs that doesn't do MoveChase, and these are mobs which have no combatmovement. (ie Caster)

This information _could_ be checked in SelectHostileTarget, as I already proposed to move combat movement (same in EventAi and SD2, and usefull for summoned mobs) to CreatureAI

[qsa]

I'm looking for 100% guarantee that we pick a reachable target, assuming that there is one. I'm not convinced yet that what you propose (no pathfinding during target selection) is going to accomplish that. Even after several iterations, how can we guarantee it will settle on one reachable target? How can we guarantee correct behavior when there are 0 reachable targets?

iteration start (update call):

- MovementGenerator::

Generate path to current target.

- SelectHostileTarget::

Path generated for current target is valid -> noop.

else

mark current target in thread list as unreachable

select target with highest thread (and unmarked) from thread list (+ all current readability tests)

Iteration end.

If we have 0 valid (path wise valid) targets, out of X, it will take us X updates to figured that out.

By all means, it is finite, best effort. If here is valid reachable target, it will find it.

The MovementGenerator isn't aware of the big picture, and less-than-ideal circumstances may cause problems:

In the previous example, assume that Alice and Bob (and for the sake of argument, 8 other players) are on the roof. Eve's movement generator will reject each target in turn, but never all at the same time.

SelectHostileTarget is already dealing with the big picture. It already makes decisions based on location of the potential target, and pathfinding is a (really complex) extension of that functionality.

AI should use whatever information it has at its disposal to make the best choice possible. Categorically denying information based on cost is possible, but in this situation I think the cost is reasonable most of the time.

By the time SelectHostileTarget runs it has all the data it needs to make educated decision.

MovementGenerator don't have to know anything - it takes its commands from AI.

I know it's potentially costly to generate paths in SelectHostileTarget, but in most cases it should only generate (or update) one path. I think that it will take special circumstances (exploits, bugs in pathfinding, bad navmesh, etc) to create a true bottleneck. It would be better to catch and handle these root causes. For example: count the number of incomplete paths generated in SelectHostileTarget - if there are more than 5, log an error with information about what map, location, creature, etc.

Exactly the same applies to 2nd solution too. In most cases first target we select will also be the last.

In addition to the fact it is wont be used by anything but npc's which use targetmovement generator ( its maybe 1% of all units in any given moment).

Probably 99% of units which call SelectHostileTarget use TargetedMovementGenerator:

SelectHostileTarget calls AI()->AttackStart(). All core AI implementations of AttackStart() call MoveChase.

I'm not familiar enough with scriptdev2's AI implementations to know what to do to allow them to skip pathfinding. I'll post more on this after I look into it.

Sure, its just Players derive from Unit, Units not in combat do not chase anything. So it still stands : "maybe 1% of all units in any given moment".

Maybe I'm really failing to see the major advantages of generating paths as soon as SelectHostileTarget over generating them in movement generators.

Please do explain me.

I'll try to explain once again why I'm against generating paths in AI code.

Firstly and most importantly : it single handedly destroys entire modularity concept. By creating those ties between unrelated section of the code, unnecessary dependencies created.

Integrating them one into another just creates blob of code.

AI: what to do.

MovementGen: how to do.

We should not mix those.

2nd: path generated are valid until ANY target moves. If you generate X paths every update call, you are wasting alot of resources here for very, very little gain ( corner case ).

We may not want to solve it at all.

Consider it : as soon as primary target changes, the creature will switch target anyhow.

I think something like can be fair solution: if cannot reach main target, try one more target, if not evade.

The more I think about it, the faster I come to conclusion that we should not deal with this case at all.

All that has to be done, is to move the evading code out from movement generator to SelectHostileTarget and "call it a day".

If main target not reachable due to terrain - evade. This cannot be "natural" case.

Consider this : all thread list out of reach ( since they found hold in map and they are abusing it or something ).

How is that different from main tank constantly out of reach? I think it isn't.

Back to my point : We should just evade. End of story.

Thanks in advance.

[Schmoozerd]

I am not sure, but we not really say that we would want to generate the paths in SelectHostile, we only would want to _know_ if a path can be created - and this is an information that the AI "needs to know"

think of a complex situation:

let threat list be: normal mob(reachable), taunter1(unreachable), taunter2(reachable)

SelectHostile selects taunter1, sets target as taunter1, calls MoveChase(taunter1)

MoveChase(taunter1) fails, movement generator either does nothing, or Chases normal mob

next tick (though target is taunter1)

SelectHostile skips taunter1 and selects taunter2, calls MoveChase(taunter2)

MoveChase(taunter2) works, and we have taunter to as target, and as chased mob

if you extend such an example further, you see that it might take many ticks till you get correct working mechanics

the logic must be:

AI: I have my targets

AI: which of them can I chase

AI: which of the chaseable do I want to chase

AI: start chasing

MoveChase: Do Chase.

as this is very ineffective, we start the first optimation, which is also still very logical:

AI: order targets along preference

AI: check if reachable till found a reachable target

AI: no reachable target found: do something cool (evade, return special value in some cases)

AI: start chasing reachable target

MoveChase: Do Chase

So, that is a wonderful modular logic, and this only has the disadvantage that the check if a target is reachable is (likely) the same work as creating a path to this target

So, if we implement the check clever, and use a even cleverer storage system for the created path(s) - we get rid of double work.

[qsa]

So, that is a wonderful modular logic, and this only has the disadvantage that the check if a target is reachable is (likely) the same work as creating a path to this target

That's the main problem. If we could check for reachibility "for free", there would not be any problem "just checking" before selecting target.

What you actually saying is same thing faramir118 does : all paths at once.

Sorry, I had to edit my previous post with some thoughts on the subject.

[faramir118]

The advantage is that we have an algorithm that correctly emulates retail behavior, no matter the circumstances.

It's been a long time (couple years) since I played retail, but I remember how this part works.

In Magtheridon's Lair there is a spot on the door/portcullis where you could stand that monsters can't path to. If the tank jumped on there, Magtheridon would start killing other members of the raid. He would only reset if the entire raid (minus the dead people) were standing on that spot.

In most cases first target we select will also be the last.

The same is true for my suggested way. We generate the path, it is valid, so save it somewhere where the MovementGenerator can use it. We don't do double work.

If the AI doesn't require a complete path the the target, it should tell SelectHostileTarget not to use pathfinding - no wasted cpu, no unused path lying around somewhere.

Units not in combat do not chase anything

They also don't have anything in the threat list or attacker list, nor do they have taunt auras applied.

As long as this is true, we generate 0 paths for creatures that aren't in combat. No extra overhead here.

It's not going to turn into a code blob, I promise. We are making the pathfinding API - make the API right, and there won't be any problems of this sort.

[Gotisch]

think of a complex situation:

let threat list be: normal mob(reachable), taunter1(unreachable), taunter2(reachable)

SelectHostile selects taunter1, sets target as taunter1, calls MoveChase(taunter1)

MoveChase(taunter1) fails, movement generator either does nothing, or Chases normal mob

next tick (though target is taunter1)

SelectHostile skips taunter1 and selects taunter2, calls MoveChase(taunter2)

MoveChase(taunter2) works, and we have taunter to as target, and as chased mob

if you extend such an example further, you see that it might take many ticks till you get correct working mechanics

Let's put it into perspective, Creature AI ticks every 100ms (yes?) So with 10 players qsa modular way would take maximum of 1 second to find reachable target, assuming that only 1 player is reachable. While at every tick only generating 1 path.

faramirs way would take 100ms but generate 10 paths in that time.

the logic must be:

AI: I have my targets

AI: which of them can I chase

AI: which of the chaseable do I want to chase

AI: start chasing

MoveChase: Do Chase.

Still same example with 10 players. you will generate 10 paths every tick (at least that is what your pseudo code suggests).

I know it's potentially costly to generate paths in SelectHostileTarget, but in most cases it should only generate (or update) one path. I think that it will take special circumstances (exploits, bugs in pathfinding, bad navmesh, etc) to create a true bottleneck. It would be better to catch and handle these root causes. For example: count the number of incomplete paths generated in SelectHostileTarget - if there are more than 5, log an error with information about what map, location, creature, etc.

Exactly the same applies to 2nd solution too. In most cases first target we select will also be the last.

The same is true for my suggested way. We generate the path, it is valid, so save it somewhere where the MovementGenerator can use it.

Do i see infinite "this is true for my way too!!" loop here?

Here are pseudi codes as i understood them

Creature::Update()
 Unit::Update()
   process events (might die here, damage aura or something)
   MotionMaster::UpdateMotion()
     active MovementGenerator::Update()
       (IF there is no valid path for current target)
         !generate one new path!

 (IF (not evading))
   UpdateAI()
     Unit::SelectHostileTarget()
       (IF current path is INCOMPLETE)
         mark target as unreachable
         (IF possible other target)
           switch to next possible target
         (ELSE)
           evade

Path generation is limited to MovementGenerator.

Target selection is limited to CreatureAI.

Faramir proposes to rewrite Unit logic

Creature::Update()
 (IF (not evading))
   UpdateAI()
     path Unit::SelectHostileTarget()
       Try to find valid target by checking everything in taunt/threat list
       normally and with
       path Unit::isInAccessiblePlaceFor()
         !generate one new path!
       (IF generated path is INCOMPLETE)
          drop it
       (ELSE)
          save it (But probably not from isinaccessibleplace but in AI?)

 Unit::Update()
   process events (might die here, damage aura or something)
   MotionMaster::UpdateMotion()
     active MovementGenerator::Update()
       !Access Saved Path from AI!
       or
       !generate same path!

Path generation is limited to AI/Unit (or if path not saved movementgenerator generates path too)

Target selection is limited to AI

What are the differences between faramirs way and qsa's?

faramirs way

* might generate more then one path per iteration

* needs "shared" memory to save path to

* needs one iteration (100ms) to decide if it should evade

* breaks modular coding way by mixing pathfinding into AI

qsa's way

* path is only generated by Movementgenerator

* needs more then one iteration to decide if it should evade (worst case sizeof(threatlist))

What are the real differences?

faramir would need some field for saved path and rewrite of unit logic

qsa needs some way to save if unit is accessible or not

My rationale (and other random stuff) about why this way is good:

• Creature::Update() no longer wastes an update on the wrong target when it should have switched due to threat/taunt/death/whatever.

bonus bug fix

• We can guarantee that we evade only if there are 0 reachable targets

(reachable is an ugly word, thanks to ranged attacks and spells - not a huge problem, just something to be aware of)

[rest is rambling and not advantage of good way]

From what i understand (and remember) from official. Official mobs will run as far as possible to unreachable target and then evade if they can't reach it.

With your way that won't happen. With qsa's way this won't happen either. Way to make it happen imo is to make isinaccessibleplace only return true, if generated path was incomplete and mob is already at last node of path for at least a few ticks.

If Mob has to follow invalid path anyway, i don't see advantage of "not wasting updates" because to be official mob should not do anything else.

Wasting also only happens in case of invalid path. Creature::Update() already takes care of threat/taunt/death cases.

qsa way also garantees that mob will evade only if there are 0 reachable targets, so i don't see how this is advantage

So to me main difference between the two methods is the mentallity where to generate path.

[qsa]

The advantage is that we have an algorithm that correctly emulates retail behavior, no matter the circumstances.

It's been a long time (couple years) since I played retail, but I remember how this part works.

In Magtheridon's Lair there is a spot on the door/portcullis where you could stand that monsters can't path to. If the tank jumped on there, Magtheridon would start killing other members of the raid. He would only reset if the entire raid (minus the dead people) were standing on that spot.

I'm almost 100% sure they do it by either dropping unreachable target or reducing its threat by %.

So we automatically have new target to attack, hoping we can get to him.

Maybe someone can test this on retail? There is no freaking way they generate paths to all targets at target selection.

We can do the same: no path -> SelectHostileTarget drops ~50% of the threat of main target -> next iteration.

Looks like we agree to disagree.

Therefore the only logical solution is to have 2 different versions. Test them properly. Only then (maybe) we will come to better conclusions, understanding of the good, the bad and the ugly about every way.

Gotisch : thanks for summarizing it all up. It is pretty accurate and will surely help people too lazy following the walls of text from above

EDIT: didn't want to make new post.

below patch adds support for extractor under linux.

CMakeLists.txt : http://pastie.org/1223272

code diff against 213e909001 :: http://pastie.org/1223273

cmake file can be used to generate any project under VC as well.

The source changes include mainly missing includes, warning fixes.

The only "real" issue was that *nix systems are case sensitive while win aren't.

Take care.

[Toinan67]

Gotisch : thanks for summarizing it all up. It is pretty accurate and will surely help people too lazy following the walls of text from above

...and it helps people who read the wall of text, but think it's difficult to understand sometimes ^^

I have access to a retail account, what could I do exactly to help?

I can only test with a single player, or maybe with my player + a pet.

I'm almost 100% sure they do it by either dropping unreachable target or reducing its threat by %.

I can see what's happening with the threat with Omen or something like that

[Gotisch]

well if you can go to outland or northrend and land on a roof and then attack a mob that can't reach you and tell us what happens that would probably clear things up.

- does the mob not react at all?

- does the mob try to attack you and then give up?

then if you have pet, try to get on top of aggro list and then get out of reach of mob, he will attack your pet. when you get back into reachable grounds does he stop attacking pet and attack you again, or does he continue attacking pet?