Archives for: 2012

2012-08-20

Final Update Of The Summer

Permalink 17:24:16, Categories: GSoC 2012  

Hello CrystalSpace,
Since my blog post on Friday, it has been brought to my attention that behaviours and the behaviour layer have been deprecated. Several of the apps I have worked on this summer, and in 2009, use these methods. In particular they are: bttest, pathfindingtest, questtest and steering. An example of how to remove this dependence from them can be found in Jorrit's revision 4958. There is not enough time left to make similar changes myself before the end of GSoC to all the apps I have worked on, but I have begun the removal of them from the life sim demo (Please see revision 4972.)

I have also, since the summarising post at the end of last week, kept myself busy trying to create a navmesh for the island level used in the life sim demo. Unfortunately, during construction an assertion fails in celNavMeshBuilder::GetSectorData. More specifically the problem seems to be in the line polyVerts[0] = csVector3(xbase, cell->GetHeight(x,y), ybase); and occurs because at this time csTerrainCell::heightmap is empty.

This will be my last update for the summer as the hard deadline set by google is today. However, I do hope this will not be my last involvement with CrystalSpace/CEL. I will continue to keep an eye on the mailing list and occasionally lurk in the irc channel. Thank you all again for having me for another summer and I hope the code continues to be of use to the community.

Kind regards,
Sam.

2012-08-17

The End of GSoC 2012

Permalink 11:58:50, Categories: GSoC 2012  

Hello CrystalSpace,
With the hard GsoC deadline rapidly approaching, I thought it suitable to wrap up what I have achieved this summer and my ideas for future development that could be done in the areas I have been working.

Event Driven Behaviour Trees.
Behaviour trees have been updated to an event driven design using a wider, more expressive set of termination statuses (See BTStatus in tools/behaviourtree.h.) Instead of evaluating the whole tree every frame, the new trees only expand a set number of nodes each frame. The number of these can be set using the property "Update Rate." These changes will improve the ability to handle large trees or applications with large numbers of characters.

Furthermore, I have implemented the behaviour tree as a propclass allowing a tree to be assigned to an entity. Because of this change trees are now executed by performing the action "BT Start" as opposed to the previous method of executing the root node. Examples of this can be found in appbttest and the Frankie's in lifesimdemo.

The manual coding of trees, however, has remained largely the same - with nodes constructed and children added using the same methods. Therefore, existing implementations only need to replace the previous execution of the root node with the initiation of the propclass celPcBehaviourTree and starting it by the action "BT Start."

Alternatively, behaviour trees can now be designed in and loaded from XML thanks to plgaddon_behaviourtreeload.

Other methods have also been added, most notably the ability to name a node by SetName allowing for clearer debug messages when a node raises an unexpected error and allowing loop decorators to loop infinitely.

Examples of how to load a behaviour tree from xml are available in appbttest and the life sim demo. Appbttest also has an example of constructing a behaviour tree in code and a related tutorial in the cel user manual.

Future work that may be helpful for the further development of these tools include a save to XML method (for outputting trees either coded or loaded and then manipulated at run time), the continued development of additional decorators (expanding the capabilities of the trees) and the incorporation of behaviour trees into csEditor and/or AresEd. I think the latter may be the key to wide spread adoption of this method in future applications and so am very keen to assist with this where I can post-GSoC.

Recast and Detour (R&D) Update.
The R&D plugin has been updated to revision 345 (the currently latest available) and the construction of NavMeshes is now performed in parallel.

I have also fixed a large number of issues left over from the pre-existing implementation of this plugin that required app developers to handle the deletion of variables initialised within the R&D plugin.

Appnavmeshtest and apppathfinding both demonstrate how to construct, display and use navmeshes.

Due to the unexpected discovery of the bugs mentioned above, I did not get time to get around to a number of deliverables that were considered lower priority but would be significant improvements to the R&D plugin. Namely they are the better handling of portals and the partial loading of NavMeshes. The first I think is a key improvement and should be addressed asap as the current method hardly/doesn't work and effectively limits users to only path finding within a sector, not across sectors.

Other issues noted with the creation of NavMeshes that could do with further attention have been noted in the outside sector of the bias level and the interior sector of the castle level.

--
Bias Level: Outside Sector.
When constructing a navmesh for this sector, the process seems to never stop. However, I predict it would given a very long time. The delay is in the double for loops on lines 2343-2345 of celNavMesh.cpp in the function celNavMeshBuilder::BuildNavMesh. Normally tw and th take values approximately in the range 1-20 but for outside they are both over 600. I think this is because the outside sector is huge, but also because it is a very uniform, flat surface. However, the latter should make it very simple to cover.

