Your browser (Internet Explorer 6) is out of date. It has known security flaws and may not display all features of this and other websites. Learn how to update your browser.
X

Milestone 3

Today we had milestone 3 for the specialization projects at Gscept. For me this means that the project is finished and the next step is the grad show at friday. All milestone deliveries can be found under the “Milestone 3” link in the menu.

Overall I’m satisfied with the result of my project, and have reached my goals.

/Per Erskjäns

 

Behavior tree implementation

I was planning to post an overview of my behavior tree implementation on thursday but ended up fixing some stuff instead, including some minor changes to the data structures for the behavior tree.

Without further dely, this is my behavior tree implementation.

The implementation is a data oriented solution without heritage, virtual functions and recursion. Instead the whole tree is laid out in a flat array in a depth first order.

All nodes share the same data structure;

struct BehaviorTreeNode
{
node_types::Enum node_type;

union
{
u32                       end; //this is the index after the last child
BehaviorFunction   execute;
};
};

there end is the index after the last child for a selector node and execute is a function pointer to a behavior function which takes a blackboard and the delta time as arguments. For example the priority selector (index 0) has (index 9) as end. After the creation of a tree (or loaded it from disk) the array is run through a initiation function to set the correct function pointers.

in run time each AI entity have a behavior tree interpreter which contains a pointer to the appropriate behavior tree and a blackboard with the needed state knowledge for the entity. On each frame an interpreter  function loops through the behavior tree. The parent nodes are pushed or poped to/from a stack and used to decide how to handle a return state from a behavior function.

For now the only parent node types are priority selector and sequence selector since no more are needed for this application. Also the only return states from the behavior functions are FAILURE or SUCCESS. However it shouldn’t be to hard to expand with more node types and return states.

/Per Erskjäns

 

(None) progress report for last week

Here comes a long over due report of what I did last week, which frankly wasn’t much. It feels like most of the week was trouble and bug hunting, with one problem in particular that took a lot of time to fix.

I discovered that something made the frame rate drop drastically then the application had run for like 20 seconds. In the end I managed to fix it by redesigning my system and it actually ended up to be better and easier to work with than the original design. I’m still not 100 % sure what the cause of the problem was but I think it was a memory access or cache thrashing problem then two threads wanted to read from different places in the same array at the same time. However if I didn’t somehow miss it, it didn’t show up in the profiler (Intel Parallel Inspector) as a memory access problem or a data race condition.

Also I had some trouble to get my flocking to work as it should, and the reason for that turned out to be some really simple and dumb mistakes I had done. It was really a case there unit testing would have helped a lot.

Because those things I probably have to cut away more things than I planed to before last week, but on the bright side the flocking now work as it should and today I’m going to implement a predator with a pursuit behavior and flee behaviors for the standard “birds”.

On Thursday I plan to post some pictures how the system and behavior tree implementation is designed and maybe a video of the application in action.

/Per Erskjäns

Behavior tree implementation finished

Today I finished the implementation of my behavior tree structure. Since it is sufficient for this project, the only inner node types are sequence selector and priority selector and the only return states are success or failure, but it shouldn’t be to much work to add usage of more states if needed.

Next week I will implement my sensory system and more behaviors. Hopefully I also have time to do some drawing of my system design and a closer explanation how the behavior tree works.

/Per Erskjäns

First behavior finished

Last week I finished my first AI-behavior which is a wander behavior. The solution is based on the paper “Steering Behaviors For Autonomous Characters” by Craig Reynolds, and isn’t difficult to implement. However I made a very silly and simple mistake with a pointer so most of the entities ended up with the exact same movement. This took much more time to find than it should (don’t do your code checks then you are tired), a very annoying noob mistake.

So far the wander behavior isn’t a part of a behavior tree but I wanted to to finish at least one behavior before creating my tree structure.

This week I will implement my behavior tree structure and the big challenge is that I want to do it in a data oriented way without virtual functions and heritage. The only things I have found on data oriented behavior trees are Björn Knafla’s posts in #AltDevBlogADay and I think I will do something like his example with a traversal stack, but nothing is set in stone.

/Per Erskjäns

Milestone 2

I have added my deliveries for milsestone 2, they can be found in the milestone 2 link.

The deliveries are “project_M.AI.S_ms2_source.zip” with all the source code and dependencies. Also there is “project_M.AI.S_ms2.exe.zip” with a release build. So far the application don’t do very much, there are some entities that move in a straight line with no AI at all. The source code is open source and if you want you can take it and do whatever you want with it. However some of the libraries used have their own licensing so make sure to look at them.

/Per Erskjäns

Back working

Unfortunately I lost whole of last week to a flu, which have totally ruined my time plan. The probabillity that I need to cut some of the things a planed to do is pretty high, but only the future can tell for sure.

So far this week I have finished my entity handling, and started to implement my task scheduler. I aim to have my change controll finished before the end of the week, and hopefully I  can start with my first AI behavior .

/Per Erskjäns

Sick today

Yesterday I was completely out with a sour throat, fever and a killing headache. I’m better today but not really fit for any programming activities. This isn’t good for my time plan but fortunately I have the weekends as buffer time for my project. Now I hope that I’m good enough to work tomorrow, but today I’m going to stay home and cure myself.

/Per Erskjäns

Renderer implemented

I have now implemented my renderer. I’m using the SFML library with an OpenGL context and plan to keep it simple, no bells and whistles in this project since the graphics is not high on my priority list.

I have also started to implement my entity manager/system. It is a component system there  the subsystems only have access to the components necessary for it to do its work. Hopefully I can finish the implementation of that system tomorrow so I can get started with my AI system.

/Per Erskjäns

Progress report

The last few days I have spent my time learning how Intel® Threading Building Blocks (TBB) works. I have also looked at “Smoke” a demo project made by Intel using TBB. I Think I have got a pretty good understanding how TBB works and how I going to design my system. There are still a few things that I haven’t decided how I’m going to do, but this week I plan to design and create most of my system so I have a solid basis for the rest of my work.

Sidenote: Under the day I’m going to update my research document.

/Per Erskjäns