W.U. 10.1: Behaviour Tree Decorators

I’ve properly changed the HasSufficientStamina hack into decorators instead:

The “enough stamina to” decorator essentially turns the action it decorates into a condition, stifling it from actually doing the action and just querying the amount of stamina it costs to do. It then accumulates that stamina cost (among siblings in the sequence) in another variable and check if the unit has enough stamina to match the accumulated cost. If not, it returns failure.

I wanted the decorator shapes to look nice when stacked on top of each other, so this is how I designed them to look like:

Here, a bunch of (test dummy) decorators are in the Retreat sequence, and a few more are in the health check condition.

Advertisements

Modding Options

So for modding support, I’m running the options through my head.

1. Mono dynamic code generation
? Mono/.NET allows to compile code from within code, via the Code DOM compiler
? so the idea is to let modders create C# code and the game will compile those
? compilation results in either a compiled DLL file which will be loaded, or stored in memory. if you don’t save it as a DLL, you’d need to recompile the user’s C# file every time the game is run (not really a problem)
+ possible to let end-users create C# code, code that will run just as fast as the C# code in the game
– potentially allows end-users to cheat the single-player game by editing values or forcing commands on the game, similar to Game Genie
– potentially encourages end-users to share DLL files to each other, an avenue for a security breach on a user’s PC
– won’t work on web or mobile versions as they are sandboxed environments that do not allow compiling during runtime

2. KopiLuaInterface
? a Lua interpreter written purely in C#
? modders will make Lua scripts
+ a completely sandboxed environment, users will not be able to write malicious code
+ will work on web versions
+ will also work on mobile versions

– running a Lua script is slower than running a C# script. even slower since KopiLua is slower than the standard Lua1

3. LuaJIT + LuaInterface
? Unity (via Mono) can load a DLL of compiled C/C++ code (native code)
? modders will make Lua scripts
+ a completely sandboxed environment, users will not be able to write malicious code
+ runs faster than KopiLuaInterface, even faster than standard Lua with Just-In-Time compiling
+ can work on mobile versions with a little extra work
– will not work in web builds as they are sandboxed environments that do not allow loading of native DLLs
– works only on Unity Pro
– running a Lua script is slower than running a C# script1

LuaJIT is a no-go only because I have no Unity Pro.

Mono is the fastest for this situation, but it also has more potential to create malicious code. I’m only targeting Windows standalone so a web or mobile version is irrelevant for the moment. But if I ever decide later on to move some stuff into web/mobile, then mods made in C# won’t work, and that’s a loss.

So I’m going to use KopiLuaInterface for mod scripts.

When I get Pro, it’ll finally be possible for me to load native DLLs. It will likely be possible to convert what I have to use LuaJIT instead, at least, when making the standalone/mobile version of the game. If ever a web build is released, it would just fallback to using KopiLua. The nice thing is end-users’ Lua scripts will work regardless if the game is using LuaJIT or KopiLua.


1: The speed difference between Lua and C# should largely be trivial depending on what the Lua scripts do and what it is used for. Scripts shouldn’t be executed in tight loops, but for handling events, they’ll be fine.

W.U. 10: Basic Attack AI

Here I have the enemy A.I. spamming the Lunge attack. UPDATE (2012Aug18 1540 PHT): It turns out my enemy A.I. was erroneously allowing the enemies to Lunge even when they didn’t have enough stamina points to do so. This has been fixed.

One thing to note was that it was starting to become a pixel hunting process for me to get the proper place to move to for an attack, as I suspected. This was why I wanted to make an attack preview where you see a ‘ghost’ of your unit doing the attack before you confirm the command. The ghost’s attack would highlight which units will get hit from the attack.

I also need a better stamina cost display.

Now, about the A.I., here’s the behaviour tree used for the enemies in the video:

It goes basically like this:

  1. Retreat if I need to
  2. Find nearest enemy
  3. Check if I still have enough stamina to get near him and attack
  4. Do the actual attack if I can
  5. Just close in if I can’t move and attack in the same turn

