My plan is to use A* to mimic intelligent A.I. movement along a terrain. Im using a simplified set of nodes (a graph) that i created based on the terrain. So I know exactly how many nodes and edges (represented by an adjacency matrix). Would it be necessary to have a complex heuristic if im using A*? I figured sine I know the node connections for every node, I would only need to choose the edge and go to the other side of the connection (the other node). would this work? ps - what exactly is a heuristic, and why is it termed that instead of something like "algorithm?"

quote:Original post by GekkoCube
My plan is to use A* to mimic intelligent A.I. movement along a terrain.

A* is merely a search algorithm that seeks to minimise a given cost function along a path from a start node to a goal node. So, the only intelligent thing going on here is that an agent following that path is doing so at minimum cost to themselves.

quote:Original post by GekkoCube
Im using a simplified set of nodes (a graph) that i created based on the terrain. So I know exactly how many nodes and edges (represented by an adjacency matrix).

If you have a complete adjacency graph, then you might want to consider using Dijkstra's algorithm instead. I presume by the fact that you have this adjacency graph that you compute it offline... if so, you can run Dijkstra's offline as well to return the shortest paths between any pair of nodes in the graph. The down side of this approach is the data storage and load requirement at the start of the level... but then you don't need to do any further pathfinding during runtime of the level, other than a table lookup.

If you are not computing this offline, then you will want to build a search tree at run time based on the start node.

quote:Original post by GekkoCube
Would it be necessary to have a complex heuristic if im using A*?

Not at all. For most pathfinding domains, straight line distances between the current leaf node and goal node (SLD) is a sufficient heuristic as this never under estimates the goal (for Euclidean spaces).

quote:Original post by GekkoCube
I figured sine I know the node connections for every node, I would only need to choose the edge and go to the other side of the connection (the other node).

This will give you the possible successor nodes of any leaf node that you choose to expand during your search (if I understand your statement correctly). It will also give you the cost from start node to each successor, since it is just the sum of the partial paths from the start to the current node, plus the cost of getting from the current node to each successor node.

quote:Original post by GekkoCube
ps - what exactly is a heuristic, and why is it termed that instead of something like "algorithm?"

A heuristic is merely a rule that approximates the truth (an educated guess). So in the case of search algorithms like A*, an heuristic is used to approximate (estimate) the cost of getting from a currently considered node to the goal node, since we don't actually know that cost within considering some describably path to the goal and integrating a cost function along that path. Since there are conceivably an infinite number of paths from the current state to the goal, it is not practical to do this. Thus, we estimate the actual cost using our heuristic (guessing rule).

For A*, the heuristic must be admissible. That is, it must never over-estimate the true cost to the goal and it must be a monotonic function for any given path to the goal. That is, given a path, there must be a 1-1 relationship between distances from the goal on that path and heuristic estimates of the path cost. As mentioned above, for Euclidean spaces, straight line distance works well as an admissible heuristic.

I hope this has aided in your understanding of A*. Good luck with your implementation.

Cheers,

Timkin

[edited by - Timkin on September 1, 2003 9:42:05 PM]