Hello,
how does A* search work? Are alternative methods for generating the nodes?
And when should I use it?
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:
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};
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.
Quote:Original post by yaroslavdQuote: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...
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement