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:

Refactoring

With my plans on changing the combat system, a big refactoring effort on my code is needed.

I received good feedback on my article about a loosely-coupled system for code in games. So I think I should apply the principles back to my code in Tactics Ensemble.

Low-level

UnitAnimation:

My previous code was a thin layer behind Unity’s Animation class. Users of this class had to compute things by themselves, specifying blend time between animations, needing to check for animation playback positions themselves, etc. I need to change this so it would be a fire-and-forget scenario. Just send requests to do a certain animation, and let the UnitAnimation class figure out the little details by itself.

AnimationsUsed:

Some simple class should facilitate what default animations should be used for idle, what default hurt animation should be used when getting damaged, what animation should be played when unit is selected, and whatnot.

UnitMovement:

This is a good time to revisit the arguments between Character Controller and Rigidbody. Which one should I use now? I should also redo pathfinding, obstacle avoidance, and pushing other units, in a cleaner way now. I should also consider how this class is used by the human player input and by the AI system, how different should handling those two users be.

UnitAttack:

This is the class that was missing from my systems. A separate class should handle the little details of turning on or off melee collisions, and launching of projectiles at the right time.

UnitGui:

This is also something I need to add. A class that handles GUI for the unit, meaning what effect should happen when the unit is highlighted, when the mouse is hovered over it, when it is selected, etc.

The healthbar and any other icons floating above this unit should also be handled by this class.

Should also communicate with the GUI HUD to display this unit’s actions, portrait, name, etc. on the HUD.

UnitReplay:

Something I could add later on. It would basically take note of all incoming function calls to all low-level classes, record at what time they were called. When watching a replay, we simply review the list made, and call the appropriate functions at the proper time. This only handles the replay for one unit, so we have one UnitReplay for each unit in the battle.

I should make the Unit class refer to the low-level classes via interfaces only. I’d need to clean this up as well to accommodate the new combat system.

Actions

I think I also need to question my system on Actions and Effects.

It would be beneficial if I convert my Effects system to just use behaviour trees instead. It would make editing more consistent, and add flexibility to attacks; you could add conditional effects easily (e.g. if my health > enemy health, deal 2x damage).

Actions (i.e. attacks) would get a revamp, to accommodate the new combat system to be experimented on. I also need to consider if it can be improved to integrate with the AI system better.

Local Player Singletons

This is the set of singletons used to facilitate player input from mouse and keyboard.

They manage selecting a friendly unit on behalf of the player, relaying orders to it, facilitating when the game is asking the player for a destination/target to click on, etc. Basically it handles player input from the local machine (as opposed to input from across the network in a multiplayer game).

I think I should separate this to a low level that handles mouse and keyboard directly, and a high level that sits in problem domain. With that, I should be able to add touch-screen controls later without messing the existing code.

UnitSelector

The class that handles which unit is currently selected. In the normal flow of how a player plays the game, this is where it all starts.

Since it manages which unit is selected, this dictates which unit will be given orders by the player.

This is one of the things that probably needs decoupling, with a UnitSelectorMouseKeyboard that listens for left-clicks and keypresses, and a high-level UnitSelector that facilitates OnSelected events, tells which unit is currently selected to whoever asked it, and whatnot.

GUI HUD

Accepting input from GUI buttons should also be handled by a separate, low-level class. BattleNGUI. This would be the one directly handling NGUI.

This low-level class will listen in on unit selection events, so it can make sure the currently selected unit’s action buttons, portrait, name, etc. get displayed (in NGUI). Each action button would somehow be able to fire off requests to activate that action of that unit.

A BattleHotkey class or something would essentially do the same of allowing sending of requests to do an action of the selected unit, but now by keyboard hotkey presses instead.

Camera System

Camera movement would normally be independent from everything else, being controlled by the player only.

However, there are times when the camera would be controlled by the game.

When an enemy unit is moving on its turn, the camera should center to it (which I haven’t implemented).

And some actions or events may call for showing cinematic shots of characters.

Effects like camera shake would also be handled by this system.

Decoupling is also in order here. A CameraControlMouseKeyboard would listen for keyboard and mouse input while CameraControl provides the actual moving, rotating, zooming. There would be a CameraControlTouch for touchscreen devices.

AI Players

Fairly rudimentary right now, and I don’t think I’ll be changing this soon. When the time comes, I may experiment on giving AI players a central behaviour tree to use.

Right now, each AI unit thinks for itself. But coordination may be better if I give the AI player its own behaviour tree. It would look at the battlefield map from a tactician’s point of view, then it would tell each unit what role they should be in (go to the defensive, attack from this side, scout here, etc.).

Battle Manager Singleton

This singleton acts as umpire, deciding when the battle has ended, who won and who lost. It manages a list of all players in the game, so it can decide whose turn is next. Very simple piece of code, and I probably don’t need to do anything here.

If I knew how to make UML diagrams I probably would make one now.

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.

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. 12: Victory/Defeat Conditions

I was tackling on implementing the checking of victory/defeat conditions to check if the player won already or not, and I realized, “Why not use behaviour trees for this?” Is this really going to help, or is it a case of “when you have a shiny new hammer, everything looks like a nail”?

What I have are these so far:

Types of Victory Conditions:

1. All enemies defeated
2. Kill certain units
3. Survive for N turns
4. Default: Only player left who is not defeated

Types of Defeat Conditions:

1. All my units defeated
2. Certain units of mine are dead
3. N number of turns passed
4. A (non-ally) player is victorious

(There’s a lot of redundancy there, like “all enemies defeated” would also trigger “all my units defeated” for the opposing player, but for cases where there are more than two players, defeat of one player won’t automatically mean victory because there would be at least two players left.)

Usually there’d be a list of victory conditions and another list for defeat conditions, for each player.

The question is, does triggering at least only one condition in the list constitute an automatic victory (for that player), or do you need all conditions in the list to trigger true to mean victory? Basically, are the conditions in the list strung together in an AND operation or an OR operation?

And the answer is, it depends on each mission the designer creates. So why not allow the designer the flexibility to specify how he wants it? And with my goal of allowing mods, this does need to be flexible.

So I was thinking, why not structure it as a behaviour tree? One behaviour tree for checking victory, and another for checking defeat. And each player will have one of those pairs (there shouldn’t be only one meant for all players since the AI can have different victory conditions than the human player, for example).

So there it is. Right now it’s just a simple message saying “YOU WON” or “YOU LOST”.