Bug #2726

[dteviot]

I'm creating this so we can have a permanent, easily findable, record of my screw-up.

Original problem was bug https://bugs.openmw.org/issues/1317. where Erene Llenim did not wander because his wander distance was not big enough to include 2 waypoints. In Vanilla, Erine walks between the two waypoints closest to his starting point.

The first attempted fix was, when an NPC has a non-zero wander distance, expand the wander distance until two waypoints are available.
Unfortunately, this introduced two unwanted side effects, due to pathgrids not being uniformly supplied.

• Aquatic creatures would appear on land (because there are very few waypoints in water.
• #2726 NPCs would walk out of position. When the nearest pathgrid points in the cell were some distance from the NPCs location, the NPCs would wander away from their expected locations.
• There's over 700 NPCs and creatures which have wander distances between 10 and 128 units (inclusive), which is less than the typical distance between waypoints. Implying the NPCs are supposed to wander a only a few steps from their starting locations. (Aside, Why they have such a range of small values I have no good idea, other than at the time of writing Bethesda had no standard, so different artists just plugged in any old value. With Tribunal and Bloodmoon the distances are much more uniform.)

Anyway, this patch removes the original faulty fix, and attempts to fix Erene and any similar cases where the selected wander distance isn't quite big enough to encompass 2 points (possibly because Vanilla applies a small scaling factor to the wander distance which we are unaware of), without introducing the above problems. It does not attempt to fix the problem of what to do when there are no waypoints, (or the wander distance is < 256.)

FWIW, I don't believe vanilla works this way at all. i.e. AIWander does not require pathgrid points. You can see that by creatures with AiWander in places where there are no pathgrid points. OpenMW's implementation that relies on pathgrid points will require these kinds of workarounds.

Yeah, I'm not fond of the expanding idea. The correct fix is to support wandering with no pathgrid nodes. This PR is much better than the current behaviour though (not sure how that slipped past review). So let's merge it.

This is not correct.
Expansion may feel nice for now but it is entirely a
band-aid solution and I don't think merging would be a good idea.

Wandering with no pathgrid nodes was an issue involved in the pathgrid
format itself if I remember correctly, which is why I didn't implement it.
The true pathgrid also creates nodes for the initial position of each NPC
on the map and also allows for stopping in between path nodes. Meaning
everywhere there is a line between nodes, the NPC can go there as a final
destination with AIWander. As well as anywhere (even places not linked to
with path nodes) that an NPC was placed on the ground when initially
loading the cell, is also a usable destination for building a path.

I am heavily against merging this, but it is not up to me.

Actually, creatures do rely on pathgrids in vanilla if I remember correctly. Morrowind generates a blanket pathgrid for exterior cells that do not have one, this pathgrid is very basic and just has holes for static objects and water (being the reason NPCs and creatures in the wild walk around like idiots a lot of the time).

If we correct the pathgrid generation in OpenMW and adjust AIWander to work with it, the current implementation would be vanilla accurate.

@TorbinC
Even if this is correct, it will not solve all cases. e.g. https://bugs.openmw.org/issues/2726 refers to the "GhostGate" cell. This cell does have a path grid, it's just that none of the points are in the camp where two NPCs start at. (The screenshot associated with #2726 which shows the pathgrid has been taken from the position of the camp.)
It also doesn't solve the case of what to do when wander distances are smaller than the grid size, but non-zero.
(Note, if distance is < 256, I think we can assume ground is going to be close enough to flat (in most cases) to just move that distance in a random direction.)

edit: corrected quote attribution.

[TorbenC]

This Ghost Fence pathgrid actually has me quite confused, but it has been over a year since AIWander was my fascination haha.

[dteviot]

I've put together a very simple routine for AiWander to handle the “no path grid points” case.
Basically, it picks a point thats “Wander Distance” from the NPC's initial location, and heads for it, doing castRay() to check if the destination is accessible.

https://github.com/dteviot/openmw/tree/ ... NoPathGrid

I think it works pretty well, although it does highlight that the ObstacleCheck class doesn't work very well. (and StuckCount is never reset.) And I should probably replace the castRay() with getDistToNearestRayHit().

Probably best places to see the problems are habasi in “Balmora, South wall cornerclub”, and the king dreugh in “koal cave”.

Anyway, I thought I'd post it up for people to give it a try and see what they think of it.

Thanks for your time.

[cc9cii]

I had implemented something similar a long time ago but couldn't find a nice way to deal with rocky areas (terrain height can be used as well as water level in deciding whether a spot is a suitable target, but statics such as rocks are not reported). Your idea of ray casting might be the solution.

[dteviot]

@scrawl
@TorbinC
@zini

Thinking about this a bit more, AiWander has 3 scenarios when trying to figure out a destination for an actor to wander to.

• There are 2 or more nav points within the wander distance.
• There is 1 nav point within the wander distance.
• There are no nav points within the wander distance.

Our existing code (prior to my attempt to fix #1317) handled the first case. And ignored the other two. So actors didn't wander for cases 2 and 3.
Looking at Vanilla some more, it looks like when case 2 occurs, AiWander will generate something like the following a set of possible destinations:

• The actor's initial location.
• The nearest nav point.
• point(s) partway along the path(s) between the nearest nav point and it's connected neighbours.

Further, it looks like this is kind of what Erene does. I've seen her stopping partway along the paths. So, if I rip out the "expand the range" code, doing the above should get Erene moving. Along with all the other Actors with small wander distances, but a nearby nav point. e.g.
"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"

This doesn't solve the case of what to do when there are no nav points.
In this case, I think something like "Pick a point in the wander distance at random and go there" is the solution.
Aside: As this behaviour is (to an observer) similar to the "only one nav point" case, it raises the question; should I even bother implementing the "one nav point" case?
I think the answer to this is yes, for the following reasons.

• OpenMW goal is to reproduce the Morrowind behaviour as exactly as possible.
• The "one nav point" case seems to be common, and by following the path grids, I think there's much less chance of the actor getting "stuck".

Final note, the above model does NOT accurately match what Erene does. She actually travels past the second nav point node from her start location, and stops between the second and third nodes. She also stops on between the first and second nodes, and on the first (closest) node.

My opinion is, implementing the above model will at least get Erene moving, and 99% of players won't notice the difference. However, any thoughts on where my model is incorrect would be appreciated.

[Chris]

This doesn't solve the case of what to do when there are no nav points.
In this case, I think something like "Pick a point in the wander distance at random and go there" is the solution.

I think the correct result is to walk nowhere. There's at least one NPC in vanilla that's supposed to stand in place, not wander randomly within his set radius (or go to the nearest nav point, which is across the river).

[dteviot]

This doesn't solve the case of what to do when there are no nav points.
In this case, I think something like "Pick a point in the wander distance at random and go there" is the solution.

I think the correct result is to walk nowhere. There's at least one NPC in vanilla that's supposed to stand in place, not wander randomly within his set radius (or go to the nearest nav point, which is across the river).

I think I wasn't clear. The AiWander struct contains a "Distance" value, indicting how far the NPC is supposed to wander.
There are 27 creatures and 705 NPCs with a wander distance of 0. See: viewtopic.php?f=6&t=2916&start=30

Obviously, these creatures and NPCs should not move, and the existing AiWander logic explicitly tests for this condition and does not move them.