Feature #2229: Improve pathfinding AI

Everything about development and the OpenMW source code.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

Studing Morrowind.esm, Tribunal.esm & Bloodmoon.esm, there are 5 "swim only" creatures.
  • "Dreugh", which has an AiWander of 1000 units.
  • "Slaughterfish", which has an AiWander of 1000 units.
  • "Old Blue Fin" (slaughterfish_hr_sfavd), which has an AiWander of 512 units.
  • "Dreugh Warlord" (dreugh_koal), which has an AiWander of 1000 units.
  • "Small Slaughterfish", which has an AiWander of 1000 units.
All of them are in Morrowind, none are in Bloodmoon, and Tribunal has a copy of the Slaughterish.

How do they move in Vanilla?
(Note, I created a ring of invisibility, and then went observing.)
In the Koal Caves, Dreugh move a bit like pinballs.
They travel in straight lines in the X-Y plane (i.e. don't change their depth) until they hit a wall, then "bounce off" at a different angle.
Slaughterfish, move a bit like the Dreugh when you first see them, in straight lines, then change direction at random, with no change in depth.
Except, after a few seconds, maybe as long as 20, they stop moving.


Looking at morrowind.esm.
I see the following distribution of wander distiances for Creatures.
Distance = 0, count = 27
Distance = 32, count = 1
Distance = 64, count = 1
Distance = 128, count = 3
Distance = 256, count = 35
Distance = 512, count = 44
Distance = 1000, count = 91
Distance = 1024, count = 6
Distance = 2000, count = 7

And this for NPCs.

Distance = 0, count = 705
Distance = 1, count = 2
Distance = 5, count = 1
Distance = 16, count = 1
Distance = 30, count = 1
Distance = 32, count = 81
Distance = 40, count = 2
Distance = 56, count = 1
Distance = 64, count = 522
Distance = 66, count = 1
Distance = 70, count = 1
Distance = 100, count = 1
Distance = 126, count = 1
Distance = 128, count = 757
Distance = 200, count = 1
Distance = 256, count = 76
Distance = 300, count = 1
Distance = 384, count = 1
Distance = 500, count = 2
Distance = 512, count = 320
Distance = 1000, count = 26
Distance = 1024, count = 6
Distance = 1280, count = 1
Distance = 2000, count = 71
Distance = 2048, count = 1
Distance = 4000, count = 6
Distance = 5000, count = 2
Distance = 10000, count = 2

This suggests to me that the cut-off distance for wandering is 128.
To check if NPCs at a distiance of 128 should wander or not, I grabbed 6 and observed them in Vanilla.

"orrent geontene", cell = "Ald-ruhn, Guild of Mages"
"tanar llervi", cell = "Ald-ruhn, Guild of Mages"
"tralan", cell = "Ald-ruhn, Guild of Fighters"
"allding", cell = "Ald-ruhn, The Rat In The Pot"
"galtis guvron", cell = "Ald-ruhn, The Rat In The Pot"
"durzum gro-shagrak", "Hlormaren, Underground"

Turns out They do move, but just for short distances along the paths between the nav points.
i.e. They follow the paths, but they don't go as far as the waypoints.

Also looking at "Phane Rielle" in "Balmora, South Wall CornerClub", he DOES face the wall, just not all the time.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

I believe I have improved my prior experiments to show the "Running in Circles" (RiC) issue.
The following image shows the path taken an NPC running AiCombat.
1st AiCombat Path
1st AiCombat Path
00.AiCombatPath.png (28.59 KiB) Viewed 7264 times
Points to note.
The blue circles and the yellow lines are the PathGrid for the cell (Dren Plantation).
The red line is the path the NPC takes when doing a "Line of Sight" (LOS) pursuit.
The black line is when the NPC is using the path grid.
Note that almost every time the NPC tries to use the Path Grid, the NPC starts running in circles.
Steps to reproduce:
  • Go to Dren Plantation.
  • Set player speed to 300 and toggle god mode.
  • Set "frinnius posuceius" speed to 100
  • Hit Frinnius.
  • Make player run until Frinnius looses LOS.
This second image shows my second attempt, which shows the same behaviour.
1st AiCombat Path
1st AiCombat Path
00.AiCombatPath.png (28.59 KiB) Viewed 7264 times
I hypothesise that I could reproduce the behaviour more consistently by doing the following:
  • Modify AiTravel so that NPC will run.
  • Go to Dren Plantation.
  • Set "frinnius posuceius" speed to 100, and AI to AiTravel 20143, -52102, 730
However, as you can see from this image, there's much less RiS occurring.
1st AiTravel Path
1st AiTravel Path
02.AiTravelPath.png (23.62 KiB) Viewed 7264 times
It does occur, but only for 2 of the way points, and it stops after only a few "orbits" (It's hard to see in these reduced images. Using the original images from the data it's more clear.)

A second attempt shows similar results. RiS occurrs, but at reduced levels compared to AiCombat.
2nd AiTravel Path
2nd AiTravel Path
03.AiTravelPath.png (26.38 KiB) Viewed 7264 times
Finally, attached zip contains:
  • pathgridData.js: data used to create the pathgrid in the images
  • 00.AiCombat.ActorPath.js: Actor's path for the first image.
  • 01.AiCombat.ActorPath.js, 02.AiTravelPath.js, 03.AiTravelPath.js: Actor's path for following images.
  • Visualization.html. Code to render the data. (Change filename in line 14 to select actor path to draw.)
  • dumputils.cpp, dumputils.h, code to add to OpenMW to dump out the pathgrid and actor's path
Visualization.03.zip
(13.17 KiB) Downloaded 265 times
Attachments
2nd AiCombat Path
2nd AiCombat Path
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

When I add code to PathFinder::checkPathCompleted() to detect overshoot, it virtually eliminates the Running in Circles.
As shown in this image where frinnius is running AiCombat to follow the player.
01.AiCombatPath.WithOvershootChecking.png
01.AiCombatPath.WithOvershootChecking.png (30.63 KiB) Viewed 7239 times
01.AiCombatPath.WithOvershootChecking.js.zip
(2.92 KiB) Downloaded 258 times

Code: Select all

bool PathFinder::checkPathCompleted(float x, float y, float tolerance)
{
    if(mPath.empty())
        return true;

    ESM::Pathgrid::Point nextPoint = *mPath.begin();
    if (sqrDistanceIgnoreZ(nextPoint, x, y) < tolerance*tolerance)
    {
        mPath.pop_front();
        if(mPath.empty())
        {
            return true;
        }
    }

    // Catch case where 2nd node on path is closer to actor
    // than distance between 1st and 2nd nodes on path
    // Can occur when
    //    Have overshot a nav point, or
    //    Final point on path is between last two PathGrid points
    if (1 < mPath.size())
    {
        std::list<ESM::Pathgrid::Point>::const_iterator it = mPath.begin();
        const ESM::Pathgrid::Point& point1st(*it);
        const ESM::Pathgrid::Point& point2nd(*++it);
        float distBetweenPoints = sqrDistanceIgnoreZ(point1st, point2nd.mX, point2nd.mY);
        float distTo2ndPoint = sqrDistanceIgnoreZ(point2nd, x, y);
        if (distTo2ndPoint < distBetweenPoints)
        {
            mPath.pop_front();
            if (mPath.empty())
            {
                return true;
            }
        }
    }

    return false;
}
User avatar
ElderTroll
Posts: 499
Joined: 25 Jan 2012, 07:01

Re: Feature #2229: Improve pathfinding AI

Post by ElderTroll »

Very cool. I wish I understood the intricacies of this. I am sure working with A.I. involves a lot of trial and error. Thanks for improving this, dteviot. It would be terrible if all the npc's were suffering from acute inner ear infections or possibly side-effects of skooma.
corycohen
Posts: 30
Joined: 26 Sep 2012, 03:05

Re: Feature #2229: Improve pathfinding AI

Post by corycohen »

Hopefully this observation will assist in testing the running in circles bug.

Escorting Huleeya from the Black Shalk Cornerclub to Jobasha's Rare Books as part of the Vivec Informants quest triggered what I assume is a variant of the running in circles behavior. Huleeya runs in circles (permanently?) almost immediately after entering the door and completing the escort quest. I've tested this twice, and the same behavior occurred both times.

This same quest shows another unfortunate feature of the current pathfinding algorithm, which is that when you exit the Black Shalk Cornerclub, Huleeya and the player are at the exact same location, causeing teh first few frames to be rendered from inside Huleeya.
corycohen
Posts: 30
Joined: 26 Sep 2012, 03:05

Re: Feature #2229: Improve pathfinding AI

Post by corycohen »

Has there been any consideration or discussion about using something like Recast/Detour?

https://github.com/memononen/recastnavigation

I don't have any personal experience with this beyond downloading, building, and playing with the demos, but this is a notoriously hard problem, and this library seems to have thought through a lot of the issues.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

I've updated AiCombat to call PathFinder::checkPathCompleted() and PathFinder.getZAngleToNext() each frame.
This results in significantly less "Running in Circles" (RiS). It still occurs on my system, but it occurs much less, and when it does occur, the actor fixes itself within a few "revolutions". Note, I suspect the reason I'm seeing it is because I'm running at 4 FPS. (Because I'm using a Windows, 32bit, debug build. Reconfiguring to make a release build is just too painful and time consuming, given that I have to manually configure cmake. It refuses to recognise that OSG is installed.)

However, even with per-frame updates, there's still some RiS, which occurs when the AI shifts from Line-of-Sight pursuit to following the path grid. This can be seen in the below diagram.
20.actorpath.doublingBack.png
What's happening is when the path grid following starts, the actor heads for the nearest pathgrid point. Which in image below, is the waypoint the actor has just passed. This is the same problem that was seen (and fixed) in AiFollow, where the "path to follow" is constantly re-calculated.

Checking to see if actor should ignore the first waypoint on a path and start with the second is easily implemented, and seems to fix the problem. Note, that there is still some RiS.
21.actorpath.Check2ndWaypoint.png
And here's the raw data, if anyone wants it.
NewPathing.zip
(6.25 KiB) Downloaded 259 times
@corycohen
I have not been able to reproduce Huleeya running in circles. That said, Huleeya appears to be using AiFollow., and that bug was fixed a few weeks ago.
For future reference, including a save game file would save me time and usually makes problems easier to reproduce.
User avatar
cc9cii
Posts: 523
Joined: 28 Mar 2013, 04:01

Re: Feature #2229: Improve pathfinding AI

Post by cc9cii »

corycohen wrote:Has there been any consideration or discussion about using something like Recast/Detour?

https://github.com/memononen/recastnavigation

I don't have any personal experience with this beyond downloading, building, and playing with the demos, but this is a notoriously hard problem, and this library seems to have thought through a lot of the issues.
I'm trying to get this going at the moment, but cant quite get my head around it.
corycohen
Posts: 30
Joined: 26 Sep 2012, 03:05

Re: Feature #2229: Improve pathfinding AI

Post by corycohen »

dteviot wrote:I have not been able to reproduce Huleeya running in circles. That said, Huleeya appears to be using AiFollow., and that bug was fixed a few weeks ago.
For future reference, including a save game file would save me time and usually makes problems easier to reproduce.
My apologies for not posting a save game. I didn't know if you'd want/need one. I tried to attach a save file just now, but the server won't accept it. I have a save where I'm looking at Huleeya with the behavior occurring as soon as I can figure out how to upload it.

I hope we're talking about the same behavior. He'll stop occasionally to perform an animation (such as scratching his head), but most of the time he just twirls in circles, both clockwise and counter clockwise. He seemed "trapped" in the square immediately inside the door. If this isn't related to the problem you've been investigating, and you want me to open a ticket, please ask. I've assumed it was the same issue you were troubleshooting already.

I'm running a development build from commit ac1f64b5593f742fe34017dd07077a6c0da71956 on July 28, so it sounds like I should already have the AIFollow fix you're referring to, but maybe not.
corycohen
Posts: 30
Joined: 26 Sep 2012, 03:05

Re: Feature #2229: Improve pathfinding AI

Post by corycohen »

cc9cii wrote:I'm trying to get this going at the moment, but cant quite get my head around it.
Like I said, I'm no expert, but I did get the demos to build, and I played with it for a while, and it seemed pretty robust. The demos essentially allow you to drop a whole bunch of path-finding agents into the level, and then dynamically change the obstacles, path-end points, etc. The agents all collide with each other and reroute. You can split the agents into groups with placed obstacles, and they'll route differently depending on which side of the obstacle they were on. The agents also seem to understand limits about jumping off edges and climbing stairs. It knows how to keep the agents a minimum distance from walls so that they don't clip into the walls while walking around corners.

If you haven't found them already, these videos will give you the idea without having to build the demo:

https://www.youtube.com/watch?v=a9fbwKWFHFo
https://www.youtube.com/watch?v=gYnfWx4cBEs
https://www.youtube.com/watch?v=veZIqHTcBFk

And this was the article singing the praises of navigation meshes that originally led me to recast/detour.

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

The demo I ended up running was actually this one (in addition to the level in the YouTube videos):

http://masagroup.github.io/recastdetour/
Post Reply