I was looking for a bit of a challenge today and decided I’d attempt to create a node-based pathfinding system. I succeeded - and this is the result.
I’ve not only created a pathfinding system, but an entire toolset that contains everything you would need to set up your own pathfinding non-player characters.
For those of you wanting to try it for yourself, you can find it here.
The plugin comes with four tools:
Here’s a run-down of what they do:
[ul]
[li]Insert ModuleScript: This is more of a convenient button. It places a ModuleScript containing all neccessary pathfinding functions to make a non-player character work.
The ModuleScript returns a table containing the following functions:
[ul]
[li]resetValues() - This function is used internally to initialize the pathfinding system. It sets all values used by the pathfinding algorithm to -1. Returns nil.[/li]
[li]calcValues(Instance targetNode) - This function is also used internally. It calculates the minimum distance to targetNode for each node. Nodes not connected to targetNode in any way will not be considered. Returns nil.[/li]
[li]findPathFrom(Instance startNode) - Uses the values calculated in calcValues to determine the shortest path to the target node that was given to calcValues. Returns an array containing all nodes in order, and a boolean stating whether or not the search was successful.[/li]
[li]findPath(Instance startNode,Instance targetNode) - Uses all of the above functions to find the shortest path between two nodes. Returns an array containing all nodes along the path in order as well as a boolean stating whether or not the search was successful.[/li]
[li]findClosestNode(Vector3 position) - finds the nearest node to the given position.
[/ul]
[/li]
[li]Create Node: Creates and connects pathfinding nodes. A click will place a node. Clicking and dragging will create two connected nodes (linked by a blue line). By clicking and dragging from and to existing nodes will connect the existing nodes rather than creating a new one.[/li]
[li]Remove node: Removes a node or a connection between two nodes. This tool makes sure that the nodes or connections are removed properly so that the pathfinding system can function properly. And it’s convenient too: It’s much easier to remove a node with this tool than it is using default studio functionality.[/li]
[li]Test path: Finds the shortest path between two nodes and displays it in green. Click the start node and then the end node to find the path.[/li]
[/ul]
While any of the tools are selected, the nodes and the connections between them will be shown. The following picture was taken after I have given the Test Path tool the task to find a path from A to B. The purple spheres represent nodes, the blue lines represent connections between them. The green lines represent the path that was found.
Oh, and the path was found practically instantly.
The main idea behind this was to make pathfinding NPCs accessible to anyone with basic scipting knowledge. I think many people and their games could profit from this.
Feedback and suggestions are welcome, as always. 
EDIT: For anyone who’s interested:
The algorithm is quite simple and has two main steps:
Step 1: Calculate the distance of every node to the target node. The script starts at the target node and measures the distance to every node it has a direct connection to. This distance is saved for each node.
It then continues with each of those nodes, measuring the distance to each node they have a direct connection to, and so on. The distance saved for each node is the sum of the distances of all the nodes that preceded it.
If a node already has a distance value written to it, it can be overwritten by a smaller distance. This only happens if there are loops in the node system.
Step 2: Now that the minimum distance of every node to the target node was calculated, the rest is very simple. The script starts with the first node and moves to the node with the least distance to the target that is directly connected to it. This process repeats until a node with minimum distance 0 (the target node) is reached.
