W.U. 23: Pathfinding Test

With the outdoor map I made it was clear that I needed some pathfinding for the characters.

Typically this is achieved with overlaying a cell grid on your map, or perhaps manually placing markers/nodes on your map indicating possible pathways.

Then an A-star pathfinding algorithm is let loose, finding the optimal path from one spot to another with the help of the aforementioned cell grid, or node map, or what-have-you.

(Unity Pro has a really nice Navigation Mesh feature but since I don’t have Pro, I can’t use that.

There’s this: Certain Logic’s Navigation Opensource Framework, and I’ll probably take a look at it some time.)

My problems were:

1. This is a strategy game that features a gridless map (like Skulls of the Shogun or Phantom Brave), so adding a grid wasn’t very appealing to me at first.
2. The characters consume resources to move (i.e. action points like in the old XCOM: UFO Defense). Among the costs for movement, the slope or angle of the terrain influences this very much. Steeper terrain costs more to travel to. Coupled with a gridless map, this means the exact slope of the terrain has to be used. A cell grid would be a coarse sampling of the terrain, and the resulting calculations of angles from that would be inaccurate, leading to discrepancies in cost to a unit’s action points.

To get accurate measurements, I’ve had no choice but to make hundreds of raycasts on-the-fly.

This unit can’t move very far up, as that consumes more stamina points.

But this was clearly taxing on computer resources, so I had to do something about it.

My first attempt was to make the cell grid very tiny, about 0.1 meters per cell! This turned out to be even slower than without pathfinding because of the amount of cells to consider.

The path up the mountain should be included in the movement range, but how would that be calculated?

I tried ditching the pathfinding and used a brute force approach, but it was clearly very slow and unwieldy.

The brute force approach to include detours in the movement range was inefficient.

I had to make concessions. I focused on giving pathfinding to the enemy AI movement only instead. Movement range calculation wasn’t something I can solve anytime soon.

I tried a pathfiding solution again, but this time, the resulting path would only serve as a guide to detour around obstacles, not as the actual path to be used (to keep movement costs accurate).

I can get away with making the cell size coarse this time, 1 meter in size. While this means a really optimal path won’t be taken, at least the enemies won’t mindlessly keep running toward walls.

It worked nicely, but my characters still end up moving through impassable terrain, and even other units, bumping them off-course.

Valve’s presentation slides on The AI Systems of Left 4 Dead shared a nice simple solution: a simple steering behaviour on top of the pathfinding. I realize, despite my ignorance, that steering is probably a common method anyway.

While it still manages to bump other units slightly, at least the enemies now have some semblance of intelligent movement. A more sophisticated approach would be squad formations.

Furthermore my little Influence Map project may come in handy later on, to give a more tactical decision-making process to the AI.

Amidst all the experimentations, Git handles all the code changes gracefully.

W.U. 15: Another update on the Behaviour Tree Editor

This Behaviour Tree Editor is really taking up much of my time. Its the “Editor” part, to be more precise.

1. Traversals can now be watched in the Editor. That is to say, the Traversals Display Window and the Editor now show the same thing.
2. This also means proper editing of Behaviour Trees can now be done in-game.
3. The Editor can now be used to add new nodes to the tree.

1. The rest of operations for nodes: deleting, duplicating.
2. Tabbed interface: more than one behaviour tree open at a time.
3. Make it work for the Player class in addition to the Unit class (for editing victory/defeat conditions)
4. Minor enhancements: add feedback on where node gets placed when dragged.

W.U. 14: Behaviour Tree Editor Update

Sorry for the voice and volume, this was done in a hurry. I’m really busy.

Here I demonstrate how my Behaviour Tree Editor works so far.

If you don’t know what that is, basically, it’s what powers the A.I. system. Here I have a tool to make these A.I. systems and tweak them while playing the game.

I got some updates on it, and I may release it as open-source if anyone wants.

So far, the editor can now be used to edit the properties of actions and conditions (even while the game is running), drag nodes around, and load/save Behaviour Tree files. Files are saved in JSON format.

I was surprised and annoyed there was no ready made free code to draw a color picker dialog box in runtime for Unity, so I made one. But it was surprisingly easy, thanks to the HSBColor code in the Unity wiki site. I can also release it in open-source if anyone wants.

Also quite nice is the file dialog box code in ImprovedFileBrowser. If anyone is looking into making a runtime file dialog box, that’s a good place to start.

W.U. 11: Behaviour Tree Traversal Display

Here’s a video where the A.I.’s behaviour tree traversal is inspected. I decided against watching a traversal as it happens because of performance reasons and instead, the game records traversals and you can watch them after they are recorded.

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.

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. 9: Retreat Behaviour

(Finally gotten around to making my screen recorder work at tolerable speeds. The sound also works though its really just recording from a microphone. Its also registering properly as 720 HD on YouTube now.)

Here is a demo video of the retreat behaviour, although it takes quite a while (i.e. multiple turns) until they figure out where to really go. I suspect once I start using influence maps this will work better.

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
}
]
}
]
}
]
}```