16
\$\begingroup\$

My question is what would be the best approach to pathfinding on an uneven planetary surface?

Background Information

I have created a planet from displacement mapping 6 sphere projected planes. The planes initially formed a cube before being projected into a sphere shape.

enter image description here

I'm wondering if it is possible to use each "sphere projected cube face" as grids and use a simple A* algorithm to find the best possible route, I would also like the displacement height to be taken into account so the path avoids climbing mountains etc (I guess this would just be a heuristic within the A* algorithm) Another consideration is that I have achieved planetary movement by leveraging Unity3d's physics engine, apply gravity towards the centre of the planet. Would my proposed solution require the agents movement to be controlled independently to gravitational physics.

To help better articulate my question this is my current planetary body:

enter image description here

| improve this question | |
\$\endgroup\$
  • 2
    \$\begingroup\$ You may be interested in this video from Planetary Annihilation. They appear to be doing the same as you wrapping the world from a cube and path finding around it. It's not really an answer, but you can see that they're using A* along with some other strategies for optimizing path-finding around on a sphere. Path finding bit starts at 24:30. \$\endgroup\$ – MichaelHouse♦ Apr 15 '13 at 17:44
  • \$\begingroup\$ @Byte56 Thanks for this link really interesting approach to costing, can't wait to see that game when it's finished! \$\endgroup\$ – Caius Eugene Apr 18 '13 at 17:28
12
\$\begingroup\$

It seems you've already answered your own question. A* is likely the best approach. Yes of course it can be used in the way you describe, including using the height information to avoid mountains. As long as you're able to access information about any grid on the surface of your world, there's no reason you can't use it in the A* heuristic.

Finally, you're confusing path finding with path following at the end of your question. Path finding doesn't care about gravity, unless you add it as a heuristic and since you're on the surface of a planet, gravity will be essentially the same over the entire surface. Many games have gravity together with movement, I see no reason you can't.

Basically we want to map going from red to blue, to be the same on a sphere as it is on a cube.

enter image description here

Since A* is frequently getting neighbors to its current node, you can easily create a set of functions for getting adjacent nodes. For example, getXPlus(), getXMinus(), getZPlus() and so on. These functions will take the current node and return the node in the direction specified by the function name.

Most of the time these functions can just increment a value and be done, however, on the edges, that will change.

You'll want to map the surface of your cube to a 2D coordinate system. However you do this is up to you, they don't have to line up, just give each grid space a unique X, Y coordinate.

Now when on an edge, and getting the adjacent grid space it's not necessarily going to be just incrementing the coordinates. We have to find out which face we're moving to and switch to the coordinates of that face.

For example, getting the XPlus coordinate here will change both the X and the Y coordinates because we're moving to a new grid space on a new face. The green line represents an edge between two faces.

enter image description here

Now these are just global coordinates, it may be easier to use an internal local coordinate system, with a 3rd dimension that represents the cube face you're currently on.

Either way, you need to have a unique coordinate for each grid space on the face of the cube. Traversing between them will depend on how you implement the coordinate system. You need to know where that coordinate maps to the surface of the sphere too.

All this should eventually be abstracted away so that you don't even know about it.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Cheers for the response. I think what I'm struggling with is with each plane being a isolated grid. Would you have any suggestions (or further reading) on how to deal with the seams, I'm guessing I will be to mathematically unfold my "cube", combine all the grids and calculate the path using that dataset? \$\endgroup\$ – Caius Eugene Apr 15 '13 at 14:49
  • \$\begingroup\$ Really it's just the edges you need to worry about. That's easily solved by a wrapper function (wrapping your cube in a wrapper function, that wraps your world...). You can abstract the cube into a flat surface that wraps. Create functions for getting the adjacent grid space, getXPlus() will get the grid in the XPlus direction, doesn't matter if it's on the boundary between faces, the function will just switch faces and return the appropriate grid information. \$\endgroup\$ – MichaelHouse♦ Apr 15 '13 at 14:56
  • \$\begingroup\$ The only inaccuracy with path finding on the folded cube is that vertices are skewed and therefore the edges have different lengths. It's possible that it won't make a noticeable difference in resulting paths and otherwise you simply could take the lengths into account. \$\endgroup\$ – danijar Apr 15 '13 at 18:19
  • 1
    \$\begingroup\$ The important thing to understand here is that A* does not necessarily operate on a plane; it operates on a graph. Although within each cube face, the nodes are arranged and connected in a grid, there are also node connections across the edges of the cube. \$\endgroup\$ – jmegaffin Apr 16 '13 at 18:54
  • 1
    \$\begingroup\$ @Byte56 Thanks for the great answer, I've started implimenting a solution however I've hit a bit of a roadblock. Maybe i've misunderstood. I've posted a question over at stackoverflow as I felt its more of a math/programming problem stackoverflow.com/questions/16089074/… \$\endgroup\$ – Caius Eugene Apr 18 '13 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.