Castle: Interior Sector.
The navmesh constructed for the interior sector appears to be made up of multiple overlapping (and slightly different) navmeshes. There should be only one. I think this may be related to the handling of portals, because if you generate the navmesh for this sector alone or even with only one other sector it does not occur. As soon as navmeshes are generated for this sector and two others the overlapping occurs. I think that focussed efforts on a new method of handling portals will fix this incorrect behaviour. This problem is less severe than the above, however, as the path finding still works correctly in this sector despite the overlapping meshes.
--

Finally, I have also added methods to PcSteer for adding a HNavStruct if available and then using this when seeking to find a path rather than the bespoke path finding solution previously used. For an example of this use please see appsteering.

The work I have done on PcSteer could be improved by allowing pursue, flee and wander to also use the HnavStruct but I think a more significant change should be made to this plugin.

I propose that the plpfsteer is deprecated and the functionality of pcSteer merged into pcPathFinder. If the merged propclass is given a HNavStruct it can use that to move between sectors and pathfind within (with HNavStruct eventually being updated to have improved functionality between sectors) or alternatively it is given a celGraph to move between sectors and uses it's naeve move directly towards goal position pathfinding within them. It would also then allow methods such as FollowCyclicPath or FollowTwoWayPath to be used with R&D as well.

The new pcPathFinder would then include all methods for moving agents in an environment with the possibility of using either the celGraph or the recast plugin. Rather than the current convoluted architecture where pcPathFinder uses celGraph and pcSteer which may or may not use the R&D plugin.

Conclusion.
In closing, I think this has been a very succesful summer. I feel this year I have learnt a lot more about the architecture of CEL as a whole and the experience of fixing memory management bugs in other people's code I'm sure will be priceless in the future (despite how frustrating it was at the time!)

Last GSoC I hoped to continue working on CS/CEL after the summer alongside my PhD, this never happened because I understimated how much of my life would become my PhD. After this GSoC I will be writing my thesis and trying to secure a job, so I will not make any promises for how much code I will be able to commit but I do hope to still be a part of the community and assist where I can with getting this code merged back into trunk and used more in future games and applications.

Finally I would like to thank everyone that has made this summer so productive and enjoyable. In particular: Anthony for being my mentor, Christian for his input and advice throughout, Matthieu Kraus for some key comments/suggestions regarding R&D and Jorrit, Vincent Knecht & Anders Reggestad for checking out my branch and testing/trying the apps I've worked on. Thank you all.

Kind Regards,
Sam.

2012-08-10

Final Week of Coding

Permalink 16:12:23, Categories: GSoC 2012  

Hello CrystalSpace,
As expected it's been a tough week of coding, but I'm proud to say that as of my latest revision (r4963) appSteering, appPathFindingTest and appNavmeshTest are all working again, with the latest R&D library and without the deletion of variables initialised in either the recast or celgraph plugins. These deletions, left over from LeonardoRD's original work on integrating R&D, were not picked up on when compiling with DLLs but were when compiling with static libs.

Officially this is the last week of coding for GSoC, however, the suggested end of coding is next Monday and I intend to push that to the maximum to complete the last of the original deliverables on my list; adding a working Frankie to the lifesimdemo using the new BT and R&D code. It is not as much as I had hoped to achieve in the lifesimdemo but due to other issues like the bugs mentioned above this will be all there is time for now.

After this the focus is documentation, which I think can justifiably include updating the apps I have worked on to CS::Utility::DemoApplication so that instructions on their use can be displayed by iHudManager and the PrintHelp() method. It will also include thoroughly documenting the changes I have made and the changes I still feel need to be made to pcSteer/pcPathFinder.

I hope you are all happy with the code I have added, and I look forward to helping (where I can) with integrating it back into the trunk.

2012-08-03

Bug-Ridden Week

Permalink 16:40:19, Categories: GSoC 2012  

Hello CrystalSpace,
This week has been decisively marked by Jorrit's discovery of a number of bugs and inefficiencies in the Recast&Detour plugin. I have dedicated my work to fixing these, and hope to have a solution before I need to head off for the weekend. Fingers crossed I can do it in time :) Either way I will commit what I have so far before heading off and finish any problems remaining early next week.

As I am still working on this, I will keep this week's post brief. The most significant commits I have made this week are revisions 4936, which switches to parallel construction of navmeshes, and 4942, which allows pcSteer's seek method to use R&D for pathfinding.

