Final Fantasy Hacktics

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?

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.

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.  

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?

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.

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.

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).

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).

@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?

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.

Quote>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.

I want to play it already!

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?

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.

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

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

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.

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?

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.

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

No, thats cheating. Making an AI that cheats results in the game not being fun. Id rather there be a strategy for each level then have the player figure out how to beat the AI at that one particular game (what do I bring in to win, against what it will bring in to counter me) and use the strategy every time.

Its possible I could make it so that certain core abilities are always present somewhere on the team (like rez).

---

One thing Id like to discuss is Speed. Atm, I plan for speed to be static - dependent upon class and equips but NOT upon level or what class you leveled up in.

The effects of progressively higher speed isn't directly felt in FFT - only in that your longer casting skills start taking even 'longer' to cast. This is counter productive in my mind. I would have to either plan obsolescence, increase the skills speed in level, or something similar.

Can you think of any draw backs to this? Itd give me more control, but slightly decrease the options the player has for building characters.

How is it cheating? The AI is usually stuck with static builds and r/s/m combos... having it choose it's own items and r/s/m seems like a logical process to me. It doesn't HAVE to be based on what the player brings, but it can be based on a set of pre-defined (read: not optimal) combos which work together, odd or common. It's still AI, and it will always be at a disadvantage vs the player.

This wouldn't mean that strategy is removed for every level... They would still be stuck in pre-set jobs and pre-set positions.

An AI that knows more about the game state then a human does/can is said to 'cheat'. It is generally agreed upon that cheating AIs are bad. An AI that knows what you are bringing to a fight, and adapts its build accordingly, is 'cheating'.

I was already planning on having pseudo random builds. Never having considered random battles in depth I never realized that many (all?) of the builds of foes in an encounter are static.

Also, you might want to rethink this: "AI will always have a disadvantage to a human". With the right approach, enough RAM/CPU time, an AI will kick a human's ass every time, on any zero sum game. The problem, of course, is if the platform is powerful enough for the AI to play perfectly, without exceeding the time limit.

Quote from: "Voldemort"It doesn't HAVE to be based on what the player brings,

Yes; I was replying to a question you asked before you clarified.

I then further clarified by stating that I was always planning on pseudo random load outs for the enemy team.

I think I have a name for the Witches Curse/Blessing Skillset:
vergeltung
revenge, pay someone back, compensate them, reward them, even to bless them
German, I think.

It's gonna be nice to have an enemy that creates favorable conditions for itself and knows how to work together.  How about abilities like equip change?  Will the AI know what to equip?  And could you do something to increase the odds of enemies equipping x ability and y equipment if they already learned z ability?

If a human player already has MP Switch learned, then he is more likely to learn other abilities which work in tandem with MP Switch, like Move-MP Up.  Shouldn't the enemy mimic this behavior?  And I only said increase the chances of this happening, it shouldn't be 100%, or even 75% of the time.

Witch's Curse/Blessing skillset? What are you talking about there? Regardless, Vergeltung is cool and all but why obfuscate the word Retaliation?

Equip Change presents a problem. Not insurmountable, but the effort required to solve it exceeds the need to, at this time. Thus, for the foreseeable future, Equip Change will be unavailable to the AI.

Choosing skills will occur before choosing gear, when generating the enemy load-out. Some combinations of items might not be chosen together well, but I think I can definitely swing making item choice dependent upon skills. Implementing this before the AI will actually give me a framework to ease the transition (it is very similar to how I plan to make the stochastic vector - that is, the playout strategy).

As for how to choose the skills... what if I create skill groups? Having skills within the group gave you a chance of having other skills in the same group, for free, decided after the rest of the process. Since having X may strongly imply Y, but Y may weakly imply X, this can best be stored as a 2 dimensional array.

I think the order Im going to make the classes in is gender (irrelevant to stat growth, I have a trinity of stats instead of FFT's duality of  Brave/Physical and Faith/Magical ), then primary class, then secondary class, equipped RSM, then random active skills from both skill sets, then skills from skill groups, then items.

Only problem with above approach is how to resolve conflict from RSM gains from skill groups and the equipped RSM's themselves. Especially if multiple skills are chosen from the skill groups.

That, and it makes no allotment that, as an example, "Fire 3 shall not be used by characters under level 5".

What about a passive skill that lets you change your reaction or movement skills? I think that could be damn powerful. AI will need to be tweaked to use it, but doable come Beta. Thoughts?

Also, what do you guys think about speed being level/growth independent? Im really torn on if this is a good idea or not.

Speed was level dependent in the sequel games, FFTA and FFTA2. So obviously, squads with mismatched levels would have huge speed differences and high level units might move several times before lower level units got to have a chance. Whether this matters or not depends on the goals of your game, I think. In single player it is not a big deal, it only amounts to extra challenge if the player moves through the campaign without leveling (I do this, often I just want to see the story missions without grinding levels for my units). If your game is going to have any sort of multiplayer, or if enemy unit levels do not grow with the average level of the player's party, then you could get some balance problems.

(In FFTA, enemy levels did not increase with your party's average level as they do in FFT, you would occasionally come across a low level mission that you had skipped earlier on. When it's the player's squad that has 30+ more levels than the AI's, the mission is a boring cakewalk!)

The way I see it, most of the time we want our units of the same level to have relatively the same power, with some minor variance based on selected job, equipment, etc. So why bother implementing a speed increase system if we want most units of the same level to have the same speed? We can just *give* bosses and tougher units a higher speed than average. It just seems like extra work for little payoff. (You could make the same argument for most of the statistics in FFT though... how about a game with no levels, where learning abilities, unlocking jobs and finding equipment are the only means of progression?)

On generating random encounters, yeah, every band of enemies you face in FFT (and the sequels, I'm pretty sure) was preset. You could come up with a system for generating random units with r/s/m abilities and gear that make sense together... but at that point, it might be easier to design a few hundred preset units, and choose from that pool for each random battle. It might also be interesting to generate some units completely at random, with no effort to make sure the abilities blend well together. There will be plenty of misses, but I bet that such a system would turn out unexpectedly tough and interesting combinations too. An easy way to maximize the utility of a completely random unit: randomize which two A-ability lists it gets to have, give it every skill in each category, and let your AI figure out which of those abilities to use together.

The game you're developing sounds great! FFT is in dire need of a good spiritual successor; I've been playing with the same idea. I have written some very preliminary code in my spare time (for a different engine than Unity3D), but mostly I've been thinking about the mechanics of the game and what purpose they serve exactly. The linked thread on AI for an FFT-like game is illuminating. I could talk about game design and balance all day. Good luck!

If you don't want to do away with leveling altogether, then you could make something similar to FF2 or the SaGa games, where you gain stats according to what actions you choose in battle.  SaGa games usually come with something called Battle Rank, which is a score based on how many battles you fought and how difficult those battles were.  The higher your BR, the higher your enemies stats/smarter the enemy AI.

Romancing Saga divides speed into Dexterity, which is part of the hit rate for weapon attacks and partly determines how fast you act, and Agility, which is part of evasion and affects the trigger rate of some counters and interruptions.

SaGa Frontier 2 uses your skill level for each weapon type (hand to hand, Sword,...) to determine who acts first, as well as for counters and interruptions.

I'm not familiar with SaGa Frontier 1.

One other thing... In your tactics engine/game, please include options to turn off the in-battle messages (like the navigation message, jp/exp gained,...), speed up battle effects, and fast forward through dialog.

FYI -> difference between counters and interruptions.
Hamedo is an interruption and a counter.
Counter Dash is a counter.
Blade Grasp is an interruption.