Feature #2229: Improve pathfinding AI

Everything about development and the OpenMW source code.
Chris
Posts: 1625
Joined: 04 Sep 2011, 08:33

Re: Feature #2229: Improve pathfinding AI

Post by Chris »

scrawl wrote:Logic depending on framerate is something we'll just have to accept for the time being, until a bigger refactoring comes along to decouple all game logic from rendering, decouple physics from logic and rendering, etc (and I'm not convinced that would be a good idea, either).
I think it is, if we want to be scalable at higher framerates. As it is, we're running physics every frame, so getting 60 fps means 60 physics updates per second. If you want to get 120 to 140 fps (or more, considering g-sync and the like), that means we're doing that many physics updates per second, which besides being completely overkill, could harm the simulation as movement sizes shrink and we start running into the lower bounds of fp precision. We could cap the physics to 60 updates per second, but then we're effectively capping the framerate at 60; even if we render more, nothing will have moved.

The better option would be to use Bullet's simulation loop with the appropriate character controllers/callbacks, which I believe does 30 updates per second and applies interpolation when in between updates, effectively decoupling the physics from the logic and rendering. This makes sure the update period is long enough to prevent slow moving objects from rounding to a 0 delta, while also being able to efficiently move objects more than 60 times per second.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

@scrawl
@Zini
TL;DR;
I will concede Scrawl's point, calling checkPathCompleted() will reduce the "running in circles" incidents.
I'll test that out this weekend and see how it works.
But I suspect we still need to check for overshooting waypoints when framerate is low.

Also, I'll point out PR 606 doesn't just contain the fix for "running in circles when overshoot waypoint".
It also contains "running in circles when path is recalculated and nearest point is one NPC has just passed", and "removed duplicated code from AiTravel".

More details:
gus wrote:good to see that it works! Do you still notice it? I see that in one of your data it take almost 2 second to detect the running in circle. Or is it me not reading the data's correctly?
Viewing the NPC running, I didn't notice it. But then I was only running at 2 frames / sec.
You could try for yourself. Go to Dren plantation (coe 2, -7), set speed on a guard to 100, give yourself speed of 400, hit guard and run around.
Then apply my change and try again.
scrawl wrote:The NPC isn't within the waypoint threshold yet, which will throw off pathing to the next waypoint, as in, the NPC might get stuck on geometry because it didn't stick close enough to the waypoints.
If NPC is overshooting the waypoints in the first place, then NPC is just as likely to be stuck in the geometry due to that.
scrawl wrote:Running in a circle should never happen in the first place.
Only if the framerate is sufficiently high that the distance an NPC can move between frames is less than the tolerance for deciding if the NPC has reached the waypoint.
When it's not, overshooting the waypoint is GOING to happen, and "running in circles" will happen.

Which I think is the point that Gus was trying to make. If someone has a high framerate, they won't experience the problem. If someone has a low frame rate, they will.

That said, calling checkPathCompleted() every frame instead of every 0.25 seconds will reduce the problem. It won't solve it. The positional data I've already posted is one row for each frame, and you can see overshooting the waypoint occurring.

I also think I've figured out a better way to way to check if overshoot occurs.
Basic idea.
For each frame, record distance from waypoint, and NPCs position.
Next frame, compare NPCs new position with old position to get distance travelled.
If distance travelled > distance from waypoint at previous frame, then NPC overshot the waypoint.
(And to be safe, check that NPC was sufficently close to waypoint in the first place, probably around 100 units.)
User avatar
gus
Posts: 390
Joined: 11 Aug 2011, 15:41

Re: Feature #2229: Improve pathfinding AI

Post by gus »

@scrawl: you idealy want the smallest possible thresold. Thus choosing the smallest possible thresold depends on the framerate. Testing which thresold works will be difficult if it depends on framrate I think
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

@scrawl
PR #606 https://github.com/OpenMW/openmw/pull/606 contains three commits. You've rejected the third one of these, but are the other two acceptable?
If they are, I'll put together a new PR with just those two, so at least one source of "running in circles" can be eliminated.

Thanks.
User avatar
scrawl
Posts: 2152
Joined: 18 Feb 2012, 11:51

Re: Feature #2229: Improve pathfinding AI

Post by scrawl »

The first two commits look ok, yes.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

scrawl wrote:The first two commits look ok, yes.
Done. https://github.com/OpenMW/openmw/pull/611
Thanks.
mrcheko
Posts: 2
Joined: 03 Jun 2015, 19:31

Re: Feature #2229: Improve pathfinding AI

Post by mrcheko »

I would bet that checking each frame won't affect running-in-circles problem (or will affect it minimally). The main cause of the problem is limited turn speed, not frequency of threshold checks. You can tweak that max turn speed value (don't remember where is it) and see how the circling disappearing. So another idea to achieve
scrawl wrote:Running in a circle should never happen in the first place.
is to predict that circling: take into account distance to waypoint, direction and max turn speed and if an actor don't have time to turn directly on wp in the first try then switch to walk or stop completely, turn and continue moving.
... or go to waypoint backward or sideways, without turning :D

