# More on Movement System

The movement range works on the idea of having move points, points that you expend for moving.

I made it that I can also restrict movement based on the angle of the terrain being walked on.

Orange lines mean you can’t go further because the angle of the ground is too steep or too high.

Green lines mean he can’t move farther in that direction, but only because he ran out of move points. He has to end his turn to go further.

Here’s how it looks like as I increase the available move points.

At 75 move points:

At 100 move points:

He can go further upwards the hill’s path, and further downwards to the tower.

But notice all those orange lines. That means he’s not allowed to climb near-vertical slopes, nor can he jump down from the hill. Later on I may implement climbing and jumping down.

I can also make moving upwards more costly, making the move range shorten on upward paths only.

Such properties are meant for heavy units with bulky armor; they get tired faster walking upwards.

Here, upward movement is greatly restricted, but notice downward movement hasn’t changed.

Contrast that to units that can move upward easily, like a Scout or Pathfinder type of unit: lightly protected and has low survivability in thick battles, but can easily move where heavy units have trouble.

# Fixing the Movement System

My problem with my movement system was that it did not take detours around obstacles into account.

Here’s another example:

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

And here I was trying to calculate such things, with a brute-force experiment (see post):

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

It looks ugly and takes something like 10 seconds to compute.

I realized that to do what I want, I will really have to put a grid in the map. But the idea is that grid will only be used for calculating move range. Characters will still not move by the grid.

So here’s the grid:

So with this, I can run a plethora of algorithms for calculating paths.

Now what I did, was to use Dijkstra’s algorithm without specifying an end goal. So I’m letting it run on all directions, but imposing a limit on how much squares it can go to.

It’s similar to displaying the movement range in square grids of games like this:

It’s sort of like doing a flood-fill. But here I need to take into account the slope of terrain: steeper angles cost more to move. And with Dijkstra’s algorithm, it was easy to put that in.

So what I get is this:

But now that I’m using a proper pathfinding algorithm, it will take obstacles into account properly.

For example, this is my movement range in top view. If you add an obstacle (like a building) within the perimeter, the movement range will adapt properly.

My next step was to collect all those points and connect them to each other, forming the perimeter:

Now obviously, it’s looking ugly. The curves are jagged. So the next step was to apply some sort of smoothing to the points’ x,y,z positions.

And then we get this:

Which is quite nice and exactly what I want.

All I’m doing here is a simple average (i.e. mean) filter: for each point, you average its x,y,z position, and that of the point next to it, and the one before it.

Now actually, I’m applying the filter 4 times, to get a good smoothened out look.

For comparison, here’s the top view of the unsmoothed border:

And here it is, smoothed:

And here it is, super-imposed:

It follows the original path fairly well.

And as a nice bonus to all of this: it takes about 0.1 seconds to compute this movement range, so it really is far better than my old code.

As a final comparison, here’s what it looks like before and after:

# Finally Modularized My BT Library

My behaviour tree library now exists as a git subtree in my game’s repo!

This means any updates I make to the library from other endeavors can easily be incorporated to this project. Likewise, any updates to the BT library from this game can be applied to the BT library’s own repo.

One such update is the Parallel Composite. I realize they’re really needed for real-time games, so I added them in. For example, when you need your A.I.’s moving, to act independently from shooting, allowing a run-and-gun behaviour (shooting while evading, shooting while charging in, etc.).

It’s not multi-threaded though (with this being in Unity), and I haven’t added completion policy or failure policy to it yet.

The way I made my Parallel, I think is different from the one explained in AIGameDev.com. It’s far more rudimentary since I’m still not finished with it.

• The Parallel executes all its children once in sequence, but does no early-out aborts.
• It waits for all of them to finish executing, then deliberate what its return value should be, based on the return value of its children.
• Even if a child returns “Running” (a request to suspend tree traversal), we still wait for all children to complete.

There would be two types of deliberation policies:

1. At least one failure from any child will make the parallel return failure. The parallel will return success only if all children returned success.
2. At least one success from any child will make the parallel return success. The parallel will return failure only if all children returned failure.

Essentially, one is strict, and the other isn’t.

What if two children of a Parallel return “Running”? I haven’t taken this into account but I imagine it would be like this:

