• Advertisement
Sign in to follow this  

A*

This topic is 4354 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

List of pathfinding links

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 this post


Link to post
Share on other sites
Quote:
Original post by rlange
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

List of pathfinding links

Here 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 this post


Link to post
Share on other sites
Quote:
Original post by yaroslavd
Quote:
Original post by rlange
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

List of pathfinding links

Here 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 this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement