Well I'm back, had a great conference and have dived into implementing the stack-based behaviour tree I discussed here before leaving.
One design change I found necessary was to add another status, BT_NOT_STARTED, to use in resetting and initialising nodes.
Revision 4907 switches from the previous 2009 method of parsing the entire tree every frame to passing a single node every frame. This will make the method far more scalable and should help with debugging as progress can now be tracked in the behaviour tree's stack. This is a significant revision that is key to this part of the project. If there are any comments in particular on this revision I am very keen to hear them.
In a smaller commit, revision 4906 merged all changes from whilst I was away and since I began coding. I intend to complete these merges at least once a fortnight to make the eventual process of merging my branch to trunk far simpler.
That's all for this week, next week I intend to add more to the debugging tools by making better use of the status BT_UNEXPECTED_ERROR and starting to look into loading from XML and making a dedicated propclass for the behaviour tree. Any suggestions either here, by email/mailing list/irc are always appreciated.
First, to quickly wrap up last week's discussion of the problems with a few apps hanging, I have raised a ticket covering this problem (Ticket 103) and will look to help with a solution later into the summer once I am sure to have met the planned deadlines.
This week work moved on to focus on beginning to implement event driven behaviour trees (BTs). I spent some time studying openly available implementations and have made some initial decisions that I would like to discuss briefly.
The current CrystalSpace BTs parse the entire tree every frame starting from the root node. This will obviously not scale well to large trees or games with many trees. Event driven BTs instead remember where in the tree they have reached and parse only active nodes on each callback.
Therefore, my intention is to add a stack of pointers to BT nodes to the behaviour tree and pass a pointer to this to a node when it is executed. This way parent nodes can push their child nodes to the stack instead of calling their children themselves. Then when the behaviour tree receives it's callback it only needs to execute the top node on the stack.
This will reduce the number of nodes executed per callback to a constant number. It should also help with debugging, as by watching the stack a developer can understand which nodes in the tree are being executed and which path has been taken to reach there.
Furthermore, this should allow me to easily add the function of being able to control the rate of updating a BT as the top node can be executed multiple times per callback (with the callback set to either every frame or by time.) On each execution of the top node the subsequent top node may change and so repeat execution of the top node is effectively parsing through the tree.
Whilst exploring existing implementations and designing our solution I noticed that the easiest milestone to add first was Christian's suggestion of extending the termination statuses. Previously a node would indicate only success or failure on termination, but now (as of revision 4899) a failing node can indicate whether it failed cleanly or whether it has exited unexpectedly. (For more detail on why this is useful please see this article.)
This revision will be used more in the upcoming work on event driven BT's as a parent node will want to check the final status of a child node once the child has terminated and the parent has returned to the top of the stack. To do so I intend to add the current status of a node as a public variable of the iBTNode interface.
Please feel free to comment on this blog, email me on the mailing list or catch me in the IRC channel if you have any comments or suggestions.
As mentioned in my proposal I am now leaving for a conference, and so will not be updating the blog next week nor likely to commit any code. However, I do have my linux laptop with me and the source code checked out, so I may get time to think more about the design and look further into prop classes and existing XML code in CEL (as needed for the later BT milestones.) I will update the blog again Friday 15th June.
See you all in 2 weeks time, Sam.
As the first week of GSoC is coming to an end, I thought it best to update the blog with my progress so far. I intend to (as I did previously during GSoC 2009) post weekly on Fridays with quick updates for anyone interested in following the project.
This week has been mostly occupied by getting bttest to work again. It seems there may be a bug in trunk that is causing bttest (and graphtut, steering and walktut) to hang. I have not solved the problem but I have commited a workaround to my branch in revision 4893. If anyone else is having the problem or has suggestions to fix this please join in the conversation on the mailing list (Archived here.)
Revision 4893 also contains a workaround fix to get plgtcpnetwork to compile as DebugWithDLLs in Windows. Which may also be a general problem at this time in trunk.
The final changes in revision 4893 are what I needed to overcome compilation and linking errors in appelcmtst, plg_guiinventory and plg_guiinventory2 due to CEGUI. I think from the discussion on the mailing list these changes were needed only by me.
Since overcoming these difficulties, I have fixed a minor but significant bug in the bttest app that stopped the tree from being evaluated (see revision 4897.)
I now have a working bttest app, a better understanding of my code from 2009 and am ready to start implementing event driven behaviour trees next week.
A quick update and thank you to all who have helped me out the past couple of weeks. Thanks to the mailing list and in particular Christian's efforts I now have a fully compiled and up to date CS and CEL. I have refamiliarised myself with svn-merge.py (I typically use TortoiseSVN but wanted to stick to the tools other CS developers are using for this project), and with my code from the previous GSoC project on behaviour trees. I now feel ready and keen to start coding next week in time for the official start of GSoC.
I include below my proposed timeline and goals, with priorities labelled 1-3 with 1 being the highest:
-Update to event driven BTs (May 21st – July 1st)
(1) -- Focus on debug tools
(2) -- Allow all termination statuses
(2) -- Add load from XML option
(2) -- Create dedicated propclass (set root node, set update rate)
(1) -- Documentation
-Update to latest version R&D (July 1st – July 29th)
(1) -- Allow iPcSteer to use its methods
(2) -- Partial navmesh loading (with missing sector callback)
(2) -- Make navmesh creation parallel
(3) -- Improve function with portals
(3) -- Optimise debug mesh
(3) -- Optimise Terrain
(1) -- Documentation
-Improve life sim demo (July 29th - August 13th)
(1)-- Make behaviours work (perhaps requiring other new propclasses or
fixes to existing ones)
(1)-- Use new BTs and R&D
During this time, I will have one significant break (as mentioned in my proposal) from June 2nd-12th when I will be attending a conference in Valencia. Other than that I am excited to be back and keen to get started :)
Hello CrystalSpace and thank you for again choosing me for GSoC.
Coding begins again May 21st, before then I will be updating this blog with plans for the new project and getting up to scratch with the recast and detour code.
If anyone has any suggestions for behaviour trees, recast and detour or the life-sim demo please contact me :)
Excited to get started again.
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
|<< <||> >>|