The parallel construction has been tested by a number of members of the community and appears to have sped up construction successfully. The integration of pcSteer and R&D shows how these two can work together. However, there is a lot more work that could be done, as I alluded to last week, to update pcSteer and pcPathFinder. Unfortunately, with the end of GSoC now in sight I will not have time to do so as part of this project. I will, however, make sure to write up all my thoughts on this fully during the write up week and may be able to spend some time on this later in the year.

Next week is the last official week of coding, it's going to be a busy week of coding to meet my last intended deliverables but I am confident that I should be able to complete all top priority deliverables.

But to do that I best get back to the code... :)

2012-07-27

Further R&D Updates, and Concern Regarding PcSteer

Permalink 18:53:44, Categories: GSoC 2012  

Hello CrystalSpace,
This week I have been focussed almost entirely on celPcSteer, celPcPathFinder, celHPath and celHNavStruct. I have spent more time than I care to admit trying to get my head around these, but before I get into my concerns regarding this I would like to briefly comment on the positive outcomes of this week. In particular:

- Revision 4933, which fixes the problems I mentioned in my update to last week's post when saving/loading navmeshes with the new R&D library. These are now resolved, with no changes to the CEL api and so all existing apps using R&D should be able to now use the latest available version of the library.

- Revision 4936 switches to creating NavMeshes in parallel. On my single-core machine this causes a significant slow down. To avoid this, users with a single-core machine can call the thread manager's SetAlwaysRunNow method with true passed as the sole argument. An example of this is included in the message attached to this revision. On multi-core machines this should be faster, any readers with a multi-core machine and willing to test this are greatly encouraged to join in this discussion on the mailing list.(Updated 30/07/2012)

Moving back to my work on integrating R&D into PcSteer, I have noticed significant redundancy between the classes celPcSteer, celPcPathFinder, celHPath and celHNavStruct. In particular celPcPathFinder and celHPath both seem to be designed to create high level paths between sectors. The exception being that celPcPathFinder also includes steering behaviours. I think these classes could do with a significant refactoring. I see no purpose to celPcPathFinder now that we have celHPath. Instead I think celPcSteer should be tidied up, made to use celHNavStruct and some of the functionality from celPcPathFinder included (i.e. cyclic and two way paths.)

Furthermore, some of PcSteer is simply not functional - as noted as far back as revision 3391 by caedesv (Pablo?) This does not seem to have been resolved since but is probably beyond the scope of my summer project.

I also think there may be room for some links between DetourCrowd and the separation and cohesion methods of PcSteer. I have not looked into DetourCrowd sufficiently at this time to comment further on this, but perhaps this would also be a way to improve these plugins in the future.

Overall, I am trying to use this blog post to collate my views but am very keen to hear any feedback at this time regarding these suggested changes. Some of you may have reasons to keep celPcPathFinder for instance or a suggestion for a better refraction? My concern is that as it stands the overlap of these modules is unnecessary and makes choosing which to implement challenging.

Kind regards,
Sam.

2012-07-20

R&D Updated And Functional! :)

Permalink 16:37:33, Categories: GSoC 2012  

Hello CrystalSpace,
I'm very glad to announce that my problems with Google's website have been resolved and I have passed the midterm assessment. I am very grateful for all your support in this project and am enjoying the experience greatly.

This week has been a frustrating, learning experience getting very familiar with the MSVC debugger. My progress so far is that all necessary changes to accommodate the API changes in Recast and Detour(R&D) have been made (See r4930) and all previous changes made by Leonardo and others that were lost in the update have been reimplemented (See r4931).

Finally, revision r4932 fixes a few minor issues that were causing unexpected results when building a navmesh. As far as I have tested both appnavmeshtest and apppathfindingtest are again fully functional as of this update.

Next week my focus will shift towards allowing iPcSteer to use the functionality of these libraries. I will also need to reconsider (with my mentor) my schedule for the remainder of the project. If anyone has any comments on what should be our priorities please feel free to let me know.

Update: There seems to be some issues with saving and loading navmeshes still, I will make fixing these my first priority next week before moving on to iPcSteer.

2012-07-13

The Midway Point

Permalink 11:48:45, Categories: GSoC 2012  

Hello CrystalSpace,
Well we've reached the midway point of the summer (although you wouldn't know from the weather here!) I've been having some trouble this week with the google website after completing my midterm assessment but hopefully this is not a significant problem and I will find out over the weekend if you are all sufficiently satisfied with my progress to continue.

I have begun this week to work on the Recast and Detour (R&D) part of my project. So far this has mainly consisted of getting familiar with the library and Leonardo's previous work implementing it into CEL. I have committed revision 4928 which updates the library files to r345 of R&D and have since tested them in msvc - they do not yet compile.