I also assume this should be done only for the 1st wp, cause distance and angle between wps will be sufficient for an actor to make a turn.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

@scrawl
scrawl wrote: Can we fix this for all AiPackages at once please?
Actually, I've updated AiPackage.pathTo() to call the buildSyncedPath(), which I believe fixes it for all packages but AiWander (which doesn't need the synced path) and AiCombat, where I explicitly call buildSyncedPath(). So, done.

My longer term plan is to get all packages to use AiPackage.pathTo() for movement. But I'm trying to do the changes in small steps (excuse the pun.) Because when I put in a multiple changes, you tend to reject one of them, and I have to re-work and re-submit. So, I'm doing this in small pieces, to reduce the re-work I have to do.
scrawl wrote: Is there any reason now to build a "non-synced" path? If the answer is no, then we should merge buildSyncedPath into buildPath so that all AiPackages profit from the change
I considered this, but there was at least one place where non-sync was called.
IIRC, it was AiWander. And AiWander has some very customized logic, so it CAN'T just be wired into AiPackage.pathTo(). AiWander does NOT need the non-sync version, because it only creates a new path when NPC reaches the destination. So there's never an old path to compare.

As regards merging buildSyncedPath() into buildPath(), I don't think that's a good idea.
buildPath() already has complicated logic, and adding the sync logic will make it more complicated.
That said, my plan is be to make buildPath() a private function that is only called by buildSyncedPath(). I could also rename the functions, changing buildSyncedPath() to buildPath(), but I have not been able to come up with a good new name for buildPath().

But again, small steps.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

DataVisualizationHtml.zip
HTML + Javascript + Data used to create images.
(16.1 KiB) Downloaded 240 times
Check for waypoint each frame
Check for waypoint each frame
I did a bit some work to visualize the "walking in circles" problem.
I used the following code to record data for each frame in AiCombat:

Code: Select all

        if (actor.getCellRef().getRefId() == "frinnius posuceius")
        {
            ESM::Position pos = actor.getRefData().getPosition();

            // NPC position
            std::cout << "[" << pos.pos[0] << ", " << pos.pos[1];
            if (0 < mPathFinder.getPathSize())
            {
                std::list<ESM::Pathgrid::Point>::const_iterator p = mPathFinder.getPath().begin();
                
                // waypoint co-ords
                std::cout << ", " << p->mX << ", " << p->mY << ", ";
                
                // now do current heading and desired heading
                std::cout << pos.rot[2] << ", " << movement.mRotation[2];
            }
            std::cout << "]," << std::endl;
        }
I then used some javascript to convert the resulting data into a 2D path.
(black line is NPC's path, red circles are waypoints (NPC needs to end inside a circle to start next path segment.)

First picture shows path when call checkPathCompleted() each frame.
Second picture shows path with unmodifed code.
Note in both cases, when circling started, I broke the NPC out of it by moving close enough that NPC started "shortcutting".
Zip file contains the HTML used to create the images.
Attachments
No changes to code
No changes to code
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

scrawl wrote: Noticed a problem introduced by this commit. In "Balmora, South Wall Cornerclub" Phane Rielle always faces the wall, instead of towards the room.
I do not believe there is a bug.
"phane rielle" has an AI of wander 64 with a speed of 46.
Looking at the Path Grid, this means there are two points he moves between. One directly behind the bar, the other beside the wall behind the first waypoint.
When phane walks to the wall waypoint, when he stops he faces the wall. Then when he walks back to the bar, when he stops he faces the bar.
He does seem to spend a lot of time at the wall waypoint, and it can take a while before he moves.

On further thought, this may be a bug.
Introduced by https://github.com/dteviot/openmw/commi ... 25c22aebbd
Basically, if AiWander is not 0, then distance is expanded until NPC has two Path Nodes to wander between.
I suspect a wander distance of 64 is so small that Phane does not wander in vanilla.
Could be fixed by only doing the distance expansion if wander is greater than some tolerance value. (e.g. 128 or 256).
Note to self, should analyse the Morrowind data files, and see what the wander distances are. May be other characters with same problem. (Should allow me to figure out what the best threshold value is.) Will do this weekend if I remember.

Incidentally, I suspect be6ee92 is also responsible for the "Disallow AiWander fast-forward for water creatures" bug that you've checked in a fix for. As it stands, be6ee92 will probably make a water creature try to swim onto land, as again, most way-points are on land. Suggested fix, getAllowedNodes() should probably return nothing for water creatures.
Instead, water creatures probably should get their own pathing. If I remember, I'll do a little studying of Vanilla this weekend.

Thoughts anyone?
Post Reply