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.
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.
The next unit to be implemented is the Shieldsman. A heavily armored soldier carrying a retractable tower shield. This unit serves as the tank, incoming attacks from the front are negated while the shield is in place. It is slow, however, and cannot traverse steep slopes. It cannot even climb ladders as they would collapse under its sheer weight.
Retractable Tower Shields are the Shieldsmen’s namesake. Made of solid steel, only the strongest warriors take up this role.
While in limber mode, the shield offers more mobility (limited as it is for a Shieldsman).
When activated, the shield is as good as a wall of steel, shrugging off even the high-speed bullets of Sharpshooters.
My first step is to concept the Shieldsman’s shield. I won’t bother actually making the Shieldsman yet; I’ll just reuse the Dragurian Colony Soldier 3d model for now.
This sketch shows how Shieldsmen may look like.
I got carried away and made another shield:
Adorned with three hideous faces, the Mad Kings Shield is not for protection as much as a tool to strike terror to enemies.
The retractable component doubles as a tool to kill, serving as a portable guillotine. In practice, this miniature guillotine only works best as a coup de grâce move.
WordPress.com also has a little statistics report for the blog.
Here’s an excerpt:
600 people reached the top of Mt. Everest in 2012. This blog got about 1,900 views in 2012. If every person who reached the top of Mt. Everest viewed this blog, it would have taken 3 years to get that many views.
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:
- 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.
- 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.
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.
I tried ditching the pathfinding and used a brute force approach, but it was clearly very slow and unwieldy.
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.