DevBlog

I implemented some kind of hierarchical path finding...

Hierarchical because as the planet is in fact a curved cube, each face of the cube has its own grid. So to move from one face to another there need to be a high level graph telling if a point on a given face can reach another point on another face (or on the same one!)

Constructing this high level graph need only be done when the terrain is modified and can be done partially to only reconstruct the parts that changed.

So the first step is what I call: Island detection. It consists in finding for each face the walkable tiles and regroup them in separate sets. Each set containing all the tiles of an island. (I know I might not be the clearest here. :-)) This is done by a simple fill algorithm.

Next step is : Neighbor islands linking!
It consists in creating links between islands that are connected but from different faces of the cube. (Two islands connected on the same face is not possible : they are ONE island.) It's easily done by querying neighbour faces for islands that touch on or more borders of the face. It allows to construct an important data for the pathfinding to come : links between islands and their intersection!

Here we can see what I call "Islands" and how several islands are connected between the planet's faces.

With this information available we are now able to generate a path linking several faces. First we find the start and end islands. With the island graph, we do a brute force search for the end island starting from the start island. We're looking for the smallest path linking the two islands in term of the number of faces traversed. This could be unoptimal as a path traversing three faces could be shorter than one traversing only two faces. But for now, I live with it and maybe I'll look for a better solution if problems arise (Murphy tells me they'll do and certainly at the worst possible time).

Then, we launch several consecutive path searches: First from the start position to the intersection zone with the next island on the next face. Then from the insertion point to the intersection zone with the next island on the next face. Rinse and repeat until we reach the last island where we can search from the insertion point to the end position.