Hi. I'm currently working on a game for my Artificial Intelligence class. It's your basic top down, fixed size; kill everybody else, arena game. Combat is very… ummm Zelda-esque. For simplicity they be just three attacks, a close range punch/sword and long range bow and arrow (which requires ammo), and the boomerang (stuns but no damage.) Random item pickups also appear both of health and ammo. Yeah yeah, this has all been done a million times by everyone including me, which is why I decided to use it for my AI project since I can write it in less than 3 weeks. Anyway, I’m using an A* algorithm to have my AI characters make there away around the map. My real question is does anyone have any suggestions for what kinds of heuristics I can use to make my AI characters act like a human player. I have many ideas of my own, but I wanted to hear what the more experienced peoples out there think. Thanks!

Hi.

Im not sure I understand. Are you talking about the heuristics for the path-finding? In that case, since A* returns an optimal path, any valid heuristic will yield the same result, but with different performance. If you want to vary the path chosen using A*, it is the actual cost function you have to change, not the heuristic.

If you are talking about heuristics for a problem other than pathfinding, please state the problem better.

Good luck with your project!

Steadtler

Sorry about that...

What I meant to say was, I have pathfinding working. That's the easy part. The part which I am wondering about is how best to emulate a human players actions.

Basically I though that I would keep track of the state of the AI player, and use that to formulate what his current goal might be. So if he is fairly damaged or something, he might avoid other players and wait for a health pickup to appear.

Do I just use a set of heuristic rules for this? Is there some kind of data structure or method other people have used to keep track of this information?

Thanks.

States machines are fairly common for this problem. There are more complex solutions, but its probable whats gonna work best for you. Check the AI tutorials in the "articles" section of Gamedev, you'll find plenty of information.

Quote: In that case, since A* returns an optimal path, any valid heuristic will yield the same result, but with different performance.

It's late and I'm tired so I may be mistaken, but I could have sworn adjusting the heuristic can change the path. An example might be a heuristic that, for whatever reason, scores paths that towards the top of the map better than ones taht go south. If an obstacle existed in the middle of the map, it would tend to result in paths that went ABOVE the obstacle. Change the heuristic to favorite the bottom, and I'd expect the path to go around the other way.

All admissible heuristics for A* generate the same (optimal) path from the start to the goal. Having preferences for type of path over another would be reflected in the cost function. The only way an admissible heuristic could affect the path is if there was more than one optimal path, and even then under certain conditions it may be difficult to tell which routes would be favored.

An inadmissible heuristic has more flexibility in affecting the result since the path it finds is not guaranteed to be optimal.

What algorithm are you using to drive the selection of goal (kill player, evade player, seek pick-up, determining between different pick-ups, etc)? And then, what algorithm are you using to determine the action you must take to achieve the goal? Heuristics are easier to formulate if we know what framework to formulate them in.

Of course, if your algorithm is simply "run a bunch of heuristics, and pick the one with the highest score" then the heuristics are about as simple as the algorithm -- and really, really hard to tune until they're right, because they interact or counteract each other in surprising ways.

I would probably code up three simple kinds of players -- one that prefers waiting in a corner and attacking at range ("camper"), one that prefers running up to people and hitting them, and one that prefers power-ups and staying the hell away until everyone except one other player is dead. I wouldn't tune them too hard. Then, I'd make up a buttload of possible heuristics, each with a matrix of input signals, a vector of weighting factors, and an output signal for the possible actions. Then, I'd drop various randomly seeded versions of this fourth heuristic into the arena, pitting them against the three hard-coded ones, and run genetic selection on them until I have a few good ones.

Genetic Algorithm eh? Interesting idea... Hmmmm, I'm not sure If I'm clear on what the output signals would be. Something like, "attack the nearest enemy", "find a health pick-up", "run-away". Or something different?

Like most of us, you are doing things in reverse.
Begin by listing the possible motives

-> Health level, ammo, position, moon cycle, etc

and list the possible actions

-> shoot player, get health pack, run in circles, etc.

When you have two complete lists, then can you begin to work on a way to choose an action for any combinaison of motives.