I’m a little confused about 3D A*. From what I see, “navmeshes” are used, see this image from L4D2:
While i don’t much about how L4D2 construct their navigation mesh, valve seems to describe a little bit about it there:
https://developer.valvesoftware.com/wiki/Navigation_Meshes
and from the L4D wiki there is this: L4D Level Design/Nav Meshes - Valve Developer Community
i don’t know the specifics, but it is probable that with that specific navigation mesh above, if it is navigated with normal A*, nodes are just directly linked together, with no specific order.
From what I’ve seen A* using a Navigation mesh data structure is often still used in 2d space! For the most part, many Navigation mesh & A* implementations I’ve seen are still treated as if the mesh is still 2d behind the scenes.
Normally agents (“bots”) don’t really “recognize” the stairs themselves (unless they need to for some reason), but the Navigation mesh is usually the one that needs to “work with them”.
Automatic generation is definitely easier to use (not make), for a manual alternative to navigation mesh there are also way-point graph data structures.
if you are interested in making your own automatic navigation mesh generator:
There are many types of navigation mesh systems and many different ways to construct them, if you are trying to make your own navigation mesh and use A*, its pretty easy–that is…manually at least. One easy way you could make one manually is by using a triangulation algorithm (for the actual mesh) and then using A* to search for nodes and then finally a string pulling algorithm perhaps this: funnel algorithm to do some smoothing for traversal. However, for automatic navigation mesh generation…it’s not so easy–and information on how to specifically make one is pretty sparse.
Here are just a couple (there are likely more, many probably with long reads) :
CritterAI Study --an ok study on the famous Recast library
Mesh Generation in Configuration Space
While automatic navigation mesh might be difficult to tackle-- making efficient dynamic navigation mesh generation is likely even harder. By dynamic, i mean navigation mesh that can be rebuilt during runtime. Rebuilt when stuff moves, blocks a path, gets added or removed, or when other significant changes occur. Because dynamic navigation mesh needs to be rebuilt at run time, it also needs to be quite preformant, which is a task in on its self. in my opinion, easy to follow-complete resources on making a navigation mesh dynamic are hard to come by…
if you are trying to make your own navigation mesh–What type of navigation mesh system are you trying to implement?
All a navigation mesh does is describe where an AI is capable of walking. That isn’t directly related to A*.
A* is an algorithm for pathfinding. So all the nav mesh does is tell the algorithm where potential nodes (to walk to) can be placed. Then, whenever the AI needs to walk somewhere, nodes are generated (using the A* algorithm) from paint a to point b. Using the nav mesh makes it where it won’t just draw a line through a wall, since walls are not valid locations on the nav mesh.
I’ve done a looooot of AI on and off roblox for many years now, and I can confidently say that for 90% of all cases on roblox, using the PathfindingService is your best bet. Making a legitimate navigation mesh is impossible on roblox since there is no on-the-fly mesh creation. However, the pathfindingservice does exactly that internally. For this reason, it will pretty much always be faster than your own solution, and generally more accurate.
i don’t agree on this completely, i don’t think it is impossible to make navigation mesh in roblox, in terms of visualization in some cases-maybe. but i don’t think it is impossible…
or perhaps i’m misunderstanding?
but i do agree that the Pathfindingservice handles most needs
I spent a few weeks playing around with this in the past for a game I never finished, huge waste of time.
Generation:
Pathfinding:
You’ll end up with something like this (shaded green/blue wedges are the resultant navmesh):
Manual placement:
Hi, i really am confused with all what you are saying, but this maybe can help:
@Jaycbee05
So, if the navmesh is still treated as 2D behind the scenes, how would this work with two stories? I have a floor above another, how does this work?
@ImFarley
Pathfindingservice is slow and unoptimized. I want to have lots of agents and smooth pathfinding.
@Isocortex
Why Raycasting? I want the bots to be able to move in and out of buildings, up their stairs/ladders to pursue players. Raycasting would make it so they cannot enter these buildings or do these things.
@Eternalove_fan32
I have made numerous A* implementations in the past, for example, one for Neo Warfare X’s scrapped AI Ship mechanic. However that one was very straightforward and 2D, and required very basic systems. My confusion is implementing A* into a 3D space, where agents/bots can move up and down stairs and ladders, and be on numerous floors.
You can still do that with raycasting? I noted on my post that you can combine NavMeshes, just iterate through the the bounds of models you know contain open spaces. If not, as I mentioned, you can build an octree of the map:
Check if there are objects within your cube, if they are, deconstruct into 4 cubes, repeat until you have an octree of walkable places on the map - ensure these are on surfaces, and voila.
I think your problem here seems to be that you’re thinking of it as a ‘one thing fits all’ solution. Yes, these algorithms work in 2D space (although can implement 3D heuristics), but let’s say you have a bunch of NavMeshes as described in my post:
Also, please note the image in my initial post, there are slopes in that with varying heights - the agent is able to traverse along the mesh despite the actual mesh being a 2D projection. If I wanted it to be able to walk under that bridge in the image, all I would have needed to do was to have a secondary navmesh underneath it and to connect the navmeshes by an edge so the agent could traverse between them (as described above).
Alright, still a little confused by your octree system/cube system. Can you show a bit more practical application?
From the second point you make, after this navmesh is made, try to find which plane the player is on, and pathfind based on that navmesh?
IE: Player is on roof, find the ladder that leads to that roof, go up it, then path on the roof navmesh.
Hopefully this visualisation will help. However, do note that that video is showing a sparse navigation octree used for true 3D navigation i.e. movement in every axis. Your agent really only needs 2D pathfinding with the ability to alter its altitude by traversing to other ‘zones’ i.e. other NavMeshes. I would still recommend raycasting for your use case - you’ll always get the normal that’s traversable for your agent.
In fact, unless you have a ridiculously large number of maps, a map that’s incredibly large, or a map that’s procedurally generated at the start of the game I’m not sure why you’re certain you need a NavMesh generator. If I were to go back to that game I mentioned above, I wouldn’t have wasted my time on creating one - it would have been far quicker for me to have set up a plug-in that allowed me to drop nodes across the map, which would then triangulated and would provide me with a NavMesh. Considering you want to implement ladders and other more complex behaviours, it would be far easier to do this with an editor plug-in as you could define any special ‘edges’ that required some action / allowed traversal to other NavMeshes on the fly.
In regard to the second part of your post, that example would be correct, yes. For example:
Black shape is one NavMesh, red is another NavMesh - both are connected to each other by the orange ‘Traversal edge’. You know where the Agent’s position is, and you know where the goal position is. You find which plane the agent and the goal is on - if they’re on the same one then just pathfind towards it. If not, use A* (or programmatically) determine which Traversal Edges you need to pass through to finally get to that goal position. Once you know this, you just need to pathfind from Player → Traversal edge(s) → Goal
I plan on having an open world zombie survival game that emphasises on PVE. I want smart enough zombies, and enough to pose a real threat. While I can have a master AI Director (see R4D2 PDF I link here: https://steamcdn-a.akamaihd.net/apps/valve/2009/ai_systems_of_l4d_mike_booth.pdf) that optimizes based on player location or number of players, it might just be too tedious to manually craft the navmesh for an entire island.
Also, how would an agent figure out what traversable edge/node to go to?
EDIT: I must also note that I intend for players to be able to build structures, which might pose a major issue for this entire thing…
I think you may need to reconsider, this wouldn’t be a trivial task.
If your map is that large and it would be too tedious for you to manually craft it then you already have some issues with what I’ve previously mentioned. You would need to separate the NavMesh into sections and perform graph traversals - having it that large without splitting it up would be ridiculously computationally expensive. This is called ‘zoning’.
Similarly, adding the ability for users to build complicates things further. You would need to recalculate the NavMesh zone that this building is being created dynamically, or even better, create a new zone for each build after removing the intersection from the current NavMesh and recalculating the triangulation, then performing the calculation of the new NavMesh on that newly created zone.
This is all doable but it’s not going to be perfect, and it’s certainly not going to be a cheap process - it’ll be costly to your game’s performance, especially in RBLX where we’re throttled.
If you’re certain you want to continue with the features/characteristics that you mentioned, I would stick to the Roblox PathfindingService. It’s C side, and can perform dynamically. You can improve its functionality by implementing similar behaviours as mentioned in that link you posted - make it reactive, perform ‘jump/climb’ actions when necessary, start following the player instead of redrawing the path etc. The ‘enough to pose a real threat’ has nothing to do with Pathfinding, it’s the behaviour of the AI/NPC.
Pathfindingservice is slow and unoptimized. I want to have lots of agents and smooth pathfinding.
I have used the pathfindingservice on games with several hundred agents (300+) operating at the same time and run into no issues. Saying a service is “slow” as a blanket statement is silly. It’s how you implement it.
If you want to make your own custom pathfinding etc etc, be my guest. The reality, though, is that you’re going to spend endless hours of development time both making and then maintaining that system, as every new iteration on the map will introduce new issues.
Alright, well I guess this would be far more of a wasteful task than just using PathfindingService, but that doesn’t bring up the issue of allowing them to climb things like ladders.
Any reason you couldn’t change your map to work within the confines of your system if you aren’t able to create the above? Couldn’t you just make all ladders stairs?
If not:
