How to implement AI in FFT-similar game?

[The_Absent_King]

I am creating a game engine for making tactics games. Rest of my indie team is working on story, assets, etc. I am just about at the point where I need to start modeling the AI. I need help with ideas.

The game is a spiritual successor to FFT, close enough to be considered a clone. XP / JP growth is same. 15 classes, able to select secondary reaction passive and movement skill. It even has an analog to the zodiac system. Basic game mechanics are similar to 1.3, except Brave/Faith has been split into three new parts and there is no speed growth.

So, anyways, AI. How to best approach it? Fuzzy state machines? Hierarchy of needs?

Or, even better, how does FFT handle its AI?

[R999]

Which platform are you working on? I am very anxious to start this project in a year's time. My eyes are on the iPhone, as long as Square's not doing it, I believe there's a very good demand for this kind of game.

As for the AI, I'll try to assist you with that as well. I believe that the AI in FFT scans every single panel in the map and checks every single one of the unit's ability and calculate their decision based on some kind score ranking. FFT also factors in consecutive turns and the AI tries to calculate basic things a few turns ahead. Most abilities in the game are bundled with a large set of AI flags that influences the score (some more significant than others). And then, things start to get really ugly with status effects. AI executes their action with the highest score and then proceeds to make a movement (the movement part of the AI is rather not very smart at all; it's as simple as walking towards allies and or enemies depending on your unit's HP and or status effects). When the unit is on the offense, movement is executed prior to action most of the time.

[The_Absent_King]

I am doing it in Unity3d. By the time we're done itll be able to port to... well, everything that isn't Linux or an XBOX, tbh. Depending on how much $$ we have for licenses.

I was afraid someone would give me the "brute force at N ply" response. That makes me a sad panda.  

[Dokurider]

So how far are you on this project? Do you have a rough estimate on a release date? Can you keep us posted on your team's progress?

[The_Absent_King]

No release date. I am only one working on engine. Its hard, but Ive rededicated myself to it. Large sections of code are present only as pseudo code. But, the pseudo code is there, and slowly being stripped away... A year? Two?

Thematic setting is what I like to call "post apocalyptic steam punk done right". Some time in our future, a nuclear war is fought over energy scarcity. 200 years later, steam power is created from still-functioning-but-failing portable pebble bed reactors. Etc.

Maps will be FFT size and larger. There will be a newgame plus, and a hard mode (vanilla vs 1.3 in terms of difficulty).

*begin thinking aloud*

So for AI, brute force with alpha-beta pruning culling one half of the nodes each iteration still results in a horrendously large search tree, even at low ply. Part/most of this is movement. What do you think, have movement be a bit deterministic? So to run away, a single best node is chosen. Or, to launch an attach on an enemy, a single best node is chosen. Yeah... I think I like that... still leaves a huge tree, but:

I have, in typing this, figured out how to take it to a realistic search space. Ill let you know details once I get pseudo code mapped out.

[Pickle Girl Fanboy]

I have a bunch of notes on a tactical rpg game I'd like to make, if I had the resources.  If you want, I'll post them here, for you to do with what you want.  It's not like it's ever gonna happen, and if I can't make any money off it I may as well give it away for free.

[The_Absent_King]

Sure, post away.

Been busy this week, cant explain AI idea right away. Will likely try to talk method of implementation through here, as I believe quality design depends on understanding the game type's emergent dynamics (and I havent gotten to *play* FFT often in recent years).

[R999]

FFT never pays much attention to movement at all. They hardly ever choose the "best node". There are some random variables involved for sure to make it seemed like it does. If you mean by testing abilities that are within range, that can be calculated linearly if you just add / subtract the range from the ability's range / radius / height etc. As for the Actual Movement of the unit, just move to the closest Ally or Enemy depending on your unit's HP (and the nearby units' HP). Yon don't have to scan the whole map for movement, not even FFT currently does this. Calculating nearby units' distances can be done linearly as well.

Why don't you actually test it out and see how well it runs?  Movement should be pretty straightforward; you might be able to take code from an open sourced engine (anything related to tile movement, or even continuos movement such as a RTS game).

[The_Absent_King]

@R999 : When I said node I meant a single state node in the search space, if youre referencing what I think I remember.

But I still havent learned to do things the easy way (read: simple).

---

Within I am mostly talking aloud. Sorry for it likely not making any sense. Furthermore, Ill talk solely in FFT terms here, despite my game not being THAT big of a rip off.

In general terms, combat is of two parts: Offensive and Defensive. Within both there are complementary types of action (which Ill call metrics).

Debuff / Buff
Kill / Ressurect
Aggregate Damage / Aggregate Healing
Hasten Death / Stall Death

Stall death is simply removing yourself from risk (so CT accumulates, you wait for an opportunity to get a killing blow, not pressuring team to rez you). Hasten Death calls for an exaggerated example:

   Turn order is 1) Allied OOM caster 2) Allied DPS melee 3) Enemy healer. Your melee is capable of dealing 95% dmg to the full health healer. Your caster can melee for 10% dmg. Should you have the caster hit the enemy healer? Generally, yes.

The AI has to be able to score various approaches to determine their usefulness. Above are 8 metrics, each can have different scores for the same action. The Debuff metric would score casting Raise2 on Ramza a 0, for example. But the Rez metric would score the same action as (for example): hitChance * Ramza'sLevel. Discrepancy of scoring between metrics is important, and can be resolved by a simple scalar (coefficient).

Let me explain a heuristic I am considering. (a heuristic is an algorithm that doesn't always work)

   Scenario: It is the AI's turn, ply1. A tree is created, with 16 branches off of the root node. These 16 branches represent the best course of action by each metric's measure at that immediate turn - with and without movement (because of the CT gains of not moving). The search space is now 2^4.

   It is ply2. The AI simulates the character's (actor's) turn by its own methods, regardless of if its AI or player owned. Each one of the 16 branches off of the root node has 16 branches in turn. The search space is now 2^8=256.

   It is plyN. The search space is now 2^(4*N)=16^N. For N = 5, the search space is ~1 million. At the conclusion of the simulation, each possible game state is evaluate for how favorable it is for the AI, and assigned a score. The possible game state with the best score wins. The action by the actor at ply1 which resulted in this state becoming possible is chosen as the best and executed.

Looking at ply5 isn't that great. 1million is a manageable number (I believe), but can be decreased. In example: at ply1 you consider every possible action (space size, 16), but at each subsequent ply you only consider the best HALF of the metrics. This means that at ply2 the space size is (16*8=128). At plyN=5 the space size is 2*2^(3*N)=~64,000. That can be searched in 6% of the time of plyN=5 without this culling method.

If you further assume that all players but the first move, then the search space at plyN=5 is 4*2^(2*N)=4,096. Ply9 can be searched in this manner in the same time as ply5 without any culling.

Some metrics may have 0 scores, and thus needn't be considered (ie, rez, get the kill). This effect at ply1 alone can cut the search space by 1/4.

Further, actors can be procedurally flagged at battle's start to consider only certain metrics. These metrics immediately return score 0 upon call. A unit with no rez skills shouldn't consider the Rez metric, no buffs shouldn't consider the Buff metric, etc. Every unit can always consider Kill and Damage, though.

How to accommodate hit chances? Simply assume that the average damage is done every time? (75% hit with 200 damage = assumed to deal 150 static) Its simple and I think it could work well despite that. (changeToKill * targetsLevel = killMetricScore)

---

Movement. Movement! So frustrating! Okay, think back to boids - cohesion and avoidance. Also, good place to use pre-calculation.

Build 2 meshes, one for each team, that represents proximity (for purposes of cohesion, and avoidance).

Initialize all nodes to 0. For all nodes, if node is occupied by allied, add 32 (do nothing). All 4 adjacent nodes are increased by 16. Their 8 adjacent nodes are increased by 8, then their 12 adjacent nodes gain +4, then +2, then +1, and no effect after that.

Actors will prefer nodes with a friendly proximity score of <16 to avoid standard 1-radius AOEs. Casters will prefer slightly higher score. Actors will have a greater aversion to exceeding an allied proximity score then being under it. Actors will have a variable preferred range of enemy proximity scores. This preference will be low for casters, high for tanks.

