0

I did some research about A* algorithm and other graph-based algorithm but most of the tutorials and implementations are made with a 2D-grid and with 2 parameters (x,y coordinates).

Does someone has good tutorials with examples (C++ or Java) or links about A* in different configuration space. Such as 3D environment or non-grid, with x,y,z coordinates or x,y, orientation, or anything else...

Thanks

Improve this question
1
  • 1
    It's the exact same thing in 3D but your heuristic will compute the distance between the current position and goal as the length of a 3D vector instead of 2D. As for not having a grid, it really depends. I suggest you go through implementing it in 2D and then port that to 3D. If you have a specific question then, it'll be better suited for this site. Commented Aug 25, 2015 at 14:03

1 Answer 1

Reset to default
3

The general A* algorithm does not include a grid nor a dimension. It is a shortest-path algorithm for a weighted graph. What the nodes and edges of this graph are, is completely scenario-specific.

In the case of a 2D-grid, the nodes are the grid cells and edges specify adjacency. A similar graph can be built from a 3D grid. If you don't want to restrict yourself to grids, you can built any graph with an arbitrary connectivity.

Nodes do not necessarily need to correspond to positions and weights do not necessarily need to correspond to distances. For example, the Pinocchio System uses A* to grow a skeleton embedding. The distance here is the embedding quality / energy (although the energy is not accumulated along a path). Nodes correspond to partial embeddings.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for your answer and the nice example ! If you have others kind of example like this one, let me know. Thanks again !

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.