So today is the final day of GSoC 2009 and I have just committed my final major revision of the program. Although this will not be my final contribution to CrystalSpace, I thought it fitting to take the time to summarise the project undergone this summer; both the deliverables achieved and those that were missed.
Dismissed at an early stage due to unforeseen delays, this feature was originally intended but has not been produced. Unfortunately, I can not provide any insight at this time as to how future work could implement this feature.
CEL Expressions in Triggers
Again a personal target that was not reached. The mailing list discussion on this topic faded rapidly and with my faulty system delaying the generation of documentation in the final week, this deliverable was pushed back in favour of the documentation deliverables. Unlike nesting, however, I do have some insights as to how or if this feature should be implemented that I would like to share.
Firstly, my concern comes in that CEL expressions optionally require a parameter block to be parsed. This is readily available in rewards and sequences as when rewards are executed the calling trigger passes a parameter block consisting of the dynamic (@) parameters that specific trigger generates. It was then noted that this could be passed on to sequences when started or finished by the associated reward and therefore CEL expressions have been implemented into sequences (a small compensation for the lack of this feature in triggers.) However, with no data stored in a parameter block inside triggers and certain expressions calling parameter block methods on the optional argument could easily cause runtime errors and, even with these caught and reported, the full functionality of expressions would not be possible.
This opinion though is based on my current understanding of CEL expressions and may be inaccurate. Anyone considering taking up this development issue in future would be wise to consider this but also to read around themselves. Predominately, the following expression tokens need to be considered for their use of the parameter block:
Similarly, the method GetParameter from ParamaterManager that calls for the evaluation of expressions also attempts to get parameters of type dynamic/@ which are only generated inside triggers. Therefore, I think a new method probably should be called to prevent the accidental, attempted use of dynamic parameters inside a trigger.
The remaining list of features not developed were not originally proposed but have been raised in mailing list discussions as being of interest to the community. Anyone keen to take on a quest-related project may want to consider:
- Adding constraints to sequences
- Creating filters for Message Trigger by sender and parameters
- Making quest variables accessible as pc properties
- Standardising the start-finish protocol of sequences
After the sour note of what was not achieved, the following is a brief overview of what I have added to CrystalSpace during GSoC 2009.
Rewards, Triggers, Sequences & Parameters now Quest Independent
One of the largest goals of this project was to factor out Rewards and Triggers from the Quest system where they may be of use to developers in other contexts. This development led to the refactor also of sequences and quest parameters with the creation of cel sequences and the parameter manager. All of these tools can now be created and used without the need to construct a quest.
Added CEL Expression Functionality to Sequences
As discussed in the previous section, CEL expressions can now be passed as parameters to sequences and seqops.
A Brand-New Behaviour Tree Tool for Character Development
Successfully completed in time, CEL now offers the tools needed to create and execute a Behaviour Tree. Serving as a proof of concept for the usefulness of factoring out rewards and triggers from the Quest subsystem, the Behaviour Tree tool is a new AI method quickly gaining popularity in the commercial game development scene to create reactive and complex characters in game environments.
Tutorials on Quests and Behaviour Trees
An original deliverable that, having personally struggled to understand at first the Quest subsystem, is proudly presented to help all new-comers to CEL and this powerful FSM implementation.
It is hoped that the inclusion of such documentation for the Behaviour Tree implementation at the time of its creation will help to introduce existing CEL developers to the new tool, growing the BT user base and resulting in the further development of BT features. Examples of such future BT work could include:
- Crystal Architect integration
Already discussed briefly on the mailing list, this will require the addition of Error handling and (De)Serializing Methods.
The current implementation evaluates the whole tree each frame.
This could be detrimental to a game's performance. Instead a scheduler could dictate how many nodes to expand each frame. A BT scheduler also would allow for the development of more advanced features such as a parallel selector.
- Expansion of the Decorator Plugin
Currently only three decorators have been implemented. These three show the use of a decorator but only begin to implement the functionality. A wide range of possible decorators are possible and will hopefully in time become available in CEL.
A Final Personal Note
To conclude, I would like to thank everyone that has supported or shown interest in this project and a special thanks to Guillaume for being my mentor and helping throughout the programme.
Special mention also to Pablo who has been very vocal in all discussions, without your input a lot of this may not have been achieved. I hope you find my work useful and that we can continue to work on BT integration with Crystal Architect in the near future.
My personal plan, is now to enjoy the next two weeks of my summer and to take a break from my computer (although this will involve at least sometime trying to recover my fallen machine... grumble :( ). I am busy then throughout September with a conference in Milan and moving back to university. However, I will be available at all times by email so will keep track of the mailing list for any quest/bt discussion or anything required of me to successfully finish this programme.
My intention then still remains to continue developing for CS/CEL. My interest for the BT implementation is obvious and I hope to work further on this alongside my PhD that begins in October.
I believe that the project has been a great success, and hope that you all agree likewise. If anyone has any queries or difficulties with what I have produced I will as always remain open to questions and love to help. I hope that this work is found to be useful to the community and that it makes it into a CEL release version soon. :)
Kind Regards, Sam
My post this week is coming noticeably early. Unfortunately this is due to me being able to do little else today. I have been having a few problems over the past fortnight with my machine, but today it decided to finally blue screen and fade away. I am sad to see its demise, but am optomistic about being able to repair it soon.
However, given that we are now in the final week of GSoC I have put that on hold for now and am in the middle of installing/recompiling all the required software/code on an old laptop for me to remain functional. This is not ideal but I almost have a working environment set up again for the final programming tasks and the documentation will be easily producable on this machine.
Although I have lost this day, I am confident that my deadlines will be met for producing the documentation.
With regards to the final programming deliverable of implementing cel expressions in triggers I have had some difficulties but hope the mailing list discussion will overcome these. If anyone reading feels they can help in anyway please contribute to the discussion.
I will not make a further post this week, but I will keep the post on progress below updated.
Kind Regards, Sam
As of 14/08/09
- Parameters, Sequences and all Rewards/Triggers/SeqOps factored out
- Clean redundant code
- Tutorial Program - Partially Complete (appquesttest)
- Update manual pages on quests
- Bug fix factor out of sequences
- Implement cel expressions into sequences and seqops
- Complete questtest
- Write tutorial
- Implement cel expressions into triggers
- Implemented all selectors, decorators and lear nodes
- Basic functioning behaviour tree demonstrated in example program
- Behaviour tree executes inside csDefaultRunLoop
- Complete bttest
- Write tutorial
- Write manual entry
Regrettably Unlikely During GSoC 2009
- Deserialize/Load methods for parsing an XML BT
- Allow for nesting FSMs
- Add constraints to sequences
- Filters for Quest Message Trigger by sender and parameters
- Make quest variables be accessible as pc properties
- Standardise start-finish protocol
I have had a very successful week implementing the Behaviour Tree(BT) I introduced in the design documentation below. I am happy to say that I now have all selectors, decorators and leaf nodes implemented and have a working example of a BT that will form the basis of the tutorial.
The final major obstacle to overcome to reach my originally planned deliverable is to have the BT execute within the default run loop. At this time, the example BT is executed once effectively before the "game" begins. However, I am confident that this issue can be overcome in the few remaining days of coding left.
In addition I am very keen to support the future integration of behaviour trees into the crystal architect editor. I am taking careful consideration of the issues raised both on the mailing list and in irc with regard to this and hope to implement as many of the required methods as I can before the GSoC period ends.
Finally, google has set the suggested pencils down date as next Monday with the remaining week dedicated to documentation. I do not think that the documentation I have left to produce will take me a whole week, however, I do want to ensure that I provide good quality documentation covering all implemented features. Therefore, my plan is to start writing on Monday at which time I hope at the very least the final BT obstacle will be overcome and committed. I aim to complete the documentation by Wednesday/Thursday next week leaving a few days remaining to tackle any left over programming tasks and further develop BT features for CA integration.
As always I will remain available on irc as often as possible and can be contacted via the mailing list. Both discussions of CA integration and BT design are still active on the mailing lists and I appreciate any and all input.
Kind Regards, Sam.
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 :)
:: Next Page >>
|<< <||> >>|