Sign in to follow this  
wolfram

A*

Recommended Posts

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this