(I really wouldn’t need to add that additional check in the third step because of the way behaviour trees work. But it’s there because I plan on adding more to the tree.)

One thing I did not anticipate the A.I. to do, was that after they attack, they spend time backtracking to the proper range to do the lunge attack, so they’d be in the right position come their next turn. I was surprised that the A.I. was that clever, and yet, all it did was follow the instructions I gave it. And there it was in step no. 5 (i.e. close in if I can’t attack yet). Its just that I didn’t realize it would also do that immediately after an attack.

Editor

As for the behaviour tree editor, I was thinking of making the display look more like a folder layout, given the cramped space it needs to be shown on.

Here’s how that kinda looks like:

And here’s how my initial trial on the code for that looks like:

The purple, stretched hexagons are selectors, while the large rounded boxes are sequences. Sequences are allowed to have different colors for easier recognition.

Selectors arrange their children vertically, and sequences arrange theirs horizontally.

The white hexagons are conditions, while the white boxes are actions.

Watching Traversals

With my goals for modding support, I want to be able to show a behaviour tree in-game, so I made sure to use plain GUI code and not EditorGUI. With that I can show tree traversals as they happen. This is meant for debugging.

Stamina Cost Check Hack

The “CanLungeNow?” is a special (i.e. hack) type of sequence that I was forced to make. It basically accumulates the stamina cost of its children actions and returns failure if the A.I. agent (the unit) does not have enough stamina to do all those actions. I’m in the process of redoing it with decorators instead.

Static Tree

I designed my trees so that multiple agents can traverse one tree simultaneously. This means I can have only one tree that powers the A.I. of multiple units. While my game is turn-based and wouldn’t need such a feature, I may, however, add squadron units who will move and act together (goblin horde units).

This means nodes in the tree do not keep information themselves. Whenever they want to store information, they store it in the A.I. agent. If a node returns `Running`, it stores that state in the agent, not in the tree. Its stored in a hashtable, so they can put anything they want.

If a leaf node doesn’t have parameters, it might as well be a static class! If it does have parameters, those are most likely never changed during runtime. There could be a rare case for a need of an action that edits the tree it is in (self-learning A.I.?).

Flattening A Tree

Using Mono’s dynamic compilation features (allowing code to compile code), I can convert a behaviour tree from what it is right now, a bunch of classes arranged in a tree, to just one class with selectors and sequences converted to a bunch of nested if-else-if chains.

Most likely the leaf nodes (actions and conditions) need to stay as classes, but at least tree traversal will surely be faster, because there is no tree to traverse anymore; traversal is hardcoded for the most part. This is most likely what AngryAnt’s Behave library does as well.

W.U. 8: Behaviour Trees

That screenshot right there means the fundamentals of my behaviour tree library is working.

As a side effect of me using unit tests, I made the code output a debug text of the whole tree when traversing.

This is all only the framework though. The next things to do are add more meaningful actions and conditions (like Retreat, Charge, Snipe, AmISurrounded, AmIDying, et al), and then make a visual editor for this.

Again, I’m storing the data in JSON format. Here’s an example:

{
    "__type": "BehaviourTree.Root, Assembly-CSharp",
    "Label": "Root",
    "Remarks": null,
    "InheritsFrom": null,
    "Children": [
        {
            "__type": "BehaviourTree.Selector, Assembly-CSharp",
            "Label": "Sel1",
            "Remarks": null,
            "Children": [
                {
                    "__type": "BehaviourTree.Sequence, Assembly-CSharp",
                    "Label": "Seq1",
                    "Remarks": null,
                    "Children": [
                        {
                            "__type": "TrueCondition, Assembly-CSharp",
                            "Label": "Scond1",
                            "Remarks": null,
                            "Children": null
                        },
                        {
                            "__type": "TrueAction, Assembly-CSharp",
                            "Label": "Sact1",
                            "Remarks": null,
                            "Children": null
                        }
                    ]
                },
                {
                    "__type": "BehaviourTree.Sequence, Assembly-CSharp",
                    "Label": "Seq2",
                    "Remarks": null,
                    "Children": [
                        {
                            "__type": "TrueCondition, Assembly-CSharp",
                            "Label": "Scond2",
                            "Remarks": null,
                            "Children": null
                        },
                        {
                            "__type": "TrueCondition, Assembly-CSharp",
                            "Label": "Scond3",
                            "Remarks": null,
                            "Children": null
                        },
                        {
                            "__type": "TrueAction, Assembly-CSharp",
                            "Label": "Sact2",
                            "Remarks": null,
                            "Children": null
                        }
                    ]
                }
            ]
        }
    ]
}

