AI for a Final fantasy tactics-like game

Question

I am implementing a small grid based, turn based strategy in the lines of Final Fantasy tactics.

Do you have any ideas on how i can approach the target selection, movement and skill selection process?

I am considering having the decisions disconnected, but all these 3 decisions are largely coupled. (eg. i can't decide where to move unless i know who i am going to attack, and what range the skill i will use has, and vice versa, i can't decide who to attack unless i know how many turns it will take me to reach each target)

I want to move towards a unified system, but trying out things from Potential field research used in a manner like in the Killzone 1 AI has me getting stuck on local maximums.

=== Update 1

I am currently trying to use potential fields / influence maps to generate the data i take decisions upon.

I have no idea how to handle having many skills, and skills that don't do damage but rather buff/debuff or alter the world.

Someone elsewhere suggested using Monte Carlo Tree Search, used currently in Go games.

I believe the space my actors will be using is not good for it, as many many moves in the game don't result in a position from which you can attack and affect the world (i am in a world bigger than final fantasy tactics)

In final fantasy tactics it might be applied successfully, although the branching factor is much bigger than that of 9x9 Go (from what i understand)

===

Thanks in advance, Xtapodi.

ps.1 - A problem is that to know accurately how far an enemy is i would need to pathfind to him, because although the enemy is near, an impassable cliff might be separating us which takes 4 turns to go around. Or worse, a unit is blocking the way on lets say a bridge so there is actually no way to reach him.

Betroth

Answer 1

One approach I've used is to do a two-pass system.

First, find out where your unit can go. Use A* or whatever to flag out the terrain to see how far the unit can move this turn.

Once you know that, step through your available tactics (melee attack, heal friendly unit, whatever), and assign a fitness function for all available uses of the tactic. If you pass in the flagged terrain, you can very quickly determine what your space of possible tactics are.

This gives you a list of available tactics and their fitness functions for each move. Select the best one or randomize from the top. If there aren't any tactics available, repeat the process with flagging the terrain for two moves, and so on.

What I mean by fitness function is to decide on the "value" of performing the tactic on a certain unit or location. For instance, your "heal a friendly unit" tactical decision phase might step through all friendly units. If a friendly unit is within range (i.e., is reachable from a location your unit can reach), add it to the list of possible tactics and give it a fitness rating equal to, say, 100 * (1.0 - unit health), where unit health ranges from 0 to 1. Thus, healing a character down to only 10% health remaining would be worth 90 points, while a unit only down 5% would only be worth 5, and the unit wouldn't even consider healing an undamaged unit. Special units (i.e., "protect the boss" scenario units required to retain victory conditions) could be given a higher base number, so that they are given more attention by friendly units.

Similarly, your "melee attack" decision phase would step through all reachable enemy units, compute the likely damage, and compare that to the unit's health. Give each unit a "desirability" to attack, and multiply it by the percentage of remaining health you'd likely do, and you've got a pretty detailed fitness function that favors eliminating units when you can, but still goes after high-value targets.

Using a process like this, you'll get a list of options like "Move to location A and heal friendly unit B : 50 points", "Move to location C and attack hostile unit D : 15 points", etc. Suddenly, it's really easy to choose a tactic.

Further detail may be added by multiplying the fitness of the tactic by a fitness for the path you'd have to take to implement it. For instance, if the place you'd have to move to in order to heal a friendly unit puts you in severe danger (i.e., standing on a lava space or something), you might factor that in by multiplying the fitness of that tactic by .2 or so, so that the unit may still consider it, but only if it's really important. All this takes is writing an algorithm to assess the fitness of a given location, and could be as simple as a pre-computed "terrain desirability" number or as complex as maintaining "threat maps" of enemy units.

The hard part, of course, is finding the right measures to make the engine smart. But that's the fun part of your system to tweak.

Precedence

Thank you very much cc for you detailed response. I often came close to what you describe, what is a great insight is that you expand your search space if nothing intersting is found. How would you take in account positions with no action that offer tactical advantage. For example you have a knight and 2 archers, the knight would charge far out of the range the archers can be of help in your model. Vice versa if you add fitness to just standing somewhere then how would you decide to expand your search space. – Betroth

Handle it by giving fitness to terrain that favors the behavior you want. For melee fighters, locations close to the enemy having higher fitness moves the fighter closer, but adding "close to friendly units" keeps your units together. Layer enough fitness considerations, and your units get smart, even if you don't look ahead a turn. It's also easy to drop in specific tactics with this system. If you have a level with a raised drawbridge, add a fitness function for the path to the lowering mechanism. – Precedence

Answer 2

If the terrain where the battle occurs are pre-determined, or not too wide, there is an article on terrain reasonning in FPS that can be used as a basis for a turn-based game.

In short, you pre-calculate for each cell of the map a set of values, such as suitability for shooting in a given direction, protection, visibility... and so on. the AI can then use these values to choose a correct action. For exemple, fighter will walk as quickly as possible toward ennemy, using protection if available, while thief will take a path where visibility from ennemy direction as low as possible, with the goal of attacking from flank or rear.

if the terrain is randomized and/or too wide, the pre-calcul can be to long to be useful, however.

regards Guillaume

Stallworth

Thank you Guillaume for the reply, i am still reading the paper and thinking on how and if i can apply it. I have the feeling that for some things having approximate data can seem really bad on this type of game, for example line of sight. – Betroth

yes and no. you don't have line of sight, just the fact that the cell the ennemy is on has a low visibility on the left. Thus you can use it to restrain your path search to this side of the foe. Another exemple : knowing that the ennemy will have to pass by an area and knowing that the is a very good shooting position for this area (ie good visibility for this area, lot of small obstacle in this direction, low acces or visibility on other direction) can be useful for an AI sniper :) But you effectively have to check the real line of sight – Stallworth

Answer 3

A good question the answers can be all over the place. Personally, I don't have a lot of experience with this but I would set a strategy around concept not distance.

You are going to create a state machine for each NPC. It will be predicting a character to attack via some settings.

For example a NPC would be flagged as Attack weakest or Attack Strongest or Attack Most Injured. Then I would attempt to position them such that they can damage there desired target.

If you also have healers you can do the same thing in reverse for the healer target.

Target changing will be an important part of this system too. So you will want to think about that. A simple version is to reevaluate changing target a given percentage of the turns.

And finally, I would add random chance into the system. For example a character could be set as follows

Attack Weakest .25 Attack Strongest .50 Attack Most Injured .25

Change target .1

When it's time to attack. You generate a random number from 0-1. If it's under you Change targets you change target by generating another random number of what target to attack.

You can begin to factor distance into your system by augmenting the attack mode percentages. For example if it would take 3 turns to attack the most injured. Decrease it's percentage of being targeted by dividing that value by 3 and distributing the difference to the other two possibilities.

Frisby

Thank you for the great input madmik3. I like many of the ideas you propose, my current mindset is based around a greedy algorithm always choosing the best action this turn, which might be largely flawed when viewed from a player. On your last paragraph, the thing is that i might be near an opponent but actually separated by a river that takes 3 turns to cross around, would you suggest to pathfind for each possible target (expensive) at target selection, but keep target selection from happening every turn to balance the execution load? – Betroth

@Xtapodi: Real-time strategy games implement pathfinding routines for all of their units without much problem. The cost of implementing pathfinding routines for the much smaller number of units in a turn-based, FFT-style game, where computation time is much less of an issue, would seem to me to be quite negligible, even if you're checking paths to all possible targets. In fact I would suggest doing it like that, because you can then calculate, based on other factors such as player unit health, etc., whether the enemy units should be moving elsewhere rather than focusing on the closest PC unit. – Prerequisite

@JAB: Thank you for your comment. What you say about RTS might be true (depending on the game) but also took some months of work from people who had already lots of experience. Yes being turn based gives me a lot more time to process. Would you suggest running a Dijkstra from every player unit (currently 4 - 5) and then let the AI work on that data? – Betroth

@Xtapodi: I'd suggest trying the A* algorithm, which is an extension of Dijkstra's algorithm and is usually more efficient. You may also want to check out incremental heuristic searches. – Prerequisite

@JAB: Well, on a 1024x1024 map of an RTS you would have 1 million nodes, there are algorithms documented for such cases and i will leave the subject at that. Yes A* will probably do the trick, but A* is on worst case the same as Dijkstra, so if for example i need to do A*'s from an AI unit to each player unit doing only one Dijkstra might actually be an optimization, my problem is deciding what i need to make my tactical decision, and then use the appropriate pathfinding algorithm (if any, i am currently using attraction fields, thus i get stuck in dead ends) – Betroth

@JAB: Seems like i answered while you edited your comment, thank you for the link on incremental heuristic searches, i will go read it now :) – Betroth

@XTapodi: you said 'small grid based'. You don't need to worry about 'worst case' or even what the appropriate algorithm is. You could probably use a trivial breadth-first search for pathfinding here and you'd notice no slowdown at all unless you're using a slow game-maker scripting language or something. – Warm

@Kylotan: Well the main problem is how i would go about choosing where to move and which of my skills to use, since the first might depend on the second and vice versa. – Betroth

@Xtapodi: Sure, but that's a separate issue to your pathfinding. – Warm