CODEWITHSUNDEEP
c++algorithmgraphpath-findinga-star
Snoopyjackson
Snoopyjackson

Reputation: 25

A star algorithm in a 3D configuration space

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

Upvotes: 0

Views: 6332

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32597

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.

Upvotes: 3

Related Questions