NPC Jumping - How would someone do that?

General discussion regarding the OpenMW project.
For technical support, please use the Support subforum.
Post Reply
User avatar
Greendogo
Posts: 1467
Joined: 26 Aug 2011, 02:04

NPC Jumping - How would someone do that?

Post by Greendogo »

So our new pathfinding looks pretty slick, but, as usual, NPCs still can't jump over simple obstacles that their acrobatics and such should allow for.

For an example of this, check out the Navmesh video at around 1:22 https://youtu.be/BYuGEsScpf0?t=82. The NPCs should easily be able to get over that wall if they jump, but they're never told to use Jump (I think ever).

How would you implement Jumping in OpenMW? My first and only idea would be to only allow it when the NPC is fighting or running. Of course, this runs into problems with Jumping in to lava. (That's another consideration for much further down the road - how do you prevent them from running into meshes with scripted damage?)
imec
Posts: 37
Joined: 13 May 2012, 22:03

Re: NPC Jumping - How would someone do that?

Post by imec »

This is a really complicated subject and seems like it's going to be hard to fix after testing in-game a lot. Also, as you touched on with the lava there is some overlap here with AI behavior.

Some problems:

1-way paths:
If NPCs could drop anywhere there is a small ledge they would regularly trap themselves. If the solution is to drop only where there is a clear path to the target, then this could be exploited to trap NPCs in pits.

Some NPCs should never drop:
NPCs (archers mainly) are meant to be trapped on top of ledges and shouldn't be able to drop. How does the game identify them?

Some NPCs (in the future) might always need 2-way paths:
I wouldn't be surprised if NPCs are given the ability to return to starting position eventually. Such NPCs would probably need to perform two checks: one to see if a piece of navmesh below connects to target, but also allows them to return to their starting position. But that causes big problems too (running around in circles because of a ledge). On the other hand, this would solve the problem in the video and should be an improvement over the current behavior.

This is just if NPCs are able to drop. NPCs that are able to jump can probably overcome some of these problems, but that's sure to have its own set of issues. Also to my knowledge creatures do not have jump animations, so that's also something to think about.

Jumping is in the pull request however, so I have faith that elsid will come up with something given the quality of his work so far.
User avatar
drummyfish
Posts: 154
Joined: 22 Oct 2017, 10:13
Contact:

Re: NPC Jumping - How would someone do that?

Post by drummyfish »

I've never dealt with this, just thinking aloud:
  • You can either try to make a clever if-then-else algorithm whose behavior will probably be easily guessable and exploitable as imec mentioned and you'd be dealing with all the special cases manually. or
  • You can apply some general state-space-search algorithm, you know, like with chess. I.e. every N frames the NPC could stop to think what situation it's currently in (a function of "am I stuck? low health? enemy is near of far? etc.") and then try to mentally find the best action to do next (jump, shoot, keep running, ...), thinking ahead let's say 2 or 3 actions. This would be general, i.e. work for newly added actions etc., but would require to simulate the game ahead of time.
I don't know if case B is used in games for combat/path AI, just what came to my mind. Maybe would be too complicated, slow etc. Don't know, is it bad?
imec
Posts: 37
Joined: 13 May 2012, 22:03

Re: NPC Jumping - How would someone do that?

Post by imec »

Looking at the RecastDemo, it turns out that RecastNavigation supports something called Off-Mesh Links. They are essentially arches that connect meshes or bypass holes in a mesh. I am not sure if there is a way to generate them automatically in the library or not, but I suspect they will play central role in jump support.

They can be set as bidirectional or 1-way too, so modders would have a lot of options to keep anything from getting stuck or acting weird if they were to be placed manually.

Here is what they look like in Unity:
https://www.youtube.com/watch?v=5p4zqnGqK2A

I think they are probably good enough to support some kind of zombie mode. I put a ton of them up in Balmora and the crowds are able to pursue their targets virtually anywhere a navmesh had been generated (lots of building hopping). It's really neat.

@drummy
I think the current implementation is pretty aggressive with how often new paths are drawn going from console output and I've never really noticed any slowdown from it. Enemies pretty much instantly change direction when you go over a wall for instance, even if there are 20 or more of them.

I think something similar to what you're talking about is going to be necessary in the end. Even in the base game, actors need to be able to flee when they're hit with a fear spell for example. Also, some kind of functionality that tells actors where they need to be on the navmesh in order to be out of view of the player would be so much better than vanilla Morrowind behavior. Bethesda games up to FO4 had a huge problem where enemies would just let you snipe them in the face if you were out of reach and there seems to be an opportunity to fix that here.
Rovlad
Posts: 19
Joined: 11 Apr 2018, 06:29

Re: NPC Jumping - How would someone do that?

Post by Rovlad »

Wow, improved pathfinding and AI behavior definitely sound like a life changer.
Now that would definitely be a feature to win people over from the original engine.
erretel
Posts: 14
Joined: 29 Jan 2018, 23:20

Re: NPC Jumping - How would someone do that?

Post by erretel »

imec wrote: 11 Apr 2018, 06:07 Some NPCs should never drop:
NPCs (archers mainly) are meant to be trapped on top of ledges and shouldn't be able to drop. How does the game identify them?
This one has a crude and easy solution. Enemies wielding ranged weapons or reading spells shouldn't be allowed to jump. This solution would also create the cool situation when one enemy uses up all his ammo, equip a melee weapon and jump down in the fray.
Post Reply