You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Game AI is a very broad subject and while there is a lot of material out there, I didn’t find something that introduces the concepts gently and at a slower, more understandable pace. This article will try to explain how to design a very simple but extendable AI system loosely based on the concept of Behaviour Trees.
What is AI?
Artificial Intelligence is the human-like behaviour exhibited by the entities participating in the game. It’s more the illusion of intelligence and thoughtful action performed by the entities than an actual intelligent reasoning driven behaviour. The goal is to try to fool the player into thinking that the other “intelligent” entities are controlled by humans and not by a machine. It’s easier said than done, but we can use a lot of tricks to achieve some really good, seemingly random and “intelligent” behaviours.
An Example
Before we jump right into the fun bit, let’s draft up a plan of what we want to achieve. Again, I will use droids as an example. Imagine an arena where droids will battle it out amongst them and whichever droid is the last one standing is the winner.
The arena will be a board and droids will be placed randomly on it. We’ll make it a turn based game so we can follow the whole AI unfold, but it can be easily turned into a realtime game.
The rules are simple:
The board is a rectangle
A droid can move one tile per turn in either direction to any of the adjacent unoccupied tiles
A droid has a range and can fire at droids within its range
The droids will have the usual attributes: damage they inflict and hit points
For the sake of simplicity we will use very simple structures.
The application will have a Droid class and a Board class. A droid will have the following attributes that define it:
The Droid is just a simple pojo with a few attributes. The attributes are self explanatory but here’s a short summary of them:
name - the unique name of the droid, can be used for ID as well.
x and y - the coordinates on the grid.
health, damage and range - what it says.
board - is the reference to the Board the droid is on along with other droids. We need this because the droid will make decisions by knowing its environment, which is the board<./li>
There is also an empty update() method which is called each time the droid finishes its turn. If it’s a realtime game, the update method is called from the game loop, ideally from the game engine.
There are also the obvious getters and setters and the toString() method which are omitted from the listing.
It has a width and a height and it contains a list of droids. It also contains a few convenience methods to check if a droid is already present at a given coordinate and a method to easily add droids one by one.
So far this is pretty standard. We can scatter a few droids on the board but they will not do anything. We can create the board, add some droids to it and start calling update(). They are only some dumb droids.
Not so Dumb Droids
To make a droid do something, we could implement the logic in its update() method. This is the method called every tick or in our case every turn. For example we want our droids to wander around the arena (board) and if they see an other droid in range, engage them and start firing at them until they die. This would be a very rudimentary AI but is still a AI.
The pseudo code would look like this:
if enemy in range then fire missile at it
otherwise pick a random adjacent tile and move there
This means any interaction between the droids will result in a stand-off and the weaker droid gets destroyed. We might want to avoid this. So we can add that if a droid is likely to lose, then try to flee. Stand and fight only if there is nowhere to escape.
if enemy in range then
if enemy is weaker then fight
otherwise
if escape route exists then escape
otherwise fight
otherwise wander
This is all good. The droids will start acting “intelligently” but they are still very limited unless we add more code to do more clever things. And also, they will act the same.
Imagine if you drop them in a more complicated arena. An arena where there are items like power-ups to pick up to enhance powers, obstacles to avoid.
For example decide between picking up a health/repair kit and picking up a weapon power-up when droids are swarming around.
It can get out of hands quite quickly. Also what if we want a differently behaving droid. One is an assault droid and the other one is a repair droid. We could achieve this of course with object composition, but the brains of the droids will be extremely complicated and any change in game design will require tremendous effort to accommodate.
Let’s see if we can come up with a system that can solve these problems.
Here Comes the Brain
We can think of the AI module of the droid as some kind of a brain. The brain is composed of several routines that act on the droid following a set of rules. These rules govern the execution of the routines so it maximises the chances of survival and winning the game as an ultimate goal.
If we think of our human brain consisting of routines and having Maslow’s hierarchy of needs as a reference , we can identify a few routines instantly.
Physiological routine - a routine that needs to be executed every time otherwise there won’t be any living
Subsistence routine - this routine needs to be executed once the living conditions have been met so the long term existence is secured
Aspirational routine - this will be executed if there is time left after the subsistence has been secured and before subsistence needs to be executed again
Let’s break the human intelligence down a bit.
A human needs to breathe to live. Each breath consumes energy. One can breathe so much until it runs out of energy. To replenish the energy one needs to eat. One can only eat if he/she has food at his/her disposal. If there is no available food, it needs to be acquired which consumes some more energy. If the procurement of food takes a long time (needs to be hunted for example) and the amount of food obtained is small, after eating it, the human is in need of more food and the routine restarts without delay. If the food was bought in bulks from a supermarket, after eating it, there is plenty left so the human can move on to do more interesting things which are in his/her aspirational section. Things like making friends or wage war or watch television for example.
Just think of how many things are in a human brain to make us function and try to simulate it. This all by disregarding most of the stimuli we are getting and responding to them.
To do this, we would need to parametrise the human body and each sensor triggered by a stimulus will update the correct parameters and the executed routine will examine the new values and act accordingly. I won’t describe it now but you get the idea I hope.
Let’s switch back to our much simpler droids.
If we try to adapt the human routines to the droids we’ll get something like this:
Physiological / Existential - this part we can ignore for this example because we design robots and they are mechanical beings. Of course for them to exist, they still need energy (eg. action points) which they can take from a battery or from some other energy source which can be depleted. For the sake of simplicity we will ignore this and consider the energy source to be infinite.
Subsistence / Safety - this routine will make sure that the droid will survive the current turn and live by avoiding an immediate threat.
Aspirational - this kicks in once the safety routine checked out OK and didn’t have to activate the droid’s fleeing routine. The current simple aspiration for the droid is to kill the other droids.
Although the described routines are very simple and can be hard-coded, the approach we will take to implement is a bit more elaborate. We will use an approach based on behaviour trees.
First and foremost we need to delegate every activity of the droid to its brain. I will call it Routine instead of brain. It can be called Brain or AI or anything, but I have chosen Routine because it will serve as a base class for all the routines that will consist of. Also it will be in charge of governing the flow of information in the brain. The Routine itself is a finite state machine with 3 states.
Running - the routine is currently running and will act on the droid in the next turn. Eg. the routine is responsible to move the droid to a certain position and the droid is in transit and still moving uninterrupted.
Success - the routine has finished and it succeeded doing what it was meant to be doing. For example if the routine is still the “move to position”, it succeeded when the droid reached the destination.
Failure - using the previous example (move to), the moving of the droid was interrupted (either the droid got destroyed or some unexpected obstacle appeared or some other routine interfered) and it didn’t reach the destination.
The Routine class has the act(Droid droid, Board board) abstract method. We need to pass in the Droid and the Board because when the routine acts, it does so on the droid and in the knowledge of the droid’s environment which is the board.
For example the moveTo routine will change the droid’s position each turn. Usually when the routine acts on the droid, it uses the knowledge gathered from its environment. This knowledge is modelled on the realities of the situation. Imagine that the droid (like us humans) can’t see the whole world but only as far as its sight range. Us humans have a field of view of about 135 degrees so if we would be simulating a human, we’d pass in a slice of the world containing the section we see and all the visible components in it and let the routine process just that to the best of its capabilities and come to a conclusion. We could do that for the droids too, and just pass in the section of the board that is covered by the range, but we will keep it simple for now and use the whole board.
The start(), succeed() and fail() methods are simple public overridable methods that set the state accordingly.
The reset() method on the other hand is abstract and it has to be implemented by each concrete routine to reset any internal state proprietary to that routine.
The rest are convenience methods to query the state of the routine.
Learning to Walk
Let’s implement the first concrete routine which will be the MoveTo discussed above.
It’s a very basic class that will move the droid one tile towards the destination until it reaches it. It does not check for any other constraint than if the droid is alive. That’s the condition for failure.
The routine has 2 parameters destX and destY. These are final attributes which the MoveTo routine will use to achieve its target. The routine’s single responsibility is to move the droid. If it can’t do that it will fail. That’s it. Single responsibility is very important here. We will see how we’ll combine these to achieve more complex behaviours.
The reset() method simply sets the status to Running. It has no other internal state or values to deal with, but it needs to be overridden.
The heart of the routine is the act(Droid droid, Board board) method which performs the action and contains the logic. First it checks for the failure condition, which is if the droid is dead. If it’s dead and the routine is active (its status is Running) then the routine failed to do what it was supposed to. It calls the super class’s default fail() method to set the status to Failure and exits the method.
The second part of the method checks for the success condition. If the droid is not yet at the destination, then move the droid one tile towards the destination. If its’ reached the destination, set the state to Success.
The check for isRunning() is made to make sure that the routine only acts if the routine is active and hasn’t finished.
We also need to fill in the Droid‘s update method to make it use the routine. It’s just a simple delegation. This is how it looks like:
1 publicvoidupdate(){2 if(routine.getState()==null){3 // hasn't started yet so we start it4 routine.start();5 }6 routine.act(this, board);7 }
It should consist only of line #6 but I also put in a check to see if the state is null and if so, then start the routine. This is a hack to start the routine the first time update is called.
It’s a quasi command pattern, as in the act method gets the receiver of the action command as a parameter, which is the droid itself.
I also modified the Routine class to log the different events in it, so we can see what’s happening.
It’s a standard class with a main method which firsts sets up a square 10 x 10Board and adds a Droid with the provided attributes at the coordinates 5,5.
On line #10 we create the MoveTo routine which sets the destination to (7,9). We set this routine to be the only routine of the droid (line #11) and print the droid’s state (line #12).
Then we execute 5 turns and display the droid’s state after each turn.
Running the Test we see the following printed to the sysout:
As we can see the droid starts at position (5,5) as expected. Calling the update method for the first time, starts the MoveTo routine. The subsequent 3 calls to the update will move the droid to the destination by changing its coordinate each turn by one. After the routine succeeded, all the calls passed to the routine are ignored, because it’s complete.
This is the first step, but it’s not very helpful. Let’s say we want to have our droid wander around the board. To achieve this, we will need to execute the MoveTo routine repeatedly, but every time it restarts, the destination needs to be randomly picked.
Wandering About
But let’s start with the Wander routine. It’s nothing more than a MoveTo but we generate a random destination given that we know the board.
Following the single responsibility principle, the Wander class’s sole purpose is to pick the random destination on the board. Then it uses the MoveTo routine to get the droid to the new destination.
The reset method will restart it and pick a new random destination.
The destination is set in the constructor. If we’d like our droid to wander, we would change the Test class to the following:
Notice how the Wander contains and delegates to the MoveTo routine.
Repeat, Repeat, Repeat …
This is all good but what if we want the droid to be wandering repeatedly?
We will make a Repeat routine which will contain a routine to be repeated. Also we will make this routine so that it can take in a parameter to specify how many times we want to repeat a routine. If it won’t take in a parameter, then it will repeat the containing routine forever or until the droid’s dead.
The code is easy to follow but I will explain a few things that were added.
The attribute routine is passed in the constructor and that will be the routine that gets repeated. The originalTimes is a storage variable that holds the initial number of times value, so we can restart the routine with the reset() call. This is just a back-up of the initial state.
The times attribute is how many times the provided routine will be repeated. If it’s -1 then it’s infinite. This is all coded in the logic inside the act method.
To test this out, we need to create a Repeat routine and provide what to repeat.
For example, to have the droid wander endlessly, we’d have this:
So far we’re just composing behaviours. But what if we want to add decision making to the droids and build a more complex behaviour? Enter the behaviour trees. This term doesn’t describe what it is and neither do most of the articles that I found. I’ll start with what I want to achieve first and hopefully it will all make sense.
I want to implement the behaviour described at the beginning of the article.
I want my droid to scan if there is a weaker droid in its range and engage it if it is, or flee otherwise.
Take a look at the following diagram. It shows a tree. It’s nothing more than a routine composed of multiple different routines. Each node is a routine and we will have to implement some special routines.
Droid AI (Behaviour Tree)
Let’s break the routines down.
Repeat - is the routine implemented earlier. It will repeat the given routine forever or until the embedded routine fails.
Sequence - the sequence routine will succeed only when all the routines that it contains have succeeded. For example to attack a droid, the enemy droid needs to be in range, the gun needs to be loaded and the droid needs to pull the trigger. Everything in this order. So the sequence contains a list of routines and acts on them until all succeed. If the gun is not loaded then there is no point in pulling the trigger so the whole attack is a failure.
Selector - this routine contains a list of one or more routines. When it acts, it will succeed when one of the routines in the list succeeds. The order in which the routines are executed is set by the order in which the routines are passed in. If we’d like to randomise the execution of routines, it’s easy to create a Random routine whose sole purpose is to randomise the list of routines passed in.
All the grey routines are leaves in the tree, meaning that they can’t have any subsequent routines and these are the ones that act on the droid which is the receiver.
The above tree represents the very basic AI we wanted to implement. Let’s follow it through starting from the root.
Repeat - will repeat the selector indefinitely until neither of the branches can be executed successfully. The routines in the selector are: Attack a droid and Wander. If both fail that means that the droid is dead.
The Attack a droid routine is a sequence of routines meaning that all of them have to succeed in order for the whole branch to succeed. If it fails, then the fall back is to pick a random destination through Wander and to move there.
Then repeat.
All we need to do is to implement the routines.
For example the IsDroidInRange could look something like this:
It’s a very basic implementation. The way it determines if a droid is in range, is by iterating through all the droids on the board and if the enemy droid (assuming that the names are unique) is within range, then it succeeded. Otherwise it failed.
Of course we need to feed in this droid to the next routine somehow, which is IsEnemyStronger. This can be achieved by giving the droid a context. One simple way could be that the Droid class could have an attribute nearestEnemy and on success the routine will populate that field and on failure it will clear it. This way the following routine can access the droid’s internals and use that information to work out its success or failure scenarios.
Of course this can be and should be extended so the droid will contain a list of droids in its range and have a routine to work out if the droid should fly or fight. But it’s not the scope of this introduction.
I won’t be implementing all the routines in the article, but you will be able to check out the code on github: https://github.com/obviam/behavior-trees and I will be adding more and more routines.
Where to go from here?
There are quite a few improvements that can be made just by looking at it. As a first step to test the system out, I’d move the creation of the routines to a factory for convenience.
/** * Static convenience methods to create routines */publicclassRoutines{
Of course this is not the best solution by far but it’s still better than the constant instantiation of routines. Ideally the AI should be scripted and loaded from an external source, either via scripting, or at least provided as a JSON for example and have a AI assembler create it. This way the game does not need to be recompiled every time the AI is tweaked. But again, it is not the scope of this article.
Also, how shall we decide which action will take up a turn/tick or is evaluated instantly? One possible solution could be to allocate action points to the droid that it can spend one turn (tick if realtime) and for each action to assign a cost. Whenever the droid runs out of points, then we can move on. We’d also need to track which routine is the current one so we can optimise the traversal of the tree. This is helpful if the AIs are very complex especially in realtime games.
If you think the article was useful and want to get the code, please check the github repo. You can also check back because I intend to extend it and to update it so it evolves into a more complete AI example. As it is my first encounter with AI, there will be lots of things to improve and I am always open to criticism and ideas on how to improve.
Game AI - An Introduction to Behaviour Trees · Obviam
http://bit.ly/2WRha4d
About 0 Minutes
Game AI is a very broad subject and while there is a lot of material out there, I didn’t find something that introduces the concepts gently and at a slower, more understandable pace. This article will try to explain how to design a very simple but extendable AI system loosely based on the concept of Behaviour Trees.
What is AI?
Artificial Intelligence is the human-like behaviour exhibited by the entities participating in the game. It’s more the illusion of intelligence and thoughtful action performed by the entities than an actual intelligent reasoning driven behaviour. The goal is to try to fool the player into thinking that the other “intelligent” entities are controlled by humans and not by a machine. It’s easier said than done, but we can use a lot of tricks to achieve some really good, seemingly random and “intelligent” behaviours.
An Example
Before we jump right into the fun bit, let’s draft up a plan of what we want to achieve. Again, I will use droids as an example. Imagine an arena where droids will battle it out amongst them and whichever droid is the last one standing is the winner.
The arena will be a board and droids will be placed randomly on it. We’ll make it a turn based game so we can follow the whole AI unfold, but it can be easily turned into a realtime game.
The rules are simple:
For the sake of simplicity we will use very simple structures.
The application will have a
Droidclass and aBoardclass. A droid will have the following attributes that define it:The
Droidis just a simple pojo with a few attributes. The attributes are self explanatory but here’s a short summary of them:name- the unique name of the droid, can be used for ID as well.xandy- the coordinates on the grid.-
-
There is also an emptyhealth,damageandrange- what it says.board- is the reference to theBoardthe droid is on along with other droids. We need this because the droid will make decisions by knowing its environment, which is the board<./li>update()method which is called each time the droid finishes its turn. If it’s a realtime game, the update method is called from the game loop, ideally from the game engine.There are also the obvious getters and setters and the
toString()method which are omitted from the listing.The
Boardclass is vey simple.It has a
widthand aheightand it contains a list of droids. It also contains a few convenience methods to check if a droid is already present at a given coordinate and a method to easily add droids one by one.So far this is pretty standard. We can scatter a few droids on the board but they will not do anything. We can create the board, add some droids to it and start calling
update(). They are only some dumb droids.Not so Dumb Droids
To make a droid do something, we could implement the logic in its
update()method. This is the method called every tick or in our case every turn. For example we want our droids to wander around the arena (board) and if they see an other droid in range, engage them and start firing at them until they die. This would be a very rudimentary AI but is still a AI.The pseudo code would look like this:
This means any interaction between the droids will result in a stand-off and the weaker droid gets destroyed. We might want to avoid this. So we can add that if a droid is likely to lose, then try to flee. Stand and fight only if there is nowhere to escape.
This is all good. The droids will start acting “intelligently” but they are still very limited unless we add more code to do more clever things. And also, they will act the same.
Imagine if you drop them in a more complicated arena. An arena where there are items like power-ups to pick up to enhance powers, obstacles to avoid.
For example decide between picking up a health/repair kit and picking up a weapon power-up when droids are swarming around.
It can get out of hands quite quickly. Also what if we want a differently behaving droid. One is an assault droid and the other one is a repair droid. We could achieve this of course with object composition, but the brains of the droids will be extremely complicated and any change in game design will require tremendous effort to accommodate.
Let’s see if we can come up with a system that can solve these problems.
Here Comes the Brain
We can think of the AI module of the droid as some kind of a brain. The brain is composed of several routines that act on the droid following a set of rules. These rules govern the execution of the routines so it maximises the chances of survival and winning the game as an ultimate goal.
If we think of our human brain consisting of routines and having Maslow’s hierarchy of needs as a reference , we can identify a few routines instantly.
Let’s break the human intelligence down a bit.
A human needs to breathe to live. Each breath consumes energy. One can breathe so much until it runs out of energy. To replenish the energy one needs to eat. One can only eat if he/she has food at his/her disposal. If there is no available food, it needs to be acquired which consumes some more energy. If the procurement of food takes a long time (needs to be hunted for example) and the amount of food obtained is small, after eating it, the human is in need of more food and the routine restarts without delay. If the food was bought in bulks from a supermarket, after eating it, there is plenty left so the human can move on to do more interesting things which are in his/her aspirational section. Things like making friends or wage war or watch television for example.
Just think of how many things are in a human brain to make us function and try to simulate it. This all by disregarding most of the stimuli we are getting and responding to them.
To do this, we would need to parametrise the human body and each sensor triggered by a stimulus will update the correct parameters and the executed routine will examine the new values and act accordingly. I won’t describe it now but you get the idea I hope.
Let’s switch back to our much simpler droids.
If we try to adapt the human routines to the droids we’ll get something like this:
Although the described routines are very simple and can be hard-coded, the approach we will take to implement is a bit more elaborate. We will use an approach based on behaviour trees.
First and foremost we need to delegate every activity of the droid to its brain. I will call it
Routineinstead of brain. It can be called Brain or AI or anything, but I have chosen Routine because it will serve as a base class for all the routines that will consist of. Also it will be in charge of governing the flow of information in the brain. TheRoutineitself is a finite state machine with 3 states.The 3 states are:
Running- the routine is currently running and will act on the droid in the next turn. Eg. the routine is responsible to move the droid to a certain position and the droid is in transit and still moving uninterrupted.Success- the routine has finished and it succeeded doing what it was meant to be doing. For example if the routine is still the “move to position”, it succeeded when the droid reached the destination.Failure- using the previous example (move to), the moving of the droid was interrupted (either the droid got destroyed or some unexpected obstacle appeared or some other routine interfered) and it didn’t reach the destination.The
Routineclass has theact(Droid droid, Board board)abstract method. We need to pass in theDroidand theBoardbecause when the routine acts, it does so on the droid and in the knowledge of the droid’s environment which is the board.For example the
moveToroutine will change the droid’s position each turn. Usually when the routine acts on the droid, it uses the knowledge gathered from its environment. This knowledge is modelled on the realities of the situation. Imagine that the droid (like us humans) can’t see the whole world but only as far as its sight range. Us humans have a field of view of about 135 degrees so if we would be simulating a human, we’d pass in a slice of the world containing the section we see and all the visible components in it and let the routine process just that to the best of its capabilities and come to a conclusion. We could do that for the droids too, and just pass in the section of the board that is covered by therange, but we will keep it simple for now and use the whole board.The
start(),succeed()andfail()methods are simple public overridable methods that set the state accordingly.The
reset()method on the other hand is abstract and it has to be implemented by each concrete routine to reset any internal state proprietary to that routine.The rest are convenience methods to query the state of the routine.
Learning to Walk
Let’s implement the first concrete routine which will be the
MoveTodiscussed above.It’s a very basic class that will move the droid one tile towards the destination until it reaches it. It does not check for any other constraint than if the droid is alive. That’s the condition for failure.
The routine has 2 parameters
destXanddestY. These are final attributes which theMoveToroutine will use to achieve its target. The routine’s single responsibility is to move the droid. If it can’t do that it will fail. That’s it. Single responsibility is very important here. We will see how we’ll combine these to achieve more complex behaviours.The
reset()method simply sets the status toRunning. It has no other internal state or values to deal with, but it needs to be overridden.The heart of the routine is the
act(Droid droid, Board board)method which performs the action and contains the logic. First it checks for the failure condition, which is if the droid is dead. If it’s dead and the routine is active (its status isRunning) then the routine failed to do what it was supposed to. It calls the super class’s defaultfail()method to set the status toFailureand exits the method.The second part of the method checks for the success condition. If the droid is not yet at the destination, then move the droid one tile towards the destination. If its’ reached the destination, set the state to
Success.The check for
isRunning()is made to make sure that the routine only acts if the routine is active and hasn’t finished.We also need to fill in the
Droid‘supdatemethod to make it use the routine. It’s just a simple delegation. This is how it looks like:It should consist only of line #6 but I also put in a check to see if the state is
nulland if so, thenstartthe routine. This is a hack to start the routine the first timeupdateis called.It’s a quasi command pattern, as in the
actmethod gets the receiver of the action command as a parameter, which is the droid itself.I also modified the
Routineclass to log the different events in it, so we can see what’s happening.Let’s put it to test with a simple
Testclass.It’s a standard class with a
mainmethod which firsts sets up a square 10 x 10Boardand adds aDroidwith the provided attributes at the coordinates 5,5.On line #10 we create the
MoveToroutine which sets the destination to (7,9). We set this routine to be the only routine of the droid (line #11) and print the droid’s state (line #12).Then we execute 5 turns and display the droid’s state after each turn.
Running the
Testwe see the following printed to the sysout:As we can see the droid starts at position (5,5) as expected. Calling the
updatemethod for the first time, starts theMoveToroutine. The subsequent 3 calls to the update will move the droid to the destination by changing its coordinate each turn by one. After the routine succeeded, all the calls passed to the routine are ignored, because it’s complete.This is the first step, but it’s not very helpful. Let’s say we want to have our droid wander around the board. To achieve this, we will need to execute the
MoveToroutine repeatedly, but every time it restarts, the destination needs to be randomly picked.Wandering About
But let’s start with the
Wanderroutine. It’s nothing more than aMoveTobut we generate a random destination given that we know the board.Following the single responsibility principle, the
Wanderclass’s sole purpose is to pick the random destination on the board. Then it uses theMoveToroutine to get the droid to the new destination.The
resetmethod will restart it and pick a new random destination.The destination is set in the constructor. If we’d like our droid to wander, we would change the
Testclass to the following:The output would be something similar to this:
Notice how the
Wandercontains and delegates to theMoveToroutine.Repeat, Repeat, Repeat …
This is all good but what if we want the droid to be wandering repeatedly?
We will make a
Repeatroutine which will contain a routine to be repeated. Also we will make this routine so that it can take in a parameter to specify how many times we want to repeat a routine. If it won’t take in a parameter, then it will repeat the containing routine forever or until the droid’s dead.The code is easy to follow but I will explain a few things that were added.
The attribute
routineis passed in the constructor and that will be the routine that gets repeated. TheoriginalTimesis a storage variable that holds the initial number of times value, so we can restart the routine with thereset()call. This is just a back-up of the initial state.The
timesattribute is how many times the provided routine will be repeated. If it’s-1then it’s infinite. This is all coded in the logic inside theactmethod.To test this out, we need to create a
Repeatroutine and provide what to repeat.For example, to have the droid wander endlessly, we’d have this:
If we’d call the
updaterepeatedly, we’ll see that the droid will be moving constantly.Check this sample output:
Notice how the
Repeatroutine does not end.Assembling the Intelligence
So far we’re just composing behaviours. But what if we want to add decision making to the droids and build a more complex behaviour? Enter the behaviour trees. This term doesn’t describe what it is and neither do most of the articles that I found. I’ll start with what I want to achieve first and hopefully it will all make sense.
I want to implement the behaviour described at the beginning of the article.
I want my droid to scan if there is a weaker droid in its range and engage it if it is, or flee otherwise.
Take a look at the following diagram. It shows a tree. It’s nothing more than a routine composed of multiple different routines. Each node is a routine and we will have to implement some special routines.
Droid AI (Behaviour Tree)
Let’s break the routines down.
Repeat- is the routine implemented earlier. It will repeat the given routine forever or until the embedded routine fails.Sequence- the sequence routine will succeed only when all the routines that it contains have succeeded. For example to attack a droid, the enemy droid needs to be in range, the gun needs to be loaded and the droid needs to pull the trigger. Everything in this order. So the sequence contains a list of routines and acts on them until all succeed. If the gun is not loaded then there is no point in pulling the trigger so the whole attack is a failure.-
- All the grey routines are leaves in the tree, meaning that they can’t have any subsequent routines and these are the ones that act on the droid which is the receiver.
The above tree represents the very basic AI we wanted to implement. Let’s follow it through starting from the root.Selector- this routine contains a list of one or more routines. When it acts, it will succeed when one of the routines in the list succeeds. The order in which the routines are executed is set by the order in which the routines are passed in. If we’d like to randomise the execution of routines, it’s easy to create aRandomroutine whose sole purpose is to randomise the list of routines passed in.Repeat- will repeat the selector indefinitely until neither of the branches can be executed successfully. The routines in the selector are:Attack a droidandWander. If both fail that means that the droid is dead.The
Attack a droidroutine is a sequence of routines meaning that all of them have to succeed in order for the whole branch to succeed. If it fails, then the fall back is to pick a random destination throughWanderand to move there.Then repeat.
All we need to do is to implement the routines.
For example the
IsDroidInRangecould look something like this:It’s a very basic implementation. The way it determines if a droid is in range, is by iterating through all the droids on the board and if the enemy droid (assuming that the names are unique) is within range, then it succeeded. Otherwise it failed.
Of course we need to feed in this droid to the next routine somehow, which is
IsEnemyStronger. This can be achieved by giving the droid a context. One simple way could be that theDroidclass could have an attributenearestEnemyand onsuccessthe routine will populate that field and on failure it will clear it. This way the following routine can access the droid’s internals and use that information to work out its success or failure scenarios.Of course this can be and should be extended so the droid will contain a list of droids in its range and have a routine to work out if the droid should fly or fight. But it’s not the scope of this introduction.
I won’t be implementing all the routines in the article, but you will be able to check out the code on github: https://github.com/obviam/behavior-trees and I will be adding more and more routines.
Where to go from here?
There are quite a few improvements that can be made just by looking at it. As a first step to test the system out, I’d move the creation of the routines to a factory for convenience.
This will allow to test some scenarios out in a more elegant way. For example to place 2 droids with different behaviours you could do the following:
Of course this is not the best solution by far but it’s still better than the constant instantiation of routines. Ideally the AI should be scripted and loaded from an external source, either via scripting, or at least provided as a JSON for example and have a AI assembler create it. This way the game does not need to be recompiled every time the AI is tweaked. But again, it is not the scope of this article.
Also, how shall we decide which action will take up a turn/tick or is evaluated instantly? One possible solution could be to allocate action points to the droid that it can spend one turn (tick if realtime) and for each action to assign a cost. Whenever the droid runs out of points, then we can move on. We’d also need to track which routine is the current one so we can optimise the traversal of the tree. This is helpful if the AIs are very complex especially in realtime games.
If you think the article was useful and want to get the code, please check the github repo. You can also check back because I intend to extend it and to update it so it evolves into a more complete AI example. As it is my first encounter with AI, there will be lots of things to improve and I am always open to criticism and ideas on how to improve.
https://github.com/obviam/behavior-trees
via obviam.github.io http://bit.ly/2WU6qCb
June 21, 2019 at 01:33AM
The text was updated successfully, but these errors were encountered: