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.
The current PhotonMap class was painfully slow when accessing the KD-tree for the purposes of irradiance estimation (the final gathering phase of photon mapping). Upon further inspection I found that the tree was implemented as a linked structure instead of the more efficient heap approach and that it was not being balanced. I replaced the PhotonMap with the code from Jensen's book which not only keeps the KD-tree in a heap but balances it before accessing it (in oder to guarantee O(log(n)) performance) and now things are significantly faster. For example, 1M photons used to take over 43 minutes to simulate start to finish (without final gather). Now, this is working in about 30 seconds!
Of course, this could be a fluke, perhaps I have missed something in the new lightmap. However, the results are looking promising:
Now, I need to clean up the gathering phase. The simulation looks better than before but now it is too bright and too noisy. Furthermore, I need to enable Final Gather on Jensen's photon map. It does not implement this out-of-the-box.
I want to re-work Jensen's allocation scheme for the heap. At present, it requires a 'maxPhotons' when you initialize the map and this is all the space that gets allocated. Since photon emission is stochastic you can't accurately predict just how many will be emitted before hand, you can only give a maximum upper bound. In practice this upper bound is about 3 times bigger than it needs to be. A data structure than can take an initial guess and resize as needed would be preferable to avoid the initial over-allocation this causes. This may be difficult as not only do Jensen's functions expect pointers to the photons but it expects them to be stored sequentially which I'm not sure an expanding array structure can guarantee (or allow me to access).
The more at look at the photon map visualizations the more I think that the shadows are there. If I view them from across the room and squint my eyes the density of photons seems to be less in the areas where the shadows from the boxes should be. Furthermore, the whole point of indirect illumination in this scene is to add light to the shadowed parts that direct illumination cannot account for so they shouldn't be as sharp and pronounced as in the direct lighting version.
So, I think it's safe to say that the photon emission phase is okay (or at the very least, it's not the source of the current problems). I went ahead and added some attenuation of the total photon count (now, the power is divided by the total number of photons being emitted) but as a principle of russian roulette you shouldn't decrease the power of bouncing photons so I think I'm going to leave it there.
Given the observation that light is getting under the boxes at the gathering phase I know that this phase needs more work. Furthermore, the kd-tree implementation at this phase is slower than it should be, not to mention the other problems I'm seeing (the really dim results) don't seem to be coming from the emissions phase, I think it's time to turn my attention there.
That should be the mantra of every graphics programmer ... at least, that's what some professor told me one time.
I worked up a direct visualization of the photon emission stage by simply drawing points in space for each photon. I set the color of each point to the power of the photon and now I'm seeing something very important. The power is not attenuating ... AT ALL. That's why we aren't getting any shadows and that's probably why everything is a constant power and too dim.
I thought that I could safely ignore the photon power until milestone 2 but I think I need to deal with it now so that's going to be the current task.
Here's the visualizations:
Note: the number of photons listed is the number of emitted photons. Since photons are recorded each bounce there are actually MANY more being added to the map and drawn. With russian roulette in play, the photons are bouncing about 5 times on average so multiply the number of emitted photons by 6 to get the number being drawn and the number of rays being traced. This is all still happing quite efficiently. The last case has about 6M rays to trace and it does so in only a few minutes. Not bad! Unfortunately, the splatting/final gather phase is painfully slow still. I think it's because the kd-Tree for the photon map is not being properly balanced.
Some Observations about these images:
So far, it's been a lot of house cleaning. There's still several key problems with the photon map algorithm that did not resolve themselves as I expected.
The key change was to the photon emitting phase. I added a progress structure to this phase so that we could see when it was happening and how many rays it was creating. More importantly, I changed the photon scattering code to scatter photons diffusely instead of specularly. In the end, we are going to need both but for now, the diffuse scattering is more important and I don't think the specular scattering was being done right anyways. My hope is that by changing to diffuse and by ramping up the number of photons being emitted we would get better results right away. This has not been the case.
There are two key problems in the final light maps that have yet to be resolved:
While these are not the only problems, these problems are the most troubling ones and ones that I theorized were caused by improper photon scattering.
To proceed, I'm going to finish up the scattering with both diffuse and specular components chosen with statistical russian roulette (exactly as suggested in Jensen's book) and then start working on the splatting / gathering phase of the simulation. The code for this phase comes straight from Jensen's book so mostly I'm just going to confirm that its correct before I start to play with it and debug the implementation.
Here's some visuals for what's going on. These images are the actual lightmaps generated by lighter2. In both cases lmdensity was set to 10.0 so that the images generated would be high enough resolution to examine directly:
Sunday I was in Paris in a tavern called Oiseau on the Avenue de Clichy (near the Moulin Rouge red.) with my girlfriend discussing the topic 'Zombies are evil'. We came to the conclusion that zombies fall in three categories: natural (non-man made virus, evolution, ...), supernatural (voodoo, magic, evil(as in Evil Dead), ...) and science (like Resident Evil, monster of Frankenstein, ...).
With zombies defined as 'reanimated dead organic tissue' mummies and vampires (Interview with a vampire, not Blade style, the body has to die before turning into a vampire, where in Blade it just 'turns' the victims) also fall under it. So do reanimated people having had a cardiac arrest or other and declared clinically dead before having been resuscitated. There for zombies exist!
Anyways made some progress on CSSoC as well, made a pure java software renderer applet with a assxml (assimp xml red.) loader. Since XML is a bit big I also added support for gzipped files to be loaded. Gzip turning a 1.2MB file in 110KB so it's quite a bit lighter on your connection. The models can be limitedly controlled with the mouse, mouse button 1 allows to rotate the object and mouse button 2 zooms.
Unfortunately this blog doesn't support applets so I made a mock-up of what the asset site could look like and hosting it on my site.
On the todo there is:
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
Here are some test cases I'm working with to debug and develop the global illumination changes. They are small tests that display important effects of globally lighting very clearly and have appeared in the literature describing various algorithms for such.
The scene for the cornell box already exists in the 'data' directory of the main development branch but the materials describing the different colors are broken. I instead uses a scene of the Cornell Box for Blender. First I generated a ground truth image using the radiosity system in Blender, then I exported the geometry and fixed up the color materials inside the world file to make sure we can achieve the same result in lighter2. Here are some images to show the differences. I will use images of this scene to show progress through each milestone.
One very interesting test case for radiosity is a sculpture in the Hirshhorn Museum in Washington D.C. by John Ferren, entitled "Construction in Wood, A Daylight Experiment". It was discovered by some of the early radiosity researchers (particular credit goes to Cindy Gorn who first modeled the sculptured and presented it in her thesis) and used it to show how important diffuse-to-diffuse light interaction can be. All of the color visible on the viewing side of this sculpture comes from light bouncing off the surfaces on the back of the sculpture diffusely (not specularly). The result is a structure that looks completely white and boring when naïvely ray-traced or directly lit but vibrantly colorful when a global lighting solution is computed. I will also use this scene to evaluate and demonstrate progress on this project.
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
A New Plan
Thanks to all who offered feedback for my previous post. With the discovery of the GSoC '08 branch for lighter2 with photon mapping plans need to change. I've been examining Greg Hoffman's changes to lighter2 to determine what work could be done and I think there's a good chunk here to constitute a project. Here's my assessment of what the branch contains:
So, it seems given the original content of my proposal and this discovery from last summer that the new course of action should be to work on the photon mapping implementation. So, here's a basic outline of what I could do again welcoming comments:
Milestone 1: Repair
Milestone 2: Improve Quality
Milestone 3: Improve Speed/Features
Concerning the optional task under Milestone 2, Photon Mapping just handles caustics well (it's famous for it) and as such it would be easy to render this if the information about refraction is available in the material structure (namely index of refraction). It could make for some interesting but very specialized effects.
I'm planning about two weeks for each milestone with an extra week for the first one just for getting out of the starting gate. Here's a rough time-line to completion of these milestones:
I want to make sure that the amount of work I'm doing is worthy of a full SoC project regardless of the time frame. I'm definitely slow getting started here and I want to ensure all involved that I will make that up as we go either by putting in extra time now or beyond the scheduled GSoC end. Therefore, I think it is best to make sure I get a project defined that is of a scope appropriate for SoC so that no one feels short changed.
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||> >>|
This is the long description for the blog named 'Blog All'.
This blog (blog #1) is actually a very special blog! It automatically aggregates all posts from all other blogs. This allows you to easily track everything that is posted on this system. You can hide this blog from the public by unchecking 'Include in public blog list' in the blogs admin.