# Thread: AI programming help wanted

1. Dijkstra's algorithm is a special case of A* for an always 0 heuristic.
That means that its not doing any 'guessing', which is exactly the problem with A*.

If you chuck a load of walls between the origin and destination it can screw up the heuristics resulting in an estimated distance that is much less than actual distance needed to reach the target.

The only way to truly be exact is to not use heuristics, although that is a lot slower.

 also you have not explained how you would model the terrain cost into the heuristics.[/edit]

2. Originally Posted by Perspective
I would break things down into basic actions, like attacking a unit in neutral territory, invading enemy territory, expanding your territory, etc... As well as the state of the game (I have an alliance, x territory, x units).

All of these can then be fed to a scoring function for a particular goal. If you have a goal to make an alliance, than attacking a unit in neutral territory carries negative weight for that goal. Invading an enemy carries even worse weight. However, they carry positive weight towards other goals such as winning the game. Not having an alliance also contributes negatively to winning the game. etc..

The AI then evaluates the effect of candidate actions on all of it's goals and chooses accordingly. Different AI strategies will value (or weight) goals differently. Tuning these weights (or learning them) is what makes a good AI.
Sounds like a good place to apply fuzzy logic if you ask me... Programming Game AI by Example maybe something you want to look into. While the examples may not fit exactly, a lot of the logic will be useful.

3. Programming Game AI by Example, ISBN 1-55622-078-2

good introductory-intermediate text on the subject, although the author is a bit stuck on writing everythign as a class and Im not real fond of singltons. Other than that he does a decent job of covering most aspects of AI as it applies to games.

4. Originally Posted by mike_g
That means that its not doing any 'guessing', which is exactly the problem with A*.

If you chuck a load of walls between the origin and destination it can screw up the heuristics resulting in an estimated distance that is much less than actual distance needed to reach the target.
Ok, you've now made it clear that you don't understand A*. In order for A* to give you an optimal path, you're "guess" has to be equal to or less than the actual distance. If that is the case, A* is always optimal. period.

Originally Posted by mike_g
 also you have not explained how you would model the terrain cost into the heuristics.[/edit]
Build a graph with a node for each position. Edges are placed between nodes that you can walk to (allows you to model all of your walls and obstacles). A weight is placed on each edge representing the cost of traversing it (based on your terrain type or anything else you'd like). A* will, as long as your heuristic does not over-estimate any distances, always find a minimum cost path through the graph.

A simple heuristic that will work fine for your games is straight-line distance. Minimum cost path guaranteed.

I suggest you read this. It's a good description and there are some links to A* demos that can show you how it works.

Also, these slides from a CMU prof are pretty good. You'll notice slide 11 makes your claim, that A* is not optimal, but that is only because the heuristic overestimates costs. On slide 14 the main theorem of A* is stated "A* with an admissible heuristic guarantees an optimal path". Admissible means that the heuristic never over-estimates as I've mentioned a few times. The proof that A* always finds an optimal path starts on slide 21.

5. Just an observation, but this thread isn't discussing path finding and if you folks are going to continue discussing A* or Dijkstra's perhaps you should start your own thread.

6. Originally Posted by Wraithan
Just an observation, but this thread isn't discussing path finding and if you folks are going to continue discussing A* or Dijkstra's perhaps you should start your own thread.

3/10.

7. Originally Posted by Wraithan
Just an observation, but this thread isn't discussing path finding and if you folks are going to continue discussing A* or Dijkstra's perhaps you should start your own thread.
ah, btut he thread is discussing the guys need for AI, and part of game AI is pathfinding algorithms.

8. Wraithian: Yep, Pathfinding is AI

Perspective:
Ok I went through my A* code and there was no problem with the heuristics, but I discovered that my cost function was counting one less tile than had been traversed. So yeah you were right my implementation was broken and I'm an idiot. Thanks for pointing it out

It seems understandable to me now that A* can find the shortest path as long as it does not over estimtate the heuristics, but from what I could see it appears you could still get problems using A* heuristics with terrain.

In the crude diagram below A is a current end node on a path, T is the target, and numbers indicate the squares move cost (A and T have a cost of 1). Assuming I understood you right and you would factor in all tiles along the line drawn by the heuristic, this would give a heuristic value of 9 when the actual cost is closer to 3.8.
Code:
```1 1 1 1

A 5 5 T

1 5 1 1```
Putting accuracy aside there is another reason why I would chose Dijkstras algo for a turn based strategy game. Since A* uses a heuristic to a target, it needs a target first. A common way to get the closest target is to use Pythagoras, which would be guessing the distance for this purpose. Using an algorithm that dosent use heuristics means that it can expand nodes outward up to the units move range and not only find the closest target, but build up a list of all reachable targets from which the AI can make decisions based on stuff like: distance, stength, proximity to allies etc.

9. >Assuming I understood you right and you would factor in all tiles along the line drawn by the
> heuristic, this would give a heuristic value of 9 when the actual cost is closer to 3.8.

The heuristic can be independent of the tile costs, it just has to be some conservative estimate. If you use city block distance for example, you will estimate the cost (h) of A->right to T as 2, A->up to T as 4, and A->down to T as 4. Then, the actual cost of your next step is cost(A->move) + h(A).

Assuming it cost us 0 to get to A so far, the estimate for going right is (5+2) = 7, and for going up or down is (1 + 4) = 5. So the long path is ruled out immediately. In the next step we'll rule out the bottom path in the same way and A* will find the top, least-cost path.

10. Sorry, I explained that example incorrectly. 'A' was meant to refer to a tile checked from an adjacent tile, not a position from which the surrounding tiles would be checked. Also I said there would be a heuristic of 9 when it should be 11 o_0.

Anyway since the heuristic for A would then be high that node may not be as high up on the list as it ought to be. Hope that makes sense.

11. >Also I said there would be a heuristic of 9 when it should be 11 o_0.

If the heuristic from A to T returns anything higher than 5, than it is not an admissible heuristic. The city block heuristic from A to T would be 3.

12. Yeah I guess that by using the base move cost for a tile you would never overestimate the heuristic, but the pathfinding would be a lot slower.