Page 1 of 5

Feature #2229: Improve pathfinding AI

Posted: 01 Jun 2015, 07:11
by dteviot
I've submitted a PR for fixing the "running in circles" thats seen is AiCombat. https://github.com/OpenMW/openmw/pull/602

I'm providing this post because I believe the fix requires a bit more explanation than just the PR.

I believe the problem is the pathing can have problems when it "overshoots" a nav point.
Basically, at t = 0, NPC is pointed at a nav point, and is close but not within the "reached navPoint" threshold.
time advances by one frame, and NPC position is updated.
At which point NPC is now gone past the nav point, and is past the threshold again.
So AI starts turning the NPC around, while still running at full speed.
And because NPC can only turn so fast, well, you get the "running in circles" effect.

Simplest fix would be to increase the navPoint threshold. Changing the value from 32 to 80 will do it.
But this makes the pathing sloppy. So fix only applies the higher threshold when it looks like a navPoint has been overshot.

Easist way to test that I've found is go to Dreen Plantation
Turn on God Mode and togglepathGrid.
Set speed to 300.
Then walk up to "Frinnius Posuceius" and punch him.
Frinnius and "Hrargal the Crow" should start chasing you.
If you run around the huts they tend to start "running in circles" around at the navPoints at corners.

Note, I haven't applied fix to other AI packages at this stage.

I've also looked into #2559 some more. https://bugs.openmw.org/issues/2556
On further investigation, the "spin at the corner" is not due to pathfinding.
Instead, it appears to be due to the script ColonyUryn attached to "uryn maren".
The script directs uryn to the destintation in a series of AiTravel commands.
The spin occurs when the end point of the on AiTravel segment is off the ideal path.

So, if uryn is not moving after he finishes the first AiTravel segment, it suggests a problem with the script.
As sjek and I are unable to reproduce, I'm going to suggest this be closed, as I believe it's a problem with one of the plug-ins Alex C had loaded.

Re: Feature #2229: Improve pathfinding AI

Posted: 01 Jun 2015, 21:38
by dteviot
scrawl wrote: Unnecessary complicated, IMO. Plus, we need it fixed for all AI packages and not just combat.
If this fix was deemed acceptable, I was going to add it to the other packages.
scrawl wrote: AFAIK the basic issue with the circling is an actor restarting on the same path again and again whenever it's recalculated (typically when the target moves).
With respect, this doesn't match what I observed, at least for the AiCombat package. (It may be different for the other AiPackages, as their logic is different. I have not studied them in detail.)

Firstly, once "circling" starts, it remains in a circling mode. Even if you as the player move sufficiently to trigger a new path generation. Note that the new path still has the same navPoint as the first destination as the previous path, as that is the closest navPoint to the NPC.

In the AiCombat module, every 0.25 seconds the pathing logic is invoked. This is where a new path may be generated.
However, if the new path has the same first navPoint, then the NPC behaves in the same way.
i.e. The logic is (lines 600 to 635 of aicombat.cpp):

Code: Select all

if  (can should NPC attack or shortcut?)
{
    attack or shortcut
}
else
{
    if (path to target no longer valid)
    {
        calc new path to target
    }
    move towards first navPoint on path
}
On reflection, a repathing may trigger a "running in circles", if the new path occurs just after the NPC has passed a navPoint, So a new path would take the NPC back to the point that had been just passed. And if the NPC was too close it could trigger an overshoot and circling behaviour. However, I believe circling can be triggered by passing too close to a navPoint. Or possibly when two navPoints are close together and require a sharp change of direction.

Re: Feature #2229: Improve pathfinding AI

Posted: 01 Jun 2015, 22:24
by scrawl
I didn't see this topic before I commented on your PR. Could you place a cross-link when there are discussions in two different places. Thank you.

Seems that we're talking about two different issues then. I'm sure the path-restarting is what causes circling in many cases. An easy way to reproduce:
- set an NPC that is not in the player's line of sight to AiFollow on the player
- keep walking back and forth
The NPC will then run in circles indefinitely, so long as the player keeps walking back and forth (which cause the NPC to recalculate his path).

The pathfinding code just has so many issues that IMO a rewrite from scratch would be the most effective way of fixing them. Not keen on adding more bandaids to a broken system. I still plan on doing that rewrite, probably some time after I'm done with the graphics rewrite.

Re: Feature #2229: Improve pathfinding AI

Posted: 01 Jun 2015, 23:32
by dteviot
scrawl wrote: Seems that we're talking about two different issues then. I'm sure the path-restarting is what causes circling in many cases. An easy way to reproduce:
- set an NPC that is not in the player's line of sight to AiFollow on the player
- keep walking back and forth
The NPC will then run in circles indefinitely, so long as the player keeps walking back and forth (which cause the NPC to recalculate his path).
How do I "set an NPC that is not in the player's line of sight"?
I know about opening the console, click on NPC and then "AiFollow player 0 0 0 0 0 0", but how do I do it when not in line of sight? Also which NPC do you recommend doing it on, and location for best effect?
scrawl wrote: The pathfinding code just has so many issues that IMO a rewrite from scratch would be the most effective way of fixing them. Not keen on adding more bandaids to a broken system. I still plan on doing that rewrite, probably some time after I'm done with the graphics rewrite.
I agree that pathfinding code needs a rewrite. e.g. Duplicated logic in AiCombat and AiPackage.
That said, I think applying band aids has merit.
  • By adding the band aid, you know there's a bug, and at least one method of fixing it. So you're less likely to duplicate the bug when you do the rewrite.
  • http://www.joelonsoftware.com/articles/ ... 00069.html.
  • Replacing the current logic with a navmesh is a pretty big job. Based on my available time (periods of < 8 hours per week) I don't have time to do a navmesh, I do have time for bandaids. And at the moment, I think the AI Pathing problems are probably the biggest/most annoying problems in OpenMW for players (as opposed to the CS).