I anticipate these proximity meshes will be more important in my game than FFT, as I will feature lower damage dealt, similar HP scores, larger squad sizes, and larger map sizes. (changes from FFT are low %, not grandiose changes)

Of course, actors do not consider their own contribution to the proximity mesh.

**Also, revise what I said earlier. Act while standing, move to act and act then retreat must(?) be treated separately by AI. So thats 24 branches max per ply.**

**Also, having friendly proximity mesh start higher and drop off by 1/4 could allow better cohesion with varying number of actors without accidentally letting them idly stand next to each other**

How to handle projectiles? As follows:

Prerelease (ie, not at run time) each node builds 3 arrays (an array is a type of list). First is list of nodes that can be hit from this node with a linear projectile (ie, gun) are contained in the first list. All nodes on this list are assumed to be able to return fire. Second list is list of nodes that can be hit from this node with a parabolic projectile (longbow). Third list is the list of nodes that can hit this node with a parabolic projectile (as in, incoming arrows, not outgoing).

I may want to expand the above to include nodes that can be threatened with 1..i move (as 0 move is exactly what is already present above) and 0..j jump. This may be overkill but can be achieved with relative ease and within realistic memory requirements.

Enemy units may on their turn attack you while standing still, or move to engage. Forcing an enemy to move to engage instead of retreating after attacking is preferable. This is particularly useful since more of my skills require a projectile to reach their target.

--

Okay so tying it together. How to evaluate a metric coupled with a move type.

Say metric is "Damage". Example actor is a summoner with geomancy, why not. We are evaluating attack then retreat.

The metric of Damage has a list of skills to be considered. A new list equivalent to the intersection of the actor's full skill list and Damage's skill list. For each skill in this new list, each node within range radius is considered. Result PER NODE is:

score = (SUM for each enemy effected)(hitChance * enemyDamageSuffered * damageScalar)
score += (SUM for each enemy potentially killed)(hitChance * enemyLevel * killScalar)
score -= (SUM for each ally effected)(hitChance * allyDamageSuffered * healScalar)
score -= (SUM for each ally potentially killed)(hitChance * allyLevel * rezScalar)

Node with best score is the score for that skill. Skill with the best score is the score for that metric. (remember, at plyN>1 only best half of metrics are pursued further.)

After attacking, node within move radius with lowest proximity error is chosen as destination. Proximity error is calculated by:

allyProxError = targetAllyProx - allyProx
if allyProxError < 0 then allyProxError *= N // generally where N > 1
foeProxError = targetFoeProx - foeProx
if foeProxError < 0 then foeProxError *= M // typically 1, I'd think
proxError = absolute(allyProxError) + absolute(foeProxError)
if newNodeProtectsFromProjectileBasedActor then
proxError = ??? // decreased somehow, to make hiding from projectiles a good thing

--

Unresolved questions - mana conservation? Separate metric for instant vs charge time? Metric system starting to feel like its falling apart with those two questions.

Should I examine more nodes at start? Seems like it'd get stuck in a local maxima and think casting, say, Bahamut every time was awesome, and overlook the usefulness of faster casting summons. Or always go for summons and then fall back to geomancy, though sometimes keeping enough mana to cast a summon is useful.                                      

Thought: should target of charged skills be exposed to enemy team? In example: Foe starts charging an AOE, but I am left to wonder "Did he cast it on the lone critical ally, or my units clumped together"?

Thought: should I allow charged spells to follow their targets? In FFT if I cast meteor on a unit, it doesn't matter how far he runs away. This doesn't make sense in my scenario, but Ill gladly give up that sliver of realism for gameplay if its important. Im on the fence. Doesn't make any less sense then starting to charge a skill then moving out of its range, I guess. Leave it in due to emergent behaviors?

[Pickle Girl Fanboy]

It's a bunch of text documents in a 7zip archive.

I stole some ideas from here, but the most original idea, subclasses, I thought up myself.  I haven't seen it anywhere else, but then again, I haven't played an RPG since they stopped making games for the PS2.

The subclass idea works like this:
1.  Everyone has their own, customizable job wheel.  When the player unlocks a subclass for a specific job, then anyone who has access to that job and meets the criteria for the subclass can change to that subclass.  For example:

