Crowds Control

Contributions to Recast/Detour

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 08 Oct 2013 00:00:00 -0700

In a previous post I’ve announced that, as a part of our work on MASA LIFE, the team will work with Recast/Detour and that we would release our updates to the community.

This have been effective since the beginning of the summer and we’re just releasing today a new version which is the first to be used in a released version of MASA LIFE, the upcoming (if all goes well, this week) v1.2. Our work is available on github at https://github.com/masagroup/recastdetour.

Introduced features

Modular crowd framework

DetourCrowd was a rather monolithical, we redesigned a large part of its basic framework with two goals in mind: modularity and usage safety. In the process we introduced several new concepts:

Navigation behaviors, self-contained navigation algorithms defining how agents take movement decisions, eg. how they update their velocity (cf. the user documentation), such behavior is assigned to each agent and used to update it, the existing path following and collision avoidance algorithms were encapsulated in navigation behaviors;
Indirect agents access, forbidding direct read or write to dtAgent, introducing explicit fetch/push queries based on the agent’s id, as a result it is easier to make checks (are we out of the navmesh?) and the users always safely manipulate data (cf. the user documentation);
Modular Update loop, allowing more complex update strategy by supporting the update of part of the crowd in different steps, environment, velocity and position (cf. the user documentation).

Navigation tests

We introduced unit tests on ‘DetourCrowd’ in order to test the new features we introduced. We chose to use Catch mainly because it is dependency free and with an active community.

Additionally we created a simple framework to create functional visual tests for navigation based on JSON configuration files.

Known issues

This fork is still very young and several issues are remaining. The most important being:

Bad usage of the pathfinding queue in the path following behavior;
Dumb neighbors retrieving, we had to remove the previous proximity grid that couldn’t work properly with multi-level scenes;
Removal of the navigation test features from the RecastDemo application, we didn’t took the time to port them to the new framework.

Once we are fully happy with our state, we’ll send a pull request to Mikko and make these updates part of the “main” repository. In the meantime contributions and issue reporting are welcome!

We have nice features in the MASA LIFE pipe that will surely lead to new contributions. I’ll keep the community in touch on this blog or on the Recast Google Group.

A sample iOS application using Ogre 3D

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 13 Aug 2013 00:00:00 -0700

I’m currently working on an iOS demo of MASA LIFE, the AI middleware I’m developping; in fact I’m porting the demo we did for this year’s GDC to iOS. It is called PaperArena, and it is a small capture the flag tank game showcasing the kind of AI you can develop with LIFE. This demo was originally developped for Windows using Ogre 3D.

Long story short, while porting LIFE runtime and the core of the PaperArena code to iOS was quite easy and straightforward, I ran into some problem trying to make Ogre use a UIView that I gave him.

No documentation is available but I found two interesting forum threads, here and there. While providing good base information, none gave a final solution.

After a few hours of work I finally got something running and decided to share it, expecting it might help others and hoping to get some feedback, being neither an Ogre3D nor an iOS expert.

The full repository can be browsed, pulled and forked on github.

Interesting stuffs

The Objective-C side

The app delegate handles the lifetime of the application, it creates the window, the view controller (from an interface builder file) and start the “simulation”. The windows is passed to the view controller because it is needed to properly initialize the Ogre renderer.

 1 - (void)applicationDidFinishLaunching:(UIApplication *)application
 2 {
 3     self.mWindow = [[UIWindow alloc] initWithFrame:[[UIScreen mainScreen] bounds]];
 4     
 5     self.mViewController = [[ViewController alloc] initWithNibName:@"ViewController" bundle:nil];
 6     
 7     [self.mViewController startWithWindow:self.mWindow];
 8     
 9     [self.mWindow makeKeyAndVisible];
10 }

The view controller start method initializes the OgreApplication, the C++ instance that encapsulate the Ogre context and all the actual “simulation”, in this case.

 1 - (void)startWithWindow:(UIWindow*) window
 2 {
 3     unsigned int width  = self.view.frame.size.width;
 4     unsigned int height = self.view.frame.size.height;
 5     
 6     mOgreView = [[OgreView alloc] initWithFrame:CGRectMake(0,0,width,height)];
 7     [self.view addSubview:mOgreView];
 8 
 9     mApplication.start(window, mOgreView, self, width, height);
10     
11     // Linking the ogre view to the render window
12     mOgreView.mRenderWindow = mApplication.mRenderWindow;
13 
14     // Ogre has created an EAGL2ViewController for the provided mOgreView
15     // and assigned it as the root view controller of the window
16     //
17     // Let's first retrieve it
18     UIViewController* ogreViewController = window.rootViewController;
19     
20     // I want to be the actual root view controller
21     window.rootViewController = self;
22     
23     // But i want to add a child link with the ogre one
24     [self addChildViewController:ogreViewController];
25     
26     // add the ogre view as a sub view
27     [self.view addSubview:mOgreView];
28     [self.view sendSubviewToBack:mOgreView];
29 }

On line 6, a sub-view is created, that is the one actually used by Ogre. I would have preferred to be able to directly create such view in the interface builder and even get rid of the parent view but it Ogre creates its own view controller for it (which I failed to replace) and I wanted to keep my own.

This view uses the custom class OgreView (.h, .mm) that “mimicks” what Ogre is expected as a view, ie. the not exported EAGL2View (.h, .mm).

On line 18, Ogre’s created view controller is retrieved, self then takes back its place as window’s root view controller and a parenting link is created between the two view controllers (should help propagating OS events).

Finally, the Ogre view is attached to the main view and sent to the back for other sub-views to be visible.

The C++ side

On the C++ side, the given pointers are provided when creating Ogre’s render window.

 1 void OgreApplication::start(void* uiWindow, void* uiView, void* uiViewController, unsigned int width, unsigned int height)
 2 {
 3     mRoot = new Ogre::Root("", mResourcesRoot + "ogre.cfg");
 4     m_StaticPluginLoader.load();
 5     
 6     Ogre::NameValuePairList params;
 7     params["colourDepth"] = "32";
 8     params["contentScalingFactor"] = "2.0";
 9     params["FSAA"] = "16";
10     params["Video Mode"] = Ogre::StringConverter::toString(width) + "x" + Ogre::StringConverter::toString(height);
11     params["externalWindowHandle"] = Ogre::StringConverter::toString((unsigned long)uiWindow);
12     params["externalViewHandle"] = Ogre::StringConverter::toString((unsigned long)uiView);
13     params["externalViewController"] = Ogre::StringConverter::toString((unsigned long)uiViewController);
14     
15     // Initialize w/o creating a renderwindow.
16     mRoot->initialise(false, "");
17     
18     // Create the window and attach it to the given UI stuffs.
19     mRenderWindow = mRoot->createRenderWindow("",width,height,true,&params);
20 }

And voilà, everything works as expected!

On top of that, this sample application uses CoreMotion for accelerometer/gyroscope control of the camera as well as touch gestures recognizers and more. Once again it’s available on github.

I’m sure I’ve done some bad stuff and that there is a much simpler way of doing all that. Experts of iOS, experts of Ogre, please let me know, I’ll update the application accordingly!

If you are going to GDC Europe next week (19/08/13 and 20/08/13), drop by and say hi (booth #170 on the GDC expor floor). If all goes well for me, you should be able to play PaperArena on an iPad!

Update - 26/8/13

I’ve updated both the code on github and the post. I was previously setting params["externalViewController"] instead of params["externalViewControllerHandle"] which is the actual good name for the parameters. That was in fact the reason why this piece of code was working.

Furthermore I have discovered that the system doesn’t handle well screen orientation when starting in non portrait mode (e.g. when you set the valid orientations from the settings of the app). This needs further investigation.

AI Summit 2013

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 24 Apr 2013 00:00:00 -0700

This long overdue post is about my takeaway from this year’s GDC AI Summit, I tried to organize that in rough categories.

Spatially located data

One key part of an AI system is to have meaningful data as input to the decision-making. In most of the games genres, it is very important to have spatially located data and to be able to extract from these meaningful data.

Several talks focused on this area:

“AI Postmortems - Warframe” by Daniel Brewer (Digital Extremes);
“Spaces in the Sandbox: Tactical Awareness in Open World Games” by Matthew Jack (Moon collider) and Mika Vehkala (io interactive);
From the Behavior Up: When the AI Is the Design - Third Eye Crime by Damian Isla and Christian Baekkelund (Moonshot Games).

Basically, we were presented methods to map various kind of data (cover percentage, distance to objective, probability of presence, visibility, …) to spatial location: positions or areas. This information being design to allow complex queries from the decision-making systems such as “give me the most probable place where the thief is that is not so dangerous and where my teammate can still see me”.

Mika Vehkala presented a system based on an area map extracted from the navmeshes, a runtime job abstraction and a set of runtime traversal helpers allowing the creation and composition of queries. With the same goal in mind (but working with positions) Matthew Jack presented a small domain language allowing the creation of these queries. These little “spatial query” scripts are compiled to byte code allowing a safe usage and providing a chance for optimizations. Daniel Brewer explained how he and his team relied on a area map to implement not only NPCs AI but also a game director on warframe. Those talks showcased different usage:

classical but effective investigation using a propagating and cooling-on-sight heat map of the last seen position of the player;
cover point selection using a distance-to-objective metric to define “good” cover point (between player and objective);
choking point selection by identifying small iso distance-to-objective zones;
pacing monitoring by mapping killed enemies, and taking the derivative of it to evaluate how the player is doing (steady pace toward the objective, falling back, …);
buddy/squad placement using distance-to-objective (e.g. buddy should be ahead of the player) and distance-to-ideal-path-to-objective (e.g. buddy shouldn’t be in front of the player).

Damian Isla and Christian Baekkelund also presented their new game, Third Eye Crime, whose gameplay design is completely based on the occupancy heat map concept. I’m really looking forward to it.

Any decision-making system, be it a lua script or a fancy planner, will look dumb and any behavior designer will be mostly helpless if this kind of spatial queries are not available or not powerful enough. These talks provided very good insights on different approach to implement such system and on what is possible with these.

Utility systems

“AI Postmortems - X-Com - Enemy Unknown” by Alex Cheng (Firaxis);
“Architecture Tricks: Managing Behaviors in Time, Space, and Depth - Infinite axis utility system” by Dave Mark (Intrinsic Algorithm).

A few days after the summit I was telling everyone that I felt utility systems was one of the major topics. While going though my notes for this post I could only find these 2 talks that were talking explicitly about utility system, but well, this is for me part of my main takeaways.

I’ve always thought of “utility system” as a fancy word for saying “turning lots of intractable knobs to evaluate possible decisions and take the one with the highest weight”. The summit didn’t really change my perception.

Anyhow, I thought Alex Cheng presentation of the AI of X-Com interesting in the sense that, from what I saw, the resulting AI is pretty good and the method to get there are pretty simple: At each turn, NPCs can do one action and one movement, every possible one is weighted from a set of rules that depends on the class of the character and the better one is taken.

Dave Mark presented the system he uses in his consulting work. For each possible decision:

Define its weight as the product of an infinite number of axises…
Ranging from 0 to 1…
Mapped from game values (health, ammo, distance to nearest medkit…) using defined bookends and a response curve parametrization of one of the predefined function (linear, sigmoid, logit, …).

The underlying idea is that you control the influence of each axis by tweaking the parameters of the curve. Tweaks made easy thanks to … an Excel sheet. The approach propose a unified way to evaluate possible decision thus limiting the complexity of designing a utility-based system. I’m still not completely convinced that the “infinite” number of axises have any interest, the interaction of more than 2 axises can’t be visualized and with axises more complex than boolean gates (0 before a threshold, 1 after) it’s really difficult to explain, thus control, what is going on.

Given the number of things that are possible with them and the apparent comfort AI devs have with these, I do think it would be interesting to add some utility flavor to something like BTs, through a particular selector node for example.

The next giant leap?

From the Behavior Up: When the AI Is the Design - Shigi by Paul Tozour (Intelligence Engine Design Systems)

This talk started by the hilarious Shigi video, a parody of Siri showing us Paul Tozour vision of world where AI can help with the design process.

The presentation was really interesting, it focused on how to achieve the long term goal showcased in the video. The idea, creating a virtual wind tunnel for game design to test the aerodynamic of player experience.

During the development of City Conquest the team took baby steps in that direction by implementing Genetically evolved generations of AI players that would test the game over night whenever a change to the rule occurred. The analysis of the taken sequence of actions allowed the team to tweak the balancing of the game.

Off the Beaten Path: Non-Traditional Uses of AI - The Restaurant Game by Jeff Orkin

Jeff Orkin started his talk by asserting that, in general, AI is a content problem, the behavior of a NPC is content. For it to be better by an order of magnitude, spending more time on creating the content won’t work as “Human imagination is a limited resource”. His idea is to base future AI on actual players behavior (an idea a friend of mine explored in his phd thesis), record these and replay fragments of the played patterns when it fits. In short, for him, the future AI engine is a search engine.

To validate this approach he did an experiment with a simple restaurant game featuring the interaction between a customer and a waitress. He recorded thousands of play sessions, and crowd sourced the annotation of these transcripts (over 450h of work). In the final game, the player is the customer, the system tries to match his action to one of the transcripts and play the reaction of the waitress. With 167 different ways of asking for the bill, variety is no longer an issue and thanks to the manual annotation the waitress’ mood can be configured for a different experience each time.

These two talks were really interesting and shows that their promise is not so crazy, I believe we will get to this kind of AI in the next decade.

Random notes

Luke Dicken was perfect in his famous role “academics are not evil, please love them”. His talk on planning was seriously interesting though, I have to take some time to go through his papers.
Ben Sunshine-Hill did a nice talk on the interface between navigation an locomotion, it should be shown to anyone puzzled by their navigation engine being not as good on animated characters than on cylinders. I also had a good laugh during his rant on AI devs being proud of unwanted “emergent” behaviors (the infamous “Playmobil, en avant les histoires”-effect). I have an issue though, whenever I meet him I’m starting to hum this song, it’s a pain.
You can find old (and hopefully some of the newer soon) AI summit presentation here.

Conclusion

All in all a pretty solid conference with a large variety of depth level: from a 30 minutes talk on a 25 years old method (half of the seesion “The Next Vector: Improvements in AI Steering Behaviors”) to the very interesing and clever Jeff Orkin talk, beginners and veteran are adressed. This come at a price for someone with decent knowledge of the field: feeling uninterested by 1/3 of the sessions. I don’t know it there is A solution to this problem but I never felt that at the similar Game/AI conference. In any case the remaining is enough for me to go back next year!

LIFE with Recast/Detour

cloderic.mars@gmail.com (Clodéric Mars) — Thu, 21 Mar 2013 00:00:00 -0700

I sent this mail earlier today to the Recast/Detour mailing list.

Hello,

I’m working on LIFE, the new AI middleware MASA is showcasing at the GDC next week. I am sending you this email to announce that LIFE uses Recast/Detour as its built-in navigation solution. I’d also like to explain how and what we will contribute to this great project. We are committed to open source our development on Recast/Detour for the benefit of the community.

LIFE aims at providing a solution for behavior authoring and execution for games and simulations alike. It provides a 3D sandbox where behavior designers can preview, test and debug their work, hence our need for navigation. We ruled out rebuilding a system from scratch, something we had experience doing, and decided to integrate Recast/Detour, thus benefitting from the lean and robust (and, to be honest, awesome) software Mikko and all the contributors have built.

Recast/Detour offers two mature features: navigation mesh generation and queries. but beyond that, we needed a full-fledged reactive navigation solution to make our little simulated autonomous pals able to gracefully move around, aware of their neighbors and environment. We are building this system from the existing DetourCrowd and will release it publicly in the next months as a part of Recast/Detour and under the same permissive licence.

Our first goal is to provide a versatile framework for navigation behaviors thus allowing developers and scientists to develop, test and use their algorithms. We plan to include well-tested and efficient behaviors for path following, collision avoidance and group navigation. We hope these new features will benefit to the whole community and also help it grow.

We are looking forward for your comments and questions. Stay tuned for the upcoming release!

Thanks again to Mikko and the other contributors for making such a great piece of software.

PS. I’ll be at the GDC next week, both at conference (including the AI summit) and at the exhibition on booth #1936 with colleagues to present what we’ve been working on for 1 year: MASA LIFE. I hope you’ll be many to come have a look!

PPS. On the booth, you’ll be able to play a small top-down tank shooter we’ve developed using LIFE for AI, it’s awesomely fun!

Boudica's last stand

cloderic.mars@gmail.com (Clodéric Mars) — Mon, 21 May 2012 00:00:00 -0700

A few weeks ago, I received a mail from a reader of this blog: an ancient history enthusiast.

I use novel techniques to try and identify the UK battlefield where the Romans defeated Boudica in 60/61AD.

Boudica isn’t just a Civilization IV leader, she is a British ancient heroin who led an uprising against the Romans conqueror and was severely defeated at a not yet identified location (interseting how this story is closed from French’s Vercingetorix).

At this point 3/4 of you are wondering how that is related to the topic of this blog. I do hope 1 or 2 are interested in history, for those and the rest, the mail continued.

I have been thinking about crowd control/behaviour modeling as another method to help answer some questions – hence my arriving at your page.

The major objectives he described would be:

Being able to validate/invalidate the locations;
Have an idea of the casualties and especially evaluate the veracity of the Roman writer, Tacitus, reports of 80 000 dead British rebels;
How were the bodies geographically distributed, and thus where could archeological evidences (armors, weapons or gears remains) be found.

Needless to say this is quite ambitious for any individual with existing crowd simulation softwares. This project made me thought of how we could tackle this.

To get a simulation, we’d need a - wait for it (what a cool middle name!) - simulator. First we need to specify the characteristics of the simulation:

is it microscopic (each warrior simulated by an autonomous entity), aggregate (several warriors belonging to a group simulated by an autonomous entity) or macroscopic (simulating macroscopically the various crowd phenomenom - not very adapted for this kind of behavior modelling);
what level of behavioral simulation do we need, we’d surely need planning to handle battle strategies as well as reaction to the opponent moves, but do we need reactive navigation (i.e. maintaining groups, avoiding collisions) or motion coordination;
do we need to involve a physics simulation for realistics hits in fights, projectiles, falls, … ;
what kind of output are needed, 3D/2D rendering, localized metrics (density, number of deads…). A number of commercial crowd simulation software might be able to do help with this: Golaem Crowd or Massive would do fine to model the behaviors and get a pretty rendering but would fall short for data analysis, Legion is designed to study crowd motion but I wonder if modelling a battle would be possible, Masa Sword is designed for combat simulation but the lack of low level behavior and animation wouldn’t allow all use cases, game engines such as Unity provide sufficient AI basics to be able to build such simulator but would need lots of effort. In any case, we’d need to involve specialized software engineers to customize or even build our simulator.

For the resulting simulation to be somehow valid, we’d need to gather information from the domain experts, in this case, historians. In order to model the behaviors at the individual and collective level, military strategies and tactics as well as the warriors behaviors need to be investigated for each belligerent:

What kind of combat arms (infantry, cavalry, …) could have been present?
What weapons were used, how?
What strategies and tactics were used?
How did warriors took advantage of the terrain?
What was the level of discipline?
etc.

This gathering must be conducted by specialists of behavior modeling, they’ll be able to get the relevent data and create the behavior modelizations for our simulator. If we want to involve realistic character visualizations we’ll also need to involve computer graphics artits.

One major point of doing this simulation is to validate potential geographical locations of the battle. Thus we’d need to recreate faithfully the possible setting with the help of GIS specialists and perhaps geologists to get an idea of how the landscape looked like at that time.

Once all of this is done, we would have a configurable simulator, ready to test theories, the fun part would start, finally! To go back to the start of this long article, that’s exactly the part my reader is interested in.

It should be possible to execute a scenario and statistical variants, extract metrics, not to scientifically validate it, the process defined above introduces too much bias to deduce anything, but to get a feeling of its validity. Do not understand me wrong here though, I do think this kind of simulator could help us understand how any historical event took place, it can be another, rather powerful, tool for historians. The interesting part for us, software engineers, is to reduce the work to do to create the simulator and to facilitate the authoring of the behaviors.

Maybe one day, retired history enthusiasts will be able to use our tools, as easily as they edit their holiday movies.

Yet another migration

cloderic.mars@gmail.com (Clodéric Mars) — Sat, 12 May 2012 00:00:00 -0700

The first post of 2012 (in May… shame on me) is about yet another migration of the site!

As you may know Posterous, that I previously used, was bought by twitter. It is pretty sure they will close or at least let die their current service. So I moved everything to GitHub Pages! You can browse and even fork this site’s repository. The setup was a little longer than expected (basically you have to write html and css on your own), but I’m pretty happy with the result and because its basically a git repository of the site sources I have no fear of losing pages. More important, my inner geek is satisfied!

I’ll be back soon (hopefully) with real content !

Formation Sketching

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 09 Nov 2011 00:00:00 -0800

I have updated the Group navigation state-of-the-art report with an interesting article I read a few weeks ago: * Qin Gu and Zhigang Deng. Formation Sketching: An Approach to Stylize Groups in Crowd Simulation. In Graphics Interface. University Houston, Delmar Thomson Learning, 2011

I’ve also set up a static page for the report.

ml-class

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 08 Nov 2011 00:00:00 -0800

I’ve been pretty busy lately following the wonderful machine learning Stanford open course of professor Andrew Ng.

When I learned about this Stanford initiative this summer I was really interested and decided to follow one course just to see how it was done. I chose machine learning over AI because I felt I had more to learn in that field, as a matter of fact I have followed a machine learning course in my final MSc year but never put what I learnt into practice and just remembered enough to impress a recruiter during an interview. I didn’t consider following the database course, but I’m sure I’ld have learn more, but perhaps having less fun…

I’m roughly halfway through the course, here’s my takeover for the moment.

It IS possible to deliver a compelling video course, the key aspects: short segments (~10 minutes), good video and audio quality, simple slides and colored doodles.

The quizzes, both those during the videos and the review questions, are very good to memorize stuffs.

The simple programming exercises debunk the complexity of the algorithms. The use of Octave (a free alternative to Matlab) allows you to focus on the maths not on technical time-consuming stuffs.

I like the way professor Ng puts the emphasis on the intuition of how the system works before he takes us for a tour of the machinery.

Neural networks back propagation is not a magical trick, it’s actually a cost optimization relying on the cost gradient.

Anyway, I think I’d now be able to start tinkering with machine learning in some projects. I hope this experiment will be renewed, I’d like to take another class next semester!

Changes

cloderic.mars@gmail.com (Clodéric Mars) — Sun, 16 Oct 2011 00:00:00 -0700

I’ve been pretty busy this past few months, busy sending resume, cover letters and doing interviews.

Let’s go back in time a little bit, in March my girlfriend and I moved from Rennes to Paris (actually Versailles) for her new work. As I didn’t want to quit my current job at Golaem (and they didn’t want me to leave) we decided I was to work remotly from home and come back to Rennes ~2 times per month. I was able to work quite efficiently but quickly felt isolated working alone in my home office.

In late June, I knew this wasn’t working for me. From July, I worked from a Golaem’s partner office in Paris. This solved the social isolation problem, but as I didn’t worked at all with my officemates, I still had no work interaction beside some mails and IM. I know lots of people work this way without any problem but it seems I personally need to have real time work interactions to keep me motivated.

Anyway, I started looking for a job and now I’ve found a pretty good one! In January, I’ll be lead developper at Masa Group working on high level AI technology.

PS. I’ve converted my “Group navigation state-of-the-art” report to Latex and created a github repository to make the sources openly available, check it here!

Airport hall populated with Golaem Crowd

cloderic.mars@gmail.com (Clodéric Mars) — Thu, 15 Sep 2011 00:00:00 -0700

A new showcase video of Golaem Crowd has been published a few days ago. It features our new integration with the rendering engine VRay, but most importantly (from my point of view) it shows the capabilities of our navigation engine. The animation is not that good though, especially compared to the new things we’re developing.

Anyway this is a great showcase for the navigation engine I’ve been developing since more than 2 years. The path following is natural and the collision avoidances are smooth !

Please enjoy !

Hosted WebGL Toy

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 30 Aug 2011 00:00:00 -0700

I’m so trendy, I now have a brand new github account!

I’m using it both as a git repo for my WebGL experiments and, thanks to their well thought pages feature as a hosting facility for the project itself. You can check this awesome work at paperplane.crowdscontrol.net. Stable versions of the project will be published there.

Don’t get too excited though, there’s nothing impressive to show yet, just a crate to manipulate with the mouse. This is the basis for my world conquest! my hopefully, someday, working WebGL toy. Anyway there’s a ton of things I’ve done for the first time with this little website and spinning crate: working JavaScript, git repository, light css, markdown files, and of course WebGL.

This is so lame for the moment I’m wondering why I’m even writing this, but, heh, I’m a little proud!

Learning WebGL

cloderic.mars@gmail.com (Clodéric Mars) — Sun, 21 Aug 2011 00:00:00 -0700

So this is my new home project, I’m learning WebGL.

I haven’t worked with a new platform in a long time (except 3DVIA Studio, but let’s just say it’s not that fun) and I’m getting quite bored by the usual C++ I’m doing at work; I’m just speaking about the code part, I’m hopefully very interested by the algorithms and software architecture parts. I have several reasons to chose WebGL :

I’m a little familiar with the 3D on the web thing and most of what I’ve seen has not delivered on its promises (VRML, papervision, MPEG-4 System, O3D…);
Some guys are doing really amazing things in webGL;
I never used directly OpenGL or shaders, webGL is an opportunity to get back those basics;
Practice javascript.

Anyway, I’m currently doing those tutorials, so far (I’m at lesson 8) they are really good ! But, as I thing you can’t learn anything without a real project, the objective is to do a working little webapp. My current goal is to implement a Reynolds-style bird flocking algorithm, I’ve never implemented those kind of things in 3D and I don’t need lots of assets to get something ! Once I got this working I’ll work on a shephering game; nothing is designed yet but I think it might be fun.

I’m currently looking at high level 3D libraries for webGL, I was wondering if someone had done a little comparison of those.

Autonomous agents nursery

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 10 Aug 2011 00:00:00 -0700

Finally, we’ve got some Golaem Crowd animated eye candy to show to the world !

Our partner Mikros Image have produced a wonderfull short showcasing our plugin !

We’re now ready to take on the world !

Agents order and more videos at http://golaem.com/golaem-project.

Group navigation state-of-the-art report - Part 3, Who's in charge?

cloderic.mars@gmail.com (Clodéric Mars) — Sun, 19 Jun 2011 00:00:00 -0700

The full article is available here.

Who’s in charge?

In the previous part, we studied how group members are able to maintain cohesion or stay in formation. In this part, we’ll study how the group, a whole, is able to make navigation decisions: path planning, path following, steering (including collision avoidance) and formation changes.

Anchor

While some behavior might be decentralized (c.f. part 1), in order to leverage groups in a context where we need to make them go from A to B, top-down decision making is needed (Musse and Thalmann 2001). A group level process will be able to make the group move while each of its member follows. We call anchor a virtual object that group members use as a reference for their formation or flocking behaviors and to which they delegate some navigation processes. It aggregates various data relative to the group, such as its position, orientation and velocity and it’s where the group level decision-making is done.

Leader

Trying to enforce a strict equivalence between simulated entities and actual characters, lots of works rely on a leader-followers approach. In such approach, one member of a group is the leader where the others are the followers. The leader takes responsibility for the whole group regarding the navigation; it becomes the anchor of the group (Loscos et al. 2003; Qiu et al. 2010). The implementation of such an approach using a navigation engine for independent entities is straightforward: the leader is similar to an independent entity; while the followers uses a subset of the default processes and maintain a reference to their leader.

But the leader can’t reuse the exact same processes of an independent entity. Its navigation must take into account the bulk of the whole group as well as the different locomotion constraints of its followers. It is also better to differentiate the the leader’s own attributes (position, orientation and velocity) from the anchor’s (Millington 2006). Taking all these constraints into account makes the decision-making process of the leader very different from the other members.

Group entity

Noting that the leader-based approach as several flaws, a growing proportion of architectures chose to move the group anchor from the leader to a virtual group entity (Schuerman et al. 2010; Silveira et al. 2008; Karamouzas and Overmars 2010b). This virtual entity is similar to any other simulated entities but doesn’t have visual or physic (i.e. regarding collision detection) representation. In such architecture, the group members are identical to one another. In Schuerman et al. (Schuerman et al. 2010) work, other entities detect groups entities during their collision avoidance process, trying to avoid collisions with groups as the whole. Entities are thus able to simulate the fact that pedestrians tend to avoid to pass through a group. The group entity creates a one level deep hierarchy of entities. This approach can be taken a step further to create groups of groups and so on (Schuerman et al. 2010; Millington 2006) allowing a more structured crowd.

Path Planning/Following

One of the reasons for group navigation is to factorize a costly aspect of navigation: path planning. As a matter of fact the members of a group are expected to follow the same high-level path through the environment, a single query should be sufficient for the whole group.

The most important aspect of group level path planning is to choose how to take the bulk of the group into account. Contrary to a single entity where its bulk can’t be changed and thus is a hard constraint, a group can reconfigure in order to pass through narrower corridors. The query has to be tuned in order to prefer paths on which the group, in its current spatial configuration, can navigate but be able to select narrow passages if necessary. This implies that the cost of falling back to a narrower spatial configuration can be compared to the cost of taking a longer path (Kamphuis and Overmars 2004; Pottinger 1999; Bayazit et al. 2003).

Once the path is computed, the path following process is able to provide local steering orders resulting in the entity following the path. Adapted to groups, this process makes the anchor follow the path. In some work (Bayazit et al. 2003; Pottinger 1999), the group level path following is also responsible for environment aware formation adaptation, allowing the formation to change when the clearance to obstacles changes. The following figure shows how a formation change allows a group to pass through a narrow passage more smoothly.

Collision Avoidance

Groups tend to stay coherent when navigating between obstacles and among other pedestrians, that’s why several work features group level collision avoidance. Numbers of existing algorithm for entities can be applied directly or adapted for group level collision avoidance. As we noted for path planning and following, the main difference between groups and single entities is that their bulk is not a hard constraint. The spatial configuration of a group can be adapted to occupy less frontal space, less longitudinal space or both.

Schuerman et al. consider the bulk of the group as a disc allowing them to use RVO (Schuerman et al. 2010; van den Berg et al. 2008). The resulting collision avoidance is very conservative as the disc is, most of time greatly overestimating the real footprint of the group. Karamouzas and Overmars adapted their own collision avoidance algorithm, based on velocity space sampling and sweep collision test, to work on the oriented bounding box of the group (Karamouzas and Overmars 2010a; 2010b). They further extend the algorithm by allowing formation adaptation. In practice, they generate samples based on velocity changes and formation changes interpolating the current formation with a library of valid formation. Each sample is weighted depending on its distance from the desired velocity and the desired formation and its time to collision. The number of candidate formations is limited to 15 as there’s 5 possible formations and 3 interpolations computed per formation. These limits lower the number of considered samples, preserving the performances of the algorithm.

Peters et al. rule based navigation method is able to handle both formation adaptation and group splitting which is not supported by the previously described methods (Peters et al. 2009). Unfortunately the article doesn’t provide many details on the algorithm.

Those group level navigation methods allows the group to take responsibility for a part of collision avoidance and more easily preserve the group cohesions. The members’ own navigation behaviors are still necessary both to preserve individual behaviors and to avoid remaining collisions.

Conclusion

This review was limited to the navigation aspect of the group, it is supposed to answer to the question: “How to make a group navigate in my simulation/game?”. A group is, most of the time, the result of social interactions and relations between individuals that have other consequences beyond navigation strategy: body language, facial expressions, and speech… For a simulated group to be believable those other aspects must be addressed.

This state-of-the art study was instrumental in the design of Golaem Path upcoming group navigation features (Golaem n.d.). I hope others developers or even researchers in the field will find it useful. I’ll try to update its content as other works come to my knowledge or are published.

Bibliography

Bayazit, O Burchan, Jyh-Ming Lien, and Nancy M Amato. 2003. “Better group behaviors in complex environments using global roadmaps.” Pp. 362-370 in 8th International conference on Artificial Life.
Golaem. n.d. “Golaem Path.” Retrieved (http://www.golaem.com/content/products/golaem-sdk/features).
Kamphuis, Arno, and Mark H Overmars. 2004. “Finding paths for coherent groups using clearance.” Pp. 19-28 in 2004 ACM SIGGRAPH/Eurographics symposium on Computer Animation.
Karamouzas, Ioannis, and Mark H Overmars. 2010a. “Simulating Human Collision Avoidance Using a Velocity-Based Approach.” Pp. 125–134 in VRIPHYS 10: 7th Workshop on Virtual Reality Interactions and Physical Simulations. Eurographics Association Retrieved (http://people.cs.uu.nl/ioannis/interactions/).
Karamouzas, Ioannis, and Mark H Overmars. 2010b. “Simulating the local behaviour of small pedestrian groups.” Pp. 183-190 in 17th ACM Symposium on Virtual Reality Software and Technology. Hong Kong.
Millington, Ian. 2006. “Movement.” Pp. 41-202 in Artificial intelligence for games, David H Eberlyedited by. Morgan Kaufmann.
Musse, Soraia Raupp, and Daniel Thalmann. 2001. “Hierarchical Model for Real Time Simulation of Virtual Human Crowds.” Transactions on Visualization and Computer Graphics 7(2):152-164.
Peters, Christopher, Cathy Ennis, and Carol O’Sullivan. 2009. “Modeling groups of plausible virtual pedestrians.” IEEE Computer Graphics and Applications 29(4):54–63.
Pottinger, Dave. 1999. “Implementing Coordinated Movement.” Gamasutra. Retrieved April 20, 2011 (http://www.gamasutra.com/view/feature/3314/implementing_coordinated_movement.php?print=).
Qiu, Fasheng, Xiaolin Hu, Xue Wang, and Saurav Karmakar. 2010. “Modeling social group structures in pedestrian crowds.” Simulation Modelling Practice and Theory 18:190-205.
Schuerman, Matthew, Shawn Singh, Mubbasir Kapadia, and Petros Faloutsos. 2010. “Situation agents: agent-based externalized steering logic.” in International Conference on Computer Animation and Social Agents, 2010.
van den Berg, Jur, Ming C Lin, and Dinesh Manocha. 2008. “Reciprocal Velocity Obstacles for real-time multi-agent navigation.” International Conference on Robotics and Automation 1928–1935.

How simple rules determine pedestrian behavior and crowd disasters

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 14 Jun 2011 00:00:00 -0700

Reading french magazine Marianne this week-end, I was intrigued by a small short talking about the work of two CNRS researchers on crowd dynamics.

Knowing the prior work of those two researchers (Medhi Moussaïd and Guy Theraulaz), in particular on small social groups (see my group navigation state-of-the-art report.

This article present an cognitive science approach to autonomous navigation based on observation and experimentation. It is quite similar to some of Julien Pettré’s work. To compute the motion of entities, the presented model relies on two simple heuristics computing the direction and the speed of the movement depending on the distance to collision for the available directions. To this “intentionnal” movements, a contact force is added to take into account the occurence of unavoidable collision in high density cases. This addition is interesting as it save the main model from handling those difficult cases ; I should try this!

In the prior art section, the authors compare heuristic base model (such as theirs) to force base model (such as the social forces by Dirk Helbing, on of the authors). They say, and having implemented social forces I agree, that these models are hard to tune and ahve inherent flaws because they model reaction of one-on-one interactions and doesn’t provide a valid solution to combine those forces. Those models are alos very dependent on the framerate due to their integrative nature. This prior art section is really incomplete though, they doesn’t talk about other experiment based models (such as Julien Pettré’s) nor about geometric methods which are really popular (RVO and co.). Their method is not compared to these approaches. I’ll read Medhi Moussaïd Phd Thesis (in french) to see if the comparison work is done in it.

Anyway, and to go back to Marianne’s article, I’m impressed by the communication work that’s been done as they’re cited by general public press (another article in Les Echos was just published)!

Group navigation state-of-the-art report - Part 2, Stay Grouped!

cloderic.mars@gmail.com (Clodéric Mars) — Thu, 19 May 2011 00:00:00 -0700

The full article is available here.

Stay grouped!

In order to get a valid simulation of group navigation we first have to design the behavior of the group members. In this part we’ll study two families of methods to obtain groups: using local rules or following a designed formation. Finally we’ll focus on how a member’s individual navigation behavior is affected when part of a group.

Emergence

In most modern navigation engine, the simulated entities are autonomous, their behavior rely on their local “perception” to take action not on an external choreographer. With this approach in mind, several works relies on decentralized behavior to enforce group constraints.

Flocking

At the core of Reynolds’ work (Reynolds 1987; 1999), three steering behaviors allows entities to flock. For any given entity in the group, separation makes him move apart too close neighbors, alignment makes him go in the same direction as other members and cohesion makes him move towards the group’s COM (center of mass). These simple behaviors allow the emergence of a flock. Others took inspiration from this work and adapt it to their architecture using voting steering behaviors (Hostetler and Kearney 2002) or relying on specific environment abstraction such as grids (Loscos, Marchal, and Meyer 2003) or roadmaps (O Burchan Bayazit, Lien, and Amato 2003; Kamphuis and Overmars 2004).

Social relations

In his recent paper, Moussaïd (Moussaïd et al. 2010), extends the social force model (Helbing, Farkas, and Vicsek 2000) to obtain flocking as well as more structured small formation introducing a communication force. The gaze of group members is attracted by the center of interest of the group; here its center of mass (COM) is used. The communication force tries to limit the gaze deviation by decelerating the entity thus enabling the observed V-like formation (cf. part 1).

In order to take into account social relations between members of the group, Qiu uses a member-to-member influence matrix (Qiu et al. 2010). This matrix is taken into account when computing the attraction between members of the group. This approach allows the definition of one or more attractive (or repulsive) members of the group such as more talkative persons or tourist guides.

More rigid formations

Local rules can also exhibit a more strict formation. Taking inspiration from molecular crystals, Balch and Hybinette designed the attachment sites method (Balch and Hybinette 2000). Each entity, given its desired formation, computes several attachment sites on its neighbors and steers to reach the nearest available. The resulting formation arrangement is a direct result of the attachment sites position and it can scale to any number of group members. But as the attachment rules are local, no control on the formation overall shape is possible.

Choreography

While groups whose members are implementing local rules can exhibit convincing behavior, they can’t take into account the group as a whole and thus are not fully controllable. If an exact group arrangement is needed, some of the behavior must be deported to an upper level of control (Musse and Thalmann 2001). In this part we’ll study the three features needed to make a group stay in a given formation: the formation design, the slot assignment and the formation hold.

Design

A formation is basically a list of slots to which members of the group will be assigned. As we focus on pedestrian navigation, a slot is basically a 2D position relative to the group “center”. In a military context two properties of the slot must be added, as we saw in part 1: the orientation and the role (i.e which kind of entity should be assigned to this slot).

Such a formation definition can be designed manually following military principles or artistic concerns (Dawson 2002). Another approach has been taken by Karamouzas and Overmars (Karamouzas and Overmars 2010), they extracted from the data collected by Moussaïd et al. (Moussaïd et al. 2010) a set of typical formations for small social groups of 2 to 4 members. The following figure shows the three kinds of formations they get for groups of 3; similar formations are obtained for groups of 2 or 4.

Assign

We now assume the formation design is chosen and defines as many slots as group members; if not, simple techniques can be used to select the used slots or create needed slots (Silveira, Prestes, and Nedel 2008). The next needed step before our entities can navigate as a group, is to assign each of them to a slot. This part might seem trivial but should be implemented right to avoid destroying the simulation credibility with traffic jams between members of the same groups.

Implementation-oriented papers (Dawson 2002; Millington 2006) describe different solutions and their quality. As everyone should expect, random or index-based (ith members with ith slot) assignment are most of the time really bad: the entities might have to cross each others and to circle around the group to get to their slot. To avoid this bad result, one solution could be to, sequentially assign to each entity, its closest free spot, this solution is easy to implement and might work but last entities might end up to far slots as the closest one are already taken. The best solutions would be to globally minimize the distance the entities are covering to get to their slots but its implementation would lead to an O(n!) complexity as every permutation would have to be tested.

One solution to get a good result and keep a good complexity is a two steps process. First compute for each members of the group what is their cost to be assigned to which slot, allowing certain slot to be specialized for certain entity roles. Then, from the most expensive to assign to the cheapest assign entities to their preferred available slot. This solution might fail to get the optimal assignment but should have decent result while keeping a low complexity O(n2) (Millington 2006).

Another solution works only when no specialized slots are defined. Given a formation design, first sort the slots spatially; for a horizontal line formation, the slot might be sorted from left to right along a horizontal vector. Then sort the group members in the same way; finally assign the ith entity to the ith slot (Dawson 2002).

Maintain

The formation being built, entities are able to reach their slots and to arrange into the designed formation. Let’s see how they are able to maintain it while the group is moving.

In earlier work (Pottinger 1999), a simplistic approach is taken: once part of a formation, entities are no longer responsible for their steering, their position is set at each time step according to the formation. This solution is fine if the group steering (cf. part 3) is robust enough to handle the desired level of collision avoidance.

Using the latter solution, the members do not have an own steering behavior: it is difficult to get anything but a strictly followed formation. To allow formations of individuals, several works uses a more loose approach, members are given a local goal to reach in order to stay in formation and are in charge of fulfilling this goal. A simple approach is to provide each member with a simple “reach target” steering behavior where the target is its slot’s future position (Karamouzas and Overmars 2010; Schuerman et al. 2010). This approach works better if the slots are within navigable space as shown in Schuerman et al. videos. To avoid this problem, Silveira, Prestes and Nedel define a group potential map using slots as attractors and obstacles as repulsors thus providing to members a velocity that maintain the formation while keeping a smooth path when obstacle are present. It allows entity to break formation to pass through tight corridors and around small obstacles (Silveira et al. 2008).

Group members steering

Whether the group is a flock or a formation, the individual steering behaviors, the collision avoidance in particular, of its members has to be considered. We’ve seen that in some case the individual steering behaviors are disabled (Pottinger 1999). In most work though, the group navigation is designed to work in conjunction with its members’, the main problematic is to blend the individual behavior with the group orders.

In some architecture, each entity has several independent behaviors producing different steering orders that are blended together using weight and priorities. In this kind of approach the group orders are executed by another behavior and are part of the final blend (Moussaïd et al. 2010; Qiu 2010; Hostetler and Kearney 2002).

In most modern architecture, a pipeline of behaviors produce a steering order each element taking the previous into account while enforcing new constraints or orders, the last one being collision avoidance (Golaem n.d.; Mononen 2010). The group orders are implemented as a part of this pipeline, they are fed to the following elements among which the collision avoidance (Karamouzas and Overmars 2010b; Silveira et al. 2008).

Schuerman et al. state that while the same collision avoidance behavior can be used by the entities when they are part of a group, it must be adapted. As a matter of fact, collision avoidance algorithms such as RVO (Van den Berg et al. 2008) try to enforce a safe distance to obstacles and other entities that might forbid tight formations. A “boldness” factor is introduced controlling how likely an entity is to yield to other entities during steering. When a strict formation is desired the “boldness” factor of its members is set high making them only try to avoid imminent collisions (Schuerman et al. 2010).

Bibliography

Balch, Tucker, and Maria Hybinette. 2000. “Social potentials for scalable multi-robot formations.” Pp. 73-80 in IEEE International Conference on Robotics and Automation, vol. 1. San Francisco Retrieved (http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=844042).
Bayazit, O Burchan, Jyh-Ming Lien, and Nancy M Amato. 2003. “Better group behaviors in complex environments using global roadmaps.” Pp. 362-370 in 8th International conference on Artificial Life.
Dawson, Chad. 2002. “Formations.” Pp. 272-282 in AI Game Programming Wisdom, Steve Rabinedited by. Charles River Media Retrieved (http://introgamedev.com/resource_aiwisdom.html).
Golaem. n.d. “Golaem Path.” Retrieved (http://www.golaem.com/content/products/golaem-sdk/features).
Helbing, Dirk, Illés Farkas, and Tamás Vicsek. 2000. “Simulating dynamical features of escape panic.” Nature (407):487-490.
Hostetler, Terry R, and Joseph K Kearney. 2002. “Strolling down the avenue with a few close friends.” Pp. 7-14 in Third Eurographics Irish Workshop on Computer Graphics. Dublin.
Kamphuis, Arno, and Mark H Overmars. 2004. “Finding paths for coherent groups using clearance.” Pp. 19-28 in 2004 ACM SIGGRAPH/Eurographics symposium on Computer Animation.
Karamouzas, Ioannis, and Mark H Overmars. 2010b. “Simulating the local behaviour of small pedestrian groups.” Pp. 183-190 in 17th ACM Symposium on Virtual Reality Software and Technology. Hong Kong.
Loscos, Céline, David Marchal, and Alexandre Meyer. 2003. “Intuitive Crowd Behaviour in Dense Urban Environments using Local Laws.” Proceedings of the Theory and Practice of Computer Graphics 122.
Millington, Ian. 2006. “Movement.” Pp. 41-202 in Artificial intelligence for games, David H Eberlyedited by. Morgan Kaufmann.
Mononen, Mikko. 2010. “Navigation Loop.” Paris Game/AI Conference 2010. Retrieved (http://digestingduck.blogspot.com/2010/07/my-paris-game-ai-conference.html).
Moussaïd, Mehdi, Niriaska Perozo, Simon Garnier, Dirk Helbing, and Guy Theraulaz. 2010. “The Walking Behaviour of Pedestrian Social Groups and Its Impact on Crowd Dynamics” Giuseppe Chiricoedited by. PLoS ONE 5(4):e10047.
Musse, Soraia Raupp, and Daniel Thalmann. 2001. “Hierarchical Model for Real Time Simulation of Virtual Human Crowds.” Transactions on Visualization and Computer Graphics 7(2):152-164.
Pottinger, Dave. 1999. “Implementing Coordinated Movement.” Gamasutra. Retrieved April 20, 2011 (http://www.gamasutra.com/view/feature/3314/implementing_coordinated_movement.php?print=1).
Qiu, Fasheng, Xiaolin Hu, Xue Wang, and Saurav Karmakar. 2010. “Modeling social group structures in pedestrian crowds.” Simulation Modelling Practice and Theory 18:190-205.
Reynolds, Craig W. 1987. “Flocks, herds and schools: A distributed behavioral model.” Pp. 25-34 in 1987 International Conference and Exhibition on Computer Graphics and Interactive Techniques, vol. 21.
Reynolds, Craig W. 1999. “Steering behaviors for autonomous characters.” Game Developers Conference 1999.
Schuerman, Matthew, Shawn Singh, Mubbasir Kapadia, and Petros Faloutsos. 2010. “Situation agents: agent-based externalized steering logic.” in International Conference on Computer Animation and Social Agents, 2010.
Silveira, Renato, Edson Prestes, and Luciana P Nedel. 2008. “Managing coherent groups” Gerard J Kim, Hong Qin, and Nadia Magnenat-Thalmannedited by. Computer Animation And Virtual Worlds 19(3-4):295-305.

Group navigation state-of-the-art report - Part 1, Introduction and Taxonomy

cloderic.mars@gmail.com (Clodéric Mars) — Sun, 08 May 2011 00:00:00 -0700

The full article is available here.

Introduction

Autonomous human-like characters being able to navigate in a 3D environment finding their paths and avoiding collisions while exhibiting a convincing behavior is now fairly common. The popularity and the quality of recent work (Van den Berg, Lin, and Manocha 2008; Pettré et al. 2009; Ondrej et al. 2010; Mononen 2010) shows that the simulation of hundreds of navigating entities is now within the reach of almost everyone. But most of these work focus on simulating lonely entities taking their neighbors into account only to avoid collisions. Like real ones, our virtual humans should be able to walk down the road with their group of friends. Like real ones, our virtual soldiers must be able to march on enemy positions while staying in formation. And like real ones, our virtual tourists have to be able to enjoy their tour of the Mont Saint-Michel following their guide’s umbrella.

Before we start designing and implementing group navigation behaviors in Golaem Path (Golaem n.d.), let’s first see what others have done. This document is a state-of-the-art study of existing work concerning group and formations navigation with a focus on algorithms and implementations. The first part defines the different categories of navigating groups we’re interested in. The second part focuses on how the group members can stay grouped or in formation during navigation. The third and last part talks about the group’s navigation from path planning to steering and collision avoidance.

Taxonomy

Before we talk velocity, steering behaviors and gradient descent, let’s first present the kind of groups we’re trying to make navigate, their characteristics and their constraints. In this part we’ll divide navigating groups in three categories, flocks, formations and small groups resulting of social influences.

Flocks

A flock is primarily a group of bird traveling together but it can be applied to other animal species as well as humans (e.g. a flock of school children is crossing the street to the swimming pool). Entities in a flock travel at roughly the same speed and form a cohesive group without strict arrangement. In what must be the two most cited articles in the field (Reynolds 1987; 1999), Reynolds studied empirically how flocks members move relatively to each others. With simple behaviors he was able to recreate a flock of autonomous entities, we’ll dig into more details in part 2.

Formation

While flocks do not follow more rules than the cohesion of the group, formations are a kind of group arrangement where members need to enforce strict rules. Both in a combat or a parade, the spatial arrangement, i.e. the relative positions of members, is designed for a precise purpose, tactic or aesthetic; it is the first rule that needs to be followed. Secondly, in a combat context, formation gets much of its usefulness from overlapping fields of fire and sight, that’s why the orientation is another rule to be followed (Dawson 2002). The last rule is to assign entities having the right role to the right slot: archers at the back, footsoldiers facing the enemy. As navigation and military simulation are important for real time strategy games, interesting and working solutions has been developed early: Dave Pottinger, who worked on the Age of Empire series, presented his in a Gamasutra article (Pottinger 1999).

Small Social Groups

Beyond amorphous flocks and rigid military formations, groups that are more common in our everyday life are small and their spatial configuration is the result of social factors and crowd density. Two recent survey focuses on those small social groups (Moussaïd et al. 2010; Peters, Ennis, and O’Sullivan 2009), they lead to the same conclusions.

The two studies were conducted from videos taken at public spaces (in France and Ireland). Their observations show that: there are more groups than single pedestrians, groups of more than four are very rare and most of the groups are, indeed, pairs.

More interesting, it appears the formation adopted by the observed groups is influenced both by the lateral clearance to nearby obstacles and by the social interaction between members of the group. When motion is not constrained (i.e. when obstacles are far and the crowd density is low) a group tends to adopt an abreast formation that facilitates dialog between its members. When facing navigation constraints, to reduce its frontal width, the group compact the formation. And when the lateral space between each member become too thin, i.e. when members are shoulder-to-shoulder, the formation is staggered. The bending of the group is, most of the time, forward (V-like formation) to maintain good communication when a backward bending (inversed-V-like or wedge formation) would be more flexible moving against an opposite flow.

Finally, while groups tend to avoid collisions, with other pedestrians or with obstacles, as a whole they are able to split if needed merging back afterwards.

Bibliography

Dawson, Chad. 2002. “Formations.” Pp. 272-282 in AI Game Programming Wisdom, Steve Rabinedited by. Charles River Media Retrieved (http://introgamedev.com/resource_aiwisdom.html).
Golaem. n.d. “Golaem Path.” Retrieved (http://www.golaem.com/content/products/golaem-sdk/features).
Mononen, Mikko. 2010. “Navigation Loop.” Paris Game/AI Conference 2010. Retrieved (http://digestingduck.blogspot.com/2010/07/my-paris-game-ai-conference.html).
Moussaïd, Mehdi, Niriaska Perozo, Simon Garnier, Dirk Helbing, and Guy Theraulaz. 2010. “The Walking Behaviour of Pedestrian Social Groups and Its Impact on Crowd Dynamics” Giuseppe Chiricoedited by. PLoS ONE 5(4):e10047.
Ondrej, Jan, Julien Pettré, Anne-Hélene Olivier, and Stéphane Donikian. 2010. “A synthetic-vision based steering approach for crowd simulation.” in The 37th International Conference and Exhibition on Computer Graphics and Interactive Techniques.
Peters, Christopher, Cathy Ennis, and Carol O’Sullivan. 2009. “Modeling groups of plausible virtual pedestrians.” IEEE Computer Graphics and Applications 29(4):54-63.
Pettré, Julien, Jan Ondrej, Anne-Hélene Olivier, Armel Crétual, and Stéphane Donikian. 2009. “Experiment-based Modeling, Simulation and Validation of Interactions between Virtual Walkers.” Symposium on Computer animation 1-10.
Pottinger, Dave. 1999. “Implementing Coordinated Movement.” Gamasutra. Retrieved April 20, 2011 (http://www.gamasutra.com/view/feature/3314/implementing_coordinated_movement.php?print=1).
Reynolds, Craig W. 1987. “Flocks, herds and schools: A distributed behavioral model.” Pp. 25-34 in 1987 International Conference and Exhibition on Computer Graphics and Interactive Techniques, vol. 21.
Reynolds, Craig W. 1999. “Steering behaviors for autonomous characters.” Game Developers Conference 1999.
Van den Berg, Jur, Ming C Lin, and Dinesh Manocha. 2008. “Reciprocal Velocity Obstacles for real-time multi-agent navigation.” International Conference on Robotics and Automation 1928-1935.

Other resources

Sheep herd photography taken from http://flic.kr/p/Yuy89.
Bastille Day military parade photography taken from http://flic.kr/p/57KrxH.

Golaem Crowd launch

cloderic.mars@gmail.com (Clodéric Mars) — Sat, 09 Apr 2011 00:00:00 -0700

For the past few months we’ve been working at Golaem on our new product: Golaem Crowd, a Maya plugin dedicated to crowd simulation for the VFX and animation market. While I didn’t work on the Maya integration, my work on Golaem Path (navigation mesh generation and navigation behaviors) is a major part of the software and provides much added value.

For the past hours lots of vfx news sites covered the launch and the generated buzz is pretty amazing.

For further information, check www.golaem.com/crowd.

Artificial intelligence for games by Ian Millington

cloderic.mars@gmail.com (Clodéric Mars) — Fri, 25 Feb 2011 00:00:00 -0800

@MJKlaim i’ve got this one. In fact, im trying to get an overview on what’s actually implemented in the real world.

"Founders at work": testimonials from the history of IT

cloderic.mars@gmail.com (Clodéric Mars) — Mon, 03 Jan 2011 00:00:00 -0800

I’ve finished reading “Founders at work” by Jessica Livingston during the past holidays. It’s been a very interesting read. There’s two reasons why I liked this book.

First, it is a valuable resource concerning IT History, a topic I am fond of. As a matter of fact I think anyone should know well the history of his field of expertise. The lack of chronological references in the computer science courses I followed at school didn’t allow me to understand properly how and why technologies (languages, hardware architectures…) rises and falls.

Second, this books shows that there’s no magic recipe for a successful product or business. Some founders are technology enthusiasts, some are driven by money only, some wanted to succeed, some just wanted to have fun. This results in very different companies almost all achieving some success.

There’s a particular excerpt I particularly liked from the interview of Philip Greenspun, co-founder of ArsDigita, it sums up what are my thought on the job of software engineer (and why I insist not to be a programmer).

To my mind, a programmer is not an engineer, because an engineer is somebody who starts with a social problem that an organization or a society has and says, “OK, here’s this problem that we have - how can we solve it?” The engineer comes up with a clever, cost-effective solution to address that problem, builds it, tests it to make sure it solves the problem. That’s engineering. If you look at civil engineers, architects, they’re all dealing directly with the customer and going through the whole process.

[…]

I want them [computer science students] to be able to sit with the publisher of an online community or an e-commerce site and say “OK, I’ve looked at your business and your goals; here are some ideas that we can bring in from these 10 other sites that I built, these 100 other sites that I’ve used.” And be an equal partner in the design, not just a coder.

[…]

I was very careful about trying to encourage these people to have an independent professional reputation, so there’s code that had their name on it and that they took responsibility for, documentation that explained what problem they were trying to solve, what alternatives they considered, what the strengths and limitations of this particular implementation that they were releasing were, maybe a white paper on what lessons they learned from a project. I tried to get the programmers to write […].

The most relevant entry point on computational geometry I know

cloderic.mars@gmail.com (Clodéric Mars) — Fri, 10 Dec 2010 00:00:00 -0800

Originally a response to @MikkoMononen

On crowd simulation validation

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 01 Dec 2010 00:00:00 -0800

This is a response to Mikko’s latest post in more than 140 characters…

Autonomous agents navigation is a very wide topic applied to a wide range of specific domains: Military simulation, public spaces design, games, CG FX and animation, training… Each of these fields has its definitions of a valid human-like characters and while the artistic aspect is very important in games or animation it is not for military simulations for exemple. Validations methods are numerous and each is suited for a few parameters only: - Motion captured data in labs can be used to check agents trajectories and velocities in various scenarios (cf. Julien Pettré work);

Survey can evaluate various visual aspects of virtual humans (cf. Rachel McDonnell work);
Real world video footage can be treated to validate a simulation output;
Hand measured flows (e.g. number of pedestrians per minutes passing through a door) can validate some aspects too;
but most of the time though, the only validation is the expert’s opinion (movie director, military instructor…).

Anyway, in the end, for real-time use cases, validity comes in consideration only after CPU/GPU/memory usage…

CASA 2010 report (part 2)

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 30 Nov 2010 00:00:00 -0800

I’ve been pretty lazy on this blog this past months… Anyway here’s the end of the CASA report.

Crowd Simulation Workshop

There was many presentations during that day, more or less interesting, a few of them staid in my mind since then. The first one was titled “On the interface between steering and animation for autonomous characters” and was presented by Petros Faloutsos.

The authors worked on a problem that every one trying to work on autonomous characters has to face: how to obtain a smooth animation AND an efficient steering behavior (particularly collision avoidance).

As a matter of fact the two problematics are solved separately with, most of the time, a top-down approach:

the steering part is solved in 2D using sliding discs to represent entities, the decision being velocity changes;
the animation engine then chooses the best motion to match the computed velocity.

In ‘dumb’ mode steering can compute velocities that are unattainable using available motion which results in foot sliding and awkward motions. When less dumb, steering has access to a velocity model describing which velocities are valid, this model can be provided directly from the animation engine. But in order to be manageable in terms of computation complexity, this velocity model is often simplistic and the animation problems still occur.

The approach presented here is quite different, no more disc motion planning, but a footprint planner. Constrained by bio-mechanical rules expressing the distance between the two feet, their sizes as well as the pedestrian body size, the planner place footprints in order to reach a goal and avoid collision. The presented videos was impressive, but the ‘real’ paper still have to be published, Faloutsos was talking about SIGGRAPH Asia but it seems they didn’t make it.

The following presentation I’d like to focus on is Jan Ondrej “Collision avoidance from synthetic vision”.

Jan is a Phd Student working under the supervision of Julien Pettré in the Bunraku research group, of which Golaem spun off. This presentation was in fact a real-conditions rehearsal of Jan SIGGRAPH presentation of his paper.

The presented work is quite unique, it propose to solve collision avoidance problem using vision algorithm. A low resolution render of simplified geometry is computed for each entity from its point of view, the result is used by a rather simple algorithm to compute a collision free velocity. And, yes, its quite efficient, and the resulting planning is good (perhaps too good to be human-like, though), anyway let’s see the result.

My major take away on this is the inherent advantage of this kind of vision based algorithm: visibility occlusions handling for free (entities hiding each other, walls of difference heights…). What is costly using traditional geometry queries is almost free here thanks to the render phase. I hope I’ll be able to experiment with this soon !

The rest of the workshop features other interesting talk about various aspects of crowd simulations including:

An overview of Legion software;
A presentation of the work done by Disney Imagineering R&D department and SpirOps on crowd simulation in theme parks;
An overview of Ming Lin’s UNC Gamma group work;
Various presentation about Dublin Trinity college GV2’s work on a populated virtual Dublin.

An interesting workshop and the chance to meet the cream of crowd simulation researchers !

CASA 2010 report (part 1)

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 23 Jun 2010 00:00:00 -0700

Well It’s been a long time since I posted here… I’ve been pretty busy since the beginning of 2010. Anyway, here’s a report of the part of this year CASA I attended to.

CASA, the yearly conference on Computer Animation and Social Agents, was held in St Malo, France, from 31/05/10 to 03/06/10 (further information here). As its name implies, the conference focuses are:

Animation techniques (motion capture, motion control, physics-based animation…),
Social agents (emotions, facial animation, crowd simulation…).

During the conference, I only attended to Craig W. Reynolds keynote and to the collocated crowd simulation workshop.

Craig W. Reynolds Keynote

Craig Reynolds is to autonomous agents navigation what Louis Pasteur is to vaccination, he virtually invented the field. His seminal work of 1987 introduced steering behavior, simple rules to models the way autonomous agents navigate in groups. When I worked on the bibliography of my master’s thesis, I was amazed to see that almost every paper I read was citing this 1987 paper or its 1999 little brother; Google scholar count more than 3000 citations! One other thing that is quite interesting about Reynolds work is its rarity, I personally know only those two articles (and google scholar tends to agree). Needless to say I was really eager to attend to the legend’s talk.

Well, I was quite disappointed.

The talk he gave was titled “Crowds and emergent teamwork”, it presented Reynolds observation on emergent constructions in nature, done mostly by insects (ants, termites, bees…), and his attempts to design autonomous agents able to do the same. The final model gave agents simple rules to add bricks to the construction. The same king of emergent construction was observed. The rest of the keynote was filled by what seems to be the entire flickr account of the host : insects construction (no global plan but a functional emergent structure), human constructions (everything is designed globally)… Some aspects of the keynote were interesting but nothing really new, controversial or brilliant… I do think my expectation were too high though… The crowd simulation workshop report will follow shortly…

std::vector is NOT a std::vector containing bools

cloderic.mars@gmail.com (Clodéric Mars) — Mon, 15 Feb 2010 00:00:00 -0800

Everything in the title, but let me explain… Lately I’ve spent a lot of time trying to make a serialization/deserialization work with the huge piece of software I’m working on at Golaem. Anyway I came across a strange compiler error when trying to deserialize a std::vector<bool>. Here’s what our serialization engine is like:

 1 template<T>
 2 void read(std::vector<T>& myVector, Bitstream myStream)
 3 {
 4   unsigned int size;
 5   read(size,myStream);
 6   vector.resize(size);
 7   for (unsigned int i = 0 ; i < size ; i++)
 8   {
 9     read(vector[i],stream);
10   }
11 }
12 void read(bool& myBool, Bitstream stream)
13 {
14   ...
15 }
16 template<T>
17 void write(const std::vector<T>& myVector, Bitstream myStream)
18 {
19   unsigned int size;
20   write((unsigned int)myVector.size(),myStream);
21   for (unsigned int i = 0 ; i < myVector.size() ; i++)
22   {
23     write(vector[i],stream);
24   }
25 }
26 void write(const bool& myBool, Bitstream stream)
27 {
28   ...
29 }

The serialization worked ok, but when trying the deserialization I got a cryptic compiler error:

impossible to convert from std::_Vb_reference<_Sizet,_Difft,_MycontTy> to bool &

WTF ? This code worked perfectly for doubles, ints and other basic types bools should be fine no ? After a quick google and follow links session I stopped on the cplusplus.com reference page of the std::vector. You should go and read this page completly, yep now ! I give you a few seconds… OK you should’ve finished now, and yeah, you read well, std::vector<bool> is a template specialization of std::vector<T> and it does not have the the same properties: std::vector<bool>::operator[] doesn’t returns a reference to a bool but a specially defined type. I love C++ and especially the STL… Yes, in most cases it’s transparent because this type defines a transtyping operator to bool. Yes, it is designed to save space as each element of a std::vector<bool> takes only 1 bit. But, it is inconsistent (std::deque<bool> is a std::deque of bools), opposed to the basic principles of c++ templates, and, apparently not normalized (see this open letter wrote by Herb Sutter the day i turned 15). Another good joke from our pals at C++ ISO committee…

Aggregate Dynamics for Dense Crowd Simulation

cloderic.mars@gmail.com (Clodéric Mars) — Mon, 30 Nov 2009 00:00:00 -0800

Ming C.Lin’s lab latest work in crowd simulation has been featured in two recent publications from MIG (International workshop on Motion In Games) 2009 and SIGGRAPH Asia 2009 (the article is already published on the author’s website). The method presented int those articles, particularly the latter one, is designed to simulate the navigation behaviors of tens of thousand pedestrians at interactive rates. Let’s see first the eye candy !

Impressed ? So do I, let’s see how it works. This approach combines microscopic goals with macroscopic flow simulation:

Each agent is described by its position and its current velocity;
A desired velocity is computed by a global planner (roadmap based path planning for example) for each agent;
The navigable space is divided in cells, in each cells a flow of particles is computed using the current velocity of the agents in the cell and their density;
Given those initial computed velocities the global particle flow is solved at the grid level computing new velocities for each cell;
For each pedestrian, a new velocity is computed taking into account the desired velocity and the flow velocity weighted by the local density (The more dense the flow is, the morethe agent’s velocity is influenced by the flow’s);
Finally a simple collision detection and resolution is applied.

Both the visual results and the computation times are really interesting ! Two major problems are still not addressed: no collision prediction (two groups heading towards each other won’t try to avoid before collision detection) and no way to add social convention to the avoidance behavior (favor one side of collision avoidance, avoid splitting groups…). This method should be great for dense crowds and/or used as a low LOD for navigation behaviors (this will be the topic of the next article !).

Bibliography

Narain et al. Aggregate Dynamics for Dense Crowd Simulation. SIGGRAPH Asia (2009)
Lin et al. Interactive Modeling, Simulation and Control of Large-Scale Crowds and Traffic. MIG (2009)

Crowds control has moved

cloderic.mars@gmail.com (Clodéric Mars) — Sun, 29 Nov 2009 00:00:00 -0800

I just finished moving the site to a brand new wordpress hosting of mine, less tinkering and more posting I hope. Also gotten a dedicated domain name www.crowdscontrol.net. Sweet !

Report: Autodesk virtual entertainment conference

cloderic.mars@gmail.com (Clodéric Mars) — Thu, 01 Oct 2009 00:00:00 -0700

Tonight, Autodesk gave a “virtual conference” featuring talks about their products, live-broadcasted, for free on their site. I virtually attended to the portion I was interested in : Ubisoft talking about AI and animation in Prince of Persia.

After an epic struggle with RealPlayer (who still uses this piece of *** by the way ?) I managed to get the live feed a few minutes after the start.

The prince was not alone, Elika was here

The focus of the talk was the character “Elika” from the Ubisoft’s 2008 version of Prince of Persia. This character is non playable but follows the player’s character, the prince, throughout the game. She is designed to help the player but never get into his way.

But their relationship was completely artificial

After a few character design considerations, the first topic was the AI used to tell Elika how to move around the prince. Its main objectives on this are :

Elika must not harm the 3 Cs (character, control, camera) that is provoking collisions with the prince, occluding the camera…
The AI has to make sure Elika appears on the screen as much as possible as naturally as possible (no teleporting, avoid getting stuck…) ;
As the social relation between the two characters evolve during the game (from strangers to friends), the behavior of Elika must reflect this.

Basically, what is used is a set of rules taking the state of the prince as input and outputting goals for the placement (for example distances, materialized by the circles in the first screenshot). Very few details are given on this.

To give the player a feel on what’s the relation between the character, a set of rules are added ; the more friendly they are, the more Elika will look at the prince and be near him.

All they needed was good animations

OK, so here comes Autodesk and their realtime inverse kinematic solver, HumanIK, which is already integrated with Ubi’s home brewed engine used for Assassin’s Creed. They use this middleware for two things :

Ground the characters, that is apply kinematic constraints for each foot to be layed on the ground without colliding with it. It seemed this IK wasn’t applied during movements as the feet where colliding with the ground when the prince was running on a slope.
Retarget the hands during acrobatics, for example putting the hands in the holds while climbing.

The IK solver is used on the prince and Elika, it is pretty efficient as it doesn’t has any impact on the framerate. The speaker concluded on Human IK praising its easy configuration despite the huge amount of tweakable parameters.

Before concluding the talk, one last problematic was addressed: how are handled the situation were one characters prevent the moving of the other. But as the rest of the talk, this topic was treated too quickly. I did not had the time to wonder in which cases the AI couldn’t prevent this that the talk was finished.

To conclude on this virtual conference, it was interesting (both the concept and the subject) but it was too much rushed and dense…

Minkowski sum

cloderic.mars@gmail.com (Clodéric Mars) — Fri, 18 Sep 2009 00:00:00 -0700

Since the end of my master’s internship I hadn’t really followed what was going on in the academic world about autonomous agent steering. I’ve done some catchup lately ; this post is a preamble to some article report I’m planning to do. Here it is, a few slides about the Minkowski sum, a fun geometric function used notably in motion planning.

SIGGRAPH: day 4

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 12 Aug 2009 00:00:00 -0700

This Thursday was my 4th day for this SIGGRAPH, it was also the last day for the exhibition. After a little sleepover my day started by the fist session of technical papers dedicated to character animations, really interesting but quite complex for my bad skills in the domain.

Dextrous manipulation from a graping pose. This paper presents a way to compute a character’s hand motion from the motion of the object it handles. As I understand, once the hand has grasped the object, the system will handle its movements taking into account the friction coeficient of the material (but not its weight).
Optimal Gait and Form for Animal Locomotion, is a method able to automatically generate the morphology and the motion for any animal having any number of legs. The animal is described using cylinders of variable sizes and some constraints. Their method is able to recreate belivable horse, giraffes, etc… They can even create motions for imaginary animal with 5 legs (the video is watchable here).
Performance-Based Control Interface for Character Animation. The work presented here is quite impressive and could be immediatly applied to game consoles. The authors original observations is that with the current trend for motion-driven games inputs (wii, project natal…), soon we’ll be able to match exactly the character’s motions to the player’s. But in some cases (climbing a ladder, jumping on a trampoline), the user can’t reproduce the movements in his living room. The presented method is able to match the player’s motions type to a type of character’s motion while keeping as much 1 to 1 motion mapping as possible. On the ladder example, the arms and hip motions of the players can be mapped directly on the character while the rest is taken from offline recorded motions.
Detail-Preserving Continuum Simulation of Straight Hair. I must admit I did not pay that much attention to this talk…

The following session I attended was called “Effects Omelette”: 4 talks about various movies special effects.

People from Disney animation talked about how they setup the production pipeline of Bolt in order to produce only one movie in 2D and stereoscopic 3D.
“Virtual” taylors from Pixar gave a talk about how they designed the characters clothes in Up. Pretty interesting to see how they “virtualized” traditionnal tayloring techniques in order to get realistic looking clothes.
One of the technical guys who had worked on Up talked about the net simulations he designed (in fact it was the same piece of work that was used for the ballon canopy).
Finally, Digital Domain presented how they simulate the Eiffel tower collapsing in GI Joe, introducing their talk by “The movie has been released last week, surprisingly it has some good reviews !”…

The afternoon, I explored the third floor : modern art, scientific posters and japanese presenting weird, but interesting, “emerging technologies”. I then attended to a production session about how they 3d-printed every faces in “Coraline”, very impressive ! But it was quite a paradox to learn that, for the faces, the created 3d models, animated them for lip synching and facial expression and then printed every frame to recreate, in stop motion, those animations.

This thursday night was the official reception night: New Orleans Mardi Gras, fanfare and buffet.

SIGGRAPH: day 3

cloderic.mars@gmail.com (Clodéric Mars) — Fri, 07 Aug 2009 00:00:00 -0700

Wednesday had been quite a busy day for me, I started the day at 8:30 for a group of technical papers presentation called “Motion Synthesis and Editing”. I’m really not a specialists but it was in interesting, there was three presented papers:

Generalizing Motion Edits With Gaussian Processes, it shows a method to refineexisting motions via editing them automatically based on the samples of the desired edit, I didn’t quite get everything (too early I think) but it seems powerful;
Optimization-Based Interactive Motion Synthesis, the described platform, given a goal and constraints, is able to synthesize the motion needed to attain that goal by optimizing different physical parameters, the article is waiting for me to read it;
Lie Group Integrators for Animation and Control of Vehicles, the algorithms shown here are able to synthesize the motion of a non-holonomic vehicles via optimization given a goal and some constraint using the Lie Group, I was quite impressed by the result they get but after the talk I was told by Stéphane that those kind of stuff was known in robotics for years.

I then attended to the third keynote of this SIGGRAPH: New York Times Steve Duendes talking about data visualization and aesthetics. As a follower of blog dedicated to the subject such as Flowing Data I really enjoyed the talk, it seems quite odd to find this subject at SIGGRAPH though. As nothing really interested me in the beginning of the afternoon, I took this opportunity to do some light tourism. It was pretty hot but New Orleans has some cute corners. I spent the end of the afternoon on technical stuffs: a nvidia talk about their scene graph and how its interactions with other of their stuffs and a chat with an Autodesk engineer about Kynapse, their solution for virtual characters pathfinding, steering and a little bit of AI. I then joined other french SIGGRAPHers for a drink and a dinner, that’s why you didn’t have the pleasure to read my prose yesterday.

SIGGRAPH: second day

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 04 Aug 2009 00:00:00 -0700

This tuesday was the second day of my first SIGGRAPH, not so great though… Let’s evacuate the disappointments:

Thinking that they got a booth at the main exhibition, I was too late to get an invitation for the Lucas Film little party (not so bad as my feet are pretty ruined right now);
The exhibition in itself is a disappointment to me, the booths are really calm, there’s nothing spectacular, and last, but not least, there aren’t many (new) opportunities for Golaem (potentials customers or partners) ;

On the bright side:

This morning Will Wright kenote was really really cool ! He talked about lots of things including human perception, cognitive load, convergences of entertainment medias, social hiveminds & how to use dedicated fans work to improve the experience of casual ones. The way he considers as “entertainment business” sports, TV, videos games, but also painting, music, theater etc. annoy me though.
I learned quite intersting stuffs on the Intel booth following a presentation about Larabee (their new processor featuring both traditional x86 and scalar processor on many cores) programming and getting a demo of Parallel studio (plugin to visual C++ allowing the profiling and debugging of parallel code). I had a weird talk with some of their devs though: - “Is it possible to use the open source version of TBB (Thread Building Blocks, a multithread C++ API) in a commercial product ? - “You’ll have to check with your lawyer.” - “Hum, but what Intel’s lawyer would say about it.” - “We don’t know but the official statement is that its Intel best interest if you use it.”
I got two Pixar’s renderman teapots !

Day two is over.

First day at SIGGRAPH

cloderic.mars@gmail.com (Clodéric Mars) — Tue, 04 Aug 2009 00:00:00 -0700

I’m happy to be at SIGGRAPH this year, throughout the week I’ll try to post little reports of what I’ve done there. After a very long trip (3 flight and a delay of 2h30 at Atlanta), Stéphane and I arrived at our hotel in New Orleans just in time to dinner and go to bed.

Day 1 - First conference day.

The conference start badly for me, my registration form had been lost but the payment had been made… 2 hours later and a few call (thanks Stéphane) to France and I was in, excited like a kid at he zoo ! The first session I attended was featuring the ACM SIGGRAPH award and the keynote of Randy Thom a famous sound designer. The awards was given to great researcher and artists, no one I knew except Rob Cook, the guy who created Pixar’s Renderman, he got The Steven Anson Coons Award. The keynote by Randy Thom was quite a disappointment, this guy, who has participated in tons of movies, chose to talk about “Designing a Movie for Sound” by presenting the work of others: Apocalypse now and Wall-E. The keynote was essentially excerpts from those 2 movies, interviews of people who had worked on (From the DVD bonuses concrning Wall-E) and common sense.

On the afternoon, I started by the screening of the nominees at the animation festival, with lots of great stuff, by the way the french touch won again :) Next was 4 interesting talks about animation and physics in games and movies. These did not features technical breakthrough but industrial “real world” implementations of advanced techniques. I was particularly interested by the Pixar guy talking about the physic simulation of the balloon canopy in “Up”. Last, but not least the technical papers fast forward. The rules are simple: each team presenting a technical paper at SIGGRAPH this year has to present his work in 50 seconds, some sort of teaser for the talk. Some were really funny, some were really impressive, some were really shy and most of the asiatics team choose to present a video with a recorded comment instead of talking… The 2 hours felt like two minutes ! I want more ! That’s all for today, tomorrow the exhibition begins !

Paris Game AI Conference '09 (part 2)

cloderic.mars@gmail.com (Clodéric Mars) — Sun, 02 Aug 2009 00:00:00 -0700

In this second part I’ll talk about the presentations of day two.

Day Two

Panel talk: Advices and tales from the trenches.

As I’m not that familiar with game industry this panel about how the work is in game studios was very intersersting to me. What they emphasized most was that it is important to have done, and finish, something yourself (a small game for example) before starting to work in a studio. I know they were trying to say “Young programmers you must know and prove that you know how to finish a project and make things work.” but to me it sounded like “I prefer a tinkerer who can do everything quick and dirty to a software engineer who knows it stuff but haven’t code pacmans since kindergarten”. As I am much more the second type of guy, to me, the first type can make things work but doesn’t see the big picture, he is unsuitable for a big project ; a teacher of mine use to say “Knowing how to make a toolshed in your garden doesn’t help you conceive a 60 story building”.

Multi-Unit Planning with HTN and A* - William van der Serren, Independent AI Consultant at CGF-AI

This talk was about an assault planner accessible from a website. The planner finds the best course of action for several units in order to start the battle in good strategical postitions. The whole thing is an A* goal oriented planning inside a graph which vertex are the possibles tasks. Task are described as HTN and weighted by its cost in itself and the distance the unit has to cover to perform it. Simple but good results. My main takeaway for this good talk is that HTN seems to amaze everyone in the audience, seems pretty basic to me but I’m not an expert.

Interactive Narrative Generation and Story Telling - Daniel Kudenko, York University

I’m casually interested in virtual interactive storytelling, so I was paying particular attention. The first part of the talk aimed at presenting the academic state of the art on the subject, not quite complete as it ignored the work of Marc Cavazza who is THE reference. The second part, features the presentation of the engine “Gadin” developed by Daniel Kudenko’s team, interesting but knowing what is made elsewhere, not really impressive.

The Racing AI in Pure - Eduardo Jimenez, Black Rock Studio

Whereas almost every other talk was about action game where the aim of the AI was to kill the opponent, this one is about racing. As presented in this talk, the main problematic of such AI is to adapt its skills to the player’s : he mustn’t feel alone behind or ahead of everyone. The presented solution is quite elegant:

Different “skills” are defined;
Each AI has values between 0 and 1 associated to each “skill” (at 0 the AI doesn’t perform well, at 1 he is good);
These “skill” values can evolve during the game (but the changes can’t be instantaneous);
A scripting language is created to define game scenarios, a scenario describes the evolution of the AI’s rank according to their skills during a game;
During the game the engine trie to match the current state to one of the scenarios and adapt AI “skills” value in order to match it. Another good talk talking about things that works in the real world on a released game.

Building Navigation Meshes by Voxelization - Mikko Mononen, Recoil Games

This talk was the one I expected the most, but I have so much to say about Mikko’s work on Recast and Detour that it will be the subject of another post.

That’s it for the report of the first conference I ever attend to ! The official report is here, much more interesting than mine (I’m very proud to be cited the end of the article). Thanks Alex and the volunteers for the conference ! Thanks too to the drunk czech student who talk all the evening about linguistic, I had a good laugh !

Paris Game AI Conference '09 (part 1)

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 29 Jul 2009 00:00:00 -0700

The Paris Game AI Conference took place on June 10th and 11th at the CNAM. It was organised by AiGameDev.com. OK it a little too late for a proper but whatever :) I needed a first real post for the blog ! Almost 200 people from Europe had came to this free event and I had the privilege to be one of them (I was the only one available in the team). The schedule was quite interesting and it was a first for me, quite exciting ! Here’s a quick report about my time there.

Day one

Panel talk: State of the industry

Alex had the good idea to start the conference by an informal panel were all the speakers talked briefly about them and the challenges they’re curently facing in the game industry. From what they say, their major problem isn’t technology in itself but more how they can fit this technology to the needs of the game designers and to the constraints of the producers. The first telling them: “I want that to improve the game experience, but I’ll change my mind in two weeks !” ; The others: “Don’t you spend too much money AI guys, I’ve already spent everything on the animation/graphics/gameplay”. Some of them still talks about technology matters, as they come: NPC emotion, Highly dynamic worlds, Multithreading, Interaction between AI and animation. Great Start, speakers are passionate and seems to enjoy talking with eachothers.

Emotions in game characters - Phil Carlisle, Bolton University & Indie dev

Starts his talk with the bibliography from which I noted two main references. Thomas and Johnston - Disney Animation: The Illusion of Life (1981). It describes the theories and techniques behind Disney characters (on Amazon). Bartneck. Integrating the OCC model of emotions in embodied characters (2002). Features works on the implementation of a simple emotion model in 3D characters. Phil worked himself on the player perception of the NPC non-verbal communication and procedural animation. Too much time was spent on the state of the art so Phil has to rush the implementation part of the talk. However, he manages to talk about how he implemented the OCC model. This model describes a given state of emotion by a few scalars, each valuating a basic emotion (happiness, excitement, anger…). His sytem gather what seems to be the best sellers here: Behavior trees and blackboard. Interesting talk but he tried to put in too much ; he didn’t have the time for a proper bibliography. This OCC model I didn’t know seems interesting. Those scalars pushed into a fuzzy logic controller linked to motion blending could do the trick…

Coordinating Agents with Behavior Trees - Ricardo Pillosu, Crytek

Ok, so I’m was to meet the famous behavior tree (BT) ! Ricardo gave a really technical talk focusing on real world problematics. His methods introduces collaboration between agnets to traditional BT using a Tactic Manager who assigns roles to the agents fulfilling preconditions for a given tactic, ie a collaborative task. Besides behavior trees mechanisms I didn’t knew, my takeaway is that Crytek switched from Lua and state machine scripting to behavior trees because of their readability. Behavior trees seems to be a efficient tool to describe reactive behaviors but goal oriented task planning is not possible. It should be interesting to compare them with our Golaem Activity…

The AI for Killzone 2’s Multiplayer Bots - Remco Straatman, Guerilla Games & Alex J. Champandard, aigamedev.com

The speakers gave a very detailed talk explaining the AI architecture used for this particular game. The Killzone 2 bots AI is organized in 3 layers : individuals, squads and a global, per team, strategy AI. The first two levels use HTN planners fed by basic perception and orders coming form the upper layer. The strategy layer uses simple rule based engines (one for each game mode) that handle high level goals. The engine is fed with semantic and topological information, give orders to squad and individuals and handles assignment of individuals to squads. Semantic and topological informations are available trough the strategic graph which is: Generated from the level roadmap and the manually tagged semantic informations (targets, flags to capture, good defending positions, sniping positions…), Updated at runtime by team influences (bots presence and goals, number of death…), The presented architecture is really interesting but suffers from what I think is a major drawback. The bots are used in multiplayer games to complete human teams, but even the strategy layer doesn’t take into account human players. The difficulty being evaluating human current goal. The way the strategic map is designed is quite clever though.

Multithreading AI - Bjoern Knafla, Kassel University

This talk was given by an awesome speaker, fun and interesting. Best practices presented in the talk : Use a task manager handling the execution of tasks in threads, Describe calculations in tasks not threads, Separate calculations in two parts, updates on private datas reading public datas and then publish private datas to public datas, Handle conflict via ad hock rules Go error free before performance optimizations

That’s all for today, part 2 will follow soon.

First post - Manifesto

cloderic.mars@gmail.com (Clodéric Mars) — Wed, 29 Jul 2009 00:00:00 -0700

For some times now I have wanted to create some kind of “pro” blog but I never took the time, until now. I’m going to SIGGRAPH for the first time next week and I want a place where I can report some of what I’ll learn there. So here we go !

I work since 2006 in 3D related fields : behavioral animation, crowd simulation, virtual realistic cities, authoring tools for 3d content… As I still consider myself a newbie, I’m constantly and eagerly trying to gather infos and learn. Hopefully, my current job at Golaem allows me just that. This blog will be a place for me to formalise and keep some of those interesting stuffs and, incidentally share them. Quantitatively, I’ll try to post articles every week or two ; I’ve also created a twitter as a sidekick for this blog, you can check it here or on the left side of the blog page.