I'm an AI newbie, but after reading through the F.E.A.R. AI document, reading through some posts on here about A*-ing through the action-space of the AI (this is an excellent forum, btw), would it be feasible to have an FPS AI A* through future world states? Let me explain what I mean. First, discretize the action space to something like: move (with a discretized number of compass degrees in which the AI could move, including a do not move action), shoot (on or off). Then, discretize time into reasonably sized chunks (maybe 1 second?). Use the A* algorithm to pathfind from the current world state (world state defined as the AI health, player health, AI position, player position) to a world state where the player health is zero, using AI actions as edges of the graph. To determine how an AI's actions change the world state, use a markov chain of some order (fancy words for a simple probabilistic approach) -- this would, for example, evaluate how likely it'd be that the player would return fire immediately when shot at, or how likely it is that the AI will succeed at hitting the player. The costs for each edge of the graph would be evaluated based on things such as the AI's cover and the AI's health. As the AI is executing the path, there'd need to be some checking to see if the error between the predicted worldstate at each step along the path and the actual worldstate is larger than some threshold, at which point the AI would need to re-plan. Does this sound like a reasonable, general approach? Or am I just making an overly complicated, poorer performing duplication of a planning algorithm?

A* is not appropriate without full knowledge of the state space. If the world can be modeled as a Markov process (which it almost certainly can't) then you should use algorithms meant to operate on Markov processes. Using A* here would be a square peg in a round hole.

Quote: If the world can be modeled as a Markov process (which it almost certainly can't)

I understand the markov process is a poor way to predict the world, but using it was my way of trying to get the AI to do some strategic thinking -- it needs to have some sort of model of what the player might do to be able to plan out future actions, right? The markovian thing was just a super simple approach to try to anticipate the most likely outcome when you don't know in advance, and it could be substituted by any system.

Quote: A* is not appropriate without full knowledge of the state space.

Well, then how do you pathfind around a scene with moving objects? Reading this page:

http://www.policyalmanac.org/games/aStarTutorial.htm

Under "Notes on Implementation" section "1. Other Units (collision avoidance)" he suggests: "you can discourage collisions by penalizing nodes that lie along their respective paths, thereby encouraging the pathfinding unit to find an alternate route (described more under #2). If you choose to consider other units that are moving and not adjacent to the pathfinding unit, you will need to develop a method for predicting where they will be at any given point in time so that they can be dodged properly."

So that to me implies that there's some imperfect predictive component necessary to guess the world state. Sure, this means A* won't path perfectly, but I'm not looking for perfect, I'm looking for "reasonable." The other difference is that I'm trying to extend the pathfinding graph from a space-based system (you start at these coordinates, you want to end up at these other coordinates, do A* on the graph to find movement actions that put you at the end coordinates) to something that also incorporates actions (you start with the player health at 100, you want to reduce it to 0, do A* on the graph to find movement and firing actions that put the player health at 0).

I'm sure you're much more experienced with this stuff than I, but please bear with me -- I'm trying to improve my understanding.

This approach will resemble expectiminimax more than A*. With A* planning, you are trying to find a set of actions to reach the desired state. There is no opponent's actions to consider. That's why in game AI, A* is usually used to find a path to a state that was determined at a higher level. Also, making a move cost more because it might be invalid is a sort of hackish approach. A* can work with nodes that represent both location and time, and this can be a more effective way to handle predictable moving obstacles.

You will probably find that you will very quickly have a combinatoric explosion of possible world states to have as candidates even with minimal future steps being considered (the more actions and results of actions and richness of terrain factors+positions, the geometricly larger your search space will grow). Metrics to use for your heuristic function might likewise prove difficult because target result progress might not be easily derived from incidental results (damage/powerups/position on map/enemy position).

Venzon, I like the direction of your research. It shows an intellectual capacity capable of becoming a very good programmer, rather than just a copy & paste guy.

How do living organisms solve predicting the future, such as catching a frizbee or playing tag? It seems to me that such problems are solved by using a recent-past buffer, projecting a continuation of what was happening forward. How far forward the prediction can remain valid to within a reasonable confidence level depends on the enemy AI's physical and tactical maneuverability.

Tactical maneuverability draws on something other than a recent-past buffer. More of a stochastic model of behaviors exhibited in a given situation, with updatable estimates of likelihood. A housefly can change course very quickly, but can be counted on to execute a standard lift-off pattern. A cock-roach does a zig-zag, a sudden-dash and a rabbit-stop. It also has short-range flight capability, but that tactic is under-used.

And here I imagine a set of probability weights for the current situation, and another for an immediate past situation. Between the two sets, each pair of probability weights for a given action forms a vector. One could even project forward a predicted set of weights for enemy actions, and act in ways to shift the weights of likely enemy behavior in your favor.

[Edited by - AngleWyrm on July 5, 2007 4:12:58 AM]

Wow, so many responses so quickly! This is totally the best gamedev forum. :-)

Quote: you will very quickly have a combinatoric explosion of possible world states to have as candidates

If I add a lot of actions, that's certainly true, although keep in mind that A* only expands the most promising nodes.

Quote: Metrics to use for your heuristic function might likewise prove difficult

That's a very good point. The time complexity of A* is heavily dependent on how good the heuristic is. Unless I have a great heuristic function, my approach won't work, because A* won't find the path fast enough, and this is exacerbated by the combinatoric effect you mentioned above.

Quote: This approach will resemble expectiminimax more than A*. With A* planning, you are trying to find a set of actions to reach the desired state. There is no opponent's actions to consider.

Ah hah, I see what you're saying about expectiminimax. I hadn't heard about that variation of minimax before, but I can definitely see how what I'm trying to do is more like a chess AI (that's what minimax is often used for, right?) because it's trying to anticipate actions by an adversary, and the probabilistic approach I talk about is kind of like expectiminimax because it's dealing with "chance" nodes.

Quote: How do living organisms solve predicting the future, such as catching a frizbee or playing tag?

The analog of living organisms is what's inspired me... I read On Intelligence by Jeff Hawkins (nice general ideas, but a longer book than it needed to be), and it seems like the crux of intelligent decision making is having an internally constructed model of how the world will work and using it to predict into the future. When something differs from the predicted model, you take notice, and you learn (adjust your model).

Anyway, thanks everyone for all of the replies so far. I've got a better picture in my head of where the trouble areas are, and some other algorithms to explore (I'm especially interested in expectiminimax modified to provide more efficiency at the expense of accuracy, possibly by ignoring large sets of nodes). I think I'm to the point where I can start prototyping, but I of course welcome additional advice.

[Edited by - venzon on July 5, 2007 2:05:29 PM]

Quote: Original post by Sneftel
A* is not appropriate without full knowledge of the state space.

I disagree with this statement. A* is a search algorithm. It's appropriateness depends only on the 'searchability' of the space it it applied to. The OPs suggestion is to use it to search the plan space (sequences of actions that are monotonically increasing in length and cost).

I have personally had great success using this approach to search continuous, unbounded state spaces to find optimal (lowest cost) plans for a given start-goal pair. It does work... but there are complications, particularly when your state transition function is probabilistic.

Timkin