tl;dr I need an algorithm similar to SSFA except for portals with 4 vertices (or n vertices if an algorithm like that exists).

I'm working on a game that requires pathfinding in 3 dimensions. By this I mean agents have full control over their position as opposed to many games where agents only control forward, back, left, right, and need to walk up stairs or ramps to go up and down.

To do this I made a "nav-mesh" using an octree that checks for collision at each region, and subdivides if there is a collision (until a certain cube size limit). So I now have a graph where each node is a cube with some size based on the octree. Using this I can run the A* algorithm for pathfinding on the graph.

Unfortunately, just moving towards the center of each node looks bad, and even moving towards the center of each connecting face of the node (the smaller of the two connected node's adjacent faces) looks bad.

In the past, I've used the SSFA for path simplification, but it only applies to situations with an edge as a portal, not a face. Is there an algorithm for this, or is there a way to make my pathing look better?

Ninja-edit: I'm already somewhat using steering behaviors, but since the center of nodes can vary wildly, based on the complexity of the octree, it still doesn't look nice.


Your Answer

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

Browse other questions tagged or ask your own question.