Feature #2229: Improve pathfinding AI

Everything about development and the OpenMW source code.
User avatar
wareya
Posts: 338
Joined: 09 May 2015, 13:07

Re: Feature #2229: Improve pathfinding AI

Post by wareya »

How about improving the AI?
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

@mrcheko
mrcheko wrote: 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
Thanks for that. I've found it and updated the PR so that AiFollow will use this sync logic as well.
That seems to reduce the “running in circles” when using AiFollow.

@scrawl
scrawl wrote: 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.
Thanks, but it doesn't seem to have any effect. I think it's because AiFollow won't start moving the NPC until you're within 500 units and have Line of Sight. This is due to code you added to AiFollow.execute() in December.


That said, the changes I mentioned above DO appear to reduce running in circles when using AiFollow, although as I had trouble setting up a test case to reliably reproduce the problem, I'm not 100% sure it fixes all cases.

Assuming that this DOES fix the “running in circles when new path is generated when first waypoint of new path is waypoint that NPC just passed", which it SHOULD do. Then the remaining “running in circles" problem occurs when NPC keeps on overshooting the waypoint.

As you rejected my first attempt at fixing it, my suggestion is change the tolerance on checkPathCompleted to 80.0f. This should eliminate most, if not all, the “running in circles" behaviour.

@wareya
wareya wrote:How about improving the AI?
Can you be more specific?
I am trying to fix the pathfinding issues. Which are AI.
Fixing running in cicles seems to be the easiest issue to fix.
Handing getting stuck is next on the list. I think I might try the "If stuck, see if there's a waypoint that does have a LOS on current position, and head for that."
User avatar
scrawl
Posts: 2152
Joined: 18 Feb 2012, 11:51

Re: Feature #2229: Improve pathfinding AI

Post by scrawl »

Thanks, but it doesn't seem to have any effect. I think it's because AiFollow won't start moving the NPC until you're within 500 units and have Line of Sight. This is due to code you added to AiFollow.execute() in December.
True. Well, then you could tell the NPC to AiFollow while you're near them, then disable AI (enter toggleAI in the console), move out of their line of sight, then toggleAI again.
my suggestion is change the tolerance on checkPathCompleted to 80.0f.
That value seems excessively large. The change would fix one bug but create others in the process.
I think the root cause of the problem you are seeing would be AiCombat calls checkPathCompleted only every 0.25 seconds (tReaction). If we check it every frame instead, wouldn't that fix the issue?
User avatar
gus
Posts: 390
Joined: 11 Aug 2011, 15:41

Re: Feature #2229: Improve pathfinding AI

Post by gus »

That value seems excessively large. The change would fix one bug but create others in the process.
I think the root cause of the problem you are seeing would be AiCombat calls checkPathCompleted only every 0.25 seconds (tReaction). If we check it every frame instead, wouldn't that fix the issue?
Checking every frame is not a good idea as it would give different results for different computers, making testing hard. However, testing every 0.1 sec should be fine.
To do the testing, one should increase the NPC speed to 100 and check for problems.
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

@scrawl
gus wrote:
That value seems excessively large. The change would fix one bug but create others in the process.
I think the root cause of the problem you are seeing would be AiCombat calls checkPathCompleted only every 0.25 seconds (tReaction). If we check it every frame instead, wouldn't that fix the issue?
Checking every frame is not a good idea as it would give different results for different computers, making testing hard. However, testing every 0.1 sec should be fine.
To do the testing, one should increase the NPC speed to 100 and check for problems.
I think I've got a better idea. Based on what I originally tried in AiCombat to fix. Which was to check if NPC is getting further away from waypoint, if I move this logic into PathFinding.checkPathCompleted() it will be available for all AiPackages.
Basic change is to add member variable to PathFinding to record distance each time checkPathCompleted() is called and compare it with previous call.

@Gus, thanks for the suggestion of increasing the NPC's speed.
User avatar
gus
Posts: 390
Joined: 11 Aug 2011, 15:41

Re: Feature #2229: Improve pathfinding AI

Post by gus »

