I have a vast terrain setup in my Unity game which includes 5x5 terrains at 2000x2000 units each direction. This equates to about 100km2 of terrain. Now, I want to have NPCs roaming around across this terrain. The built-in pathfinding doesn’t work (after crashing several times) because it can’t handle baking a mesh for that large of area… no surprise.
I don’t expect that baking any type of pathfinding mesh/grid will solve my problem. Instead, I am looking for an ad-hoc pathfinding solution. One which dynamically generates a grid as it finds a path.
Do any of these exist in either in Unity or the asset store?
I am using a great AI engine called RAIN, it’s great and it has navmesh integrated.
The only problem is the documentation, it’s lacking and the slow response times, I made a thread 3 days ago I think and they haven’t answered yet, provived as much info as I could but once you get it done it’s awesome.
RAIN looks really great! But I am curious… it says it generates a NavMesh on the fly, but does that create a navmesh across the entire terrain? I think that creating and storing an entire navmesh might be a bit much for my game in any capacity. If it were to calculate a path adHoc without a whole NavMesh, that’s just what I need. I’ll check it out and see!
RAIN doesn’t seem to work for what I want. I ended up making my own script.
It’s not completely done, but basically it produces an A* nav path between two points AdHoc with no mesh required. I was able to create a path traversing a 1000x1000 unit terrain with “off limits” areas using a 1 unit sensitivity in less than two-tenths of a second. Currently it uses Hash tables for the closed/open lists, but I will be moving the open list to a binary heap for optimization for final usage.
I am curious if I am the only one that would want this… here’s a preview of the script in action. It’s not finished right now, but this is the only AdHoc A* pathfinding algorithm I know of for Unity. Basically it uses raycasting in preset or dynamic distance increments to create an AdHoc navigation grid. This currently doesn’t do anything with dynamic obstructions - but it wouldn’t be too hard to implement. It’s also ultra fast because it uses Hash tables and binary heaps - no slow ArrayLists here!
Currently working:
Determines “Walkable” based on slope
A* pathfinding without a baked mesh (AdHoc)
Simple movement based on “MoveToPosition”
To Implement:
Better “Walkable” algorithm using slope ranges and game tags for walkable vs non-walkable terrain surfaces
Smoothening of the path (Better Heuristics)
Perpendicular raycasting for planetoid pathfinding
Dynamic obstruction detection
Screenshot of it in action:
Open List: Blue
Closed List: Red
Path: Green
Character: White Sphere
Target: Green Sphere
You might also want to consider a hierarchical version, basically the same idea but at a much lower res but over much bigger distances. That way you can be sure that long paths are actually completable and you might get better long paths if the local path goes from node to node of the high level path.
I am not quite sure I understand your suggestion. Do you mean I should create a few “grids” with larger resolutions to make sure the path can be found? For example, this one uses a 1-unit resolution, are you suggesting I use a 10-unit resolution first? Then 5-unit? etc?
Yeah. Thats the idea. If a long distance path request is actually impossible, you want to know that soon and with little work. Even valid long distance paths may have a fairly different optimal path than if you just did a series of local plans.
I understand now. However, after some experimentation, I have found a problem with that idea.
Example: A bridge over an impassable valley
If the bridge is 5 units wide and the target resolution is 1 unit, then the grid created by the navigation would be able to determine a pathway over the bridge because the minimum number of grid points on the width of the grid would be 4.
Instead of using a 1 unit grid resolution, the proposed change would be the use a larger resolution to determine that a path is possible using the least amount of computational time - lets call that the maximum estimated resolution (MER).
If the MER is >= 5 units, it will not detect any valid path across the bridge even though a valid path would still exist. In this case, the MER run would return a false negative. So in order to use this technique, one would need to know the absolute minimum distance between obstructions and make the MER < that resolution. That’s easy to do for smaller environments, but since I am aiming this to be used in vast terrains, the user may or may not know the smallest gap between obstructions.
This may be a “feature” for faster scanning though, so it’s not totally tossed out as an idea. It just requires more thought than using out of the box.
I have finished a collection of tests for my current system and it seems very promising.
Currently I am not using Binary Heaps for my open list scanning (which will be implemented soon). But my navigation system was able to calculate a path ~5000 units in length across a relatively normal foothills type environment in less than 15 seconds. That sounds like a lot, but over half the time was used to calculate the open list (which should be reduced dramatically with Binary Heaps) and 1/4 of the time was spent spawning debug objects. So I’m aiming for a target of around 4-5 seconds maximum.
The trade-off of this navigation system compared to other products is calculation time vs. size. This navigation system will work on any terrain size from 100^2 units to 1000000^2 units and beyond. The calculation time is determined by distance of the path and complexity of the obstructions. The delay in time could easily be solved by two techniques:
Long path planning
Shorter paths
The first method would be used by people like me - we want a very long distance travel path. So I might go from 0,0 to 4000,4000. After that, I might want to go from 4000,4000 to 3000,1000. Each of these might take 10-15 seconds to calculate. So my solution would be to invest on calculation on the fly. Unless my character was going 100 units a second, I would have enough time to pre-calculate the next leg of the trip before the character reaches the end of the first time. Thus, there would be no delay in the movement as I would just switch paths.
The second solution would be for people who don’t mind having shorter paths, but want to use vast terrain. For example: patrolling a small area. You can then calculate a path with a length ~100 units in less than a second in most cases. This could be calculated either during an “idle” animation or pre-calculated while walking a previous path.
