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.

If I remember right, there's an issue with new operator allocating less memory then the actual packed object size. Something to do with added padding.

Is there specific reason ( beside saving few bytes per packed structure ) packing is used?

I'm asking since non default aligned sizes are known to cause some cache inefficiencies. Simply since architecture assumes defaults are used.

From looking at mangos code, some structures are packed by 1byte while they don't use any members that take padding at all.

What I'm really saying here is, maybe we can cut it altogether?

Take care.

I'm really sorry for this question, but ...

What is the reason for posting this thread if the rest of the community cannot take part in its development in any manner?

Don't get me wrong here.

Take care.

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.

Been away for a week, but now I'm back, sort of ...

Below attached patch with following changes:

• * Integrating pathfinding into PointMovementGenerator. Since it is mostly used in scripts (via MovePoint() ), pathfinding there is optional parameter.
  * Proper packet reserve size in Unit::SendMonsterMoveByPath().
  * Optimization in PathInfo::BuildPath() - we don't have to iterate more than once on our current poly-path to get all the info we need.
  * Bad logic in PathInfo::BuildPath() ::: (startPolyFound && !endPolyFound) case. If suffix generation fails we still need to copy the new prefix into our current path. I think the original got overwritten somewhere, causing this issue.
  * Little change in findSmoothPath() define parameters, just values I found to give bit better results. Still need much more testing.
  

Patched against (321ed6f2b) :: http://pastie.org/1181579

...with loglevel=0 this spam...

Can you please tell me where and how I can reproduce those? If possible on latest.

There's no way those paths can be generated without something going really wrong.

I don't know if there is the EventAI or mmaps bug, but sometimes caster-scripted EventAI mobs get a stuck if you stay behind the wall from them, you can simply reproduce it by trying to aggro big pack of mobs and hide behind the wall in Zulfarrak instance.

Nothing to do with move maps - you can try w/o them and see that the result is exactly the same.

Just pick almost any caster-scripted mob, those that start to cast spell (with cast time) as soon as aggroed are the best. Attack him with ranged ability, move quickly out of LoS. He wont finish casting the spell and will stuck there until you come into los long enough for him to finish his cast.

On a related note : Looks like you are testing this patch. Any feedback? How about performance issues? tester counts, added load, etc.

I'm sure we all'd love to see some detailed report.

tested with .npc follow on stomrwind guard, when trying to enter into the house that near of npc 6174 - the guard is walking through house's wall

as i already seen, summoned pets works as excepted.

I'm pretty sure this is the one of few cases where PointMovementGenerator is used. I don't think we need to implement pathfinding into it.

Maybe I'm wrong.

Edit: I was wrong, it isn't PointMovementGenerator or any of its derivatives (AssistanceMovementGenerator). It must problematic place in maps.

In fact, the only place PointMovementGenerator really used, is in script calls.

What about of pet's following by these paths? As i see at my latest test (10502 rev+latest branch) pets still moving to owner/target through textures or any walls... but they shouldn't

Tested with water elemental, by clicking stay, then moving away and using follow, and it works as expected.

Can you post how it can be reproduced?

Another pack of changes.

* missing parts from my previous patches.

* some cleanup.

* better path representation in debug command.

Some side notes: findPath/findSmoothPath/etc cannot return path longer than the bound value you give them, thus checking m_polyLength >= MAX_PATH_LENGTH wont ever work. I think we already spoke about all others.

Patch against (80ef7cb97e) : http://pastie.org/1166621

Take care.

I'm just slow, I'll get to it!

Sorry, posted before following posts and edits - take your time.

Just in case findNearestPoly (in BuildFreshPath) returns a polygon that doesn't contain the destination position.

We can probably prevent this by tweaking the extents (they are arbitrary numbers right now).

hm... can it happen? findNearestPoly doesn't contain the destination position and still return a valid poly-reference? I don't think so, since our search box is pretty small, I think its acceptable error.

For cases where the monster is between two path nodes. I can't point out one scenario where it happens, but I was planning to put the travel time calculation back into SendMonsterMoveByPath, and it should make sure that the first spline's length is accounted for.

Also, we know that the path nodes sent are [startIndex ... endIndex] but the travel time is [startIndex-1 ... endIndex] - others may use the SendMonsterMoveByPath function in some other part of mangos and not realize it. Abstraction is good in this case!