A number of changes need now to be made to cellnavmesh.h/cpp and cellhpf.h/cpp to accommodate the API changes in R&D since the previous version (187) used in Leonardo's work. In particular I have limited the necessary changes down to the following R&D blog posts:

recast-api-breakage
recast-api-breakage-redux
detour-api-change 2010
detour-api-changes 2011

Once complete I may also need to (re)implement the following changes previous made to fit R&D into CEL:

r4810
r4806
r4084

I intend to work on these updates next week (provided the midterm has been passed successfully) with the aim to have the example apps appnavmeshtest and apppathfindingtest fully functional with the new plugin and latest R&D library by this time next week.

2012-07-06

Load from XML Complete, Moving on to R&D

Permalink 11:46:23, Categories: GSoC 2012  

Hello CrystalSpace,
I have just committed the final deliverable for the behaviour tree (BT) portion of this GSoC project. As of revision 4927 BT's can now be loaded from XML. This functionality is also demonstrated in this revision of appbttest.

As mentioned last week this deliverable is slightly behind schedule, but at only 5 days late and given the significant improvements in the BT code, I hope you all agree that this part of the project has been a relative success - especially given that midterm evaluations are coming up next week! :)

I am taking a slightly long weekend, leaving shortly and returning Monday. Unfortunately I will be offline for all of this time. However please feel free to contact me if there are any suggestions regarding the code or the next stage of the project and I will get back to you asap Monday.

Next week I will begin work on the recast and detour code, but until then I hope you all have a good weekend.

2012-06-29

BT PropClass & Rescheduling

Permalink 18:35:47, Categories: GSoC 2012  

Hello CrystalSpace,

This week I have switched the previous celBehaviourTree to the dedicated propclass celPcBehaviourTree. There were numerous commits but most importantly, revision 4916 includes a fully functional BT prop class and example usage in appbttest.

These revisions also add the abilities to interrupt or reset a behaviour tree and to set how many nodes per frame are parsed.

With the 1st July rapidly approaching, it is apparent at this time that not all goals of the BT portion of this project will be completed as originally scheduled. My mentor and I have agreed that the best way to proceed will be to continue with BT development for now and complete the load from XML deliverable. I will then move on to the Recast and Detour work hopefully by the end of next week and, therefore, not significantly behind schedule.

Finally, I would like to publicly note my gratitude for all the assistance I have received this week. Thank you all - especially Anthony, Christian and Mat! :)

Kind regards,
Sam.

2012-06-22

Reporting and Handling BT_UNEXPECTED_ERROR

Permalink 15:19:25, Categories: GSoC 2012  

Hello CrystalSpace,
As intended this week I have focussed on making more use of the behaviour tree(BT) specific return status BT_UNEXPECTED_ERROR. In particular, revisions 4908 and 4910 add the reporting of nodes not having the relevant children, rewards, triggers or parameters specified first with severity notify at the node itself and then again with severity error if the unexpected error is not handled but propagated back to the root of the tree.

Revision 4908 also added the method void SetName (csString nodeName) so that BT nodes cane be given a name, which is then reported if an unexpected error occurs. This should simplify debugging large trees.

Finally, in revision 4909, I added the method void MakeLoopInfinite () to the loop decorator allowing the node to be set to run forever whilst the child returns BT_SUCCESS. If the child fails, then so does the loop. This will be useful as a root node for many behaviour trees as often non-player characters will be expected to continuously repeat some set of behaviours.

I have begun now to think about the dedicated BT propclass and loading from XML. I hope to make significant progress next week towards at least one of these desirable deliverables before beginning to work on the recast and detour side of this project which is scheduled to begin after next week (for the original timeline please see this post.)

Kind regards,
Sam.

2012-06-15

Back to Coding and 1st Version of Event-Based BT Comitted

Permalink 17:17:52, Categories: GSoC 2012  

Hello CrystalSpace,
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.

Kind regards,
Sam.

2012-06-01

Early Design Decisions & Progress on Event Driven Behaviour Trees

Permalink 21:47:24, Categories: GSoC 2012  

Hello CrystalSpace,
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.

2012-05-25

Coding Begins

Permalink 16:45:05, Categories: GSoC 2012  

Hello CrystalSpace,
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.

2012-05-17

Ready To Start Coding

Permalink 17:56:39, Categories: GSoC 2012  

Hello CrystalSpace,
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
(1)—Tutorial/Documentation

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 :)

2012-04-24

The Start of GSoC 2012

Permalink 17:21:46, Categories: GSoC 2012  

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.
Sam.

2012
 << Current>>
Jan Feb Mar Apr
May Jun Jul Aug
Sep Oct Nov Dec

Search

Categories

Misc

XML Feeds

What is this?

powered by
b2evolution