Working with 'dynamic' navigation invokers

Development Programming & Scripting Blueprint
1

I have a slight problem with navigation invokers vs a fully nav meshed world.

Currently I have a system set up where my nav invoker AI will:

  1. find out which direction their target location is, which most likely is outside their ‘tile generation radius’
  2. select the closest point within their ‘tile generation radius’ and go there
  3. then repeat previous steps until they’re as close to their target position as possible.

However this can lead to problems when they have to go around objects that are larger than their ‘tile generation radius’.

Here’s a picture explaining the problem:

lyXE5jV.png
lyXE5jV.png820×717 57.8 KB

In frame 1 and 2, the AI tries to move as close to the target position as it can. Constantly finding the closest point within its generated ‘tile generation radius’, however eventually it reaches a wall and the opening is out of reach so it’ll simply get stuck there against the wall.

In frame 3, with the whole world being navmeshed the AI will find the proper route around and inside.

Is it solvable with the dynamic invokers without having giant tile generation radiuses around them?

Hopefully my crappy mspaint illustration gets the point across, I guess I can post videos or something if it’s not clear enough.

All help greatly appreciated, thanks.

2

also interested with this, but i think, best way i have planned out using av invokers is to spawn a nav invoker at the destination point and use behavior trees for the character, then for a random time between 10-15 seconds, update the path to target…
this way, as long as the target has nav invoker there is a path… and as the navi invoker keeps updating the nav mesh around it with the tile generation radius, the 10-15 second updates re update the path… this way, it wont get stuck…

well, i have not implemented it yet… but i think it would work… won;t hrt to try it out :smiley:

3

Thanks for the reply. I was starting to think I was the only one that needed my nav mesh invokers to travel large distances since I haven’t seen any solutions to this problem.

Hm, that might help in some cases to spawn another invoker at the target location, however if the distance is too long between the area thats stopping the AI and the “doorway”, there will be dead space between them so that wouldn’t help.

Unless you somehow spawned multiple invokers in a line between the AI and the target location, how would that even be done?

Even so, if the blocking area is too wide, a straight line of multiple nav invokers might not be a solution at all.

4

Random Thought of the Thread: Have the AI character look at its destination. Line trace it. Every 2000 units or so, drop a navigation marker. Navigate to the markers and clear them out when near one. Giving it a radius threshold of about 500 or so should allow the AI character to path in a general direction towards its destination.

Just a theory that popped into my head, imagining an NPC seeing past the buildings, past the mountains and at its final destination, kind of like super x-ray vision. A lot like the brief few seconds you spend when you want to go to your house from where you are and you generate a route in your mind of how you are going to get there.

5

@Yggdrasil, if I understand you correctly, please correct me otherwise, that would technically work if the way is a straight line or the buildings/blocking objects are not wider than the generated tile radius. But if it has to walk around large/wide objects, I don’t see how that solves the problem unless I spawn multiple invokers on the way offset both to the left/right.

Here’s some pics for clarification:

iVuyXbZ.png

Let’s say the target point is the large sphere on top of the platform, however the stairway is on the other side.

As far as the computer knows, thats the closest it can get to it since the stairway is out of its generated navmesh. The gizmo is where my AI is currently located.

It needs to sidetrack even further if the platform is wider, like here.

EDIT: Here’s a video of the issue. As shown, smaller platforms within the nav mes radius are no problem, the ai navigates around it just fine. However it will not go to the sphere target on top of the larger platform. I’m using the same example map as on the screenshots above.

EDIT 2 I’ve (hopefully temporarily) “bypassd” the issue by simply increasing my nav mesh tile generation radius to be larger than any platform the npcs could possibly hit, its set at around 6500 units at the moment which is quite large. But I’m hoping it’s still cheaper than having the whole map nav meshed (if my whole level is larger than 6500 units it should be cheaper, right?)

Then I used a “does path exist” decorator in my behavior trees.

So basically my npc will go towards the target until it gets blocked like in the examples above, when that happens the stairway (or doorway or whatever) should hopefully be within its (non-optimal sized) radius and it’ll simply run a move to node for the rest of the way if it can.

