Battle AI for RPG (final fantasy-like)

Ey-Lord · 2015-06-14T15:04:55

Hello everyone, I'm currently working on a web rpg and I'm at the point where desining an AI make sense. I've read lots of articles / papers but still can't really figure the best approch for my case. I'll take every hint and advice you have First, a description of my game (i've simplified a few non-important things). It is coded in html / JS (jquery) ; for now its not aimed at mobile but only desktop browser. At its core, it's a strategic idle rpg. The player's main role is to create a team of 4 characters, choose their skills (they can have 6 in total at the same time), choose/customise/improve their item with a huge number of magic properties, choose what talent they will be using and chose an AI for his party. The player has access to a "gambit" system, similar to the one in FF12 but a bit more complex, giving the player more options to really define a small rule-based AI for each of his character. He can describe fairly complex rules such as telling a character to off-heal if the main healer of its team is silenced or low on mana for example. Once the player as carefully chosen its skills/talent/items/AI he can go into battle. He simply clicks on a battle zone and then its team will fight without any interaction from him untill he decides to stop. Since it is an idle game, he can farm for a few hours or even days if the game page stays open. His team will chain battles, recover hp/mp bewteen them, gain some xp / gold (that the player can use to improve his items). And when hes strong enought he can move to the next zone. The game is not meant to have a level cap The battle in itself is a 4 vs 4 turn-based final-fantasy (6,7,8...) style. Their is no movement involved, only what skill to use at each turn (lets assume monsters got between 3-6 skills). Their is a Action Point (AP) system in place. The unit with the most AP at any given time can play its turn. If no unit has > 100 AP, a new "turn" happens in battle. A Battle turn basically add a bit of AP to everyone and update the buff/debuff system (for example with buff that deal damage every turn). For now, the AI of my monsters is non-existant : cast a random skill I got at a random target. I want the monster's AI to challenge the player, force him to both: - farm more to aquier better item and become stronger - make him rethink his whole battle strategy from time to time (he can reset his talent points for a fee, swap item/skills freely and changes his Gambits at any times) I want to AI to: - works with any kind of skills I give her withtout having to tweak things for each monster individually) - versus any kind of oponent stratgegy (more or less efficiently off-course) The hard thing is I got many constraints: - the game is fairly complex: each unit has around 100 different kind of stats, at least a demi-dozen buff/debuff on it at any given time, ect... The BattleSystem that compute damage / hit / spell cost ect... works pretty well but it needs acess to lots of datas and do lots of computations to compute the outcome of a particular attack/skill. - let's face it, my game engine works really fine on its own but is nearly not as effecient (speed-Wise mostl) as it would need to be to brute-force an AI solution - I'd like the whole AI process to decide a turn for a monster to be around a second or less. - I cannot really multithread given the amount of data I need to handle and more importantly the way my game engine works. So I need to squeeze AI into my main Update() loop of the game. - With my game engine, the only way I can compute things (damage, mana cost ect...) is to make the computation on the "live" player group. So I need be make a backup of it and realod it everytime we enter/exit an AI computation phase. - I dont have lots of room to save variables for the AI bewteen games, that will make difficult to use NNs, genetic algorithm and such. The only solution I found is an utility-based one (player&monster have acess to every stats of every one): - create a score for every unit in the game (monsters & players, from the perspective of the AI). This final score will be the weigthed sum of different sub-scoring variable - simulate each move available and simply use the one that maximise the monsters scoring and/or minimize the player's scoring after the move is done - for that I can give a direct threat score to every unit of the player taht represent an offensive threat (a dps, a debuffer, a CC-er) and give a indrect threat score to defensive units ( tank, buffer, healer) - I can also add some "weakness" scoring, that will take into consideration hp / mp / armor and such. It will help focus the weaker units and the one closer to death for example. - I think it would be "easy" to add some simple behvior modification to the process by simply changing the weigth of each score or its computation internally. For example, I could give a few tags to monsters like "berserk" (AI will then try to lower the weakness score of its oponent more) or "carefull" (AI will value its own weakness scoring system more and will prioritize recovery over damage). I can also give a "importance" factor manually to every monster so AI will try to keep them alive before. But all in all, it stays really simple and I dont see "smarter" behavior emerging from that :/ Ideally, I would use a minimax tree, alpha beta and such to simulate a few moves before choosing the best one but in pratice I'm not sure it will be usefull for my case: Here is why: - In chess, a battle state is really simple and can be store in memory very efficiently. For my game, storing all the informations of a battle at a given time to be able to simulate every action in a tree leads to huge memory consumption even at very low depth. - The solution I came up with is to only store the minimum information I need to re-create that battle state. It reduce drasticly my memory issue but brings up the issue that I've got a fair amount of computation to do each time i load/save a battle state. In other word, each time I simulate a new move, I need to save the current battleState and if I want to generate a sibling, i need to reload the parent's node Battle State. - Adding to that, when trying to generate a child node from a selected move, the computation process of damages / buff effects ect is also taxing in speed. - I've got lots a randomness (percentage of critical strike, lots of procs...) that can somewhat be approximate (discarded or taking to average or w/e) when computing a new battle state but it will definitly lead to some mistakes by the AI [its a small issue compared to the other] - in Chess an average game is like 40-50 tunrs ; in my game it will likely be way more than that and if their is a healer or if the player has chosen a very defensive team composition, it can go in the thousands turns. So, seeing 5-10 turns ahead may not offer much for my AI - Branching factor will heavily dépends on how much time I use to validate moves but with 6 monsters skills and 4 targets, it's safe to assume at least 10-15 child. The good thing is that for player the branching factor will be very limited, often 1 an at worst 4 (because I know the player's AI, I can be sure of what skill he will player given a certain situation....yeah that's cheating ;o)) What I've tried so far: - I've created a call for a special AI class that will work its magic for a maximum of 50 ms and then exit its loop so the render process and resume. I cannot really go higher than that or the rendering will be very slow (50 ms is already, at max : 20 fps) but since i've got only damage/heal numbers of animation it's not a big deal. I cannot really go lower than 50 seconds (or not by much at least) because the lower I go, the more process time will be taken by the render() function of my game and thus, the lower time will be available to the ai. - I've tried to simply save a state and load it as many times as I can during my 50 ms loop to get an idea of my performances. After a few optimisation it is very disapointing I can roughly do that around 1000 times per seconds. If we add the time needed to compute a battle state after choosing a move and the time to call the evaluation function when needed.... i'll be at best at 200-300 node in my tree. I was thinking of computing each depth level before the next ( with cut-off if needed) but maybe a dive at a certain deep first for the potential best move could be usefull. All in all, this tree approch is very time-consuming and I'm not sure if it will bring me enought data to really make a smarter decison than what I can do at depth lvl 1. I've read about FSM and the like but it doesnt seem a good fit for my game. I've also seen the STRIP algorithm but again, it seems more usefull when ou got mouvement involved. Sorry for the long post, if you got any comments / idea, it will be greatly appreciated ! Regards

Artificial Intelligence Programming

Started by Ey-Lord June 10, 2015 09:33 AM

10 comments, last by IADaveMark 9 years, 5 months ago

alvaro

21,607

June 13, 2015 10:42 AM

as a reminded, I do not store my data, I send him on-the-go each time.

I've already mentioned that this doesn't work. You need to store the data and then use random samples from your history for training. If you train for things as they happen, you'll forget what you've already learned.

IADaveMark

3,839

June 14, 2015 03:04 PM

http://www.reddit.com/r/gamedev/comments/394fu0/gdc_ai_summit_video_building_a_better_centaur_ai/

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

Battle AI for RPG (final fantasy-like)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Battle AI for RPG (final fantasy-like)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines