NavMesh Pathfinding

Feature Requests Engine Features
#1

We already have a method of pathfinding, but it doesn’t always give us enough control to do what we want. Take this scenario for instance:

r5HtrRk.png1225×611

We would like the NPC to navigate to the entrance to the cave. This is the path we desire it to take:

Ba6SdhW.png1211×551

However, with the current pathfinding system, this is the path the NPC will take:

4fV1B5A.png1286×618

The actual path it takes is not realistic – we want at least somewhat of a sense of realism in our AIs. There’s a certain amount of studs that an NPC is allowed to jump down in pathfinding, but sometimes maps aren’t always so clear cut. The path it takes in the last picture could be a rocky slope not meant to be used for travel but instead just for decoration, or it could be a path only meant for players to quickly a ccess parts of the map. Regardless of which scenario, we don’t want the NPC taking that path. In this case, our only solution is NavMesh or node map pathfinding. Node map pathfinding can’t hold a candle to NavMesh pathfinding, so NavMesh pathfinding would be the obvious choice. However, not only is such a system executed in Lua not as fast as it could be if executed from the C side of ROBLOX, not every developer can program a NavMesh pathfinding system himself/herself. Not all levels on ROBLOX are dynamic, and in that case NavMesh pathfinding may be preferred, or even a combination of the two where AIs use the existing pathfinding to navigate around short, dynamic obstacles in their current NavMesh path.

NavMesh, although tedious to set up for a level, is not difficult to use. Any developer that can use the existing pathfinding system can use a NavMesh pathfinding system. In order for us to have more control over our AI pathfinding and gain access to faster processing speed, ROBLOX should implement a NavMesh pathfinding system in tandem with the existing system at some point in time. They do not have to replace each other – the existing system is meant for dynamic maps, while NavMesh pathfinding is meant for precise control and predictable environments.

4 Likes
Introducing: Roblox Pathfinding
#2

I greatly support this because I am always in need of a NavMesh in all of my games… Not to mention NavMesh is one of best pathfinding options available.

#3

I don’t get what NavMesh is

Why not just use an invisible wall there

#4

Because if there’s an invisible wall there it means that you can’t shoot projectiles (bullets, arrows, etc) through it, players can’t take paths except the ones designed for NPCs since there’s an invisible wall in the way of every other path (which would be extremely aggravating),

Using hand-placed triangles to determine bounds where NPCs can move within:

creationkit-2013-04-12-20-32-27-79.jpg1208×906

Going back to the invisible wall thing, let’s take that path on the right side of the screen. With current pathfinding, they’d just go this way:

NTIuLez.jpg734×677

With NavMesh, they behave like normal human beings would and take the path up to the marketplace:

8ynkg0J.jpg695×583

If we used invisible walls there, players couldn’t take the shortcut in the first of the two images and they’d likely quit the game because they were running into invisible walls every time they tried to go somewhere.

1 Like
#5

I would love to have this as a built in feature along side regular path finding.

#6

Using hand-placed triangles to determine bounds where NPCs can move within[/quote]

9 out of 10 game engines automatically calculate navmeshes for a level(On map compile, not when launching a level) Tbh I’ve never known anyone would ever hand-place navmeshes

#7

Using hand-placed triangles to determine bounds where NPCs can move within[/quote]

9 out of 10 game engines automatically calculate navmeshes for a level(On map compile, not when launching a level) Tbh I’ve never known anyone would ever hand-place navmeshes[/quote]

Of course the base for it is auto-generated, but you have to go back in and fine tune it. Sometimes the auto-generator missed a spot or accidentally made a path through a tiny space that isn’t accessible. In the picture in my response to Aurarus, maybe it generated a path through that grass so that NPCs would walk through the grass and not use the path. Maybe you want NPCs to be able to jump down a one-way ledge. Regardless, you always have to go back in and make sure everything is how you want it by hand.

#8

Using hand-placed triangles to determine bounds where NPCs can move within[/quote]

9 out of 10 game engines automatically calculate navmeshes for a level(On map compile, not when launching a level) Tbh I’ve never known anyone would ever hand-place navmeshes[/quote]

Of course the base for it is auto-generated, but you have to go back in and fine tune it. Sometimes the auto-generator missed a spot or accidentally made a path through a tiny space that isn’t accessible. In the picture in my response to Aurarus, maybe it generated a path through that grass so that NPCs would walk through the grass and not use the path. Maybe you want NPCs to be able to jump down a one-way ledge. Regardless, you always have to go back in and make sure everything is how you want it by hand.[/quote]

Yeah that’s correct, you just weren’t saying that in the post, hope I wasn’t too nitpicky

#9

I’m working on navmesh pathfinding, but I can’t guarantee I’ll finish it. Mostly because I can’t focus on writing it, and I’m working on other projects. It would use a hand placed navmesh, and in theory it would be very fast to do the precalculations and ridiculously fast to calculate the actual path. I’ve got the ideas all laid out in comments. Just a matter of writing the code…

1 Like