This seems like a messy solution though, hopefully there’s something more efficient which can be used with smaller nav mesh tile generation radiuses.

This also requires me to make the tile generation radius bigger than needed for most cases since I always have to consider the worst-case (furthest distance) scenario possible.

6

I was messing with the maze generator this past weekend and in the process, played around with some AI characters as well. They auto navigate to random points in the randomly sized maze. The cubes generating the floors and walls are scaled by 8. The largest I have it generating is about 60 800x800x800 cubes across. Square. The navigation mesh encompasses the entire field and all 8 AI characters wander around and the nav mesh constantly updates itself because the characters block their occupied space so that the characters do not get stuck staring at each other while failing to get to their destination.

May be food for thought on how big you can actually get away with.

7

a bit out of topic but, i have a question about navigation invoker and nav mesh generation…

  1. when i set my navigation bounds so large, lets say, 100k counting thing below when generating… it takes a long time right?..
    so, let’s say i finish generating the nav mesh, and the game is finished, does the user / player still have o navmesh map generate when they start the game?.. or they can use the generated navmesh map when the game was built?

  2. when i tried to have many characters that has nav invoker… they somehow lag the game generating the nav map. ( this was when the radius was set to 3000 only… ) so a bit small…
    could the lag go down, if the radius was big enough?..

8

bump* :slight_smile: hopefully someone could answer and share insights related to my question//

9

@Yggdrasil any chance you could post a picture or two of your maze? Even a rough mspaint illustration would be enough, just to see how it roughly works.

@yanzco  You said 100k, do you mean 100k x 100k units? That's quite large, I'm pretty sure you'll hit some issues at that size where the nav mesh won't be generated at all at some places. I had that issue with a much smaller map. It might help to use level streaming, I haven't tried.

For example, in this picture my nav mesh bounds were around 5000 x 5000 x 3000 units across however a navmesh wouldn’t generate above that red line, no matter what I did until I shrunk the bounds size.

I’m not exactly sure if the players would need to re-generate the nav meshes every time they start the game in case you do a fully nav meshed world, or if it’s enough that you do it before building the game but I guess it should be enough for you to do it once. I base that on the fact that I always just had to do it once, until I did something that changed the nav mesh (added new geometry somewhere) which caused me to have to re-calculate the whole thing. Once calculated though, I could close my editor and start it again and it did not require me to re-calculate it. If I remember correctly, that is. I’ve been using invokers for a few months so I don’t exactly recall the details.

I’ve tried dynamic invokers with around 10-15 actors (at around 3500 - 5000 for the generated tile radius) without noticeable lag. Might it be something else that’s causing the lag? Do your actors lag less with a smaller radius?

10

Also interested in this as the stair issue is something that might happen pretty frequently in my own projects.

11

for the 100k, i meant the counter thing below when the navmap is generating…
i think it was just 2000x2000 units or something, i left it for an hour to generate the whole navmesh… (went out to buy groceries)
but it sure took a long time to generate the navmesh…

for the nav invokers, it did lag when the ‘show navigation’ is on
it was very noticeable because, when everything is green, fps is normal at 120… but as soon as the nav invokers reach it’s edge and generates the navmesh in its radius, (red tile) it kinda drops a bit, especially if there are lots of them around the bounds…
maybe the character movement was too fast that the nav invoker cant catch up…

the nav invoker seems to do fine as long as it generates slowly around the character… if its is moving slow…

12

ah 100k “tiles” or whatever that unit means. I see what you mean now. If I remember correctly I was around 160-180k where I started getting problems of it not generating everywhere in my nav mesh bounds.

I’ve noticed a little slowdown when I have navigation on, however the players won’t have it on ever I assume, so you should just check how it runs without it.

13

I will put up some pictures/video when I get home this afternoon.

14

Took me a bit to figure out how to get video to show up on the Open Broadcaster Software, just downloaded it. Pretty neat system.

The video showing what I mean should be coming up soon here: UE4 Maze Runners Example - YouTube

15

Interesting. Thanks for that. How are you generating the target destination/locations for your actors? Do they ever get generated outside of the nav mesh radius?