Binary Search Tree "Pathfinding"

Game Engine Game Engine Support and Discussion
1

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,

  1. Find nodes from the root of the BST to point A (Root->A)
  2. Find nodes from the root of the BST to point B (Root->B)
  3. Find the intersection in nodes between Root->A and Root->B (preserving order is very important)
  4. Take the last element from the last operation (Q)
  5. Subtract: Root->A - Root->B (A-B) Root->B - Root-A (B-A) (again preserving order)
  6. 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.

2

hmm, if you are operating on a tree there is only one path (= shortest = longest). Typical recursive algorithm run on any maze and dynamically create the tree on the fly by adding the currently visited nodes to the tree.

If you either choose the start or the endpoint as root of the tree, you get a single branch as path rather than two branches. Nevertheless this can be useful if the start and endpoint are not known, so you have to find them first. And yes it will tell a path exists or not. If that is known a separate more efficient path search can be started with known parameters.

3

I don’t really understand what you’re making, but it looks cool.

Here’s a excellent article on using BSP trees for navigation mesh construction:
http://www.mechanicalcat.net/richard/log/Python/Solving_Game_Entity_Navigation_Using_Python

The only real problem there is that obstacles are restricted to rectangles aligned to a x,y grid. The results look pretty good, and I expect the speed is pretty good, since it’s just a set of class instances and the code nicely removes unused space. I don’t know how they would deal with moving agents being blockers. It might be a little slow recalculating the binary quads every time a blocking object moves.

If you’re interested in pathfinding and graph creation, I’ve been working with nodes to create a connectivity graph. It can be quite slow to set up, since you have to visit each node, and get a path from each to every other node (or just ones in range), but once it’s working it gives very fast pathfinding and can be post processed to get a nice smooth route.

It’d be something like this:


nodes = [ob for ob in scene.objects if ob.get("navigation_node")]
navigation_dict = {}
node_id = 0
for node in nodes:
    for other_node in nodes:
        node_neighbors = []
        if node != other_node:
            blocking_check = ray_cast_from_to(node,other_node) ### write a function to ray cast from one node for another, checking for collision with scenery
            if not blocking_check:
                distance = node.getDistanceTo(other_node)
                node_neighbors.append(other_node,distance)
    node_neighbors = sorted(node_neighbors,key=lambda sorted_list:sorted_list[1]) 
    navigation_dict[str(node_id)] = [node,node_neighbors[:5]]
    node_id += 1

That would give you a dictionary of nodes which had at most 5 neighbors which could be checked for pathfinding using A*. It’d be possible to make it a lot better using classes or by using properties on the nodes themselves in game. in that case you could reduce the number of double checks, by adding own to other_node[‘neighbor_list’] and seeing if other node is already in own[‘neighbor_list’] when checking in future. When doing your A* search you’d just have to find the nearest node to the start and end points and work out from the start using node[‘neighbor_list’] as you open list.

Anyway, good luck, pathfinding is fascinating to me, though maybe not to other people, as I found out at the weekend when I tried to explain to my wife why the satnav was taking us on a strange route home from the beach.

4

Yeah! It’s neat. I think it would run faster than an A* algorithm in any case.
For instance, if you want an enemy to “randomly” patrol a maze given two specific points, this tree work fine. In this case it doesn’t matter how it gets to each point and this is something A* would be overkill for.

It’s nothing special, just a fun little experiment.

That link doesn’t seem to reflect BST trees, looks just like regular A* pathfinding. d:

The only real problem there is that obstacles are restricted to rectangles aligned to a x,y grid. The results look pretty good, and I expect the speed is pretty good, since it’s just a set of class instances and the code nicely removes unused space. I don’t know how they would deal with moving agents being blockers. It might be a little slow recalculating the binary quads every time a blocking object moves.

If you’re interested in pathfinding and graph creation, I’ve been working with nodes to create a connectivity graph. It can be quite slow to set up, since you have to visit each node, and get a path from each to every other node (or just ones in range), but once it’s working it gives very fast pathfinding and can be post processed to get a nice smooth route.

That’s cool. I’ve been looking into pathfinding myself. However, it doesn’t seem to be the best in python, it might be better in C where we can control memory.

That would give you a dictionary of nodes which had at most 5 neighbors which could be checked for pathfinding using A*. It’d be possible to make it a lot better using classes or by using properties on the nodes themselves in game. in that case you could reduce the number of double checks, by adding own to other_node[‘neighbor_list’] and seeing if other node is already in own[‘neighbor_list’] when checking in future. When doing your A* search you’d just have to find the nearest node to the start and end points and work out from the start using node[‘neighbor_list’] as you open list.

Anyway, good luck, pathfinding is fascinating to me, though maybe not to other people, as I found out at the weekend when I tried to explain to my wife why the satnav was taking us on a strange route home from the beach.

Yeah, another thing to try out might be to use a very simple guess and check method. You take the distance between one node (start) and another (end), and get the next closest node to end. If you hit a dead end, you just back trace and try different routes. Eventually you’ll get the to the end node (but it may not be the shortest path).