-
Notifications
You must be signed in to change notification settings - Fork 6
Granular Navigation
One of the main features of Skelerealms is the power to find paths and for NPCs to move around beyond the scene, referred hitherto as "Granular Navigation", and the out-of-scene space as "The Ether". This is done by creating a network for each scene using my network plugin, and saving it in the skelerealms/networks_path setting in the project settings. All of them will be automatically loaded into memory upon game start.
The purpose of the Portals here is to be able to connect scenes through ethereal "doors".
Using the NavMaster, you can pass in scene names and positions (Held in NavPoint objects) and it will be able to generate a path from the start to the end, provided it can find a path. It uses a hybrid Dijkstra-AStar algorithm; the Ether is non-euclidean - because scenes do not have to be laid out in a spatially consistent way (the interior of a house can be much larger than the exterior), an accurate distance cannot be found from one world to another. To combat this, the pathfinding algorithm works in stages:
- When it is not in the same scene as the destination, it will fan out evenly using Dijkstra's algorithm, going through portals as it comes across them.
- When in the same scene as the target, it will instead use AStar, since scenes are arranged in a euclidean 3D space.
Through both of these, it will try to eventually find a point closest to the target, returning a an array of NavPoints arranged in a queue - the first point is at the end of the array, intended for you to pop it off.
Currently the network resource is "rendered" into a bunch of K-D tree node structures to allow for quick nearest-point searching. Each node in the tree contains references to other nodes serving as "connections". Memory-inefficient, but it works.
- I would like to be able to create a network automatically out of a navmesh and doors inside the scene.
- Instead of a node tree, I would like to express the ether networks as a packed vector array and expressing connections as a packed int array of indices, for memory usage concerns.