Hierarchical pathfinding question

[madmenyo]

I have seen your implementation of the hierarchical pathfinding and mine is slightly different. I just have a tilemap and each tile has a node with connections. Now I want to divide my map in "sectors" and build nodes on the edges where there is a entrance.

• Is there some implementation already available that does this for me? Since this would be pretty much the same for each basic tile map I would expect something like this is already in place. Something like this:

  (forgot a view connections).

If so, I would like to know :)

If not:

• So i lookup all the borders and add level 2 nodes where there is an entrance. I (try) to connect all those within a "sector" and the bordering neighbors.
• Is this sufficient, does the pathfinder find paths in between the level 2 nodes once it finds a level 2 path? Or do I need to store the actual shortest path in the connections? I can imagine it is the former since looking up A -> B -> C -> ... -> Z is much faster then looking up A -> Z where the open list will grow out of control.

I see you store all the nodes in a single array and use an offset for higher levels. However I want to make a dynamic map. And once a node changes it will update it surrounding nodes and if level 2 changes as well it does the same. But that means I need something more flexible then a ArrayList or (like I do on the 1st level) create all possible nodes and alter there connections. I would appreciate some pointers in the right direction.

Thanks in advance,

[davebaol]

What you're trying to do is known as "graph partitioning" in pathfinding literature. There are many techniques, each with pros and cons, but none of them are currently supported.