Notes on the A.I.

Here’s some notes I was taking down while watching the behaviour tree video by Alex J. Champandard (part 1, part 2, and part 3).

Goals for the A.I.

  1. “Intelligent” enough to know how to preserve itself
  2. Compentent enough to finish goals assigned to it
    1. Adaptable to situations
      1. If it suddenly can’t do what is assigned to it, it should do some fallback action, perhaps wait until such time that it can do it again.
      2. If it can do multiple ways of achieving a goal assigned to it, it should look for the best way it can do it (HTN Planner)
    2. Fuzzy goals: give percentage as to how much attention it should give to each goal assigned to it (priority)
  3. Coordinate with allies to do joint operations (semaphores?)

Goals for the A.I. System

  1. Easy to use/understand (don’t we all want this)
  2. No need to bug the programmer every time: Once the system has been coded, let designers design behaviour without more coding (as much as possible). (How? By making the system composed of basic building blocks that can express up to the most complex ideas, like Lego, so the designer can use them in creative ways without asking the programmer to hard-code something all the time.)
  3. Easy to reuse:
    1. Reuse behaviour: Reference a (reusable) sub-behaviour within a behaviour.
    2. Use concept of cascading style sheets/inheritance: Reuse generic behaviours and just override for specific functionality. Can even use strategy pattern on lieu of this (override behaviours during runtime).
    3. Encourage creating small, modular, connectable behaviours.

A.I. Influence Maps

In order to help me more on the A.I., I’m trying to implement the technique of influence maps.

From aiGameDev:

Influence maps have been around since the very early days of game AI, tracing their history back to real-time strategy games over a decade ago. Since then, influence maps have become a cornerstone technique for game developers, and are even starting to become prevalent in first-person shooters as well (e.g. KILLZONE 2/3).

 

I’ve released my work on an MIT license. The git repository is here: https://bitbucket.org/AnomalousUnderdog/influencemapsunity3d

I’ll be working more on it as I go. Any expert help to guide me is appreciated.

More references:
http://gameschoolgems.blogspot.com/2009/12/influence-maps-i.html
http://gameschoolgems.blogspot.com/2010/03/influence-maps-ii-practical.html

A.I. Systems

My first try at an A.I. system was when I was making Death Zone Zero. I was inspired by the A.I. system in Dragon Age: Origins.

If you’re a programmer, one look at these screenshots should explain how the whole thing is set up.

To be clear about it, it works like one long if-then-else-if chain, but the important distinction is that you can add, remove, and change those if’s during runtime.

So its basically a list of conditions, with an action to do for each, when the corresponding condition is met.

You can also describe it as a priority list. It checks from the top first. If it found something to do at the top, the program won’t bother looking at the bottom conditions. Of course the program continually evaluates this long if-then-else-if chain (always starting from the top), so there is a chance the bottom entries can be triggered. It depends exactly on how lenient the conditions are.

Here is an example:

  1. Am I dying? Then I should escape from the enemy.
  2. (Assuming I’m not dying,) Is an enemy in attack range? Then I should retaliate.
  3. (Assuming I’m not dying and not being attacked,) Did I detect an enemy? Then I should pursue him.
  4. (Assuming I’m not dying, not attacked, & not seen an enemy) Then I have nothing to do, I’ll just wander/patrol the area.