I think I've got a better idea. Based on what I originally tried in AiCombat to fix. Which was to check if NPC is getting further away from waypoint, if I move this logic into PathFinding.checkPathCompleted() it will be available for all AiPackages.
Basic change is to add member variable to PathFinding to record distance each time checkPathCompleted() is called and compare it with previous call.
it's possible that it never goes further away if you run in perfect circle, or if the NPC runs in a spiral, so this might not work.But I like this idea and in the same spririt,you might do the check on the zAngle. If this angle change of 180 degrees, then you've past the waypoint. What do you think?
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

gus wrote: it's possible that it never goes further away if you run in perfect circle, or if the NPC runs in a spiral, so this might not work.But I like this idea and in the same spirit,you might do the check on the zAngle. If this angle change of 180 degrees, then you've past the way-point. What do you think?
  • Running in a spiral is not a problem. If you're spiralling in, then eventually you'll get close enough to trigger the threshold, if spiralling out, then checking against the prior length will trigger.
  • Running in a perfect circle is possible, but due to issues such as varying frame-rate and the discrete mathematics, I suspect will be exceedingly rare. FWIW, I never saw this happening in my experiments.
  • zAngle may be useful, but I don't think it will always be 180 degrees, due to the "running in circles" effect. i.e. Due to the NPC turning between checks, the path isn't a straight line going over the way point.
  • My thought is apply the "Keep It Simple" principle. Try the simple approach first (just use length) and see how well it works. (My experiments showed it works.) Now, I agree that I'd like a 100% perfect solution, but a solution that works 99.99% of the time, is probably good enough for a game, and the additional effort and complexity to get 100% is better spent elsewhere. (Note, if the cost for 100% is small, then, yes it's probably worth it.)
dteviot
Posts: 144
Joined: 17 Dec 2014, 20:29

Re: Feature #2229: Improve pathfinding AI

Post by dteviot »

@Gus
Here's the experimental data
At the Dren plantation, (cell 2, -7).
With "frinnius posuceius" given a speed of 100, who I hit to make him chase me.

First two numbers are frinnius' X and Y co-ords.
Second two numbers are the waypoint frinnius is trying to reach.
Next two numbers are the X and Y deltas between his position and the waypoint.
Last number is the distance to the waypoint.

Items of note, frinnius is running around in circles a LOT, almost every waypoint when you set his speed to 100.
Second point, Average circling distance is 100 units. (close enough.)
Third point, gus' theory seems to be mostly correct, when overshoot occurs, the delta X and or delta Y values change sign.
Spoiler: Show
Setting threshold value to 100, I get the following.
It works resonably well. Note, checkPathCompleted() is only called for every third time
the possitional information is written.
Spoiler: Show
User avatar
gus
Posts: 390
Joined: 11 Aug 2011, 15:41

Re: Feature #2229: Improve pathfinding AI

Post by gus »

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?
About the angle, I think it should work instantly in theory as they do mostly go in straight line until they reach the waypoint (unless they get stuck in something). But if it is no longer noticiable with your methods, who cares ^^
User avatar
scrawl
Posts: 2152
Joined: 18 Feb 2012, 11:51

Re: Feature #2229: Improve pathfinding AI

Post by scrawl »

I don't like this change. The code detects if the NPC has run in a circle close to the waypoint, and sets the arrived state when that happens. I can imagine that causing problems: 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.

I say that's putting on a bandaid and not a correct fix. Running in a circle should never happen in the first place.

Calling checkPathCompleted every frame would be a better fix, with no adverse side effects.

@gus:
Checking every frame is not a good idea as it would give different results for different computers, making testing hard.
Why is that a problem here? Sure, the more framerate you get, the more accurate pathing will be. But even with unplayable framerates of say 10 frames per second, the pathing precision would still be better than what we have now.
However, testing every 0.1 sec should be fine.
That still doesn't make pathing truly framerate independent. You can't check pathing more than once per frame, because there isn't new world state to respond to. If the game gets below 10 frames per second, we'd have less than 10 pathfinding checks per second.

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).
Post Reply