Quote:> Sorry let me re-explain, If I have an AI general at x1 who wishes to goto a

> location x2 then he has a skill level in finding the shortest path. This is

> a percentage chance of each node (on a grid) on the path being calculated

> by the A* algorithm or another, less accurate, algorithm such as

> abs(x2-x1). However do I need two algorithms or can A* be made to be less

> accurate? (maybe by a more pesimistic heuristic?)

Ok, you are very much on the right track.

The important thing to remember about A* is that the (estimated) cost

anywhere along the path consists of two parts -- how much we have paid

to get to the current node, and how much we estimate the rest of the

journey will cost. The latter is done by heuristics (typically the

euclidean distance, ie. d = sqrt(dx^2 + dy^2) for the 2 dimensional

case.)

What you're trying to do, is to degrade optimal performance, and I

somewhat doubt that anybody has been doing such a thing to A* before.

The usual way to deal with it is to add noise, ie. choose the optimal

path with a certain probability. This is exactly what you're doing

(provided I didn't misinterpret it.)

Another (related) method is to adjust the value returned by the

heuristic function (which is more or less what you suggest with a

pessimistic heuristic.) Adding a random (positive) value to the heuritic

value results in a more pessimistic estimate, and subtracting a value

results in an over-optimistic estimate.

The tricky part is to select the random value. It must not be totally

random. Otherwise the movement with be totally random too. If it is

zero you have a normal A*. What we want is a random value which is

mostly close to zero, and the more 'skilled' an entity is the closer

to zero we want it to be.

The solution to this is to use non-uniform random distribution

functions. Several distributions are possible, but my guess is that the

normal (gaussian) distribution will be well suited.

There are several standard (freely available) libraries that has

such functions. CNCL springs to mind. See

http://www.desy.de/ftp/pub/userwww/projects/C++/Projects.html

http://www.comnets.rwth-aachen.de/doc/cncl.html

If you want a description of how it works, the best reference I know of

is "Numerical Recipes in C" by Press et. all (Cambridge Press, ISBN

0-521-43108-5)