Archer
Subclasses: Poacher, Ranger, Expert, Amazon

Now, let's say my female squire just unlocked the Archer class, and she meets the criteria for Amazon.  She can now pick the Amazon class to permanently replace Archer in her job wheel!  Just make sure that the subclasses don't screw up your class requirements.

Think of it this way:  Every class on the job wheel has it's own job wheel.  Wheels within wheels.

[The_Absent_King]

>Amazon - Related to Monk, Witch, Dancer.
  >Female only. [...] Immune to Charm from males, but can be charmed by females.

Cant view the whole thing atm, but I ran across this gem. Made me lulz.

Anyways, at gamedev they suggested MCTS (a technique Id forgotten about / oddly never heard of). Ill probably use that, with a sprinkling of scripting.

[Pickle Girl Fanboy]

I want to play it already!

[The_Absent_King]

Btw, I have posted extensively in a thread on gamedev http://www.gamedev.net/community/forums/topic.asp?topic_id=573999 about AI for my game.

The people over there are (understandably) more clear on the details of how AI works then how AI works in FFT-like games. Id like the other side of the coin's input, though.

Could someone who has first hand experience with FFT, and is able to understand pseudo code, please read that thread and give me feedback? If you need me to translate any of the conversation, just ask.

EDIT : Oh yeah, you know how sometimes characters are able to jump over a 1 tile divide, like a river, without actually plunging in? Is there a minimum move/jump score necessary for this to happen? SHOULD there be?

[Pickle Girl Fanboy]

You can Jump over divides as wide as your Jump/2, I think.  Look at Aerostar's Battle Mechanics Guide on Gamefaqs for more info.

[Archael]

If there's one thing I could teach FFT's AI is that YOU DONT HAVE TO MOVE EVERY TURN!! AND WAITING IS OK MOST OF THE TIME!

oh and also LOOK AT THE DAMN REACTION ABILITY OF WHAT YOU'RE ATTACKING YOU IDIOT


thanks

[Oberon]

I love how the AI tends to walk into the same traps over and over again. lol

[The_Absent_King]

The AI model I have outlined doesnt hold a memory of past events, but it can 'make guesses' about the future. It will wait, not move, and (as a side effect of other processes) consider the reaction ability of who it targets.

This is because it uses a probabilistic sampling of the outcome of all possible moves. This means that if a move is a bad idea (Mage physically attacking a Hamedo Monk) then itll tend to avoid it, because that will result in a game state you are more likely to loose. The AI should be able to choose placement tactically, conserve mana, and allow sacrifices where appropriate, etc.

Not implemented yet, but it should be able to easily do all those things.

Really cool, imho, since I never had to tell it to DO any of those things - it just figures out if its a good idea to do something or not.

[Pickle Girl Fanboy]

Will it try to lure a character off from your group with ranged attacks so they can go 5 to 1 on your guy?  Will it attack in groups?  Will it split its forces in two or more groups in an attempt to break up your group or so it can surround you?  Will it concentrate it's attacks on specific, high-value targets (Units most likely to cause the most damage, healers, long range attackers)?  Will it disperse when you use a high area of effect attack?  Will it wait until all it's units can go all at once, so it can destroy as many of your characters in one go and make you waste time healing them?

[The_Absent_King]

Yes to all, but it will be able to do the following particularly well:

Dodge AOEs
Synchronize turns
Prioritizing targets

Ranged attackers will tend to snipe the same target whenever possible... but only when its effective.

It just runs simulations. Thousands of whole games played out every time the AI has a turn. It uses those to decide which decision, here and now, gives the best chance of winning. (ie, it doesnt pull punches)

In fact, due to the AI I will likely have to make the enemy less overpowered then it is in FFT1.3, lest it simply massacre the best of players. Of course, it isnt implemented yet, so I speak too soon... but I do anticipate having to bring the enemy team's strength more in line with the player's.

Ill let these forums be part of my alpha testers, since there are a bounty of players of better skill here then I am.

[Archael]

one of the reasons enemies in 1.3 are like they are is because of the AI

if you can make an AI like that you can definitely tone down enemies

or better yet, make an AI that equips items and learns abilities

based on what the player brings in