That is basically the most common A.I. you’ll ever find in videogames. I’ll reword everything to make that clear:

  1. Am I losing? Then assume a defensive position.
  2. (Assuming I’m not losing,) Is an immediate threat found? Then do something about it.
  3. (Assuming I’m not losing and no immediate threats,) Am I seeing a potential threat on the horizon? Then take it into account.
  4. (Assuming I’m not losing, and no immediate or potential threats) Then improve myself and keep on guard.

You’ll notice each condition expects that the ones before it failed. This is essential in making it a priority list.

You’ll also notice the entries are ordered from most important to least. This is also needed to make sure the A.I. works as intended.

Building upon this, I had added the ability to add more than one condition for an action. The conditions would then be attached together in essentially AND operators. If one condition fails, the program won’t bother with the other conditions and move on to the next entry in the list.

Improvements

What I had problems with back then, was how to make enemy A.I. do coordinated attacks (flanking, one distracts while the other attacks from the target’s blind spot), and to make an A.I. switch between different priority lists.

Swapping Priority Lists

Say the enemy can act stealthily if he wanted to. His abilities for stealth essentially mirror what he does while not in stealth: escape, attack, pursue, and patrol, but again, all as a stealthy variation. What I had been thinking then, is to add an action to make an A.I. switch to a different priority list if the situation calls for it.

Moving On

Then a lot of things happened and Death Zone Zero is currently on hold. Now that I am tackling A.I. systems again, I’m taking a pause and wondering how to do things again. I’ve heard about behaviour trees and how it’s very well suited for videogame A.I.

I ended up reading this #AltDevBlogADay article on behaviour trees, and chanced upon one of his references: the A.I. system in the PSN game, Swords and Soldiers (part 1, and part 2).

The more I read it, the more I realized, “This isn’t a behaviour tree, this is more like the priority list system I made up long ago”.

The A.I. system in Swords and Soldiers is very similar to the priority list system I made up long ago.

The nice thing about behaviour trees is you can create one that works exactly like a priority list.

The truth though, is that they can have a more sophisticated structure that potentially make them work a lot more “intelligently”. If the priority list is like an if-then-else chain, then the behaviour tree can add more, like a switch statement, nested if’s, and even loops. Behaviour trees are like a visual programming language but made for a more specific purpose (i.e. videogame artificial intelligence). Part of their charm is to make the design of A.I. a lot more accessible to non-programmers, the same way my priority list does.

The only problem is its a lot harder to understand. For that, I recommend the article I mentioned above.

There’s also this hour-long video about behaviour trees in aiGameDev.com. An account is required, but subscription is free. You could, however, watch that same video for free, without registration, in this three-part series: part 1, part 2, and part 3.

W.U. 6: Melee Damaging

Check the video. The attacks now damage units. You’ll see the dummy red box has its health reduced when taking hits.

Its not quite visible in the video but I’ve also added swoosh trails on the weapon when attacking. Continue reading

W.U. 4: Melee Attack Crunch Time

With 6 hours 4 hours to go before the meeting, I’ve made an initial test for melee attacks. Since I don’t have any screen recording software at the moment, here is a recording from my tablet:

(Next, time, I’ll rummage through this.)

And here I’ve still yet to explain what those rings are when you attack. I don’t have time to make a diagram right now, but basically, each ring denotes one type of attack.

The smaller ring is for weak, fast, and short-range melee attacks.

The outer ring is, as demonstrated, for farther, more powerful melee attacks.

I’m taking cue from fighting games where you have varying degrees of attacks: maybe a light punch, medium punch, and heavy punch. A light punch makes you dash forward only slightly, while (generally) a heavy punch makes you dash forward a lot more.

Likewise in fighting games, enemies that get hit by melee here will receive pushback.

W.U. 2: Editing Game Data

This is weekly update number 2. That previous weekly update was just a bonus.

So I had been working on the data representation of melee attacks. I thought it was a good time to make a nice editor front-end for editing them:

This is the nice thing with Unity, you can extend the editor GUI yourself since it’s quite modular in showing data (i.e. components). That MeleeLimits is a ScriptableObject type of class.

What is that for? Its an idea I had in my old version of Tactics Ensemble. Continue reading