Pathfinding in a Cave Network

[Soybeen]

Hi, I have been faced with a challenge for a few days and I’m looking for outside input.

I have AI that make use of the PathfindingService to plot courses above ground when wandering.
They don’t behave so well underground

See, the way they choose a new destination is by generating a Ray above themselves that points directly downwards, using :FindPartOnRay() for its part and position arguments, then they :FindPathAsync() and follow the points leading to the destination.

The Ray that determines the new destination is ± 50 studs either direction on the X and Z axis and 100 studs higher than the creature. This means that my system does not work in caves where the ceiling is low. Simply reducing the height of the ray is not enough for a couple reasons, chief among which that it would fail if the creature was against the wall of a tunnel where the ceiling tapers close to the head.

My initial thought is that I could manually map the cave systems with nodes at every junction, and they just pick a random node to path to. I’d really rather not do that, chiefly because of scalability, but I will if no better solutions are presented.

My second idea is to send a ray between themselves and the roof of the cave, and use the midpoint of that ray to then project another ray laterally until it exceeds a distance of at least 5 studs without hitting anything, and then a third ray downward from that point to determine the final destination. This runs into problems if parts of the cave roof are twice as tall as the rest and narrower than 5 studs. It would get infinitely stuck. It also means a lot of recursion. It also means they can’t navigate corners easily, and they will have a slight tendency to go downwards instead of upwards on narrow slopes.

Dynamically moving these AI each frame using raycast sensory mechanisms is not feasible for the scope of my project. All AI will use simple A to B course determination. This will allow me to manage hundreds if not thousands simultaneously.

What would you do?

[EchoReaper]

I had a similar design question I needed to answer for my game: if the area you’re looking at cannot be reached by the grappling hook, then I need to find the closest valid point to hook to so players don’t fall down to the ground if their aiming isn’t 100% perfect. The solution I came up with was to cast back/upwards from the direction the grapple was launched in until I found a valid attach point:

Bottom-most is initial launch direction, and last is found attach point

You can apply something similar for your game as well. High level:

1. Raycast in a random xz direction from the creature’s current vertical midpoint
   • Vertical midpoint means you avoid hitting the ceiling/floor when it tapers close to the character
   • Set ray length to the maxmium distance you want them to wander
2. If you have a hit, you’ve hit a wall (or slope) – add 5 degrees (or any arbitrary angle) to the direction and raycast again. Repeat until you have a free area or have come full circle
3. From the first free point or furthest point that hit a wall/slope (in case creature is in a small, isolated room), raycast downward to find the floor (if there is no floor, use the next point)
4. Pathfind to this position

Caveat: AI will always prefer flat areas over walking up sloped tunnels (you would need to expand on the above approach to resolve this)

[EgoMoose]

Could you maybe draw out the problem? It doesn’t need to be a masterpiece, but I think it would help me and others potentially come up with other solutions.

[Soybeen]

In lieu of diagrams I think screenshots will do as much justice.

Here is a screenshot of my cave system. Just your standard ant colony network.

And here is a photo taken inside the network to give you a sense of the average tunnel dimensions

My goal is to allow NPCs to wander within this cave system without me needing to deliberately plot the whole cave with nodes, since the NPCs can’t raycast downwards from above like they can on the surface. The more complex the routes, the better. If they could set a destination more than a single bend away, I’d be happy.

I can’t think of a fantastic/efficient way to do this with rays. I was hoping someone else might already have a clue.

[CompilerError]

Although I haven’t implemented this idea and it certainly has its limitations but I was thinking about an implementation which utilizes the ReadVoxels method on the Terrain object. This would give you a 3D grid which you could use to find the empty spaces in your terrain.

If you read the voxels around the NPC then you could find the furthest empty cell with an occupied cell directly beneath it in the direction you want the NPC to travel. You could then do a path test to that cell to determine if the NPC could actually reach it. If they could reach it, repeat the process, if not then find the next applicable cell to test.

You repeat this process until you’re satisfied with the destination. Once you are satisfied, you would treat cells you tested as vertices on a graph. After this you could employ Dykstra’s algorithm (distances could be obtained from your path tests) to find the shortest path. This should help eliminate the possibility of navigating in and out of dead-ends that are too small to easily determine programmatically.

In the case of a dead-end you should look back until you find another possible route and “cut” off the extra vertices that lead to the dead-end (unless for some reason you want to consider them).

This should, in theory, work even in the case that there are obstacles or even forks in the cave. There are certainly ways to improve the concept but I think it’s an intriguing idea and I would love to hear more opinions on the concept as I just now thought of it. I’m not certain how well it would perform with parts in the way, but one would hope that Roblox’s pathfinder could work around that issue.

One thing to consider: this would likely map out an entire cave system for you. So you might want to cache these paths or vertices (I think vertices would be more useful) for other NPCs to utilize instead of having to re-map this cave each time.

When it comes to finding the actual shortest path my idea has some computation expense. You would pretty much need to test paths to each vertex further down the path from each one. Granted, there really shouldn’t be too many possible shortcuts along the path in a cave but it could get somewhat process heavy.

Again, I would love to see some improvements to this idea, I know it has flaws and edge cases that could be issues.

The concept might even be expandable to your game world.

Let me know what you think!

[IdiomicLanguage]

This sounds a lot like A*. There are some really good tutorials about A* and voxel based pathfinding. This article helped me understand it years before the pathfinding service came out.