Not critical - but in current code this cannot happen, not from TargetedMovementGenerator::_setTargetLocation call at least - so, calculations of current position there are redundant. Besides, the points you get there are wrong, since only traveler have the up-to-date points if you are in the middle of travel. ( maybe I'm wrong here alittle bit - need to check code )

Thanks for porting overall.

I'll post needed changes ( if any ) in diff format later on, when I get time, so we can better discuss them.

Patience guys, everything will be solved best possible way, with time. Rushing things up will only force more mistakes.

Just few remarks about the changes:

• * in HomeMovementGenerator in call for SendMonsterMoveByPath() - path.getPathPointer() call to get path start is redundant - we just generated it, its always 1.
  

• * You still kept and using totally redundant PathInfo::isPointInPolyBounds(), any particular reason?
  

• * In PathInfo::BuildPath, why checking isPointInPolyBounds? if last poly in path is the poly we need - we don't have to check anything. We already did while getting the reference to last poly.
  *
  * Inside TargetedMovementGenerator::_setTargetLocation : that dist calculation is partially redundant (the first interval len), since point path will always contain at 0'th position out current position. pointPath.GetTotalLength can do this calculation.
  

• * Unit::SendMonsterMoveByPath() : why not including cases for path shorter than 3 points, stop case? in middle points calculation :Path[start] will always be our current location. And /2 is slower than *0.5 very likely to be optimized out, but still.
  * About using UNIT_FIELD_FLAGS instead of SplineFlags, I'd ask TOM_RUS about this one, its his packet structure. That way of sending may refer to more than just taxi paths.
  * Ay particular reason for not including WaypointMovementGenerator? Do you think, we don't need it?
  

Other than that, it looks just fine

Take care.

Found a bug at the last minute, been trying to find/fix it. I found one for sure, just not sure if it's what was causing the problem...

Just one?

Just push it as is.

With suspected bug description. More people looking on it, the sooner it will be solved.

It's OK, for every bug found there are 3 hidden. You can't get them all.

Take care.

Tested, working as expected.

Overall, nice patch to have, unless there is other source for this data (non I know of).

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.

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.

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:

• * Store the path in Unit class (easy way)
  * Store the path in a PathPool class
  Creatures could ask the PathPool for a path to their target.
  The PathPool could check to see if a path has already been found which has similar start and end locations, modify it with prefix/suffix heuristics, and return it.
  If no suitable path exists, PathPool just builds one from scratch.
  This would work very efficiently in a lot of cases - in most instances monsters are in a tight group (similar start position) going toward the tank (exact same end position).

We can try something like that. There are two options as I can think of right now.

First is for creature or search for other close-by creatures and adopt their paths with needed adjustments. This is pretty much what you were talking about in first bulletin, if I understand correctly.

2nd one, is to store paths at grid ( or something similar ). store them at start location.

Then when creature gets to some coordinate, it can query the "location" if it "knows" the way to XYZ.

I don't sure I understand your PathPool idea and how it is going to help us. If it is something like table of (from: map, xyz to: xyz, path) it is terrible idea. It is almost like pre-making path grid. Maybe we can optimize it to store only last K generated paths, hoping creatures move in packs - but then we are back to first idea. Otherwise searching in that pool will take longer than generating new paths.

But before we do any of those, we need to be really sure we can actually gain anything out of it. I mean, if looking for close-by creatures takes about the same time as generating medium path - we better forget about it and focus on optimizing the path-search algo

I personalty incline towards the "get neighbor's path" solution - since it sounds like most common case. Storing path for single creature ... the next time it will use it only maybe after respawn and that's too not very likely.

All above valid for long paths only, anything under ~10-poly-long shouldn't even be considered - short paths are generated about instantly.

Maybe we can wait with those ideas, just for now - since we have no idea how well, even our current, next to trivial solution, preforms under pressure.

Maybe we wont have to do anything too complicated. Complicated things => complicated bugs

I had come to the same conclusion, but wanted to leave options open if we can't solve this issue at mmap generation:

How do you make it so that recast doesn't see a door as an immutable obstacle? Perhaps flag all triangles that it touches, then remove the door?

Other cases will be simple, like the bridge in Gundrak - just flag the walkable surfaces like normal.

And currently there are only 6 bits of area flags to work with (for the input mesh). We can safely increase this, generator only uses 40mB on average.

Bits aren't the problem. Having 4~ bits for dynamics we can hash all our objects to those 16 cases. I mean, its not like we have anywhere 16 different dynamic objects along any single path. Having remote objects with same poly-marked values wont affect different paths.

About the way to generate those "special" polygons in the first place : I don't understand well enough how the generation works ( yet ), so I rather not say something stupid/impractical. But it sounds like something that can be done.

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 ...

Sorry for "bit long" post, but the better things are planed, the easier it is to make them happen.

We can know the path type using just the poly path... it can go wherever, just makes more sense (to me) to update type as soon as the path has changed.

Also, I think setting type should be this:

...

Without knowing if the A* open set reached MESH_MAX_NODES limit, we can't determine for sure if there is no path.

However, I don't think it's is possible without some modifications to detour.

It's exactly the check I made after building point-path in the new patch. Actually, when I think about it... It doesn't matter which check we keep, after poly-path build or point-path. Simply since if there's poly-path, there must be point path.

It sounds logical, but we have to make sure findStraightPath/findSmoothPath cannot fail given valid poly-path. If it can, keeping the check after point-path is build is a must, making one after poly-path totally redundant.

About MESH_MAX_NODES limit: I don't think we need to. As documentation of all those functions states, if it fails for some reason to find full path, it will return the closest point to destination.

I think we need to think more about those definitions and how we should processed in every case. For example, if we conclude there is no possible path at all, should we move at all? maybe come as close as we can and try again? things like that.

Nice find!

If we ever handle runtime navmesh modification, we will already be making sure we're not traversing parts of the mesh that have changed.

I don't think we should ever change the meshes.

Just a thought on mesh-changing (totally unrelated to current subject): We "need" it for dynamic objects, right?

I was thinking more in direction of generating the maps with those objects in the first place and marking those polygons. Then, when we generating the filter for our path, adding/removing those flagged polygons, just like with other marked polygons ( water, etc ). Flag can be something as complicated as including specific guid's of objects we want to include depending on their current visibility status.

Same goes for vmaps.

But as I see it, it is pretty far away from us no offense. Right now polygon status cannot change, making old poly-references valid.

We should also overload isPointInPolyBounds() so that we re-use the tile and poly from getPathPolyByPosition().

Sure, why not, we can pass them into isPointInPolyBounds() to clean up the code abit and save some getTileAndPolyByRef() calls, even tho they are trivial.

Pretty good idea. I'll change that next patch.

re: SendMonsterMoveByPath

... Probably need to come up with a better/cleaner way to handle movespeed and travel time calculation though.

We can always add function into Path<> class to calculate it, given speed.

Will save us 2 lines at call

Maybe we can integrate all this path system into DestinationHolder class. Instead of patching it into every MovementGenerator. Just a thought.

Toinan67: I have no idea what exactly you are asking for, general idea how it works, or how our implementations works or ...

Here's some general info to get some idea what it is all about.

http://www.ai-blog.net/archives/000152.html

You can search/ask for more once you know what you know what exactly you like to know about.

TOM_RUS : thanks once again. I wrongly assumed they are the same without checking. Patch updated in post #351.

faramir118: Sorry for that sufix->suffix typo.

in 0d8929c64 :

I think that change around line 315 , setting PATHFIND_INCOMPLETE is redundant, we are checking it in PathInfo::updateNextPosition() again. Knowing it early won't give us anything, since we move along point-path and not poly-path. While having less set-points makes things easier to debug.

Around Line 399, checking getTileAndPolyByRef() is redundant. It is already checked in getPathPolyByPosition(). If there's invalid poly, startPoly or endPoly is already 0. So, I dont think we need that hulk (-370,22 +382,33).

I may be wrong about those two. Rest looks good.

Toinan67: I'm not into that, sorry. I didn't meant it to sound like it turned out to be.

Another wall of text, that about 4 users will read. Hey! my pleasure guys.

Below attached another patch which continues my work on the subject.

• * Smooth path generation from my previous patch. Just read post #333.
  * Silly crash in generator at case of slightly invalid input. Happens when using any of the "--" options without its parameters.
  * Store our point path in Path<> class instead of that flat array. This class exist for ages and provides pretty much everything we need, making some things much simpler and intuitive.
  * Fixing and using Unit::SendMonsterMoveByPath() thanks to TOM_RUS and his detailed info on the structure.
  

This allows us to send the entire path to the client in single packet in HomeMovementGenerator making the code there much, much simplier and movement smoother. Also used to send _partial_ path in TargetedMovementGenerator when we have long paths generated.

I won't make this wall of text even longer, check the code or try it ingame.

• * Some minor, random changes ...
  

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

About memory leaks : older version may have some, even tho I can't point at one.

This one, I actually checked. There are no related to pathfinding. Atleast not for the common thing I checked.

I did found some other things is anyone interested.

there's memory leak in Aura::HandleAddModifier() and some read/write violations on loading of WMOAreaTableEntry.

Here's partial log : http://pastie.org/1147043

generated by edu version of purify. (sorry, no testing environment with valgrind at the moment).

What I got by making my pathfinding test, so I guess that HandleAddModifier, is nasty one.

Take care.

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.

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.

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.

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.
  

• * Optimizations
  

• * Code centralization :
  

• * General changes :
  

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.

Error persist with updated code.

Can anyone please confirm?

Tested again, just to be sure on clean rev. 10400 under gcc 444, fedora core 12 -- patch applies and compiles like a charm.

PS: please make sure the patch is applied properly, especially the new files and you reconfigured before "making".