Re: Feature #2229: Improve pathfinding AI

Posted: 03 Jun 2015, 18:14
by scrawl
I know about opening the console, click on NPC and then "AiFollow player 0 0 0 0 0 0", but how do I do it when not in line of sight?
Open the console, click on the NPC, close the console, walk out of their line of sight, open the console, then type AiFollow player 0 0 0 0.

Re: Feature #2229: Improve pathfinding AI

Posted: 03 Jun 2015, 20:38
by mrcheko
Hi. I want to clarify some things (I was working a bit on pathfinding specifically in AiCombat package).

First to mention, both of you are right:
dteviot wrote:I believe the problem is the pathing can have problems when it "overshoots" a nav point.
It's true, it applies to all packages (though maybe simpler to observe in aicombat). Recently radius to check pathpoint was 64.0 now it's 32.0 (PathFinder::checkPathCompleted, tolerance), checked that in commits history. I remember that ai definitely was not running in circles so hard earlier also.
scrawl wrote: AFAIK the basic issue with the circling is an actor restarting on the same path again and again whenever it's recalculated (typically when the target moves).
True, applies to any other package apart aiCombat. I fixed that rather long time ago (only in aicombat): PathFinder::syncStart, look for usage in AiCombat::buildNewPath. For further clarification ask here (though there is a comment in code).

Speaking about rewriting of pathfinding (pf) system - lets firstly discuss propositions here. Cause with such narrow pf info which Morrowind gives us it's very hard (maybe impossible) to develop good pf.

For you to have better understanding of how pf work: in packages apart aicombat ai cast ray to target and if in LOS than go straight on target. In aicombat: it also casts los-ray but every 0.25 sec it casts 1 more up-down ray to see if there is obstacle/pit just in front of the character (checkWayIsClear func, aicombat.cpp), and if yes - return to pathgrid (retry to shortcut again only after walked away of that "dangerous" spot on PATHFIND_CAUTION_DIST (=500 units, aicombat.cpp)). This is done for ai to not move in robotic fashion from one waypoint to another. I don't know ofcourse what They do in original game but there is rather similar system - you can watch that in Balmora for example: how ai run to you between all waypoints during combat.

Ofc navmeshes are the best option but requires a lot of preparations (meshes generation) and code-work. So its an option only for OpenMW1.X

Re: Feature #2229: Improve pathfinding AI

Posted: 04 Jun 2015, 08:48
by gus
Also (if this did not change since my original implementation), PathFinder::checkPathCompleted is sadly framerate dependant, that is why some have problems while other do not.

Ps: Hi everyone! It has been a long time, it's good to see that you are doing great :D

Edit: note that AI implementation was done in the sprit of trying to mimic morrowind AI so that it does not break any eventual quest which relies on an NPC taking a certain path. Otherwise navmesh is definitly the way to go!

Re: Feature #2229: Improve pathfinding AI

Posted: 04 Jun 2015, 09:34
by Okulo
Hey wow! It's gus! Hey, gus! It's been like... what, a year? How have you been?

Re: Feature #2229: Improve pathfinding AI

Posted: 05 Jun 2015, 09:38
by gus
yeah almost a year :) I've been fine thanks! Sadly I don't really have time to give to openmw anymore, but I follow the project closely and the progress are amazing :D I admit I'm pretty excited about the OSG port, if it solves the performances problems it would be awsome!
But let's not get too of topic ;)

Re: Feature #2229: Improve pathfinding AI

Posted: 06 Jun 2015, 02:49
by dteviot
mrcheko wrote:
dteviot wrote:I believe the problem is the pathing can have problems when it "overshoots" a nav point.
It's true, it applies to all packages (though maybe simpler to observe in aicombat). Recently radius to check pathpoint was 64.0 now it's 32.0 (PathFinder::checkPathCompleted, tolerance), checked that in commits history. I remember that ai definitely was not running in circles so hard earlier also.
A radius of 64 will reduce the running in circles, but won't prevent it. That was one of the first things I tried. My experiments measured NPCs running in circles with a minimum distance to NavPoint of 74 units. I suspect 80 units radius will nearly always work, but it makes the pathing sloppy. I've seen NavPoints with a separation of < 150 units.

As a start on improving the pathfinding, I believe I've managed to refactor the AiTravel logic so it now uses AiPackage.pathTo(). https://github.com/OpenMW/openmw/pull/606
My next step would be to get AiCombat and AiWander to also use AiPackage.pathTo().
This would mean that all packages use the same code to do the pathing.
Which would mean that fixes for pathfinding/pathing (running in circles and "getting stuck") can be applied in one place.

Does this plan make sense to you?