1. Traversal should continue at the very first one that signaled “Running”.
2. Even if one of them finished successfully, if the other one is still in “Running”, the whole tree should still return “Running”.
3. This means the traversal should keep track of all “Running” actions.
4. Essentially what we want to prevent here is resetting execution of a “Running” action, when what it should really do is attempt to continue where it left off instead.

Thankfully I already made code where the traversal stack is saved when we suspend traversal. However, the idea of keeping track of two or more “Running” actions complicate things. Could be I need to store more than one traversal stack.

Real parallel nodes I believe, will keep on running its children. If one child finishes too early while the others haven’t finished yet, it gets run again.

Since my BT library runs on Unity which is hampered by restrictions on multi-threading, I’d have to do some sort of job scheduling like operating systems do.

This was one thing I thought of before: an interleaved parallel.

• This will disrupt the normal flow of traversal. The interleave will look at its first child, let it execute one of its children, then suspend that traversal. The interleave will then move on to its next child, also only allowing it to execute one of its children only. And so on.
• It’s a constant cycle of suspension and continuation of the children’s own traversals.
• When should the interleave stop? When all children have completed their traversal at least once (remember, they repeat traversal if possible). Then the return value of the interleave will be chosen from the deliberation policies mentioned earlier.

For my scenario though, I’ve yet to need this. My behaviour tree actions and conditions are very lightweight, in that they don’t actually do the actions themselves. They just send requests to the other sub-systems in the game to do the work for them. The behaviour tree only handles the deciding part, not the doing part. As such, traversal is relatively fast, that I (so far) don’t need a job scheduler for a parallel. I just traverse them linearly.

Assertion checks, on the other hand, makes sense to be checked only after resuming traversal of the whole tree (back from a “Running” state).

Why? Because most, if not all, actions always return a “Running” signal. As mentioned, actions only fire off requests to the other sub-systems in the game to do the actual work. Once that request has been sent, the tree has no choice but to wait for that to finish. For example, an attack action sends a request to play the attack animation (among other things). And only once the animation is finished do we resume traversal of the tree.

So I made a special composite just for that. It’ll automatically traverse its “assertion” child when the resuming of traversal continues from its “main” child. I called it Auditor.

The BT library by the way, is now tentatively named “INTLord”. I’m not sure if that should be INTLord, or INT Lord, or Int Lord.

# Auditor Nodes

Here’s my answer for not having true concurrent/parallel nodes for my behaviour tree plugin for Unity: Auditor nodes.

Actually Alex Champandard already explained before, if for some reason you can’t implement true multi-threaded traversals you can fake it by using the same concept that operating systems do: job schedulers.

Which I still didn’t do. At least for now. Auditor nodes merely make sure their assertion branch gets evaluated when you resume from a previously suspended (a.k.a. “Running”) state of the tree traversal.

It didn’t justify peppering a subtree with back-and-forth checking of assert nodes and normal traversal (as how a job scheduler might do), because traversal is fast, or at least, meant to be fast.

Actions never process their behaviour immediately upon being traversed. They merely request other parts of the game code to initiate an activity for them (please start moving to this location, please attack this enemy, etc.) and such Actions that rely on something to finish first before sending Success or Fail would suspend the traversal (a.k.a. “Running” state). Which is why the Auditor’s asserts are checked only when resuming from a traversal suspend.

For cases where the Action/Condition is doing something computationally heavy, it should spread that computation over several frames (a bit like coroutines), hence another use of the “Running” state.

The only reason why I can’t make real multi-threaded traversals is because Unity doesn’t play well with multi-threading. For example, checking line-of-sight, as in raycasting, cannot be done in new threads, it has to be done in the main thread, even though raycasts are a very read-only affair.

# Of the 100 nobles watching, 100 were impressed.

Ah… Smell that? That is the smell of 0 unit tests failing on my non-recursive, brute-forced traversal of behaviour trees.

Thanks to Bjoern Knafla for the tutorials!

This is part of an effort to improve my behaviour tree plugin. Hopefully I can make a demo game out of it and sell it on the Unity Asset Store.

I lately haven’t been able to make any considerable progress with Tactics Ensemble as day job work is taking up a lot of my attention. I’m still working on it though.

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