# A*

## Recommended Posts

wolfram    122
Hello, how does A* search work? Are alternative methods for generating the nodes? And when should I use it?

##### Share on other sites
rlange    122
The A* pathfinding search works by simply arranging nodes of coordinates into a graph and using a heuristic to calculate the exact distance to the goal at each node. The final goal is to find out how to get from somewhere you are to somewhere you want to be, without bumping into walls or going too far.

There are many methods for generating nodes and the code involved in this would be too much to paste, but I'll provide some good links and a sample Node class.

A* algorithm tutorial

Here is a very basic Node class that should be modified to better fit your game:
class Node{  public:     Node *parent; // parent of successor nodes     Node *child; // ability to view the search in reverse		     float g; // cost of this node plus it's predecessors     float h; // heuristic estimate of distance to goal     float f; // sum of cumulative cost of predecessors and self and heuristic     State NodeState; // current state of node};

##### Share on other sites
wolfram    122
Thanks! I will investigate the links!

##### Share on other sites
yaroslavd    150
Quote:
 Original post by rlangeThe A* pathfinding search works by simply arranging nodes of coordinates into a graph and using a heuristic to calculate the exact distance to the goal at each node. The final goal is to find out how to get from somewhere you are to somewhere you want to be, without bumping into walls or going too far.There are many methods for generating nodes and the code involved in this would be too much to paste, but I'll provide some good links and a sample Node class.A* algorithm tutorialList of pathfinding linksHere is a very basic Node class that should be modified to better fit your game:*** Source Snippet Removed ***

Actually, the heuristic simply estimates the distance to the goal, it doesn't calculate it exactly.

##### Share on other sites
wolfram    122
what are the benefits and drawback of using A*?

##### Share on other sites
tonyg    284
Intelligent Pathfinding
contains benefits and limitations.

##### Share on other sites
wolfram    122
Thanks! I will look in to it.

##### Share on other sites
rlange    122
Quote:
Original post by yaroslavd
Quote:
 Original post by rlangeThe A* pathfinding search works by simply arranging nodes of coordinates into a graph and using a heuristic to calculate the exact distance to the goal at each node. The final goal is to find out how to get from somewhere you are to somewhere you want to be, without bumping into walls or going too far.There are many methods for generating nodes and the code involved in this would be too much to paste, but I'll provide some good links and a sample Node class.A* algorithm tutorialList of pathfinding linksHere is a very basic Node class that should be modified to better fit your game:*** Source Snippet Removed ***

Actually, the heuristic simply estimates the distance to the goal, it doesn't calculate it exactly.

Yes, estimate is a much better word. Let me try again.

'... using a heuristic estimate to find the distance to the goal at each node.'

There we go...

##### Share on other sites
Timkin    864
Quote:
 Original post by rlange'... using a heuristic estimate to find the distance to the goal at each node.'

'heuristic estimate' is unecessary. A heuristic is, by definition, an estimate, because it describes the use of an approximating rule to generate an answer for an unknown problem (in this case the cost function between a leaf node and goal in a search).

Cheers,

Timkin