Just a quick post this week to introduce the updates below. I have completed my literature review of behaviour trees and designed my proposed implementation. Details of which I have posted below and will shortly begin two mailing group discussions on. Firstly to raise awareness of this development and secondly to raise any questions or queries before I get too deep into development and secondly to discuss the potential of integrating the behaviour tree design with crystal architect as originally suggested by Pablo.
The other update below is to the project schedule and deliverables post, which has been expanded to list the deliverables I intend on implementing in the remaining 2.5 weeks. This weeks update to this post has also very proudly included the completion of the bug fixing of the refactored sequences. The entire refactor of triggers, rewards, sequences and parameters is now in a functioning state and is partially documented. I am happy with the progress here and will continue to press ahead with the behaviour tree implementation over the next week to ensure this deliverable is also met.
Kind Regards, Sam
The core components of a basic behaviour tree implementation are selectors, sequences, conditions and actions. With just these tools it is possible to recreate most finite state machines (FSMs) in a more intuitive manner. By then adding decorators the behaviour tree becomes a more powerful tool whilst maintaining its intuitiveness.
As conditions and actions can be created by making use of the refactored CEL triggers and rewards respectively the implementation of these core behaviour tree components will serve as a proof of concept of the usefulness of the recently completed Quest refactor.
More complex features of behaviour trees include memory management techniques and a scheduler controlled implementation. Both of these techniques could potentially be very useful within CEL but are beyond the scope of the proposed deliverables and would be unachievable in the remaining time frame of GSoC 2009. However, it is my intention to design the interface in a manner that will ease any future work on these features.
The remainder of this document outlines the tools I intend to develop and document in the coming weeks. Whilst I have provided a brief description here of their functionality, anybody interested in this tool is highly recommended to visit AiGameDev, specifically these freely available resources: A Brief Written Overview and A More Detailed Video Series. I was fortunate enough to sign on to the premium membership of this site with the initial payment from the GSoC project and I would have to say it has been crucial in the design of this tool.
A behaviour tree is to be executed each time an entity needs to decide upon an action. The tree evaluates from the root evaluating each chosen child node. Each node returns a boolean to indicate the success or failure of that node. Therefore, the interface requires an execute method that returns a boolean. As it is intended that the behaviour tree may make use of the refactored celParameters class, this method must receive an argument of this type.
To connect nodes and leaves of type iBTNode, each node must maintain an array of children and provide methods for adding to this array.
To use a behaviour tree, the user must first create each node/leaf and connect them. Once constructed, an entity needing to choose an action will execute the root node which in turn, upon deciding the correct child, will execute the chosen child node and pass on the parameters. Eventually the root node will receive a boolean value indicating the success or failure of its child and, presuming its own execution is complete, will return its own success or failure to the user. The interpretation of this final return status will be implementation specific in so much that a return of false is not necessarily a negative result dependent on the design of the tree itself.
To summarise, the intended iBTNode interface is:
virtual bool execute (const celParams& params)
virtual bool addChild (iBTNode* child)
Selectors and Sequences (plgSelectors)
Selectors and Sequences, or collectively known as composites, are nodes in a tree with multiple children that control which children to execute. Selectors work through the children nodes until one child returns success, if a child returns success the selector stops executing children and itself returns success. However if no children succeed the selector also fails. They are often referred to as OR nodes, as one child or another is executed.
The logical opposite to selectors is sequences. Sequences execute children in order until one fails. If all children succeed the sequence succeeds but if any child fails the sequence immediately fails and stops to execute any further children. They are often referred to as AND nodes, as the first child and the second child and so on are executed.
Due to the name clash in CEL and CS with both the refactored CelSequences and the existing CSSequences, my current design decision is to instead name the sequences composite a SequentialSelector.
In addition, the selector composite by default selects children from left to right (dictated in code by the order they are added to the node) however this selection of one specific child can be implemented in numerous methods increasing the number of behaviours achievable. To demonstrate this capability I intend to implement both a standard selector and a random selector.
To summarise the following selectors are intended to be implemented during GSoC:
Decorators, like selectors before, are nodes in the behaviour tree with the difference being that decorators tend to have one child. Their purpose is not to select a child to execute but to themselves perform some computation before passing execution to the child.
I intend to implement decorators for loops, limiting the number of times a child can execute, and negating the return value of a child (so that a sequence can continue UNLESS a condition has fired.) For a more complete list of example decorators please see http://aigamedev.com/hierarchical-logic/decorator/. If any are of particular interest to readers please let me know and I will try my best to implement them within the time frame.
To summarise the following decorators are intended to be implemented during GSoC:
Conditions and Actions (plgBehaviourTree)
Finally, the leaves of a behaviour tree are made up of conditions and actions. In CEL we already have the concepts of triggers and rewards and as such the implementation of these leaf nodes is partially complete.
In essence actions are essentially rewards except actions must return a success or failure and rewards currently do not. I intend to modify slightly the interface to rewards to return this value and update the refactored rewards to implement this change. This should have no effect upon the quest implementation. All nodes of a behaviour tree will have to implement the interface iBTNode, I do not however intend to add this to the refactored rewards. Instead I will implement a wrapper BTAction the implements the iBTNode interface and executes an action.
Similarly triggers do not directly fit into the behaviour tree paradigm. Instead of waiting for a trigger to fire and choosing an actions based on this, behaviour trees check if a trigger has fired at the time of their evaluation and base their choice on if it has already occurred. Therefore another wrapper class is needed, TriggerFiredCondition. This condition will return false if checked before the trigger has fired and true after.
Conditions are not however limited to triggers firing. Instead conditions may include, for example, checking the health of an entity that the behaviour tree belongs to. A generic condition that can be implemented is checking the value of a parameter. The condition, ParameterCheckCondition, will be set up with the name of the parameter, the value and whether to check for equal to, less than or more than.
Other conditions will be application specific and cannot at this time be implemented. However, users of the behaviour tree can easily create their own conditions by implementing the iBTNode interface within their class and returning a boolean based upon the condition they desire to check.
To summarise the following leaf nodes are intended to be implemented during GSoC:
Please note: This document is a work in progress and will be updated with the projects progress including any updates brought to attention in the mail group discussion.
This weeks work has largely involved testing, cleaning and documenting the code of the refactor. I am glad to say that the vast majority of triggers and rewards are fully factored out and functional within the testing application. My aim is to have the tutorial cover all current triggers and rewards so that there is an exhaustive reference on the purpose and use of each of these tools. Some of you will have noticed my request for examples for a select few of the rewards and triggers I do not currently have covered. I would be very grateful for anyone with experience of these tools to add to the mailing list conversation however they can. For convenience the conversation can be viewed at:
[Cel-main] Example Uses of Specific Rewards/Triggers
Outside of adding these remaining rewards and triggers to the tutorial program, I also need to bug fix the sequence refactor which is currently non-functional and implement cel expressions into triggers and sequences. I remain confident that these goals are all achievable within the time frame of the GSoC project.
However, as stated last week, I intend to start the Behaviour Tree implementation tomorrow. More specifically, I have shortlisted a number of papers and tutorials that I wish to review before proceeding. Over the next couple of days I will split my days between closing the final remaining quest refactor tasks and reading around the topic of behaviour trees. I will then move on to thoroughly designing the behaviour tree implementation and intend to have a first draft interface committed to svn by the time of my post next week. Again I will split my workload throughout this remainder of the next week between the behaviour tree and quest refactor projects. My priority at this time is the behaviour tree implementation as I am determined to reach this significant deliverable before the final google deadline, but I will remain vigilant of my progress on the quest refactor to ensure the remaining refactor tasks are also complete before the final deadline. If need be I will return full time to the quest refactor later into the summer.
As always questions, queries and comments by IRC, email or this blog are greatly appreciated.
Kind Regards, Sam
As some of you will know this past week has seen the completion of the mid-term reviews. I am very proud to have passed this milestone and look forward to completing the project in similar success. Thank you to Guillaume for all his continued support and to the community as a whole for all your help.
Given this mid-point in the programme it seems a sensible time to review the schedule and update it in relation to the progress made. I will shortly after making this post bump the schedule to the top of blog for clarity's sake.
This weeks progress was initially focussed on the factor out of sequences, and secondly on the testing of the refactor as a whole. The testing has highlighted that the sequences are currently non-functional and will require some further work. As previously stated the testing application (appquesttest) is intended to be the basis of the refactored-quest tutorial, and so this time spent testing has also seen further development of the tutorial program.
My intention is to continue working on the refactor up to a strict deadline of next Wednesday's post (22nd July). My reasoning for this is that if work does not begin promptly upon the behaviour tree implementation, I may get stuck throughout the program in developing features for the quest system and fail to produce one of my key deliverables; the BT.
Given this deadline, I am afraid the previous intended delivery of nesting FSM's is unlikely to be accomplished at this stage. However, I have as suggested by google left the majority of the final week for finalising the project. Provided I meet the set deadline of August 12th for the BT work, I will still have a solid working week to work on additional features for the refactored quest.
Therefore, the new schedule splits the refactored quest schedule into achievements in the section "Progress", goals intended for completion before 22nd July in the section "To Do" and tasks to attempt once the BT is completed in the section "Time Permitting." The tasks that will be attempted time permitting, are ordered in the intended series of attempting them. Given it was an originally proposed deliverable I have put the allowance for nesting quests at the top of this list. However, if higher priority in any of these additional tasks is desired please feel free to contact me.
Some may notice that I have removed the suggested potential to factor out sequences entirely, given the amount of work I have put in to factoring them out of quests I believe this would be detrimental to the amount achieved by this project. Therefore, whilst I am not disagreeing with this as a potential development decision I do not intend to complete this during the summer of code program.
I have also moved the additional suggestion to implement cel expressions in sequences up from an additional request into an intended deliverable. From my early look into how to add this feature to triggers, I believe that it should be achievable to add expressions to both triggers and sequences within the new quest refactor deadline. I hope that this can at least partly make up for the delay and possible lack of implementation of the nesting deliverable.
Finally, reader's may have noticed this blog was published a day early this week. My graduation is occurring this Thursday and given the long journey and early start we are travelling up tomorrow. This will limit my productivity for the next couple of days, but I will do my best to stay in contact via email if anyone has any queries or suggestions with regard to this new schedule.
Thank you all again for your support, Sam
With the deadline for the Quest refactor looming I am happy to announce that I am about to commit the final 8 refactored triggers. This will complete the refactor of all rewards and triggers. Leaving just the sequences to be worked on in the remaining days. My intention now is to spend tomorrow working on sequences, Friday on testing the refactor and Saturday cleaning up the code.
Therefore, a working refactor should be commited on Friday. However, this will also still consist of all code for the previous implementation as currently the refactored rewards are running alongside the old rewards to allow for their behaviour to be tested against the original behaviour. Once those tests are completed, I will clean the code by removing all of the previous implementation. My plan is to have this done on Saturday.
This week I have also fixed the parameter based bug that was agitating me during last weeks post. Thank you to Res for his continued efforts to support me on this problem. Finally, this morning I merged again with trunk, as recommended by Guillaume, I intend to do this weekly alongside these posts in the hope of easing the integration of my work with the project at the end of the summer.
As always any questions, please feel free to contact me.
Kind Regards, Sam
Progress this week has been relatively slow. Whilst factoring out the change property reward, I discovered a dependency on Quests that I did not fully understand. I must highlight my thanks here to Jorrit for taking the time last Friday to talk me through parameters and helping me to appreciate their use. This has caused a slight rewrite of some of the existing code that has raised a new bug, that I have been cursing for the past few hours. My patience has worn thin, I will reapproach the problem fresh tomorrow and contact the list if or when the problem continues.
The result of this work has added another plugin to the Quest refactor, implementing parameters outside of quests so that they can be used in rewards, triggers and sequences without any dependency on Quests. The results so far will be committed to svn shortly. Under vknecht's advice I will begin to commit to svn more regularly now.
Finally, as mentioned in opening this has been a relatively slow week. I moved out of my old uni house this weekend and back home for the summer. I fully intend, however, to now make up for this light week by putting in a big effort this week to push to meet the Quest refactor deadlines.
Kind Regards, Sam
This bug is no longer troubling me.
Relieved, Sam :)
|<< <||Current||> >>|