Kohaku:
Doesn't your extra storage at each level in the tree negate any gains from having a tree structure in the first place?
And won't the resulting paths be silly when the shortest path is a cross-branch step? For a simple example, consider a map that is only one huge ring-shaped tunnel (or series of rooms). Opposite the root node in the ring will be two nodes which are only connected through the root node - so the path found will go all the way around the ring unnecessarily?
Pardon me if I've misunderstood, but it seems like you're trying to squeeze performance out of pathing that is provably theoretically impossible - unless the map is *actually* a tree, topologically!
Draco18s has already responded to the first paragraph, so I'll skip that.
As for the second, you're right - you will return a valid, if theoretically unoptimized path if you simply go for the simplest, fastest, first path you can find. In some ways, this might be preferable (if you want faster pathfinding, even if it costs you optimal pathfinding in return), but there are ways to return more optimal paths, although they have some costs associated with them. I simply left them out of that last post I made, because I wanted to keep the post simpler.
In the first method, (let's use
Wikipedia's page on trees for an illustration), let's assume that we found a path in that tree from the "5" node on the bottom left to the "9" node on the right. This would return a path of "5->6->7->2->5->9", but at the same time, 7 and 5 are connected, so you can cut out the path with 2 inside of it.
When making that original chain of nodes, you basically are only looking for going up and down the tree, not laterally - you go "down" the tree ("down" being towards the roots) until you find a route directly up the tree you can follow. To do this, you have a list of all the points "up the tree" from a given node. Once you have that chain, however, you can look for lateral shortcuts by simply comparing all the connections (up, down, or lateral on the tree) that allow a given node to bypass one or more steps in the chain.
This method has a complexity of an additional O(n^2/2) where n is the length of the chain you returned previously. It winds up with some extra memory calls, but should still be much faster than A*-ing the entire fort.
This will basically return you the previous path, but with a few shortcuts taken where they are found.
The other option is more complex, and will return you an optimal route at a greater cost, especially memory-wise.
Let's look at the example picture I made earlier, again, because this was something I made to try to illustrate the exact problem you were pointing out in my idea, when I realized it was there.
The same organizational rules from the previous times I used this graph still apply - bright red stairwell is the root node (or the lowest-level node visible on this level, at least), and the changing colors radiating out from it represent lower levels of nodes (with dividers in the red-orange "ring" hallway to denote different branches on the same layer of the tree).
We path from (S)tart to (F)inish.
This map assumes rectangular nodes and doors as their own personal nodes.
The last method I mentioned will return the blue line. Although the red line really should go through the other door I punched in the F-room late in making the graph, the red line basically demonstrates an optimal path (going through the southern door would be 1 tile faster). (Also, the F-Room should have been recolored yellow-green instead of just green, as it connects to a yellow door node.)
Now, again, at least in this case, the blue line actually returns a sub-optimal but still acceptably inefficient path. Rather than going to the central stairwell, it takes the "lateral shortcut" by going from the western red-orange "ring hallway" node to the northern red-orange "ring hallway" node before going back "up the tree" by going through the hallways, door, and finally hitting the green F-room.
I cannot make a "lateral shortcut" with the pathfinding to use the yellow-orange hallway next to "D" on the map because it is not in the pathfinding chain I originally constructed.
In order to actually make that path potentially show up, I would have to make a much slower, and more complex method of building that chain of connections in the first place. This means that we are going to have to search for more than just
a path, but an optimal path, and this means that we have to start storing much more data to actually search for what is optimal, and what is not.
For example, we can make the red line a potential returnable path if we were to include the green "F" room as being "up the tree" from the western orange hallway, as well as storing it as "up the tree" from the northern orange hallway - basically duplicating the amount of data.
This means that every hallway node that connects to a given node higher than its own tier on the tree is recorded as being "directly up from it", which means that all of that area in the northwestern arc between the two big orange hallways has their nodes pointed to in the big hash list of nodes "up the tree" from both hallways.
This becomes very problematic as you get many more small nodes clogging up the diagram - the size of these lists increases geometrically with the number of layers of nodes we're dealing with if we use this method. Using some sort of method to trim down on the actual numbers of nodes in the data structure would significantly help trim down the size of the resulting data structure. Either multiple layers of nodes, or more permissive node-constructing methods would keep the overall size of the tree down.
Author
Topic: Improving Pathfinding. (Computer sciency) (Read 65250 times)