Basically you create two sets of voxels: closed and the fringe. The closed set starts as empty while the fringe set start with the voxel that your unit is standing in. Iteratively, the each voxel in the fringe is expanded. Voxels can be expanded in the order they were put in the fringe for a breadth first search, the newest voxel first for a depth first search, or using a priority queue with a heuristic like A*'s. In the case of A*, the voxel with the least walking distance to it plus the straight line distance to the goal is used. When a voxel is expanded it is added to the closed set and all reachable adjacent voxels to is are added to the fringe. If at any time the voxel that was added to the closed set contains the goal, then we retrace which voxel was expanded to get to it, and which was expanded to get to that.

Here is a simple abstract implementation. Just define getDistance and getAdjacent to work with voxels, and then you can pass any two voxels to a_star. I’d suggest replacing getMinimum with a proper priority queue (like a binary heap/tree) so it’ll run fast!

local function getAdjacent(value_1, value_2)
end

local function getDistance(value_1, value_2)
end

local function getMinimum(map)
	local minKey, minCost = next(map)
	if not minKey then
		return
	end

	local curKey, curCost = next(map, minKey)
	while curKey do
		if curCost < minCost then
			minKey, minCost = curKey, curCost
		end
		curKey, curCost = next(map, curKey)
	end

	map[minKey] = nil

	return minKey, minCost
end

local function a_star(startValue, endValue)
	local route = {}
	local routeCost = {
		[startValue] = 0
	}
	local fringe = {
		[startValue] = 0
	}

	for value, cost in getMinimum, fringe do
		-- Check if we've reached the last value
		if value == endValue then
			-- reconstruct path
			local path = {}
			local nextValue = endValue
			repeat
				path[#path + 1] = nextValue
				nextValue = route[nextValue]
			until nextValue == nil
			return path
		end

		-- Add adjacent values to the fringe
		local thisRouteCost = routeCost[value]
		for adj, travelCost in next, getAdjacent(value) do
			local adjRouteCost = thisRouteCost + travelCost
			if not routeCost[adj] or adjRouteCost < routeCost[adj] then
				route[adj] = value
				routeCost[adj] = adjRouteCost
				fringe[adj] = adjRouteCost + getDistance(adj, endValue)
			end
		end
	end

	-- unable to find path
	return nil
end

Edit: Oh, I almost forgot why this is a good route to take. There are many optimizations that can be performed on A*. For example, you could only search nodes on the floor of the cave or that can be jumped to. You exchange some runtime computation for start-time computation and memory. You could combine voxels into groups to create regions, then run A* on regions instead of the original voxels, and then run A* again but only on the voxels contained inside those regions. This is called Hierarchical A*. There are numerous other optimizations that can make this process very, very fast. I remember running this at around 50 voxels a second with FindPartsInRegion3. Considering that voxel reads are much, much faster and can be done in bulk, you should be able to reach speeds of 2,000 a second. If Lua was compiled, you could probably get in access of 20,000-50,000 per a second.

[CompilerError]

I definitely agree that A* is the way to go for most if not all pathfinding needs. I wonder though if this step would be redundant with Roblox’s pathfinder? You certainly have a lot more control with your own implementation but the built in pathfinder benefits from optimizations that aren’t accessible from the Lua level.

Holes in the caverns would definitely be a problem with Roblox’s pathfinder since it wouldn’t understand that they’re jumpable (unless the API has changed since I last saw it. It was pretty bare-bones before).

Do you think it’s better to use your own pathfinder to find the path through the region of terrain that the node is in or would it be better to let Roblox’s do that for you (granted Roblox’s can be quite finicky at times)? The tricky part in all of this is finding a proper destination within the region the path is currently in, which I figure could be the furthest node in the direction you’re trying to go which is far from a perfect or even ideal but it could work.

I love the idea of doing your own implementation and I agree it would work here but I’m not sure if it’s an optimization in the case of Roblox Lua. What do you think?

Edit: Unless you’re suggesting blowing away the whole region concept all together. That would certainly change things and your idea would definitely better than the Roblox pathfinder.

[IdiomicLanguage]

I’d say if the Roblox pathfinder works most of the time, it’ll probably be the best thing to use. I think there comes a point though at which only the game developer can decide if dealing with the bugs/features/quarks of the pathfinding service outweighs writing an A* implementation. Writing an A* implementation is one of those things that I think every programmer should do at some point in their personal development, and isn’t very hard. Generally it is an excellent learning exercise and produces very nice results. It gives a greater understanding of algorithms and data structures while providing an understanding of the basic concepts at play in pathfinding.

As for finding which sets of connected empty voxels are disjoint, This can be computed once and stored for later use and easy modification when voxels change at runtime. Given a set of empty voxels, add one to the fringe. Then, expand it and continue expanding the fringe until no voxels are left. All of those voxels are in one disjoint set. Then, while there are will unexpanded voxels in the set of all empty voxels, add another voxel to the fringe and repeat the process. At runtime, any two voxels from the same disjoint set can be picked for pathfinding. Also, the pathfinder could return an error if the start and endVoxels are in different sets, allowing an early return when no path exists rather than searching the whole space.

Hierarchical pathfinding is another layer ontop of A*, but would be create a very practical pathfinder able to find very, very large paths. Not to mention that with Hierarchical pathfinding, you can determine the most optimal direction to walk even before you are finished computing the path. You can compute pieces of it as you need it, online. This is how humans navigate: going between states they decide which highway to get on, then which entrance to use, then what main road, then the exit from their neighbor hood they want to take. They can worry about where to go when they get off the highway on the boring, long stretches on the highway or at rest stops. Not every implementation of A* needs this, but it is nice to know that if performance is an issue, this is an option. Another optimization would be baking the voxel grid into a navigation mesh. That’d be nearing Roblox performance which uses the Recast and Detour pathfinding libraries, perhaps even faster if you add specialized logic for your game.