Hi
Notes before reading on
I decided not to put this in the resource section because it’s not very useful, it’s just something fun I made and maybe some of you can comment on it.
I’d first like to point out that I put pathfinding in quotes - that’s because while a path is always found between point A and point B, it’s not necessarily the shortest. In fact, I’d go as far as saying that most of the time when the path found, it’s not the shortest (but don’t quote me on that). Calling it a pathfinding algorithm is barely suitable.
Algorithm
Using simple recursion on a binary tree, I find a path between two points.
The algorithm works like so,
- Find nodes from the root of the BST to point A (Root->A)
- Find nodes from the root of the BST to point B (Root->B)
- Find the intersection in nodes between Root->A and Root->B (preserving order is very important)
- Take the last element from the last operation (Q)
- Subtract: Root->A - Root->B (A-B) Root->B - Root-A (B-A) (again preserving order)
- Join, reverse(A-B) + Q + B - A
And that’s the path between A and B, very simple.
.blend
bst_pathfinding.zip (191 KB)
Here’s the .blend, I use Goran’s debug.py from his nlu library but that’s about it. Everything else is my own work.
I’m using Blender 2.72, make sure to click on the file to open (do not use “open” in Blender)
Visualization
There is a visualization, just move the cubes around (WASD, Arrow Keys). The green lines represent how the nodes are connected, the red lines represents the route found between the cubes.
Creating More Nodes
The nodes work off a parenting structure. So to create more paths, you need to add a child to the node you want to increase the path of (the empties are the nodes). Every node can have a maximum of two child nodes.
On Code
The code is somewhat messy - beware. If you want to see the “pathfinding” at work, look in the pathfinding.py in the Route object. It should be somewhat self-explanatory from there.