Behaviour Trees - A Boustrophedon House Search System (2025)
- Vichakshana Arangala
- Jun 27, 2025
- 7 min read
Updated: Jun 28, 2025
In this setup, I have created a virtual environment with two distinct AI agents, the Blue Agent and the Green Agent. The Green Agent patrols three different waypoints, and when it sees the Blue Agent, turns towards the Blue Agent (with a random deviation of 5 added to the angle to create the illusion of it not being 100% accurate) and fires 3 bullets, checks if the Blue Agent is still in range, and continue firing, and if it not, resumes it’s patrol. The Blue Agent wanders aimlessly through the virtual world, exploring houses, collecting Health Packs, Ammo and Coins along the way. When it sees the Green Agent, it goes through the same combat sequence as the Green Agent. If the Blue Agent does not have Ammo, it flees in the opposite Direction. The AI behaviour was set up using Behaviour Trees; a staple of modern Game Programming.
I set about developing my Behaviour Trees as a means of improving my Game Programming skills. Having used Behaviour Trees only in the context of Unreal Engine, I had a very rudimentary understanding of the subject. There is very little tutorials on Implementing Behaviour Trees, and the task seemed daunting at first, but I soon found that what little material to be more than adequate for implementing my own Behaviour Trees. My main points of reference for implementing Behaviour Trees was AltDevBlogADay’s video on Behaviour Trees, Peter Ogren’s Lectures, The github repository, btsk and the website behaviortree.dev, with the latter two being extremely helpful in understanding an implementation which till then was purely abstract to me.
The Behaviour Trees were built on top of my existing Nashcore Game Engine, which itself was based on David Churchill’s SFML lectures, and I previously used for developing Ashura’s Revengence. The main components of the Behaviour Trees are the Node, the Selector, the Sequence, the Stateful Sequence and the Loop.
Node
The Node class is the base class from which all other nodes are derived. It has several virtual functions which the inherited classes override. The node class also stores an Enum of Status to retrieve the Status of the current node, with the main ones being INVALID, SUCCESS, RUNNING and FAILURE. The enums are used to decide if the agent continues doing the same Task, starts the same task from the beginning, or move onto the next task.
Selector
The Selector Node is a Composite Node. It contains pointers to multiple child nodes and decides which child run, based on a condition.
Sequence
The Sequence is another composite Node, which runs its child nodes in a sequence.
Stateful Sequence
I came across the need for a Stateful Sequence Node when developing my patrol sequence. I found that a mere Sequence Node is not the ideal way to carry out the patrol logic, and that a Stateful Sequence Node is the solution. However, I kept the Sequence Node as it is, as a Stateless Sequence Node also has their own use cases.
Loop
True to it’s name, the loop was designed to carry out a set of sequences repeatedly, provided that certain conditions are met. Though the loop functionality was implemented, I later found this node to be unnecessary, as the effects were achieved with the two sequences nodes. But I kept the node as it is, as it may have it’s own use cases.
Vision cone
The Vision cones seemed at first glance the simplest of all to implement, but proved to be more complex than I initially thought. I integrated the Vision cone into the ECS system so that it could be attached to various different entities, and be re used for future projects if needed. However, after multiple iterations, I was able to come up with a simpler, far more elegant solution by checking objects against the vision cone’s angle and radius against other objects, and implementing a Line Of Sight check into the mixture.
Item Management
Item management turned out to be another system which seemed simple at first glance, but required many fine tunings to get right, up until the last day of Development. The Agent checks if it has more less than 3 Health Packs or Ammo Packs in its inventory, and collects it if that’s the case. When the agent’s health goes below 25 hit points, it uses a health pack to restore it’s health by 50 points, and the Health Pack is removed from the inventory. Each Ammo pack contains 3 bullets, and they are removed from the inventory once three bullets are fired (Ammo Count %3). The inventory always the left mouse respective item in the inventory, and once an item is discarded, the items all ‘slide’ to the left, making room for a new item on the right. If the inventory already contains 3 items of a respective type, the agent ignores that item. Coins are collected regardless, and are not added to the inventory.
Boustrophedon Search system
The Boustrophedon Search system gets it’s name from the linguistic term of the same name. It refers to a style of writing in which alternative lines are written in reverse. My Boustrophedon Search system follows the same principle ensuring that an area is covered with the shorts path possible. My Boustrophedon search system utilizes a Depth First Search principles to map out a room based on the number of rooms a house is divided into. Once in the Boustrophedon Search phase, the agent scans the whole room, collecting items along the way(if the agent needs them and has enough inventory space, coins are collected regardless).
Memory Retention & Item Spawning
Once an agent explores a house, the house is stored in its memory. The agent can remember 3 houses at a time. And once a house is explored, the agent ignores that house, until its memory becomes full, and it ‘forgets’ the oldest house in memory, at which point, new items are Spawned inside the house. The spawning system check if the agent needs Ammo or Health Packs, and does not spawn them if there is already sufficient amounts in the inventory.
Known issues and Trade-offs made...
No software is without bugs and issues, and that is the case for this project. While the Behaviour Trees themselves work flawless without issues, and I did encounter several issues and tradeoffs were made to ensure that the project met the deadline.
The Green Agent was originally meant to have a dedicated ‘Wall Tracing’ behaviour, where when it saw a wall, it would trace it till it found a door, and entered the house. This implementation came with too many edge cases, which proved too time consuming to implement, and I opted to using my existing AStar Pathfinding system to move the agent directly to the door.
The house and enemy placements were originally meant to be randomized, but I realized this would introduce too many edge cases, many of which couldn’t be instantly replicated to be patched around. Therefore I opted to hardcode the level, placing the Blue Agent in a safe zone. There was originally meant to be a Green Agent patrolling the space between the Warehouse and L-House. But in many cases, the Blue Agent would enter the Warehouse, explore, it ran into the Green Agent upon exiting, attempt to flee in the opposite direction, and find that there was no space to flee, and crash. Therefore the agent was moved away from that zone.
The initial plan was to have the HUD display which Node of the Behaviour Tree was currently running, and the current Status of the tree. This proved to be too time consuming, and was ultimately scrapped.
The most infuriating aspect of this is that in some cases, when then Blue Agent picks up Ammo, it restarts the entire tree for some reason, and it takes about 2 to 3 seconds before it resumes behaviour. I have run into scenarios where the agent freezes completely after collecting an item(which I assume is caused by the same item being spawn twice).
Lastly, the environment is not as balanced as I would’ve liked it to be, the Blue Agent takes a long time to die, it roams endlessly for a long time without finding the L-House and some behaviour like the ‘Flee’ Behaviour won’t always be visible, and the agents need to see another agent to engage in combat. But the goal was to show varying behaviour, there for I left in as much diverse behaviour as possible. I also implemented a Kill Switch, which sets the Blue Agents health to 0, simulating death, and changing the Scene to the score screen. Of course, this feature too has many errors. And overall it will be a good 15 minutes before all the different behaviours are seen.
What I learned
This was my most complex project to date, and I learned about cascading logic and the use of shared, unique and weak pointers for different scenarios, ensuring that the trees ran with minimum modifications whenever a new task is introduced. This was my first hands-on use of smart pointers in a project of my own and I gained new insight to their proper usage. I got the opportunity to apply many different Game Programming Patterns like Object Pooling, Singletons and the Command Pattern into a real-world application.
Future Plans
This is the a project I plan to build up on, and use in future projects. The main goal I can see for this is to begin implementing the necessary logic for the ABORTED and INTERRUPTED states, as I believe they will be the most useful moving forward. I also plan on developing racing AI(something akin to Mario Kart) using this system, as I believe it will help me further improve my C++ skills and my knowledge on Behaviour Trees and Enemy AI logic. Once done, I will update website with it’s own portfolio page. Overall, I plan on making this system extremely flexible so it can be transferred over to a different engine.
Comments