The ability to Edit/Bake a Navmesh and Joints/Actions within

[edenojack]

As a roblox developer, I am constantly trying to think of new ways to make my NPCs seem smarter, react faster and ultimately reach goals within my games.

Being able to pathfind is essential for this and the recent Pathfinding service (Both for the voxel based pathfinding and now the more recent Navigation Mesh) is a fantastic way to achieve this. Its incredibly quick, and really dynamic!

However, it doesn’t come problem free. Voxel based path-finding uses voxels, which can make traversing a map not built specifically for (Or even a few studs out) of the voxel grid very difficult. The new Navigation Mesh (While I’m sure is still being improved) has some issues creating the mesh within small spaces.

Navigation mesh minor bugs

Recently removed humanoid, un-anchored, shouldn't be considered

These are pickup objects that don't need to be considered.

Odd tear in the mesh here, not entirely sure why

The floor is the only thing that needs consideration

These also don’t take into account use besides default humanoids. There are methods around this which require either some strange uses of BodyMovers or CFraming. I have noticed there is a property in Waypoints called “Action”. So far there are only two applications of this; Walk or Jump. But what if there were more actions we could tie to this?

Here is how the pathfinding works currently, it works pretty well and incredibly fast.

But what if I wanted to tell an NPC to climb up here?

The issue is that with the current system, I can’t. I could create an object at the base of this part that would send an npc up, but the pathfinder couldn’t see that or I could do create two paths, but even then I would have to know that this is the part I want to be climbing. This is where I think it would be really useful to be able to access and edit the Navmesh, or at the very least be able to create action flags and links between edges.

Here is an example of reaching a raised platform using Joins in the Navmesh and writable Actions

Our setup

There are two joins in the navmesh here.

The first is a point to point join, our green “teleport” line. We can treat this as a single waypoint and give it the Action “Teleport”. As with everything to do with Pathfinding, we can code an NPCs response to this action.

I want to get up to the finish!

Green Cubes and solid line representing our Point to Point join in the navmesh

Our second is an edge to edge join, our red edges with black connections and our green “leap” line. If we give this the action “Leap” when our NPC reaches this section of the path, it will know that it must increase its walkspeed while between these edges. The act of getting across could be an animation, but being able to define it in a path is the only thing we’ll worry about.

Yo I bet I could jump this with some speed!

We have now gone from start to finish using a Navmesh with joins

Logic

The ability to define an Action property doesn’t necesarily have to deal with just movement either, it can be used to help an NPC work logic, such as doors with switches.

On a pre-baked path, we have a clear path.

We don’t actually have a clear path though. There is a door in the way.
We could however define this particular part of the Navmesh as “Door” and create an appropriate Action, like “Switch”
At the point of creating the path, we could see this and tell our NPC that we have a closed door and we should go and open it.

So we recalculate the path and it instead becomes this

Thats really three paths, one to find a piece of information and two to solve the problem it faces. We don’t even necessarily need to go to another point, we could just call the first lines action “Door” and tell the character to search for and open a door at this point.

Conclusion

This would be an incredibly powerful tool when creating NPCs, either being able to create our own joints or setting Actions for waypoints by themselves would be incredibly useful. It would allow us to further create enemies/allies/characters that can navigate a maps with notable “intelligence”.

It would also be cool if we edit the navmesh to determine what we want considered for a specific place.

Thank you for reading this far, if you’ve been following my posts and replies for the past few months I’m sure you’ll know why I’m pushing for this sort of thing!

Either way, these are fantastic services and if you aren’t already using them I would suggest looking into them for your games
Wiki article: http://wiki.roblox.com/index.php?title=API:Class/PathfindingService
Voxel based: http://wiki.roblox.com/index.php?title=Pathfinding

[Corecii]

All of this would be super cool, but one thing I was thinking about while reading this is cost.

I think it’s important that we can define a cost to go between two nodes.

• A “teleport” join that takes 5 seconds should have a higher cost than one that is instant.
• A switch (as in your example) could be defined as a “teleport” join from the switch to outside the door. The cost would be the pathfinding distance from the switch to the door.
• An “edge” join could have a cost defined as the time it takes to leap across the gap.
• An elevator could use a “teleport” join with a cost defined as the time it takes the elevator to go to whatever floor.
• Riskier routes/teleports/whatever could have a higher cost. It would be really cool if we could define cost multipliers for certain regions, too, so walking in a certain area could be considered more expensive.
  • In a shooter, routes that have a high likelihood of death could be considered more expensive.
  • Routes with pickups in them could be considered less expensive or have a negative cost. This could even scale with an NPC or the player’s health/energy/etc. When low in health, pickups could be given a very low cost.

Having a cost for each join-to-join connection is important because the service will be comparing between multiple routes. Costs make the these joins extremely flexible.

[edenojack]

Genuinely hadn’t thought about that. I suppose the joins could be set to having a cost vs not having a cost, that way you could see if two paths were quicker.
It might be cool if you could set which actions were allowed to be used in the search, this is what I’m doing with my A*

[EchoReaper]

In this thread I suggested portals and weighting to prioritize certain paths or create paths that otherwise couldn’t exist (e.g. elevators or literal portals).

[edenojack]

What you mention within the thread, taking into account a wall, using cannons ect, is why I’m thinking the Action property should be writable. Rather than having multiple portals for each of the breakable wall points, you could define it as a region (The region of the wall), have a set cost for that region, reach it, and know that moving through that region will give you a specific Action called “Break”, this is what you can use to tell your NPC what to do, and its not a suspended part of the pathfinding, its technically “moving” along the path.

The yellow lines are “Jump” actions and green are “Walk”, currently the only values the Action property can be.

By being able to edit the Navigation Mesh should hopefully allow for non-ground based units to be able to move as well, a topic you also bring up.

Additionally, with extra actions, to allow travel for boats on water, you could just call a path for boats that only allow the action “swim”

Really hope there is enough support for these

[TheRings0fSaturn (SaturianNightmare)]

I very much support this feature (and my apologies for the necrobump, I was seeing if there was a thread that existed for this already and I found this.)

Anyways, my AI system likes to jump onto the rails of a bridge in my map, and I’m not entirely sure how to change that, other than to have collision barriers that would ultimately ruin the flow of the game (which is supposed to be heavily inspired by games like Unreal Tournament.) I’d much rather have the navmesh be only on the actual bridge itself.

I hope that Roblox takes changing the navigation mesh into consideration, as many, many developers need it.