Hi everyone! First of all, I apologize in advance for possible grammatical mistakes in the text.

My friend and I are planning to create a small game with gameplay similar to the first XCOM games. The gameplay of the games looks like this:

• The playing field is a squared tile grid, every tile of which can contain lanscape part, obstacle or unit.
• Player and AI both has a couple of units.
• The game is played in turn - first all of the player's units act, and then all the AI ​​units.
• Each unit is given a limited resource per turn - time units.
• Each action takes a certain amount of time units.

In XCOM remakes, this system was simplified to "each unit has two actions per turn", however we do not like this approach, and we want to do it as it was in the original games

Now we are at the stage of analyzing the feasibility of the project, and I had a question related to the implementation of the AI architecture.

We set ourselves the following requirements for the AI:

• It must choose behavior depending on the goal and current situation in the game
• The decision making process should be as little "hand-authored" as possible
• It must create a "meaningful" plan to achieve the goal, and not choose one "best" action at a time in the hope that someday the goal will be achieved
• The turn of each unit must end gracefully, and must not be interrupted in the middle of action - the time units limit must be implemented.

As an example of the AI unit plan:

run up to a position where you can shoot at a predetermined target, and run back into cover. If there are no firing points (there are not enough time units to reach the place) - take a position from which it can be done later.

I've read quite a lot of articles on the topic of how AI is usually implemented in games. Several of the most commonly used architecture options are:

• FSM (Finite State Machines) and HFSM (Hierarchical State Machines)
• BT (Behavior Tree)
• Utility-based system
• GOAP (Goal-oriented Action Planning)
• HTN (Hierarchical Task Network)

I do not consider FSM, HFSM and BT, because judging by what I know, they are not capable of planning ahead.

Utility-based system, in theory, can be hierarchical, but I see issue in the movement of the unit:

I don't understand, what is considered an action in the Utility-based system, concrete full path to the destination, or just action "Move" without clarifications?

As there can be many different paths, consider each of them as a root for hierarchical plan is pure madness - it can lead only to combinatorial explosion.

But if instead, we only think of this as "Move" action without parametrization - how can we achieve time units condition satisfaction? Especially, if there is 2, 3, 5 actions in the plan?

Moreover, an even more interesting question arises - why "Move"? Same position has different utility values, if unit has different goals - for example, attack enemy or take cover.

It turns out that the calculation of the utility of the current action should depend on the the next, or even on the entire plan.

GOAP and HTN architectures seems better for this situation - as they are planners in their nature. But in fact, even hardcoded knowledge "how to solve specific problem" or "rich AI knowledge about how to do things" doesn't help a lot. I still don't understand where do I need to put time units considerations.

For example, if "method" in HTN is action "Move" without parametrization, or concrete path to destitation?

I guess this is some sort of planning or optimization problem, but I don't quite understand how it can be solved, because i don't understand where to put that time unit heuristic part, so that it will not blow up.

I think that I misunderstand some aspects of this architectures, or miss some crucial parts in it.

Current “AI” in games just isn't at that level yet. Limitations in processors and run times don't allow for anything close to the sort of “thinking” and tactical skill you want to recreate in an AI agent.

If you look at even the best AI games, they are pretty dumb.

Programmers use special tricks to create the illusion of AI - but no game can come close to matching a human at an XCOM clone game for the moment.

But that doesn't mean you can't design your game around the limitations of hardware/software to create a fun and compelling gameplay.

Tricks used include:

Modelling and hard coding the map to make the AI easy (think choke points, cover points and great firing positions) so the AI can hard code intelligent behaviour on the special map.

Hordes of dumb enemies that you need skill and IQ to beat - waves of “zombies” or “bots” that have simple AI rules that match their back story. Enough dumb zombies shambling forward into line of sight is realistic and challenging for the player.

Cheating - using special knowledge of the game state to allow “smart” decisions to be made by the AI

Scripted Events - Units pop up like magic in the most awkward places at the best times to create issues for players

BlackDice said:
I don't understand, what is considered an action in the Utility-based system, concrete full path to the destination, or just action

My behaviors in my utility stuff is simply “move to XY” and let the pathfinding take over. (That's what most architectures do anyway.)

BlackDice said:
It turns out that the calculation of the utility of the current action should depend on the the next, or even on the entire plan.

Imagine creating two behaviors, A and B, that have largely the same considerations in them – i.e. “accomplish G”. However B depends on something that A will provide. Also, A will disqualify itself once that thing has been reached. If the time is right for G, B cannot fire because A didn't provide whatever but A will fire just fine. Once A is done (and disqualifies itself because it is no longer relevant) then (assuming G is still your goal), B will fire.

I have actually had 3 or 4 multi-step long-term plans running simultaneously as the agent is stepping through these similarly constructed, related behaviors.

Thank you for advises!

I've researched a topic a bit deeper, and now I understand, that there is no “pure algorithm”, that solves my problem. While i'm not totally agree with opinion that it must be “all smokes and mirrors”, i assume that this task is more trial-and-error and domain-specific than i though before.

I want to try this approach:

1. I've decided to get main concepts from HTN (primitive, composite and goal tasks, task decomposition, method, world state etc.).
   1. I think it would be totally ordered, and least-commitment
2. For least-commitment and deferred variable binding resolve (like “where to go”) i will introduce some form of backtracking mechanism (backtracking search or smth like that).
3. Method decomposition and variable bindings will be weighted by priorities (some rough approximate utility function, influence maps etc).
4. Method decomposition, and variable binding will be equipped with some domain knowledge and constraints, to cut off large part of decision tree, I'm planning to start from constraints, which will not remove expressiveness from decisions, and gradually adding bigger constraints until performance will not be satisfied (I think hardest part of that will be to balance backtracking)

What do you think about that approach?