The most common — and arguably most important — trick for optimizing search algorithms is reducing the size of the graph. If you can search a small one, why not do that? For pathfinding, this has lead to many techniques for better triangulating navigation meshes, reducing the number of nodes without compromising path quality or validity.

In this article, we'll dig into a new feature in the most recent version of PathEngine that optimizes the case for highly dynamic obstacles that move around often, and could be expensive to update each frame. How can this be done efficiently? How does this impact the size of the graph? What's the result on the expanded search space?

NOTE: PathEngine has been a sponsor of AiGameDev.com since it launched back in 2008, and is one of the longest established pathfinding companies. We enjoy reporting these insights into the implementation of middleware, and in particular techniques that have been implemented in recent releases; we hope you do too!

The Cost Of Dynamic Obstacles

In complex dynamic environments, (large) obstacles that must be considered in the navigation mesh (not just avoided locally) can be expensive to deal with. Often, you'll need additional computation to insert these obstacles into the search graph using CSG (Constructive Solid Geometry), which not only takes time but also makes the graph significantly larger.

Thomas Young, founder and pathfinding guru, explains how PathEngine handles this:

“PathEngine's approach to pathfinding obstacles is an important SDK feature, and something I think we do well.

This is something that's difficult to get right and a bit of a bugbear for a lot of pathfinding systems, in particular where different representations are used for local and global navigation. Discrepancies can lead to some nasty fail cases for higher level behaviour code, often without there being any easy way for this to be resolved in a satisfactory way at that higher level. (So it's really worth taking some time to engineer this into the system up front!)

PathEngine's obstacles are 2D (projected) shapes, placed on an underlying pathfinding ground mesh. We can either integrate shapes into the actual pathfinding space boundaries (in a kind of CSG combination operation), or they can be applied to individual pathfinding requests as 'very dynamic' obstacles, as a set of corners + collision checks against the placed obstacle. The delayed attach optimisations apply specifically to this second scenario, for very dynamic obstacles.”

Regardless of what technique you use, integrating dynamic obstacles into a mesh is never free. The best policy, then, may be to not integrate them into the mesh at all!

Lazy Attached Obstacles

The idea of attaching obstacles lazily is to avoid doing computation if it's not required, since the engine is expecting that obstacle to move in the next frame anyway. In the screenshot above, you can see that only the obstacle in the doorway is expanded while the ones in the middle of the room don't affect the path and are left alone.

Thomas Young explains how this is implemented under the hood:

“When applied as 'very dynamic' obstacles, obstacle shapes are only connected to the graph if and when this turns out to actually be necessary for that specific set of path search criteria. Specifically, obstacles are only added if and when they obstruct a path connection that has been fully validated and is about to be closed as an explored node.”

Examples: Before and After

In these screenshots, you can drag your mouse to see the extent of the pathfinding search with delayed attached obstacles and without. The results are always better, in some cases more drastically than others!

• The 'delayed attached dynamic obstacles' optimisation is something that is useful in essentially all searches where dynamic obstacles have been placed, with the speedups getting more significant as more obstacles are added (and for situations where dynamic obstacles are 'scattered' over a pathfinding environment).
• The 'delayed attach for static graph' optimisation gives us a speedup only in certain particular situations, but with the speedups then tending to be very significant for those specific situations.

Technical Questions

Q: Are the results always the same with the lazy insertion?

TY: There's no path quality trade-off from these optimisations (unlike the 'small convex obstacle', and similar optimisations, discussed a bit in here). The delay attach optimisations are essentially transparent to external code, and don't affect path length guarantees. (So, assuming the small convex optimisation is not turned on, you are still guaranteed shortest path with these optimisations.)

Note that turning this optimisation on or off _can_ change the path result for certain specific situations, however, where there is more than one path from start to goal with the same globally shortest path length. This is for the same reason that changing certain details of the internal search implementation such as the priority queue structure or the ordering of graph connections can change the path result in the same situations.

Q: Does this take extra processing to make this happen?

There is a bit of extra book-keeping to keep track of which graph components have been attached, and some extra details relating to underlying collision checking methods, but the cost for this stuff is really pretty minimal.

Q: How are cases when obstacles block doorways, causing the A* search to have to back track, in terms of performance?

I haven't measured this case specifically, but I'd expect this to be fairly similar in performance to the same situation _without a doorway_ and with a dynamic obstacle placed nearby, since most of the cost for this kind of situation is likely to relate just to the fact that back tracking is required, and with the need then to explore connections in other directions.

Q: Can this approach be any worse than not inserting obstacles, if so in which cases?

Since there is some book-keeping cost, and because it is cheaper to do things in a kind of batch operation than individually (for processor caches and so on) cases where all or nearly all the graph components present eventually get attached would be slightly faster without the delayed attach optimisations.

For situations where there are a bunch of dynamic obstacles placed (which is what we are targetting with these opts) I think that this is unlikely to happen very often, however. And note that it is quite common for dynamic obstacles to remain unattached even in cases where we force the whole search space to be expanded!

Q: Why does the points of visibility approach make implementing this feature easier?

I guess because of the way that 'completely dynamic' obstacles are implemented for points of visibility pathfinding, i.e. we just add some additional points of visibility, plus some collision constraints that apply to other connections. Note that there is then no rejigging or rerouting (or retriangulation or whatever) required for other connections around the obstacle. So the existing, potentially already partially explored, graph remains valid.

Having said that, the idea of doing this kind of delayed attach for graph search is really quite a general idea, and it should definitely be interesting to think about ways in which this could potentially be applied to other kinds of pathfinding graph search...

Screenshot: Finding a path between buildings with highly dynamic obstacles in between, as shown in the before/after comparison above, but with only the final path drawn in green. How much more searching (or melding of obstacles into the navmesh) does your solution take to support this use case?

Many thanks to Thomas Young for taking the time to answer these technical questions and sharing the underlying implementation details of PathEngine! See PathEngine.com ]]> http://aigamedev.com/open/article/pathengine-delayed-attach/ http://feeds.aigamedev.com/~r/AiGameDev/~3/kKgQxl7OVJw/ Tue, 30 Apr 2013 12:32:59 +0000 Alex J. Champandard http://aigamedev.com/open/coverage/ctf-report/ During three months, starting mid-November 2012 and ending mid-February 2013, AiGameDev.com ran an AI Competition called Capture The Flag. We had rather ambitious goals for CTF, designing it to be more practical than academic competitions and more relevant than hobbyist contests. In the end, after many long hours of work by the many competitors and the organization team, it not only fulfilled our expectations but easily drove forward the current state-of-the-art in the field.]]> (Copyright © AiGameDev.com, 2013.)

During three months, starting mid-November 2012 and ending mid-February 2013, AiGameDev.com ran an AI Competition called Capture The Flag (CTF). We had rather ambitious goals for CTF, designing it to be more practical than academic competitions and more relevant than hobbyist contests. In the end, after many long hours of work by the many competitors and the organization team, it not only fulfilled our expectations but easily drove forward the current state-of-the-art in the field.

Over the course of the competition, almost 1,000 AI Commanders were submitted by a horde of almost fanatical hobbyists, students, enthusiasts, and professionals. In total, over 100,000 games were run online among the submissions in the continuous ladder as well as the tournaments for each phase. The winners were awarded with a signed copy of KILLZONE 3, courtesy of Guerrilla Games (who are hiring), AiGameDev.com PREMIUM memberships, and free tickets to this year's Game/AI conference in Vienna.

Here's an example of a match between the top two Commanders, to give you an idea of the game's mechanics as well as the quality of the final results!

Kefir vs. Terminator

Challenges

There are various interesting things to note from this game (other maps have similar challenges):

1. Adaptive Defense — There are many well protected locations to defend the flag, and the Blue commander exploits those based on how successful they have been so far.
2. Tactical Movement — The shortest and most naive path choice between the flag and the return location goes through enemy controlled territory, and requires tactical pathfinding.
3. Reactive Strategy — Strategies for both rushing the flag quickly (Red, 0:12) and approaching it methodically (Blue, 0:25) are both viable at most stages of the game.
4. Terrain Reasoning — Tactical reasoning has a big impact on most maps, including carefully approaching enemies, picking off flanks, and intercepting the flag carrier.

Game Mechanics

As for the low-level mechanics of the game, the individual bots have four high-level states (enabled by sending orders) that serve specific purposes and complement each other. The specific details of the states, such as cool-down timers, field of view, and aiming delays were tuned over the course of the competition to maintain balance as the commander AI submissions improved. However, the underlying principles remained unchanged:

• Defend — Places the bot in a focused crouching position, precisely aiming at a specific direction. Aiming is very quick and deadly, but the field of view is lower and it takes more time to get into position.
• Attack — More careful attacking behavior that will avoid trouble where possible, and not venture into the line-of-fire of known enemies. Speed is relatively slow.
• Charge — A much faster attack behavior that can be used by multiple bots to overwhelm static positions. Movement is much faster, too. Ideal for rushing to the flag.
• Sprint — This behavior avoids attacking altogether and simply moves very quickly towards the specified target. Often, sprinting bots can 'dodge' into cover before the enemy can take a single shot!

It took quite a bit of tweaking of the parameters of each state over the course of the competition, but overall the behaviors remain simple. The Commander AI is responsible for making the most of these behaviors.

Ladder & Tournament

The following table shows winners and their bot performances in the CTF competition.

Rank	Commander	Wins	Draws	Losses
1	Alexander Shafranov #35	72.4%	9.6%	18.0%
2	Terminator #17	69.7%	11.9%	18.4%
3	Chris St. John #53	60.0%	16.2%	23.8%
4	Traffic Jam #44	60.0%	15.8%	24.2%

Congratulations from the whole AiGameDev.com team!

Example Game Recordings

Chris St. John vs. T-Dup

Traffic Jam vs. Locutus

Commander AI

During the course of the CTF competition we were not only interested in the final results and who leads the ladder. We also encouraged participants to share insights on their solutions and how they approached to solve the challenging task of developing a good and robust AI commander. That includes AI techniques such as reasoning, planning and of course path finding.

Many of these discussions took place in our official CTF competition forums. There, competitors talked about technical questions and issues, details of how to solve a particular problem, as well as general ideas and thoughts related to the design and development of their and other AI commanders.

We asked the competition finalists to share some details on their approaches and solutions. They kindly answered all our questions and we have created a dedicated posting with their answers for you. Thanks to the finalists for sharing your ideas!

What Player's Thought

"The CTF competition allowed me to prototype Python HTN planner and use it for actually relevant task, without spending ages, thanks to the easy programming environment. Many thanks to AiGamedev.com guys!"
-- Alexander Shafranov aka shafranov

"The Capture the Flag contest achieves a great balance between simplicity for newcomers and flexibility for experienced hackers. I had great fun learning and applying new AI programming techniques like behaviour trees. Thanks, CTF team!"
-- Chris St. John aka CSJ

"I had a great time developping a bot for the CTF competition: good organization, challenging and friendly competitors, good game with a lot of possibilities, C# support. Thanks a lot to admins and contestants for making a success out of this experience!"
-- Thomas Dupuis aka tdup

"I never thought I'd wake up early in the morning to check logs, make sure blues win against reds and go straight back to bed with a glad heart. Thanks for this exciting game!"
-- Xavier aka Traffic Jam

Get Involved!

The CTF competition is over but we at AiGameDev.com are already thinking about the future of the AI Sandbox, possible enhancements and new features, as well as ideas for other competitions. We are already working hard on the next major update of the AI Sandbox software, and we want to share the results of our efforts with you.

The next iteration of our AI Sandbox application is available and ready to download from the main AI Sandbox web site. Will you test it and provide feedback to us? We are eager to hear what you like about the software, what you think could be improved, and what features you would like to see in in future versions.

Thank you!

Source Release

It's hard to ignore the potential of planning techniques for Game AI, and over the years they've drawn much attention from developers and researchers alike. In theory, planners could help build more intelligent non-player characters, and (indirectly) more believable and entertaining NPCs. Better still, planners as game directors or story generators could help craft unique experiences for each player.

In practice, planning technology has made notable inroads in the past 8-10 years since being introduced in the games industry. There are certainly a lot of open problems to solve and many more questions left to answer, but much has been achieved already...

In this article and its accompanying video, I'll dig into the history of planning in games, look at games that use planning as well as related techniques that have had an impact, and present the biggest lessons we've learned as a result of all this.

Video Presentation (26m)

STRIPS-based Planners

STRIPS is a planning algorithm that searches through possible situations (or world states) by applying operators (or actions). Typically with STRIPS, this search is done backward from the goal state rather than forward from the current world state; the first is faster, but the second is more flexible when you have complex goals. Using A* to drive the search with simple heuristics can help make the planning process relatively efficient. (This is only a short overview, but obviously it's a topic that has been studied for decades over hundreds of white papers.)

F.E.A.R. is the first game known to use planning techniques, based on the work of Jeff Orkin. The enemy AI relies on a STRIPS-style planner to search through possible actions to find a world state that matches with the goal criteria. Monolith's title went on to spawn a franchise of sequels and expansions, and inspired many other games to use STRIPS-style planning too — in particular the S.T.A.L.K.E.R. series, CONDEMNED, and JUST CAUSE 2.

There aren't very many games that use such planners in comparison to other techniques, but the AI in those games has been well received by players and reviewers. The most successful games to use planning have featured more open worlds and emergent gameplay, whereas more heavily scripted or linear story-driven characters have conversely received poor reviews when implemented with STRIPS-style planners. In the past few years, we've seen an incremental shift away from STRIPS-style implementations towards more hierarchical approaches, either HTN planners or their reactive cousins behavior trees.

HTN-based Planners

HTN planners are based on hierarchies of tasks that can be broken down recursively, like a plan that starts with the big picture and gets refined into actionable steps. Different HTN algorithms take different approaches to expanding the plan, for example starting from the current point in time and progressing one step at a time (a.k.a. ordered HTN). The ordered approach is more efficient though less flexible; partial order approaches are proven capable of emulating STRIPS for example.

HTN-based planners inspired by SHOP (an ordered planner) are becoming increasingly popular over the STRIPS-based ones. Guerrilla Games implemented a planner inspired by SHOP into KILLZONE 2, and continues to use the technology in sequels including KILLZONE 3 and presumably 4. The bots in the series have continuously received praise from players and reviewers alike, thanks in part to the planning technology but also the richness of the domain. Recently, in TRANSFORMERS: WAR FOR CYBERTRON, High Moon also switched from using a STRIPS-based planner to a hierarchical approach also inspired by Guerrilla's work and SHOP.

Behavior Trees

It's often difficult to draw the line between hierarchical planners and behavior trees, since SHOP-inspired planners often include implementation tricks or design patterns to make them more reactive for the sake of performance. In practice, this makes them very similar to the industry-standard behavior trees, which have been in heavy use since ~2004 (with ideas inspired from robotics and virtual agents from decades before).

In practice, the AI in games like TOTAL WAR (e.g. EMPIRE or NAPOLEON) has been dubbed a planner but follows implementations traits of "reactive planners" and "belief-desire intention" architectures (both are misleading terms, despite having been used often in academic research). Similarly, games like METRO 2033 switched from STRIPS-style planners, and Avalanche studios is also currently favoring its behavior tree implementation despite having a production-quality STRIPS planner available.

Utility Systems

A utility system is the term used to describe a voting/scoring system, and they are often applied to sub-systems of games like selecting objects/positions based on the results of a spread-sheet like calculation. It's interesting to establish parallels between STRIPS-based planners and utility-based systems, since both have a strong emphasis on emergent behavior that's not intended to be controlled top-down by designers.

DEMIGOD in particular uses a form of action search that's not a planner in the traditional sense, trying to satisfy clear dependencies and meet Boolean conditions in the goal state, but instead trying to evaluate the benefit of short sequences of actions and pick the best one. This approach bridges the gap between utility systems and non-hierarchical planner, making utility systems more deliberate in the process.

Another notable implementation is the one in the SIMS 3. The SIMS franchise is famous for its use of utility systems, but in the 3rd major iteration, the game puts more focus on a top-level hierarchy and keeps the utility-based decisions more isolated. This was necessary for performance reasons, but also makes the characters more purposeful.

Lessons Learned

Based on the applications in all these games, we've developed a much better understanding of planning in games:

• Technology has not been much of a problem. Applying STRIPS into a game in real-time certainly required many engineering and optimizations tricks, likewise speeding up HTN implementations. However, with additional processing power available and with much better knowledge of the problem since then, planning performance hasn't been as big of an issue as you'd expect it to be...
• The biggest open questions are about design. The most significant problems to solve have been finding ways to tweak and tune the behaviors resulting from planners, optionally integrating them with level scripts, and teaching designers to think more systematically and work with emergent AIs. This has required significantly more effort than the pure algorithmic aspects of planning, and is responsible for the incremental transition towards hierarchical approaches.
• In well understood domains, other techniques work best. In the cases of action/combat games, we can easily build robust AI that looks deliberate using simple reactive techniques like behavior trees. In fact, it's difficult to tell the difference for such applications between the behavior generated by a planner compared to more reactive approaches, yet the planning process will be noticeably slower at runtime and require more development time.

• Planning has most benefits in unknown domains. Jeff Orkin mentioned in his publications that one of the benefits of planning was in prototyping, creating new behaviors quickly by letting the planner generate behavior given new actions or goals to work with. Planners also have shown to be more beneficial in open worlds, where the sandbox simulation has significantly more complexity.
• Goal-based architectures are great! Regardless of whether developers use planning techniques or not, an architecture that separates the AI's goals (or WHAT to do) and the AI's decision making (or HOW to do it), has proven to be very effective. Planning research has helped crystallize this insight, and even when using reactive techniques this is arguably a best practice for AI architecture in games today.

Final Words

We've barely scratched the surface of what planners have to offer for game development. We've certainly learned a lot, but at the same time there's such a small amount of research on topics that are problematic in games (e.g. design and workflow questions) that progress is slower than you'd expect for such a mature field as automated planning.

Perhaps the most exciting prospect of planners, however, is their application to create new types of gameplay that would otherwise not be possible using any other approach. This part has proven to be more of a challenge, as few designers have the background in systems thinking that's required to come up with such ambitious and innovative designs.

What interests you about planning in games? What lesson do you take out of our last 8-10 years of applying planning to the game development process? Post a comment below or in the forums.

Every year AiGameDev.com runs its Awards for Game AI, shining the spotlight on the best releases of the past year. There are six different awards, ranging from technology to design and of course overall game of the year. For each, we've included the community vote results as well as the editor's choice.

Like previous years, the games this year have raised the bar in many places for artificial intelligence, including AI-based mechanics that open up new game designs, using optimization and evolutionary algorithms as tools, and procedural pipelines for AAA-quality graphics. Of course, there were some catastrophes too, but we're not going to talk about those :-)

Thanks to our Sponsors!

Content Index

1. Best AI in a AAA Game
2. Best Non-Player Characters
3. Best AI in an Independent Game
4. Design Innovation in Game AI
5. AI Technology in a Supporting Role
6. Technical Innovation in Game AI

Best AI in a AAA Game

Vote Winner
XCOM: Enemy Unknown

The winner of the vote for Game Of The Year, by a large margin, is Fireaxis' highly acclaimed remake of the original X-COM. As well as drawing players in for hundreds or thousands of hours, the game impressed AI geeks with tactical reasoning that was very solid yet could be surprised and caught off guard by the player.

For the second year running, this award for Best AI goes to a highly polished GOTY in its own regard (BATMAN: ARKHAM CITY last year). This not only emphasizes that great game AI and great mechanics go hand in hand, but that best-in-class game design is often a sufficient condition for winning the public's opinion about the AI — almost more so than technical innovation.

Congratulations to the whole team at Fireaxis!

Nominations

• Assassin's Creed 3
• Far Cry 3
• Halo 4
• Dishonored

Honorable Mentions

• Borderlands 2
• Hitman: Absolution

References

1. How To Have Fun in an Asylum: Building Batman's AI (ULTIMATE)

Editor's Pick
Far Cry 3

Ubisoft's ambitious open-world sequel captured the imagination of players worldwide and gets AiGameDev.com's pick for Best AI in a AAA Game. The game is filled with great applications of AI, from the wild-life to the combat manager that spawns enemies, and of course its NPCs. Building open-world games is a huge challenge in general, but the development team rose to the challenge and managed to breathe life into the environment and turn the island into the main feature of the game.

Congratulations to the Ubisoft teams that worked on the game, the designers for their audacity in aiming for such bold ideas, and the technical teams for pulling it off! We hope to see more from this engine in particular, and of course other equally ambitious implementations form other game studios.

Best Non-Player Characters

Vote Winner
Hitman: Absolution

This vote was the closest ever in the history of these awards! IO Interactive's big-budget sequel to the HITMAN franchise wins the Best NPC award by a statistically insignificant margin in front of FAR CRY 3. Congratulations to the team in Copenhagen for their many years of hard work on the project!

Hitman: Absolution's success with its characters can be attributed to a combination of different things; new technology such as reinforcement-learning for animation control, grid-based reasoning inspired by KILLZONE's technology and a behavior-tree implementation of classic stealth AI. The votes did reflect some polarization, possibly due to the traditional design of the NPCs, and the reduced emphasis on sandbox gameplay like the previous iteration (HITMAN: BLOOD MONEY).

Far Cry 3 on the other hand, featured iconic and memorable characters, in particular Vaas, who received critical acclaim for the voice acting and quirky writing.

Nominations

• Far Cry 3
• Mass Effect 3
• Dishonored
• Max Payne 3

References

1. Reinforcement Learning-based Character Locomotion in Hitman: Absolution (ULTIMATE)

Best AI in an Independent Game

Vote Winner
Vessel

This year's winning independent game is Strange Loop's VESSEL. (Disclaimer, one of the developers, Kieran, worked at AiGameDev.com last year :-) This platforming game innovates on multiple different fronts, from its use of combinations of behavior in gameplay puzzles, to the underlying simulation of the characters that blend skeletons and fluid simulations, as well as the dynamic music and audio which adjusts to the player's progress.

We think of the game as the "Braid of AI" and anyone interested in how character behavior can make interesting gameplay (or puzzles) is highly encouraged to play it! Congratulations to the team for winning this award.

Nominations

• City Conquest
• Prom Week
• Field Runners 2
• Awesomenauts
• Unity of Command
• Endless Space

References

1. Integrating Behavior and Physics in VESSEL (PREMIUM)

Editor's Pick
Prom Week

Our choice for the best independent game is PROM WEEK, built by a team at the Expressive Intelligence Studio at the University of Santa Cruz. You may recognize the influence of Michael Mateas, who previously developed Façade. Prom Week takes the idea of story as a simulation further by adding the concept of "social physics", i.e. predictable character mechanics that the player can interact with for gameplay purposes.

The underlying system, Comme Il Faut is well documented via multiple publications, and emphasizes how many opportunities there are still in this area! However, despite a nomination in the Independent Games Festival (IGF) and accolades from experienced developers in industry, the game didn't succeed in reaching as broad an audience as many expected/hoped.

References

1. Enabling Playable Social Models and PROM WEEK (ULTIMATE)

Design Innovation in Game AI

Vote Winner
Crowd Interaction in Hitman: Absolution

There was strong competition for design innovation in this year's awards, but HITMAN: ABSOLUTION won with its use of crowds. First and foremost, the underlying crowd-simulation technology that IO Interactive built brings scenes to life in a way previously unseen in AAA games. But beyond the experience, the crowds also add to the gameplay, providing obstacles and concealment, as well as responding to gunfire in a plausible way.

With the next generation of consoles around the corner, we can only be hopeful to see more developers experiment with this kind of technology, and find even more interesting and innovative game mechanics. Congratulations to the technical team at IO for being able to pull off this crazy idea!

Nominations

• Social Physics in PROM WEEK
• Behavioral Gameplay in VESSEL
• Enemy Steering in FIELD RUNNERS 2
• Supervised Flower Breeding in PETALZ

References

1. Crowds in HITMAN: ABSOLUTION (ULTIMATE)

AI Technology in a Supporting Role

Vote Winner
Physics-Driven Motion in MAX PAYNE 3

Over the years, Rockstar has invested a lot of time and money into its animation systems, and this year MAX PAYNE 3 wins the award for its use of AI there. The underlying implementation is based on Natural Motion's euphoria, combined with some proprietary physics simulation technology from the R.A.G.E. engine. The result is a highly interactive protagonist that you can throw down stairs while controlling his movement, and yet still respond to collisions in a reasonable way.

This kind of animation technology requires significant support from AI-style reasoning to understand the immediate surroundings of falling characters, and determine how to respond at a high-level, then affecting control on the underlying simulation. This kind of environmental awareness is becoming more and more important for animation, even for traditional ragdolls.

Nominations

• Evolutionary Algorithm as Design Tool in CITY CONQUEST
• Bots AI in DOTA 2
• Procedural Generation in SSX
• Language Recognition in SCRIBBLENAUTS UNLIMITED

Editor's Pick
Evolutionary Algorithms in City Conquest

Our choice for the best use of AI in a Supporting Role is City Conquest, an iOS tower defense game that features symmetrical gameplay against opponents. The game was designed by industry veteran Paul Tozour, who used evolutionary algorithms as part of the design process to help balance and tune the various units and towers in the game (among others).

Genetic algorithms are popular in academia, but haven't found their place in AI engine runtimes. Tools, however, seems like an ideal place for them, and Quake 3 in particular had some of its weapon selection parameters evolved. The kind of techniques behind City Conquest have significant potential to help designers understand their mechanics better and iterate quickly over them. Hats off to Paul for attempting this in such a bold fashion!

References

1. Making Designers Obsolete? Evolution in Game Design (BLOG)

Technical Innovation in Game AI

Vote Winner
Hierarchical Planning in Transformers: Fall of Cybertron

This year's winner on the technical front is TRANSFORMERS: FALL OF CYBERTRON. The game, developed at High Moon, features a hierarchical task network planner. Over the past few years, HTN have become the spiritual successor to GOAP (goal-oriented action planning, based on STRIPS technology) thanks to the pioneering work done by Guerrilla Games on KILLZONE 2.

The planner in FALL OF CYBERTRON takes the implementation further by accurately tracking side-effects of operators on the world. For non-planning geeks, this is a subtle improvement, and furthermore it can be hard to distinguish a planner from a behavior tree in practice (especially in action games). But the result of this vote also hints at the general appeal to the public of planning as a concept! Expect to see more :-)

Nominations

• Reinforcement Learning Animation in HITMAN: ABSOLUTION
• Tactical Reasoning in XCOM: ENEMY UNKNOWN
• Procedural Art Pipelines in SSX

References

1. Planning for the FALL OF CYBERTRON: AI in TRANSFORMERS (PREMIUM)

Editor's Pick
Procedural Pipelines in SSX

Arguably the most important technical innovation this year, from our perspective at AiGameDev.com, is the inclusion of procedural techniques within AAA pipelines to produce top-quality graphics. The team that worked on SSX bought into this idea fully and took the implementation as far as possible in one game. Congratulations to EA Vancouver for trying this and pulling it off!

The designers on SSX used the pipeline entirely to craft the tracks, and only the final artist touch up was done manually. The developers hope and plan to go 100% procedural with better education/training in the future! Expect this technology to spread around Electronic Arts and the rest of the industry incrementally as well...

References

1. Procedural Generation of Mountains and Tracks in SSX (PREMIUM)

Your Games of the Year

What games had the biggest impact on your year? Which ones will you continue to play in 2013, recommend to friends, or keep on your shelf for further study of the AI?

Post a comment below or in the forums, and let everyone know what you think!

No two weeks are alike at the secret AiGameDev.com labs here in Vienna, Austria. Between work on this very website, the AI Sandbox™ and its underlying algorithms, visualizations, our regular broadcasts and conference preparations, there's always something different and challenging to work on!

18 months ago we announced our first wave of hiring, a mix of experienced game developers and enthusiastic AI graduates. Now we're about to do it all again, and if you just thought "Now that sounds cool!" then read on. Here's what the team was busy with last week as an example...

Visibility Calculations

As part of an upcoming tutorial, the team implemented different ways to calculate line-of-sight specifically for 2.5D environments. We've typically used full 3D visibility checks, but here we had the opportunity to try more specialized and faster routines based on line-drawing algorithms and visibility propagation.

AiGameDev.com is involved in an EU project focusing on improving the next generation of GPGPUs, so we discussed designs of this algorithm that would be suitable for implementing in OpenCL. For 2D visibility, there are both opportunities for leveraging graphics hardware, as well as more general stream processors.

Matchmaking API

The Capture The Flag competition is in full swing, and many new Commanders are submitted on a regular basis. To make sure the rankings displayed are accurate when there haven't been too many matches played for each commander, we integrated the Python version of the TrueSkill algorithm that uses Bayesian inference. This is also used to select the matches (in a weighted fashion) to help separate bots of similar rank.

Of course, this led to team discussions of why details from the game itself are not taken into account in the rankings. Various statistics of the game such as capturing enemy flags, not conceding flags, or even eliminating enemies can be used to measure skill, and a correlation can be established with data mining techniques. As it turns out, we'd read a paper on this very subject in the latest Transactions on Computational Intelligence and AI in Games Journal, which sits on the shelf in the labs here.

Voronoi Corridor Map

At AiGameDev.com, all of us in the team are keen on pushing the limits of Game AI as a field too. And that involves trying more difficult but potentially very rewarding ideas. One of those was extracting generalized voronoi diagrams (GVD), which can be used for a wide variety of tasks such as tactical movement and strategic reasoning.

By relying on Python for high-level programming, the AI Sandbox makes it particularly easy to experiment with these things. Algorithms that take weeks to prototype in C++ can be tried out first as a combination of existing Python libraries. In this case, tweaking and tuning the image processing algorithms was necessary to make sure the graphs generated were clean enough to work with.

Level Generation

One great way to challenge AI is to procedurally generate levels. In the current Capture The Flag competition, we started investigating this option by building a simple algorithm to randomly place the key gameplay elements: flag spawning location, flag return location, and the team's base. This was written inside a Python / QT tool (a.k.a. PySide), which we've been using more and more internally

While there are no specific constraints on where gameplay elements are placed in the level, there are complex relationships between them. These can be enforced by simple constraints; the distance between flag and goal is 16m or more, two bases can't see each other, etc. Then obstacles are randomly placed within the map until satisfactory conditions are met... We haven't deployed this code on the ladder yet, but will continue to use it to generate ideas for levels.

... and Many More!

This is only a subset of the things an average week contains, and this particular one included the following as well:

• Putting in place the first parts of the plan for next year's Vienna Game/AI Conference, scheduled around September 4th 2013.
• Identifying and fixing video encoding bugs in ffmpeg and our scripts, then re-encoding some problematic videos.
• Updating the Wordpress theme for this site with some improvements, as a combination of PHP, Javascript, HTML and CSS.

As a small company, we're not looking for any specific skill, but you'll need to be good at many things and great at one or more.

Join The Team?

Two positions are open, one for an experienced developer as well as a position for students or graduates. There are many reasons you should consider working with us at AiGameDev.com. Here are a few:

1. It's a great career move that will yield many opportunities.
2. It's a wonderful cultural interlude in the city with the highest quality of life.

If you're interested in everything you've heard so far, here are some logistic details about the positions:

• Duration: 6, 12 Months and Permanent
• Start Date: Q1 2013.
• Contract: Full-Time Only
• Location: Vienna, Austria
• Salary: Experience-based
• Benefits: Social Security, Pension
• Arranged: Accommodation

Once you're ready, send an email to <team at aigamedev.com> with your application. The deadline is officially on January 14th at 11:59 UTC, but based on past experience you probably shouldn't wait that long if you're serious!

Are you looking for an AI challenge? Do you want to work on a relevant problem that’ll get the attention of the games industry? Better still, are you motivated to push the boundaries of what’s frequently done in Game AI? Or are you keen to finally get your hands on the first public release of The AI Sandbox™?

If this sounds great to you, then you’re in the right place! That’s exactly the reason we designed the Capture The Flag competition. AiGameDev.com has teamed up with Guerrilla Games, developers of the KILLZONE series and its highly acclaimed bots, who are supporting the competition with prizes — and also hiring AI programmers! Below you'll find an interview with Lead AI Programmer, Arjen Beij, to find out how this competition addresses relevant topics.

NOTE: Find out more about the CTF competition on the AiSandbox.com website, specifically the Participate page and Getting Started for mode details. Also, special thanks to our sponsors PathEngine and Havok for their support!

Production Changes

AiGD: In a development environment, from pre-production or even late on in alpha, the balancing of the gameplay and behavior of bots changes significantly. How important is it to build an AI that's capable of dealing with these changes? How does Guerrilla Games deal with this, and do you think current techniques do well for this purpose?

Arjen Beij: Developing a game is an iterative process. Game modes, weapon, character classes and abilities will be added, changed or removed throughout much of the project. It is therefore very important that our systems are flexible enough to support making these changes without requiring major rewrites. We deal with this by building our systems as components with a stable interfaces between them. For example, for the AI all weapons are addressed through the same weapon interface class. For the AI there is no difference in firing a rifle, throwing a grenade or hitting an enemy over the head; these are all just weapons. The logic and constraints of using a specific weapon are hidden behind the interface. This means adding a new weapon type, even if it is very different from existing weapons, only requires implementing a new interface class.

The CTF competition is designed to expose some of the challenges of building a production-level AI commander. You'll have to deal with new maps types, improvements to the individual bot behavior, and incremental changes to the underlying gameplay over the course of the competition. These types of changes in a game like KILLZONE 2 or 3 often require manual adjustments from the AI programmer, but can you build an AI that can deal with this more efficiently?

Layering & Responsibilities

AiGD: In games with a heavy focus on artificial intelligence, there is often a clear layering in the architecture that separates high-level strategy from the individual bot behavior. How important is this for Guerrilla Games and what benefits does it bring?

Arjen Beij: I would say flexibility, reduced complexity, performance and the potential for emergent behavior.

Dividing responsibilities up into different layers reduces the complexity of the code: the high level strategy does not concern itself with choosing positions for individual soldiers, it assigns objectives to squads and leaves the details of execution up to the lower layers. The interface between layers is stable which allows us to change the implementation of one layer without affecting other layers. Introducing a new game mode and strategy into the game will require no or few changes to the other layers.

High level strategic decisions can typically be made at a lower frequency than tactical and low level combat decisions. By making strategic decisions at a lower frequency we either free up CPU time or spread strategic calculations over multiple updates to allow for more time consuming algorithms.

Finally, more interesting behaviors will emerge because individual AI is free to interrupt strategic orders with appropriate short term combat decisions.

Our Capture The Flag competition gives you high-level orders to order your bots around such as Attack, Charge, Move and Defend. You're not encouraged to micro-manage the underlying bots (like in other RTS competitions), and in fact the game will impose cool-down timers for various orders. This will allow you to focus on the high-level AI of your commander, and assignments of bots to objectives, rather than worrying about individual behavior. It also makes the competition significantly more fun!

Cheating or Honesty

AiGD: As you've discussed in past presentations and interviews, Guerrilla Games considers not cheating very important far as individual AI is concerned. What benefits do you think this has had in your games, and do you think it's as important for high-level strategy AI?

Arjen Beij: I think it is important to give the player the opportunity to outsmart the AI in a believable manner, not just to defeat it because of the artificially limited reaction time of the AI. Outsmarting generally involves being in an unexpected location and that requires AI with imperfect knowledge of the world state. There are limits to how far you need to go with this emulation: for example our AI has perfect knowledge of the map layout. Players will also build up this knowledge as they play the game.

This approach is equally desirable at the strategic level. The strategy is aware of the map layout but has no information on enemy locations apart from the combined knowledge of its individual team members. Of course information that is available to human players such as state of capture and hold areas can be used in strategic decisions without being considered cheating.

Professional game developers have become very good at building strategic AI that uses all the information it has available, and KILLZONE 2 & 3 both make this approach shine by relying on "perceptually honest" bots. In this Capture The Flag competition, your commanders are given only the information seen by their low-level bots. We believe this will enable new and exciting emergent behaviors, which the games industry does not always have time to focus on.

Robustness and Fun

AiGD: For individual bots, the general consensus in industry is that it's important to make sure they are fun to play against — not too hard and not too easy. But as far as high-level AI, it's not as clear; many gamers enjoy competitive opponents that can out-think them. Where does Guerrilla Games stand on this debate on "optimality" and why?

Arjen Beij: It is more important that the high level AI is robust and plausible rather than optimal. I think an optimal strategy doesn’t get in the way of a fun experience, but it is not a goal for us.

Our Capture The Flag competition emphasizes robustness by throwing your commander up against a wide selection of levels, different layouts of objectives, different configurations of bots, and of course a wide variety of different opponents! The best commander will be chosen that can handle all these special cases best on average. Whether you use optimization techniques or even data-mining from the online replays, it's up to you!

What Next?

If this sounds exciting, you're not alone! Since we announced the competition a few days ago, hundreds of programmers from around the world have signed-up and many more each day... Join us and make this a particularly exciting end of 2012 (the first phase, December 10th) and start of 2013 (the second phase, January 7th)!

To get started, find out more about the CTF competition on the AiSandbox.com website, specifically the Participate page with details and Getting Started for mode details.

Good luck! ;-)

A few weeks ago the Game/AI Conference 2012 took place in the beautiful capital city of Austria. It was organized by AiGameDev.com along with the University of Vienna, where the event was held. In this post you'll slides from each talk, my take-away & analysis, as well as photos from the event. The recordings will be available incrementally through AiGameDev.com ULTIMATE membership.

If you're wondering what happened to the Paris Game/AI Conference... Vienna is home to the AiGameDev.com secret laboratory, so the organization team was on home ground! All the little details came together at the University's amphitheatre, from the Wiener hotdogs at the welcome reception to the Apfelstrudel during the coffee breaks that attendees raved about (some complained about gaining a few pounds), as well as the bamboo plants for ambiance and the "Game/AI" backdrop behind the speakers that delighted Petra (our logistics mastermind).

The conference itself featured two days of talks from recent or upcoming AAA games, as well as research presentations from leading academics (September 18th and 19th); the slides and notes for these talks are below. The days before and after the main event contained two workshops, the first on Behavior Trees as a review of the state-of-the-art in the field, and the second on Procedural Animation as a more forward looking day about the next-generation of algorithms. It was a great combination of summarizing what has been achieved and the robustness that AI has reached, along with inspiring look into the technology of tomorrow!

NOTE: Recordings of the conference presentations will be available for AiGameDev.com ULTIMATE members over the next few weeks as they are edited. There's a bonus month for new memberships until October 17th!

Thanks to Our Sponsors

Beyond the helper crew and the organization team, this event would not be possible without the support of our amazing sponsors, and they're the reason that everyone gained a few pounds on average due to tasty strudels and delicious muffins. We're particularly grateful to Gold Sponsors Autodesk! The company introduced Gameware Navigation at this very conference on Tuesday afternoon.

Thanks also to Havok for their continuing support of the conference as a Silver sponsor this year and the AiGameDev.com website. Find out more about the latest additions and technology behind Havok AI below.

Finally, thanks to PathEngine for their sponsorship of the main conference and Unity for sponsoring the Character Animation workshop.

Table Of Contents

The sessions from the first day, Tuesday September 19th, are here:

1. This Year in Game AI
2. Scaling Crowds in HITMAN: ABSOLUTION
3. Understanding Player Behavior Using Data-Mining
4. Motorstorm's AI: Racing while the World Crumbles
5. THE RESISTANCE AI Bots Competition
6. Design-Driven AI in SPEC OPS: THE LINE
7. Behavior Trees for Social Territorial Intelligence
8. Rapid AI iterations with Autodesk Gameware Navigation
9. How to Have Fun in an Asylum (Batman: Arkham Series)

These sessions are from the second day, Wednesday September 20th:

10. What's Next for Game AI?
11. Dynamic Sound and Music in VESSEL
12. Monte-Carlo Tree Search and Board Games Tutorial
13. Implementing the Living City in MAFIA 2's Open World
14. Optimizing Steering-based Animation Control
15. Reinforcement Learning-based Character Locomotion in HITMAN
16. Platforming AI Championship: Level Generation & Turing Test
17. The Evolution of Codemasters' Racing AI: From DiRT to Showdown

This Year in Game AI

Session Details

Speaker: Alex J. Champandard
Company: AiGameDev.com KG
Time: 09:30
Duration: 30 min

Description

“In this introductory session, you'll learn the high points of the past year in Game AI, highlighting the advances the industry has made and summarizing the best in AI tips and tricks that the AI community has to offer.”

Slides

Scaling Crowds in HITMAN: ABSOLUTION

Session Details

Speaker: Kasper Fauerby
Company: IO Interactive
Time: 10:00
Duration: 60 min

Description

“A key requirement in HITMAN: ABSOLUTION was dense crowds that allowed players to both interact with and influence the behavior of individual characters. This presentation describes the techniques and optimizations used to achieve the 1200 character crowds while still running at 30FPS on current-gen consoles.”

Slides

References

• Crowds and Pedestrians without Bumper-Car Syndrome, Ken Perlin, Jean-Charles Perrier (Quantic Dream), Mikko Mononen, Bertrand Faure. (ULTIMATE)
• Pedestrians with Airtight Alibis and Level-Of-Detail Trading, Ben Sunshine-Hill. (PREMIUM)

Understanding Player Behavior Using Game Data-Mining

Session Details

Speaker: Christian Bauckhage
Company: Universität Bonn
Time: 11:30
Duration: 30 min

Description

“Wouldn’t it be great if you could predict exactly how successful your game would be post-launch? What proportion of the player spike that your publishers marketing dollars bought will you be able to retain in a week, a month? Turns out, with some data-mining and machine learning skills this is a relatively easy task!”

Slides

References

• Data-Mining RPG Statistics and Predicting Attrition in AION, Dmitry Nozhnin. (PREMIUM)
• Psychology Profiling in SILENT HILL: SHATTERED MEMORIES, Gwaredd Mountain. (ULTIMATE)

Motorstorm's AI: Racing while the World Crumbles

Session Details

Speaker: Kieran D’Archambaud
Company: Evolution Studios
Time: 12:00
Duration: 60 min

Description

“Learn how Evolution Studios created competitive racing AI for the highly dynamic environments of MOTORSTORM: APOCALYPSE. Hear about the challenges for AI when you are racing down the side of a falling skyscraper while the contents of the building rain down ahead, changing the track at every moment.”

Slides

References

• Physics-based Racing AI Controllers and Track Analysis in SUPERBIKE CHAMPIONSHIP, Paolo Maninetti. (ULTIMATE)
• Indie Racing AI in THUNDERWHEELS and Physics-based Vehicle Control, Luis Javier Fornero. (PREMIUM)

THE RESISTANCE AI Bots Competition

Session Details

Speaker: Alex J. Champandard and Richard Kogelnig
Company: AiGameDev.com KG
Time: 14:00
Duration: 30 min

Description

“THE RESISTANCE is a board/card game that combines a perfect combination of hidden information and logical deduction. In this first ever THE RESISTANCE programming competition, watch AI bots compete with each other to find out who is the spy.”

Slides

Design-Driven AI in SPEC OPS: THE LINE

Session Details

Speaker: Daniel Kollmann and Jörg Reisig
Company: Yager Development
Time: 14:30
Duration: 60 min

Description

“This presentation focuses on 2K Games’ controversial cover-based shooter, which places a heavy focus on the player's experience of combat. They will discuss the project history, show examples of the generic enemy and companion behaviors and describe their player-centric design approach and how that affected many AI decisions on the project.”

Slides

References

• Climbing and Sneaking Behind UNCHARTED 2: AMONG THIEVES’s AI, Christian Gyrling. (PREMIUM)
• Design Pitfalls and Cryses for Action Shooters, Mikko Mononen. (PREMIUM)

Behavior Trees for Social Territorial Intelligence

Session Details

Speaker: Claudio Pedica
Company: Icelandic Institute for Intelligent Machines
Time: 15:30
Duration: 20 min

Description

“How can you use behavior tree-like structures to describe social behavior, and express territoriality? This research micro-talk shows a hybrid BT / activation network that allows multiple behaviors to be active at the same time, thanks to a subsumption-like architecture.”

Slides

References

• Human Territoriality for the Next EVE ONLINE's Socially Smart Characters, Claudio Pedica. (ULTIMATE)
• Enabling Playable Social Models and PROM WEEK, Josh McCoy and Mike Treanor. (ULTIMATE)

Rapid AI iterations with Autodesk Gameware Navigation

Session Details

Speaker: Guillaume Aldebert
Company: Autodesk
Time: 16:00
Duration: 45 min

Description

“Autodesk Gameware Navigation is a new realtime SDK that supports automatic NavMesh generation, PathFinding and PathFollowing in highly dynamic environments (avoidance, dynamic NavMesh, swappable sectors). Gameware Navigation also offers state-of-the art remote Visual Debugging tools that allow rapid iteration on your AI.”

References

• Autodesk Unveils Gameware Navigation Middleware, Autodesk.

How to Have Fun in an Asylum (Batman: Arkham City)

Session Details

Speaker: Tim Hanagan
Company: Rocksteady Studios
Time: 16:45
Duration: 60 min

Description

“Discover the tricks and techniques behind the creation of gameplay and AI in BATMAN: ARKHAM ASYLUM and BATMAN: ARKHAM CITY. Learn how the team worked together to create multitudes of enemies where controlled in order to create epic hand-to-hand combat which are unmatched in any other game.”

Slides

References

• Special Report on Production & Methodology. (PREMIUM)

What's Next for Game AI?

Session Details

Panelists: Jurie Horneman (Mi'pu'mi),
    Peter Cowling (University of York), Gabriel Robert (Ubisoft Paris)
Time: 09:30
Duration: 30 min

Description

“The game development community is in a state of upheaval: large AAA studios are disappearing, business models are changing, niche markets are opening up everywhere and a new console generation is just around the corner. What will this means for the future of Game AI? Come along to find out.”

Dynamic Sound and Music in VESSEL

Session Details

Speaker: Kieran Lord
Company: Strange Loop Games
Time: 10:00
Duration: 45 min

Description

“Find out how a small indie team was able to create a great audio experience using AI techniques such as clustering and behavior trees. You'll learn how to guide the player with music, to simulate the sounds of water and even some tools to telegraph events to the player you may not even have known existed.”

Slides

References

• Procedural Music Generation for Games using Statistical Models, Steve Engels. (PREMIUM)

Monte-Carlo Tree Search Tutorial

Session Details

Speaker: Peter Cowling
Company: The University of York
Time: 11:15
Duration: 45 min

Description

“Monte Carlo Tree Search is able to quickly generate plausible initial solutions which can be refined to expert play with additional CPU time. This tutorial will take participants to the point where they can implement MCTS and discuss a range of examples of successful (commercial) application of Monte Carlo tree Search.”

Slides

Implementing the Living City in MAFIA 2's Open World

Session Details

Speaker: Jan Kratochvil
Company: 2K Czech
Time: 12:00
Duration: 60 min

Description

“What details and implementation tricks are necessary to go through to create the living city and characters of MAFIA II? Jan covers streaming, handling of dynamic objects and most importantly what to do with civilians on foot and in car. ”

Slides

References

• High-Performance AI for Dynamic Large-Scale Open Worlds in » Click here to view this embedded content., Sergio Garces. (PREMIUM)

Optimizing Steering-based Animation Control

Session Details

Speaker: Ben Sunshine-Hill
Company: Havok
Time: 14:00
Duration: 30 min

Description

“There are a lot of great collision-avoidance algorithms out there that fall apart when plugged into an actual game's character animation system. You'll see how to make your steering and animation systems stop fighting each other, and how to bring out the best in both. ”

Slides

References

• Collision Avoidance for Game Characters with Velocity Obstacles, Jamie Snape. (PREMIUM)
• Navigation LOOP: Avoid Turning in Circles when Moving Locally, Mikko Mononen. (ULTIMATE)

Reinforcement Learning-based Character Locomotion in HITMAN: ABSOLUTION

Session Details

Speaker: Michael Büttner
Company: IO Interactive
Time: 14:30
Duration: 60 min

Description

“In this talk you'll hear about the novel approach to character locomotion that was used for the crowd characters in HITMAN: ABSOLUTION. The system uses a motion-graph based motion synthesis engine in conjunction with a reinforcement learning based controller logic.”

Slides

References

• Parametric Animations and AI in CRYSIS 2, Sven Van Soom. (ULTIMATE)
• The State of Character Animation Technology in the Games Industry, Alex J. Champandard. (ULTIMATE)

Platforming AI Championship

Session Details

Speaker: Noor Shaker
Company: ITU Copenhagen
Time: 15:30
Duration: 45 min

Description

“The Platforming AI Championship focuses on two critical aspects of computer games; level generation and human-behavior imitation. This session hosts the Level Generation track and the Turing Test track of the competition, with descriptions of the entries, and a live session of playing and evaluation.”

Slides

References

• Infinite Mario AI using A* Search: The Definitive Interview with Robin Baumgarten, Robin Baumgarten.

The Evolution of Codemasters' Racing AI: From DiRT to Showdown

Session Details

Speaker: Nic Melder
Company: Codemasters
Time: 16:15
Duration: 60 min

Description

“All Codemasters racing games in the DiRT, GRID and F1 series have been built from the same AI engine even though each of these titles has a very different racing style. This presentation will give you an overview of the different AI components, what they do and how they've evolved over the course of the years. ”

Slides

References

• Physics-based Racing AI Controllers and Track Analysis in SUPERBIKE CHAMPIONSHIP, Paolo Maninetti. (ULTIMATE)
• Indie Racing AI in THUNDERWHEELS and Physics-based Vehicle Control, Luis Javier Fornero. (PREMIUM)

Take-Away Summary

The official theme for this year's conference was originally "Game AI for Everyone" throughout the call for submissions. Building on last year's turning-point event where AI publicly established itself in a wide variety of domains within traditional video games (design, gameplay, analysis, level generation, etc.), this year's theme emphasized the trend that games are now ubiquitous beyond consoles and AI must follow. Though AI on mobile and in browsers is effectively decades behind PCs and consoles, it's only a matter of time before it catches up. Part of this theme played out in sessions such as the Monte-Carlo Tree Search tutorial that highlighted the explosion of AI-heavy card & board games for instance. However, it generally seemed that AI on mobile and in browsers hadn't yet caught up in all other genres. The conference theme was possibly ahead of its time, though the trend is set to unfold in the next 6-12 months with Key games such as Clumsy Ninja, Creatures, City Conquest, Cotillion finally set for release, following Field Runners 2. These games not only push the limits of AI on mobiles but in general.

The current state of mobile and free-to-play has left the traditional games industry in somewhat of a comfort zone (at best). There were whispers after the GDC AI Summit that our field appeared to be in a rut — but that's a bit too extreme. There's progress being made in a variety of important technical areas and better understanding the implications of existing technology with modern designs / workflows. But in general there was a certain familiarity with solutions being used. Multiple of the biggest franchises (across genres) are effectively using the same AI as they were N years ago. That's not necessarily a problem but it showcases a lack of risk-taking and innovation in design that's portrayed by the stagnation of the AI & gameplay in many sequels and presents a surprisingly short-term risk. Luckily, the tide is turning in AAA games, almost as I write this, with simulation and behavior-heavy games such as Dishonored, Far Cry 3, Hitman: Absolution and Assassin's Creed 3 or even Gunpoint and Monaco — setting the scene for an exciting Autumn for AI enthusiasts.

If that's not enough excitement, over the next few weeks we'll be unveiling our masterplan for the Vienna Game/AI Conference 2013 — scheduled for the first week of September. This time, rather than reiterate on the same format we're going to redefine everything — getting those of you that were so enthusiastic (either in person or online) involved in the process. If you want to join the movement, stay tuned to the conference mailing list! Bonus points if you can figure out how The AI Sandbox™ is involved...

Your Feedback & Comments

“Nice format and excellent content! Game/AI Conference definitely offered the right context to get inspired and share ideas.”
— Aris Theophanidis, AI Technical Lead, Ubisoft Montreal

“The conference was not just packed full of useful insights during the main talks; I learnt as much mingling with the other AI guys between presentations as I did in the lecture theatre. Definitely looking forward to bringing my whole team along next year. PS: The food was amazing!”
— Tim Hanagan, AI Lead at Rocksteady Studios

“It was my first time and I had a great time at the conference! You've done a great job, thank you. I look forward to seeing more cool stuff next year.”
— Marek Roefler, Programmer at CDProjekt Red

“The Game/AI Conference continues to be a highlight of the year for any AI developer or researcher. As the years go on, academia is managing to sit and talk as equals alongside industry veterans, now wanting to work with the industry. Without this conference, I such progress would not have been made as quickly. It feels that when the next big step happens in Game AI, it will thank this event as its catalyst.”
— Kieran D’Archambaud, Lead Game Programmer at Evolution Studios

“The Game/AI Conference is an interesting and valuable part of my year as a game AI developer.”
— Tim Gosling, AI Developer, The Creative Assembly

“The organisation was flawless, the talks were mind-opening and the people were truly amazing. Big thumbs up for the whole Game/AI crew!”
— Julien Desaulniers, Lead Gameplay Programmer, Ubisoft Montreal

“The Game/AI Conference is a great event to meet both AI industry and academic experts in the same place. The AiGameDev.com team does an awesome job of selecting a mix of relevant presentations and useful networking events.”
—Michaël Rouillé, VP Engineering at Golaem

“This event is getting better every year! And Vienna is so nice and friendly place to stay. Thank you very much and see you next year!”
— Petr Kalandra, Student, Czech Republic

“A very enjoyable, interesting and thought-provoking conference. This event represents, for me, one of the most important events to bring together AI games industry developers and members of the AI research community, but with a focus on what is going on in the current generation of commercial games.”
— Peter Cowling, Professor, University of York

Last week at the Vienna Game/AI Conference 2012, Guillaume Aldebert demonstrated Autodesk's new navigation middleware, part of the company's new Gameware initiative. Guillaume, Principal Engineer of Game AI Middleware, gave an interactive presentation from within the tool itself — featuring a whirlwind tour through the product's many different features.

Below you'll find the press release and some screenshots, but there's a lot more to this announcement than the official release. Note, Autodesk was the Gold Sponsor for the conference this year, though it won't affect our journalistic integrity. :-) Read our analysis just below, see what you think!

Screenshot 1: A real-time dynamic and user-modifiable NavMesh, with obstacles integrated at runtime within the mesh.

Autodesk and Middleware

Here's our analysis of the release and official announcement:

• The official release of Recast and Detour in 2009 (and subsequent updates through 2010) caused quite a stir in the middleware industry. Some middleware companies responded by de-emphasizing their navigation businesses, while others returned to the drawing board to produce the next-generation of navigation systems. Still today you'll notice the impact, and Guillaume mentioned Recast multiple times in his presentation.
• Autodesk has invested significantly in navigation in the past few years, building up a skilled team based in Paris. The company also focused its development resources on overhauling Kynapse, which resulted in comparatively fewer announcements about the product (and new features) until Gameware Navigation was introduced last week.
• This new product release signals Autodesk's strong interest in pathfinding and navigation middleware. The market has matured significantly over the past couple years, and although it's still not quite as established as other middleware segments, Autodesk obviously sees potential there. These heavy investments into producing Gameware Navigation shows the company is in it for the long term.
• Overall, there are now a handful of middleware solutions available that offer measurable improvements over open-source libraries. This applies to the runtime pathfinding (performance and reliability) as well as the tool-side generation (turnaround times and robustness). It's great to see companies like Autodesk rise to the challenge, and it's a promising sign for the future of AI in games.

Screenshot 2: Gameware Navigation allows AI characters to adapt to complex level designs through Smart Objects, for example ladders and elevators.

Official Press Release

Re-Engineered Middleware Provides More Open, Accessible and Efficient AI Solution; Empowers Game Developers to Create More Believable Character Behaviors.

Autodesk Inc. has revealed the next-generation of its artificial intelligence (AI) middleware, Autodesk Gameware Navigation. Gameware Navigation is the successor of Autodesk Kynapse AI middleware, which empowers game developers to create believable character behaviors for video games. This technology has been re-engineered to offer developers full source code access, a more accessible API (application programming interface) and remote visual debugging tools.

To date, Autodesk AI middleware has been implemented in at least 100 games to empower the creation of compelling behaviors for non-player characters. Using this technology, developers can help improve game play, while reducing development costs and cutting time to market.

“All of the tools in our Autodesk Gameware product line have been designed to streamline the game making process and reduce the need for costly custom solutions to common production challenges. With Gameware Navigation, we have overhauled our existing AI technology to make the algorithms faster and more efficient, and the API more accessible and intuitive. The result will be a tool that is much faster and easier to use, so programmers can spend more time on high-impact areas of development such as gameplay and design” — Marc Petit, Senior Vice President of Media & Entertainment at Autodesk.

Gameware Navigation provides automatic NavMesh generation, pathfinding and path following in complex game environments. Character and obstacle avoidance, dynamic NavMesh and swappable sectors are supported out-of-the-box. The middleware also offers developers extensible, remote visual debugging tools with record/playback capability, improving the speed and quality of AI iteration.

Availability Game developers can apply for the public beta version of Autodesk Gameware Navigation 2013 on this official page. Autodesk anticipates the middleware will be commercially available during fall 2012. To learn more about Autodesk Gameware Navigation, or to register for a free webinar visit the Gameware homepage.

Screenshot 3: Multi-sector streaming at runtime using previously generated NavMesh data gives predictable results while using fewer system resources.

Revolution is a strong word, but let's be clear about this... Everything you know about animation technology is evolving, from the subtle details of movement to the radical overhauls of animation pipelines. Firstly, did you notice and secondly, are you ready?

Over the past decade, procedural techniques have gone from research prototypes to being applied reliably in mainstream games on a regular basis. While many associate procedural techniques with experimental Perlin-style animation of cartoon characters, developers in industry have been using a wide variety of robust techniques that fall under the "procedural" label. For instance physics simulation, active controllers, inverse kinematics, equations of motion; all these techniques shift the emphasis from data to code.

Now, as game developers understand the implications of this technology, animation pipelines and runtimes are being redefined accordingly — to make the most of the low-level hardware and open up new opportunities in animation expressiveness. This editorial will dig into some of the problems with current systems, and show examples of changes that are happening throughout industry.

NOTE: On September 20th, AiGameDev.com is organizing a workshop on character animation with a focus on procedural techniques. It's an intense one-day masterclass that will bring together the world's best developers in the field. Think you'll fit in? If so, get your ticket now, there are fewer than 15 9 spots left!

Background

The general trend that's been reinforced over the past few years is that data-heavy animation is not good enough, regardless how elegant your motion graph or animation state machine is. Over the years, developers have been increasingly using blend trees to add more variation, parameterization and style to the resulting animations — but those have introduced as many problems as they resolved on the data front.

a. Motion Capture is Slow as Hell

At the GDC 2011, Naughty Dog presented a technique for optimizing blend trees that was introduced for UNCHARTED 3. It involves clever caching and invalidation of the tree's data, to make sure it takes the least time possible to traverse while offloading the computation.

The previous game already did all its low-level blending on the PS3's SPUs for performance reasons, but that wasn't enough. A significant amount of time was being spent preparing the data on the main CPU before anything could be offloaded. More time is spent streaming, decompressing and shuffling data around than in the actual blending. (This was discussed further via Twitter » Click here to view this embedded content..)

The obvious conclusion is that these performance problems are inherent to data-heavy solutions. Regardless how well you optimize your blending, the performance hit is managing all this data. If Naughty Dog is reaching the limits of the hardware here, what chance does everyone else have? :-)

b. Motion Capture Costs a Fortune

Ivo Herzog and Sven van Soom last year presented the approach that Crytek took for the parametric animation in CRYSIS 2, and going forward into CRYSIS 3. (See our coverage from the Game/AI Conference 2011.) The bulk of the locomotion system is actually a parametric animation with three dimensions: slope angle, turning rate, and movement speed. If you support arbitrary angled terrain, that turns into a 4D animation!

In total, this results in dozens of animations that need to be motion captured, and this is just one of many parametric animations that are required to build a locomotion system. Not to mention this is just one character style. You'd need to schedule motion capture sessions for walking (slow to fast), running (jogging to sprint), sneaking or tactical walking, etc.

Obviously, studios the size of Crytek can afford this investment in data & clean-up — but can you?

c. Motion Capture Has Slow Turn-Around

Did you know the big studios that are serious about character animation have their own motion-capture studios? EA Canada in fact has its own building dedicated to it, where FIFA and NBA animations are captured. All this helps reduce the turn-around times of scheduling mocap sessions and getting the results as-soon-as-possible.

The hassle of using motion capture has certainly dropped over the years thanks to more affordable hardware that can work in office-size rooms, or even better clean-up and post processing technology. But the overhead of turning a design into polished character animation states (via motion capture) is still best measured in days.

Can you schedule a motion capture session for your game animations on short notice? Do you have animators available to clean-up the resulting data?

The Turning Point

The good news is that advances in technology, specifically procedural animation, are changing all of this. In some studios it's faster than others, but radical changes are happening nonetheless!

d. Procedural Techniques Provide Better Performance

In a presentation at GDC 2011, Tam Armstrong showed off some of the technology behind HALO: REACH. In particular, he showed how inverse kinematics was used beyond just constraining the feet for short ranges of keyframes while feet are planted. In the HALO engine, IK is now used to adjust the foot position every frame relative to the floor, regardless of whether it's planted or not. (This has visible benefits on slopes.)

The same techniques are used for the upper body. Simple poses provide the context for the animation, where the character is looking or aiming, and the IK take over to adjust the position of the hands to match exactly with the current weapon. Controls are provided to the animators to interpolate between forward- and inverse kinematics.

During the questions and in conversation afterwards, the idea of having IK always on was elaborated further. If you assume the feet and hands will be automatically placed every frame anyway, then you can significantly reduce the amount of motion-capture data you need at runtime. The IK will be able to reproduce it on demand, effectively functioning as a domain-specific compression scheme.

Using IK in this way opens up the doors for better performance on platforms such as the PS3 (and other platforms) since less data needs to be shepherded from the disk and decompressed before hitting the dedicated processors like the SPU (or, arguably a GPU). Since proportionally more time is spent on computation rather than data management, this can be parallelized easier.

e. Procedural Techniques Have Low Overheads

By putting more emphasis on animation code rather than animation data, it becomes significantly easier to make changes. Over the years, customizable blend trees or animation graphs loaded from files have allowed technically-oriented animators to quickly prototype ideas. Similarly, procedural techniques give even more power to animation-oriented programmers and help them get incredible results with even lower overheads.

One specific example of this is OVERGROWTH (see our video interview on the topic). David Rosen is the one-man development team, and is responsible for both creating animations and setting up the underlying code. By using more code (e.g. IK-based locomotion, physics-based combat animations) than traditional AAA games, he manages to get incredible results with a fraction of the budget.

f. Procedural Animation Can Look Amazing

The primary argument made against procedural techniques over the years has been about the quality of the movement. It has managed to produce stylized results, but not necessarily believable animation that can compete with motion capture. However, thanks to a variety of different algorithms and techniques used in animation systems, that is now also changing.

One type of procedural animation that's becoming increasingly popular is physics-driven animation, which puts the emphasis on simulation to generate character movement (or augment it). For instance, MAX PAYNE 3 uses a mix of NaturalMotion's physics-driven animation technology with Rockstare's internal R.A.G.E. engine, which uses a proprietary implementation derived from Bullet Physics.

I worked on early animation prototypes of MAX PAYNE 3's animation for a few years, and of course, there's a large quantity of data under the hood too — in the shape of parametric animations. For instance, when lying on the floor you can control the character to aim in any direction; it's like a form of IK implemented by blending different poses together. The game does push the balance further toward procedural than other games today.

Modern Procedural Techniques

If we had to redesign animation systems knowing what we do now, what would they look like? It's radically different than our current solutions, which rely on a data-heavy workflow.

Runtime Rigs

The term "runtime rig" has been floating around in technical animation circles for a while now, but it's a masterclass with Laurent Ancessi that introduced the concept here at AiGameDev.com. He uses runtime rig to describe an implementation of the animation skeleton that includes additional runtime features to improve control.

In editing tools like Maya or Blender, most game studios use a character "rig" to help animators apply postures to the skeleton while creating animation clips. The runtime rig is an implementation of this within the engine. As a more formal definition, we'll use the following:

“A runtime rig is an additional layer above the traditional skeleton bone hierarchy that provides additional effectors, implemented dynamically in-engine with inverse kinematics, to provide more convenient and higher-level control that complements forward kinematics.”

Of course, game developers have been using inverse kinematics for decades now. What's different is that we can now rely on using it consistently throughout the runtime pipeline, and not only when a foot plant annotation is set or when a weapon is being held. Having the runtime rig always on means we can for example animate end-effectors of the IK chain only (e.g. feet, hands) and rely on runtime computation to figure out the intermediate joint (e.g. knee, elbow).

Active Skeleton

A large proportion of games use ragdolls these days, driven by a traditional physics simulation under the hood that combines dynamics with collision detection. Some games also use rathermore active ragdolls, using dynamically calculated forces to drive the skeleton toward specific poses. For instance, a character falling might drive towards a flailing animation and a character bouncing against the wall might drive towards a fetal position. As well as this, some games also include physics simulations on "accessory" bones like various clothing items, or even weapons like a ball and chain.

What's relatively new is the idea of having an "active skeleton" that's always on and applied to the whole body. Why limit the physics simulations to hit reactions and on cosmetic bones when it has the potential to help with overall character responsiveness? Looking at two examples.

• OVERGROWTH uses such an active skeleton during combat to make sure all hits and responses behave in physically-plausible fashion. The advantage of this approach for Wolfire is that significantly fewer keyframes are required to create combat animation hits and responses.

• MAX PAYNE 3's dive animations are also actively simulated, and you'll notice how his posture changes as he collides with obstacles in mid-air. In this case, the advantage of the active skeletons is that you only need a diving pose (single frame) which the physics simulation will augment.

There are down-sides to this approach, including performance of the simulation, stability of the resulting animation, believability of the motion, and technical challenges to set this up. However, as more developers use this approach we're making fast progress in all of these departments.

What's Next?

If you've read this far you'll probably want to attend our intense one-day workshop on character animation technology, with a focus on the procedural techniques mentioned in this editorial. The workshop will bring together the world's best developers in the field — including Ubisoft Montreal (FAR CRY 3, WATCHDOGS), Arkane Studios (DISHONORED), IO Interactive (HITMAN: ABSOLUTION), Microsoft Game Studios, Avalanche (JUST CAUSE), Ubisoft Paris (GHOST RECON: FUTURE SOLDIER), Yager (SPEC OPS: THE LINE), etc.

There are many opportunities that will open up as we start relying on Runtime Rigs and Active Skeletons more often. Of course, this will lead to new challenges as well! To best manage a Runtime Rig, engines will need an additional layer of AI decision making to decide what posture and gestures can be sensibly combined — e.g. wielding weapons. Then, to make the most of an Active Skeleton, engines will also require higher-level situation awareness to be able to drive towards the most appropriate poses in a context sensitive way...

It's only a matter of time before all these ideas make their way into commercial games. Some already have! But for the rest, it's an exciting time to be in animation programming...

» Click here to attend our one-day procedural animation workshop! There are fewer than 15 9 spots left!

If you want a challenge that's not only at the cutting edge of game AI research but also fun to work on, then look no further! How about a game that combines the best aspects of Mafia (the party game) and Mastermind (the reasoning game)? Join the competition to build a bot that can deduce who is a spy, then deceive other bots into thinking it's not a spy!

Modern board games have found an important place in Game AI research, providing many additional challenges than the classical games such as Go, Othello and Chess. In particular, larger numbers of players, partial information, non-determinism and co-operative play are all interesting traits of modern board games. Don Eskridge's THE RESISTANCE, a hybrid card and board game that's ideally played in small groups, is the perfect competitive environment.

NOTE: If you'd like to have fun and support the designer, grab a copy from BoardGameGeek. You can enter the competition whether or not you own the game. Many thanks to Don Eskridge for his enthusiastic support of this initiative!

Photo 1: The very first impromptu RESISTANCE competition, held at the Dagstuhl seminar on Artificial and Computational Intelligence in Games. There were 8 bot entries written in Python, and written about in this report.

Quick Facts

1. You can get started from the code on GitHub, and join the mailing list for notifications and support!
2. The deadline is September 14th at 23:59:59 UTC, though we encourage you to submit early versions of your bot beforehand.
3. The results will be announced at the Game/AI Conference 2012, to be held in Vienna on September 18th.
4. Anyone can enter the competition, and you don't have to attend the event to participate in the competition.
5. If you attend the conference and submit a bot, you get a special edition mug as a bonus!
6. If you submit a bot that beats the intermediate AiGameDev.com bots, you win a bonus PLUS membership.
7. The top three places include PREMIUM subscriptions to AiGameDev.com for you or your research lab!

The Rules & Gameplay

THE RESISTANCE competition features five players split into two teams, the Spies (2x red players) and Resistance (3x blue players). There are five missions that take place involving a subset of the players — each with one or more rounds of voting. The team that's first to secure three missions wins; Spies must sabotage missions, and Resistance operatives try to make the mission pass.

For example, the current mission leader picks a team of 2 players to proceed on the first mission. Everyone discusses it and votes whether they think that's a good idea. Spies try to get onto the mission, and Resistance try to avoid Spies. Then when the mission proceeds the Spies will generally try to sabotage the mission, while Resistance operatives must support the mission.

The Bot API

The game is actually easiest to explain to programmers by the API! Here's what it looks like in Python, for example in a file called mybots.py.

class Stochasticator(Bot):   
    def select(self, players, count):
        """Pick a sub-group of players to go on the next mission."""
        return random.sample(players, count)

    def vote(self, team):
        """Given a selected team, decide whether the mission should proceed.""" 
        return random.choice(» Click here to view this embedded content.)

    def sabotage(self):
        """Decide what to do on the mission once it has been approved."""
        return random.choice(» Click here to view this embedded content.)

Then you can run your bot against the others using the following command line:

# Play 1k games with your bot on its own...
> python competition.py 1000 mybots.Stochasticator
# Run 10k games against basic AiGameDev.com bots.
> python competition.py 10000 mybots aigd

The results will then be displayed afterwards, and look something like this:

SPIES				(voted,		selected)
  LogicalBot       72.13% 	 54.87% 	 27.25%
  Statistician     60.66% 	 48.11% 	 23.70%
  Bounder          59.84% 	 46.13% 	 24.53%

RESISTANCE			(vote,		select)
  Bounder          47.94% 	 100.0% 61.40% 	 71.24%
  LogicalBot       33.94% 	 100.0% 37.18% 	 58.84%
  Statistician     26.49% 	 96.81% 40.38% 	 35.74%

TOTAL
  Bounder          64.19%
  LogicalBot       55.24%
  Statistician     45.81%

In this case, LogicalBot is the best spy and won 72% of its games being voted 54% of the time and selected 27% of the time. Bounder is the best Resistance player, voting for Resistance and against spies 100% and 61% respectively, while correctly selecting 71% of the time. Bounder also wins most overall at 64% of his games against the default provided bots in aigd.py.

Photo 2: A round of voting during a RESISTANCE mission. Each vote must balance the process of revealing information as well as securing missions for the purpose of winning.

Participating

If you'd like to participate, here's everything you need to know:

• Code Repository — Download the code from GitHub using "git pull https://github.com/aigamedev/resistance.git" then look at the bots.py file as an example. Run the competition.py script as above.
• Mailing List — The Google Group is the central place used for updates, support and coordination. Join it if you're planning on participating.

For any further questions, join the mailing list.

Competition Details

The details are to be finalized in conjunction with the participants, but here are the current rules.

• Only one bot is allowed per research group or per independent researcher.
• The competition will be run in two rounds, one preliminary qualifier against beginner to intermediate bots. The second round picks the best performing bots and plays them against each other.
• The number of games run in the two rounds of the competition will be in the order of 1,000 games.
• The maximum time taken for each API call is 0.1s. Bots that time out or throw exceptions are disqualified.
• Source code will be released after the competition, under a license of your choice.

Are you looking for a fun artificial intelligence project? Do you think you have what it takes to build a competitive bot in 1 month? Want to secure some awesome prizes in the process? Then this competition is perfect for you! Go download the code and join the mailing list to get started... Then see you at the Game/AI Conference 2012!

Building on the incredible success of last year's record-setting event, AiGameDev.com is proud to announce the program of the fifth annual Game/AI Conference in Vienna, Austria, co-organized with the University of Vienna where the event is held. This year's conference takes place on September 18th and 19th 2012, preceded by a workshop on behavior trees on Monday 17th and followed by a workshop about procedural character animation on Thursday 20th. The schedule blends invited sessions from top AI developers from industry as well as tutorials, reviews and R&D oriented sessions.

Special Thanks

The organizing committee consists of Helmut Hlavacs of the University of Vienna, Petra & Alex Champandard and the rest of the AiGameDev.com team. We'd especially like to thank our current sponsors for the event, Havok and PathEngine.

If you're one of the few still looking for reasons to attend, here's the current schedule for those four days! Tickets are available in our store. If you're a student and want one of the last few Bronze tickets (at 48€) then email us ASAP at <billing at AiGameDev.com>.

Keynotes & Invited Talks

BATMAN: ARKHAM CITY

This year's winner of the “Best AI in a AAA Game” Award on AiGameDev.com is featured in a keynote. Tim Hanagan will present the processes and methodologies that Rocksteady uses to develop its AI. The team shipped some of the best-rated games with fewer developers than most other AAA teams. Find out how they do it!

HITMAN: ABSOLUTION (x2)

Michael Büttner will present the character animation technology based on reinforcement learning behind the latest HITMAN game, and how it improved the workflows and empowered animators. In a separate presentation, Kasper Fauerby will show how IO Interactive managed to create game-defining crowds that run at interactive rates on modern consoles.

GRiD & F1 2012

Nic Medler from the Codemasters Racing team will present the evolution of the AI in their titles over the years, including the F1 series as well as the critically acclaimed GRiD and DiRT franchises. How has racing AI changed over the past decade?

MAFIA 2

Jan Kratochvil is a Lead Programmer at 2K Czek, and will present the key challenges of building a large city simulation of pedestrians in MAFIA 2, an open-world game with rich interactions. You'll find out the challenges in AI design and implementation on modern consoles.

VESSEL

Kieran Lord is an independent developer who contributed to the indie puzzle platforming hit VESSEL. The game features an adaptive audio system to truly capture the fluid nature of the world. Kieran will show the behavior tree-like implementation that to maintain musical structure with authorable variations.

» See the speaker spotlight on Kieran's presentation about VESSEL.

SPEC OPS: THE LINE

Find out more technical details about 2K's latest cover-based action game. Among other things, find out how reusable behavior trees were built for enemies & companions, the player-centric design approach used, and how the game emphasizes communication and interaction between the player and the A.I.

MOTORSTORM: APOCALYPSE

Kieran D'Archambaud will be presenting the details behind the AI of the MOTORSTORM franchise. The game not only requires mechanical skill for one of three classes of drivers (bikes, cars and trucks) but also higher-level route selection too. Find out how Evolution Studios solved this problem in practice.

Tutorials

Predicting Post-Launch Engagement from Gameplay Traces

Wouldn't it be great if you could predict exactly how successful your game would be post-launch? What proportion of the player spike that your publishers marketing dollars bought will you be able to retain... in a week, a month? Turns out, with some data-mining and machine learning skills this is an easy task with Christian Bauckhage!

Monte-Carlo Tree Search and AI for Board Games

In search of AI's holy grail, researchers recently discovered Monte-Carlo Tree Search (MCTS). It works elegantly without requiring you to add expert heuristics, but even better, it performs even better than other techniques if you do! Find out all about MCTS and its applications to board games, particularly on mobile platforms, in this tutorial with Peter Cowling.

Workshops

Behavior Tree Workshop

This standalone workshop takes place on September 17th, the day before the main conference, and is dedicated entirely to creating AI with Behavior Trees — with a particular focus on character logic. The day is split into four parts, each covering an important aspect of creating believable character behavior.

1. Implementation: Principles, API, Memory Allocation, Performance.

2. Architecture: Integration with external game systems.

3. Authoring: Building for re-usability and common design patterns.

4. Tools and Debugging: Visualizing, rapid prototyping, logging.

» See the details of this behavior workshop.

Procedural Animation Workshop

On September 20th, the main conference is followed by an intense day-long masterclass about procedural character animation. It's the industry's only event dedicated to the technology of character animation. You’ll find out about two procedural techniques, their implementation and optimization, how pipelines have been completely redefined, how blend trees and motion graphs have been impacted by the changes.

1. Runtime Rigs & Inverse Kinematics
2. Locomotion and Interaction
3. Active Skeletons & Physics Simulation
4. Reactions & Combat

» See the details of this animation workshop.

Competitions

Deceptive and Deductive Bots for THE RESISTANCE

This brand new competition is at the forefront of modern board game AI, letting competitors write bots that can deduce who is a spy, and otherwise deceive non-spies. This is a game designed for humans, but turns out to be not only challenging but entertaining to write AI for.

» Click here to find out how to participate.

Platforming AI Level Generation & Turing Test

The Infinite Luigi AI competition focuses on creating levels that players find interesting, but entirely automatically using procedural generation. The competition also features bots that can play platforming games like a human would, akin to the Turing Test. Join us for this entertaining session and help evaluate the candidates!

Networking Opportunities

Last but not least, there's the networking. With the majority of the leading studios in Europe attending and sending multiple developers, there's no better place to look for opportunities! Over the course of the two days of the Game/AI Conference and the Workshop days, there'll be multiple coffee pauses and lunch breaks that will give you the chance to socialize and find amazing projects to work on.

There'll be a set of organized events as well:

• September 16th, Workshop Mixer. 20:00-LATE.
• September 17th, Demo & Poster Reception. 19:00-LATE.
• September 18th, Official Party. 19:00-22:00.
• September 19th, PREMIUM V.I.P. Dinner. 20:00-LATE.
• September 20th, Workshop Breakfast. 8:00-9:00.

Many of the leading developers from the games industry, programmers from related fields like serious games and simulation will attend the Paris Game/AI Conference (it's the largest in the field, worldwide) so be sure to bring your business cards!

Now What?

If you haven't got your ticket yet, best secure your seat now!

1. Main Conference SILVER Tickets at 96€.

2. Main Conference GOLD Tickets at 192€.

3. Behavior Tree Workshop Tickets at 497€.

4. Procedural Animation Workshop Tickets at 497€.

5. Bronze Tickets at 48€ for students only, email us!

For group purchases, also contact us directly at at <billing at AiGameDev.com>.

Welcome to the first episode of our new series: BWONG! In this series you will get to see some of the work that goes on at AiGameDev Labs.

In this episode we take a quick look at creating ragdolls. Ragdolls are the first step to combining our existing frame-based and IK-based animation systems with physical interactions between the character and the environment. On top of that, they are simply fun to play with.

If you'd like to be notified of the next video in the series, follow us on Twitter, Facebook or YouTube.

While procedural generation techniques have been sweeping the indie games scene, and incrementally making their way to AAA consoles, social games have yet to make the most of them. The algorithms used to procedurally generate content for typical games on social networks need to be very different than what's otherwise done on PC. Yet, there is a lot of promise for both innovative gameplay and new business models.

In an interview last Sunday, broadcast live via AiGameDev.com, Ken Stanley and Sebastian Risi discussed the applications of evolutionary algorithms to their upcoming social gardening game, PETALZ. In integrating an evolutionary technique called NEAT into Flash, the game is breaking new ground in a variety of different areas...

NOTE: On Sundays at 18:00 UTC, AiGameDev.com broadcasts interviews or masterclasses on the topic of artificial intelligence in games. You can attend those live free! The replays are available for two weeks for PLUS Subscribers, and higher memberships like PREMIUM and ULTIMATE also give you full access to the edited recordings afterwards.

Screenshot 1: Family tree of a particular flower in PETALZ, including contributions from multiple players, breeding two plants together as well as single-plant mutations.

Collaborative Breeding

Stanley's research lab at the University of Central Florida, is famous for its work in two areas: firstly, for applying evolutionary algorithms into games — such as Galactic Arms Race (GAR) and Neuro-Evolved Robotic Operatives (NERO); secondly, for user-driven evolutionary explorations such as PicBreeder. Combining these two approaches together turns out to be very well suited to social games.

In PETALZ, the players controls the evolutionary algorithm by selectively breeding flowers together, or mutating single flowers and picking the prefered offspring. Each flower can then be shared with friends, who can then continue the breeding process. Some flowers have involved already dozens of players to create.

Screenshot 2: An example flower with a simplified representation of the pattern-producing network (CPPN) on the right, and its DNA parameters on the left.

Crafting Unique Content

In terms of content, PETALZ distinguishes itself from many other social games by allowing players to craft unique flowers. This adds a much more personal touch to the game, and a strong sense of ownership over the core elements of the game. Flowers that are sent as gifts to friends carry more meaning because of it.

The underlying procedure is a Flash implementation of Hyper-NEAT, which evolves pattern-producing networks known as CPPN. The CPPN is made up of a variety of pattern nodes such as Gaussian functions, sine and cosine waves, as well as mirroring functions, etc. See this paper for details:

Risi discusses the specifics of applying the algorithm to flowers in the interview.

Exploring Flower Space

On the meta-level, PETALZ is an interesting experiment that fits into Stanley's research perfectly. Given a large space of possible phenotypes (in this case flowers), how do humans and machines combine to explore the space of options? Machines on the one hand have no sense of what's interesting, while humans may not be as exhaustive or creative (in a random way).

Stanley's recent keynote at ON SPLASH 2011, called "Searching Without Objectives" digs into some of these topics. Evolutionary algorithms benefit from not being driven towards a particular goal, and humans in this case can provide the exploration.

NOTE: The broadcast replay of this interview is available for another week to PLUS, PREMIUM and ULTIMATE members on AiGameDev.com. You can find it from the the broadcasts page.

At the AiGameDev Labs, we're always on the lookout for new ideas that will drive innovation in Game AI. Recently, we've been doing more of this and you'll be noticing increasing changes as we spend more time chasing those ideas that inspire everyone on the team here!

Today, we are releasing a teaser video showing the first stage of the development to support these ideas. This video is somewhat of a teaser for a much larger plan that you will no doubt hear more about over the next couple of months...

From Collision To Dynamics

We decided the best place to start was with the low-level, specifically the simulation aspects of our entities. There's a lot of potential for using such low-level simulations to improve the quality of games, as well as the behavior of characters. Today's video shows off some of the physics work that we have added over the past couple of weeks.

Until recently, we used the Bullet Physics Engine only for collision detection during navigation graph building and runtime line of sight tests. During the past couple of weeks we have been integrating the dynamic physics components of Bullet with our engine, initially supporting physical bodies and then expanding that with ragdolls. This video shows the current state of the ragdolls in our engine — low-fidelity ragdolls integrating both physics and skinning.

Grab The Binary?

Also today, we are making the scripts to this demo available to our ULTIMATE members. The release includes all the Python code from which the video was created, along with the underlying binaries for the engine. Much of our internal technology is already supported with python bindings. As we build on our technology we will be fleshing out these bindings and the documentation that goes with them.

If you're not an ULTIMATE member, don't fret. You will still be able to download the videos and follow along with our development and we're glad to have you along for the ride. If you'd like to be notified of the next video in the series, follow us on Twitter, Facebook or YouTube.

The Octagon Theory (TOT) is a two-player board game in which the goal is to push the opponents pieces off the edges of an octagonal field or in the hole in the middle. For a game with few rules it is surprisingly complex and offers strategic depth which makes it challenging to master for an AI opponent.

With the advent of mobile gaming and the popularity of board games on this platform the need for efficient AI for such games has increased in the last years. Board games are an interesting field because of their discrete nature and the often immense branching of their search tree which makes them hard to solve by brute force. Learn more about the state of the art in this field in our Monte Carlo-Tree Search Article.

We sat down with Daniel Huffman, the inventor and programmer behind the game, to talk about his approach for the computer opponent which is able to challenge even experienced players.

Introduction

Q: Can you describe the gameplay of the octagon theory and the goals you had in its design?

Daniel Huffman (DH): The Octagon Theory (TOT) was very loosely inspired by the Japanese sport of Sumo where the goal is to knock one's opponent to the ground or push the opponent out of the ring. So TOT is a two-player 'pushing' game.
You and your opponent basically take turns rotating and placing directional pieces of various strength on the board attempting to knock the opponent's pieces off the board. When the pre-decided number of game turns counts down to zero, the player with the most pieces on the board is the winner.

TOT gameplay. Red Player places a piece and pushes one of his blue opponents off the board.

Along with the Sumo inspiration it was very important to me for TOT to be a very pure and simple game that didn't need a rule book. A game that could be learned by just watching it being played once or twice. But of course I also wanted it to be deep.

I think most of the classic board games like chess, checkers, backgammon, go, etc. all fit within that simple but deep description. And I think that's the reason that they all have lasted down through the ages. And it is more important to me for TOT to be considered as one of the classics and to be played forever than it is for TOT to become an instant sales success. I want TOT to be my legacy.

Q: Which strategies and ways to play can one apply in this game?

DH: If you play in a purely offensive way you'll probably lose. I consider a defensive/offensive mix the best. Always start by securing the strongest positions on the board. Of course those are the positions that are furtherest from the board edges and the center hole. And instead of always trying to push opponent pieces towards the edges or off the board in one move, try to slowly setup the opponent pieces by slowly forcing them into a pattern which will allow later use of one of your stronger pieces to 'kill' three or more opponent pieces with one move. And timing is important too... don't wait until too late in a game to use the stronger pieces for two reasons...

1. You may run out of turns before you can make good use of all your stronger pieces. and
2. The board may become too crowded to make effective use of your stronger pieces.

And don't get the impression that placing a piece near the edge is always a bad move. If the pattern of pieces on the board is right, with 'cannoning' you can place your piece in just the right edge position to 'kill' opponent pieces that are located on far edges of the board.

Of course blocking tactics are useful at the right time and with the right pattern.
Also I have to mention that I keep learning new strategies the more I play TOT. The funny thing is I had no idea how deep the strategy could be when I designed the game. It seems to have taken on a life of its own. It's probably because of the addition of the one, two, and four-pieces (directional). The original Apple II version of TOT that I made back in the mid-1980's had only one piece...the non-rotatable 8-piece. And an unlimited number of them. So in the new version of TOT I think strategy depth has increased exponentially.

Since the game is so new I think most players have yet to develop any advanced or deep strategies. But what I have seen is very aggressive gameplay - trying to always push the opponent's pieces off the board, without giving any thought to securing safe positions if it means not being able to attack the opponent. Also timing is wrong - they may wait until too late to use the stronger pieces - the pieces that can push two to eight opponent pieces in one move. And they forget to use piece rotation and 'cannoning' effectively.

Also when playing online I notice that some players will mimic my moves because they think since I designed the game that I must be making the best moves. In this case I'll sometimes make illogical moves just to confuse my opponent and make him/her get hung up on trying to figure out why I made that move.

Developing the AI

Q: How did you approach the development of the AI. Which resources did you use while you where researching your AI and where did you get your inspiration from.

DH: Back in the late 80s when I developed the AI for TOT there was no Internet and I didn't know much about AI (even now I don't). So my inspiration came out of the early Apple II games and what game logic I could find in the few English-language personal computer books and magazines I could get my hands on here in Tokyo. The actual ideas I had about AI came out of simple programing and what one could do with it - mostly comparison, and searching for the highest value in an array.

My actual approach went like this: If I were the computer, where is the best place I'd place a piece? It was just common sense to place a piece where it could kill the highest number of opponent pieces and/or move the opponent pieces into weaker positions - weaker positions being those that are closer to the board's edge or to the center 'black hole'. Also TOT had only one piece - the 8-piece that attacks opponent pieces in all eight directions. And this 8-piece was unlimited in number and required no rotation computation. So the AI was a lot less complicated than the current AI (more about this below).

Q: You might have tried a brute force solution. This naturally leads to the question of the size of the search space. How big is it and is it possible to brute force it in a minmax approach? Did you think about pruning the search space?

DH: I guess I do use a brute force approach. The AI scans every open position on the board and evaluates how much damage it can do from that position, keeps a record of it and moves to the next open position, does the same evaluation. If the AI can do more damage from this new position than it could have done from the previous position, this new position is marked as the potential position to move to. This is repeated until all open positions have been evaluated. Currently I only do a single breadth search. I don't do any 'what if' scenarios, or do any depth comparisons of potential moves to see what consequences a move will have a few turns down the road. The AI is still very basic. But it is a bit surprising at how effective it is. But I still wonder how effective it'd be against a very serious player of perfect information board games. I have never gotten to the point of pruning the search space because my AI is still too simple to require it.

Q: Do you have an evaluation function/weighting scheme and which aspects factor in?

DH: Lots of evaluation and weighting: For example. Aggressive vs defensive play. The AI can be adjusted to get more aggressive (or defensive) at any point in the game. But right now this is a one time only switch. Each position on the board is weighted. Safer positions are given higher values. This value is added to the value computed for each open position depending on how many 'kills' (push opponent pieces off the board) and/or how many 'pushes' (cause opponent pieces to move to a less safe position) will occur if a piece is placed in the candidate position.

Description of evaluation function/weighting scheme

1. Scan all positions from top-left to bottom-right.
2. If the first board position isn't open move to the next position until an open position is found.
   
   
3. Get board weight for this position then scan in each of the eight compass directions (N, NE, E, SE, S, SW, W, NW) as described in step 4 and 5.
4. In the north compass direction look for an opponent piece. If an opponent piece is found and it can be 'killed' (knocked off the board) then add to the board weight the 'Normal Kill' value (e.g 34), If the piece can't be killed but can be 'pushed' to a position with a lower relative (to current value) weighting add +5, if the piece will be pushed to a position with a higher relative weighting add -5. The total of the additions becomes the temporary kill value for this direction.
5. Repeat for the rest of the compass directions. Add all the temporary kill values to come up with the total kill value for this position and store the value and the position location for later comparison.
6. If this total kill value is equal to or higher than the previous kill value, replace the previous total kill value and board position location with the new total kill value and position location. If this total kill value is equal to the previous kill value build a list of equal kill values. The kill value will later be selected randomly from this list.
   
7. Go back to step one and repeat for all open board positions. When all positions have been tried, the one with the highest total kill value is selected (or selected randomly from the equal kill value list if it exists), and its board position location is passed to the client which handles the killing/pushing of the opponent pieces. The client then passes the new board state to the AI.
   

Q: Which heuristics did you use in your AI and which heuristics did you find while you where playing the game yourself.

DH: No heuristics or learning algorithms are used. One thing I learned while playing, that the AI doesn't consider, is strategically blocking opponents' moves. Until recently I only considered moves that could do damage, and if no damage could be done, to place a piece in the safest possible position - far from the edges or center hole or the board. I soon discovered a 3rd way of playing - place pieces in THE positions from which the opponent could do a lot of damage. (This is something I want to put in an updated AI.)

Q: Do you have different difficulty settings for your AI - if so how did you achieve the different behaviors?

DH: I have difficulty levels. But instead of choosing a difficulty, you chose an AI player that is rated as aggressive or defensive with a strength rating on a 1 to 10 scale. My strongest is only rated at 4 as I expect I can make the AI a lot stronger using 'real' AI techniques. And I expect other people, like the people who visit AiGameDev.com, can do a lot better than I can. The weakest AI players use an earlier version of the AI that in its implementation is just not a good as the newer version. On top of that I use weightings to adjust if the AI will chose a safe position that does little damage over a position that does lots of damage. A random factor is also used to decide which it will chose. Also adjusting the weighting the AI gives to kills makes it weaker/stronger. How early and when to use the successively stronger pieces is also taken into consideration.

Q: How many different versions of your AI did you develop? What did not work that you thought would work - were there any surprises?

1. It beat me the 1st time (and every time) I played. I could never beat it which I thought was cool, but weird since I was effectively playing against my own thought patterns.
2. The computer would take about two minutes to make a move. Way too slooooow.

This led to the 2nd minor version: I kept the game in Applesoft Basic but I redid the complete AI part in Motorola 6502 assembly language. I had to order a book from the USA and teach myself assembly language. There was one surprise:
It was FAST! Way too fast!. As soon as the human player (me) would make a move. BAM! the AI would make its move. I'd make my next move. then BAM! the computer would make its next move. This was also cool but it didn't make for good game play - no suspense over what the computer would do. So I simply introduced a loop that'd wait for a random number of seconds before the computer would make its move.

The 2nd major version is the current one in which the AI has to consider which piece to use, not only the 8-piece from the original TOT, but also the new 4-piece, 2-piece, and 1-piece. And the rotation of these new pieces. And in addition the AI has to consider that only the 1-piece is unlimited in number.

There are a few of minor versions in the game that just make use of weighting to change the 'personalities' and strength of each AI player. And there are a few unreleased minor versions that dealt mostly with deciding which piece to use while taking into consideration how many of each piece was left. They are unreleased because I didn't think they were very effective.

Testing and Porting

Q: How did you test your AI?

DH: The old Apple II version of TOT could play AI against AI. But it was the same AI just taking turns so it wasn't used for evaluating AI algorithms. But it was sure fun to watch.


The new AI was just playtested by me, some beta testers, and my 90-year-old Japanese Mother-in-law who I refer to as the Chief Beta Tester. She is really sharp and many of the current UI mechanics came from her suggestions. But most importantly, the AI constantly improved due to her year's worth of play-testing. She'd easily beat the early versions of it, find bugs, and point out stupid or illogical moves that the AI would make in certain situations. (The easier AIs even now make some stupid moves). I'd make improvements, give her the new versions, and she kept play-testing. She'd play for hours every day. After about of year of this we decided that the AI was pretty good because my mother-in-law, nor I, could seldom beat the stronger AIs. The strongest AI that shipped with the game was probably the fifth major iteration.

Q: How did you approach the porting from the older version to Corona and the iPhone/iPad versions?

DH: Getting the old Apple II version of TOT to the iPhone/iPad wasn't so much of a port as it was a complete redo because I don't have a digital version of the source code, just an old dot matrix printer printout which I shallowly reviewed to refresh my memory. I then thought about how I could add more strategic depth to the game. That's when I came up with the 1, 2, and 4 pieces that could be rotated. With that new concept in mind I considered porting TOT to the Nokia N-810 which I had at that time. But the dev tools that were available for that platform were not integrated and were overly complicated, and the iPhone was really starting to hit its full stride. So before I even bought an iPhone I read some iOS dev books and liked what I saw...the tools and development environment was tightly integrated.

I then bought an iPhone, signed up for Apple's iOS Developers program, and tried the standard Apple development approach using Objective-C and Cocoa Touch. Obj-C and OOP programming weren't hard but trying to learn the Cocoa Touch library was a bit much. There is just so much to it and it seemed like it'd take forever to learn it well enough to be able to accomplish anything substantial with it. That's when (I don't remember how) I came across Ansca Corona. And it blew my mind. A week after downloading the free version I had a TOT proof of concept running, something I couldn't achieve with Obj-C/Cocoa Touch even after six months of study. A good example of why developing in Corona was so much faster was that you could get an image on the screen with just one line of Corona code while doing the same in Obj-C/Cocoa Touch would take a whole page of code.

The current skin (images) of the iOS version of TOT, the Octagon Theory website, and the on-line, two-player Flash version of TOT were all done by my partner Ben Walker at http://ubacoda.com

Anyway, the whole concept of TOT was in my mind and I pretty much remembered how I coded the old Apple II version so I just started coding away - with no serious design documents or specifications.

I completed TOT after a year and a half of twenty to thirty-hour weeks. About half of that time went into trying different graphical designs (We settled on the design done by my partner, Ben Walker), polishing the UI mechanics, and getting the AI right.

Future Work

Q: Do you plan further improvements of the AI? What features would you like to add to the AI?

DH: The next AI improvement I want to add is depth search. Currently the AI just uses brute force and makes it's decisions based on the current game state. It doesn't choose the best move based on looking a number of turns ahead at the repercussions caused by each possible move. I'd also like to try dynamic weighting of the board in that each position's weighting adjusts based on the current turn's board pattern. Currently it is static. I also want to try adding an intentional blocking ability - currently it may seem that the AI is blocking your move but that is entirely unintentional and is because of some other calculation the AI has made. And of course I want to try a minmax or negamax-based AI.

With the above in mind I can provide anyone who is interested with a TOT AI Modders Kit which includes a complete AI server and Lua source code for an example AI player. This can be run on a home computer (Lua and LuaSocket has to be installed) or even on an iPad or iPhone if iLuaBox is installed.

Also included is an TOT AI API document that explains everything and how to design your own custom AI. The included Lua source code for the AI player can be played around with, customized and modified, and then played against to see how your mods perform. Then when you become more advanced you can design your own completely new AI and plug it into the AI server API.

Although every version of TOT has been designed with the ability to access remote AI servers, this feature is disabled for now. But in mid-June I released "TOT AI", a special "AI Modders" version of TOT. This is different from all the other versions of TOT in that the feature that allows the entry of an AI Server IP address is enabled. I have intentionally priced this version very high ($10 USD in iTunes App Store) to keep the average person from buying it (but one guy already bought it, hmmm). TOT AI is available so that TOT AI Modders can easily get their hands on a client that allows testing of a custom AI running on a server. Anyone who is seriously interested in becoming a TOT AI Modder, and is thinking of buying TOT AI, should contact me BEFORE BUYING IT. dan@theoctagontheory.com

More and more developers are leveraging the benefits of procedural world generation techniques for their games. It provides many valuable benefits for gameplay, but can wreak havok on AI decisions and behaviors. AI for platformers is not the most complex there is (by design), but still the quality of the underlying world has a huge impact on the perceived believability of the enemies — as Arcen Games found out while making A VALLEY WITHOUT WIND.

On Sunday, in a live interview broadcast via AiGameDev.com, the game's Lead Developer Chris Park presented the techniques behind the procedural generation of the terrain and building, and how they affected the AI behaviors. In particular in this article, you'll see examples of how procedural generation was originally a problem for A VALLEY WITHOUT WIND, and how Arcen Games resolved these issues.

NOTE: Most weekends, AiGameDev.com broadcasts interviews or masterclasses online, and you can attend those live free! The replays are available for two weeks for PLUS Subscribers, and higher memberships like PREMIUM and ULTIMATE also give you full access to the edited recordings afterwards.

Screenshot 1: Example generated landscape for the Craggy Highlands area of the game. The Grey color represents the sky, Red is the landscape, and Beige is underground cave area.

Layers of Detail... and Complexity

During the interview, Park explained how the entire game is procedurally generated — from the high level world map to the individual levels.

“There's a world map that's a 2D top-down view, which is generated procedurally a continent at a time as you play. Each tile in the world map is what we call a region. A region is a series of surface chunks, and each chunk itself is procedurally generated with several layers within that.”

On top of this, each part of the game is itself built from layers and layers of processes that combine together to increase the detail and richness in the world, as well as fix possible problems.

“For the exterior terrain, we have overall about a dozen algorithms, and a lot of those take specific parameters as range values. » Click here to view this embedded content. There are also hundreds of rules applied to each phase.”

Compared to manually designed levels, it's the potentially random nature of the environments that cause most challenges for the AI.

Screenshot 2: Example of a landscape from the game itself. A VALLEY WITHOUT WIND generates many layers of structure in the world as well as overlaying detail onto it, in this case a landscape with vegetation.

Enemies and Procedural Generation

As Park explained in the technical interview, it can be particularly challenging to spawn enemies in the right location.

“Your game has to be able to say, this T-Rex would not do well in this narrow stairwell because he's going to get wedged... How did he get here in the first place? But we had beta players report T-Rex's stuck in corridors trying to walk under a low ceiling. That's not really an AI problem; what would you expect from a tyrannosaur in such a tight space? But unfortunately it looks like an AI problem!”

In these cases, as Park continues, it's a procedural seeding problem. That dinosaur had no business being in that hallway in the first place! As well as some enemy design tricks, A VALLEY WITHOUT WIND uses a wide variety of different filters to detect if indeed an enemy can be spawned in that specific location.

“There's another set of algorithms, unrelated to the procedural generation code, that use meta-data from the initial phases to decide how to place enemies. Some tiles have meta-data that indicate what can sensibly be spawned at this location.”

These specific annotations must also be added automatically, and they formed a significant part of the algorithms used to place the enemies in sensible locations. Arcen is planning further updates to A VALLEY WITHOUT WIND, and as the community of players report bugs, Park continues to adjust this part of the code.

Screenshot 3: The tool used during A VALLEY WITHOUT WIND allows each of the steps to be visualized, including those that setup the spawn opportunities for the enemies.

Sensible Combat Space

The process of creating a level that's suitable to the AI is very similar to the rest of the process of creating a procedural generation algorithm. It involves lots of design, speculation, testing, tuning and not least iteration.

In the remainder of the interview, Park talks about many of the aspects of the procedural generation in more details, including:

• Why using a separate tool to implement is essential to get the algorithm looking and playing correctly.
• What the benefits are to splitting up the generation into two distinct phases of generation and clean-up.
• How to optimize the procedural generation to take on average around 600ms on modern hardware.
• When to integrate human-edited patterns or sub-parts to make sure the result is believable.

If you have any questions or comments about generating worlds (or platforms) that are suited for AI enemies to show off their behaviors and entertain the player.

Simulation is an integral part of most video games, and building AI or gameplay scripts to deal with simulated part of the world is always... interesting! Certain developers take that to the extreme by not only building their entire games around the underlying simulation, but their puzzles/narratives on top of that. In particular VESSEL, a creative and inspiring indie platformer, combines physics simulation and behaviors in its unique puzzles.

On Sunday, in a live interview broadcast via AiGameDev.com, VESSEL's Lead Developer John Krajewski (founder of Strange Loop Games) discussed his insights from the development of the game. In particular, you'll learn about building AI characters to deal with underlying simulations, but also how the puzzles were built as a combination of the two.

NOTE: Most weekends, AiGameDev.com broadcasts interviews or masterclasses online, and you can attend those live free! The replays are available for two weeks for PLUS Subscribers, and higher memberships also give you full access to the edited recordings afterwards.

Screenshot 1: Particle-based water simulation in vessel and dynamic clustering of nearby drops. The clustering helps the engine (and the AI characters) understand the simulation better.

Core Simulation Mechanics

At the core of VESSEL is a custom-written physics simulation that started out with rigid bodies. However, as the game progressed, it inherited many features such as fluid dynamics, which turned out to be the core of the gameplay in most puzzles.

“The main thing we did was build the liquid simulation; it's all particle based so we all kinds of physics algorithms so it can stick to walls and emit light, etc. » Click here to view this embedded content. In VESSEL, we decided to go with a particle based approach for a number of reasons, it didn't limit the scope of where the liquid could go and you can preserve mass easier. It worked better to support different types of liquid.”

As Krajewski explains further, the underlying algorithms are relatively simple but can be a challenge to optimize.

“We started with this particle simulation, and from there we'd run different algorithms over it, called pressure kernels. Each drop would look at surrounding drops, and excert a force on each of those drops. There are techniques you can use to speed that up, because it's fundamentally an O(n²) algorithm, and using pressure kernals you can make it perform a lot better.”

For those interested, here's the paper that VESSEL's fluid simulation is based on:

As Krajewski explains, VESSEL leverages this algorithm for more than just liquids in the traditional sense.

“And then we took that a step further to see what we could do to create characters. » Click here to view this embedded content. The biggest challenge in VESSEL was creating these creatures, the Fluros. They are actually conglomerations of liquid too!”

Simulated Characters

In VESSEL, the characters themselves are built using the same principles as the characters, as Krajewski explains.

“We did different experiments of trying to integrate them into basic skeletons, having the core skeletal structure inside attract the liquid with different bones having different weights. It resulted in these shapes that were physically driven but still behaved like characters.”

By using the fluid simulation to implement the characters, this had many benefits for the gameplay. When a Fluro bumps into something (or the player) it will physically respond, undergo a chemical reaction, and often even disintegrate.

“That really connected the AI with the physics of the game, because these characters have a lot more simulation to their bodies than normal characters in games. Every particle inside of them was part of their body and influences their AI. » Click here to view this embedded content. It's what we wanted to focus the game on as well, so all of the puzzles in the game came out of that interaction.”

Understanding the Simulation

If making the characters fully simulated was not enough, VESSEL needs to also have each character understand the physics of the world and behave accordingly. Krajewski uses examples to emphasize this point.

“These little creatures are attracted to light, wherever it is in the world. In this case, the player is holding a light which the Fluro can't reach so it'll run underneath you. » Click here to view this embedded content. We implemented that using light-meters and a manual path graph system. Every few meters in the dark levels, we'd have to manually place light meters which evaluate the nearby lights every few frames. The light Fluros never queried teh lights themselves, it always went through these light-meters.”

The screenshot below helps illustrate the path graph and shows the Light Fluro in action.

Screenshot 2: Debug visualization of a Light Fluro pathfinding towards a light-meter that's activated by the lamp the player is carrying.

Similarly, another Fluro in the game, called the Drinker, had to dynamically interpret the surrounding world to identify clusters of water and figure out how to reach it dynamically.

Further Details

In the rest of the interview, for which the replay is available here, Krajewski digs into many aspects of the game both as a Lead Programmer and as a Lead Designer.

• How the Fluro's predictable behaviors are built using behavior trees.
• What tools were used to support the level design and development.
• How the puzzles were built in a very bottom-up experimental fashion.

If you have any further questions about VESSEL and its underlying simulation of fluids, physics or characters, don't hesitate to post them below or in the forum thread!

StoryBricks is a fascinating project that aims to democratize traditional role-playing games, helping users easily specify behavior for living entities in the world, then share their creations with other players. As you may suspect, the AI challenges to pull this off are incredible — on the scale of a mainstream title like THE SIMS 3 with the risk of innovative indie games like FAÇADE.

It has taken an audacious team to even attempt a project of this caliber, and this weekend we'll be interviewing the Lead Designer Stéphane Bura about the underlying technology (see the live broadcast page for details). To succeed the team will need to figure out how to do it without the budget of Electronic Arts! If you'd like to help, even if you don't have millions in the bank, go and visit their Kickstarter page.

I asked Stéphane some questions about the project by email, which you'll find in the remainder of this article. But since he had so much to say and was so passionate about the topic, we scheduled a live broadcast with him too for this Sunday!

Utility & Traits

Q: At GDC you presented a concept for a utility-based AI system combining large vectors of traits, that presumably underlies Storybricks. What's the benefit of this approach?

Stephane Bura: In most games, players and content designers don’t care about how the AI represents the game concepts it manipulates. Storybricks is different because, as a RPG storytelling platform, it allows players to directly manipulate concepts that have a deep meaning for the AI, like anger or courage. So the challenge was to come up with a representation of these concepts that would make sense both for the player and for the AI, and furthermore was easy to use.

Storybricks uses these large vectors of components to describe the qualities of any concept or behavior. Each dimension describes one such quality, like how the concept relates to “caution” (low for anger, very low for courage) or “emotionality” (very high for anger, neutral for courage). These vectors are used to qualify all the concepts used by the platform, from emotions, drives and psychological traits, to behaviors, relationships and traits that can describe items or locations. When you have such a common “language”, anything can be compared to anything else. A simple scalar product of two of these vectors yields a number, comparable to a utility value if one of the vectors qualifies a behavior, which is a good indicator of how compatible these two concepts are. For instance, (anger.friendship) yields a low score while (anger.berate) yields a high one.

The second big design constraint of Storybricks is that we have to be able to easily add content to the platform: new traits, emotions, behaviors, etc. So, we couldn’t have behaviors test a “if angry” clause or behavior tree node, because we would have had to rewrite all our behaviors each time we added a trait. The nice thing about this approach is that new traits, since they are expressed in the same formalism, are incorporated seamlessly into existing characters or objects.

Scaling Up

Q: How has this approach evolved with time and experience? Is it as easy as letting the designers paint those traits in the world and letting the decisions emerge?

This idea worked surprisingly well with a small number of traits and behaviors. But, as their number increased, it became a bit fiddly and this made it difficult to track the influence of a given trait on a given character’s behavior. This wouldn’t have been too much of a problem in a more simulation-oriented game but Storybricks aims to provide high-level tools with which players can easily manipulate the emotions of the characters in the world. If you make a character afraid, you don’t want the “afraid” trait to be just one of many, you want the character to become jumpy and to react in a scared manner to violent interactions. This led us to add a new layer of abstraction. Instead of dealing with traits, players can assign roles to characters. Roles are themselves defined with standard traits and come with their own behaviors. You can think of them as states but the nice thing is that you can assign several roles at the same time to a character (like “corrupt” and “upper class”) and, if you don’t overdo it, their respective influences on its behavior remain clear.

We’re not at the stage yet where designers can place traits in the environment themselves, so that a tavern triggers more joyful behaviors or a temple more solemn ones, but we’re getting there. I suspect that we’ll also associate roles to such places, instead of just traits, so that behaviors and mores can be added to locations, making them more modular.

Challenges

Q: What's the big challenge in using such a system to create believable characters on the scale of a RPG?

Storybricks’ goal is to offer a headache-free platform for role-playing. And by that I mean the tabletop kind of role-playing. The main challenge is not so much a technical one, but involves defining and refining what this entails.

If we want to create a virtual game master or an environment in which you can be the game master of a virtual world, we have to decide the amount of control you’ll have over the world versus the amount of autonomy AI-controlled characters have. We knew from the start that we wanted to move away from the existing tools that require their users to define every detail of every behavior. So, instead of having to plot the movements and actions of a guard, we provide you with high-level “patrol” and “guard” behaviors that you don’t have to configure (just drop a guard somewhere) and that can be interrupted by other behaviors depending on the roles you have given to the guard – a lazy guard might fall asleep, a curious one investigate suspicious-looking characters. But is it the right level of control for telling a story or for describing an interesting and believable world? Do these behaviors provide enough hooks for interaction and drama?

We’re experimenting, learning the answers and the process is as fascinating as it is elating.

What Next?

Q: Why is such an approach interesting for players and designers who'd like to create their own games, or role-playing servers?

A lot of creative people have no knowledge of programming, 3D or animation. They’re incapable of using professional development environments. Yet, when they’re provided with easy-to-use creation tools, they’re able to produce astounding works, as The Sims and Minecraft among others have proven. No such tool exists today that focuses on the creation interactive stories or complex living worlds. We believe that there is a need that we can satisfy.

Q: How can you imagine Storybricks helping future designers create their own immersive simulations like DayZ?

It’s our ambition. We’re still deciding how open the architecture will be to modders but, even in its non-modded version, Storybricks will allow creators to rewrite behaviors on a large scale. For instance, you could say things like “Everyone is sick” and “Everyone who is sick is untrusting” and create a country of plagued paranoids. If you put some effort into it, there’s no limit to the richness of the world and rules you can create. As an aside and to address DayZ, the first role we developed was “zombie”. It was a very convincing way of showing how a single brick could radically transform the behavior of a character and add interesting story possibilities.

At its heart, Storybricks is about leveraging the creative power of the role-playing community. That’s also why we chose to crowdfund the project (see this Kickstarter page), because role-players, game masters and storytellers are the ones who truly understand our goal. We build Storybricks so that players can surprise us with what they do with it.

Procedural generation techniques have been used with great success to create gameplay in indie games, for example DWARF FORTRESS. Yet AAA developers have been more cautious, primarily using proceduralism to generate minor cosmetic details or randomize the assembly of pre-built blocks.

In an interview broadcast live via AiGameDev.com on Sunday, Electronic Arts Canada's Caleb Howard talked about the huge bet that SSX took on procedural generation, and how it helped the studio generate hundreds of tracks for the game rather than dozens. This approach is now in further development at EA for future titles.

NOTE: Each weekend, interview or masterclass broadcasts on AiGameDev.com are free to attend live. You can watch the replays for two weeks with a PLUS Subscription, and get the full edited recording with PREMIUM or ULTIMATE Memberships.

Procedural vs. Automated

One of the major hurdles that larger studios face when adopting procedural techniques is objections from designers and artists, as Howard points out.

“This has been the biggest challenge of my career and I've been doing procedural workflows for at least 20 years. A lot of the resistance that you meet upfront are from people who feel you're trying to put them out of work by automating what they do.”

However, there's a large spectrum of tasks that procedural techniques are suited to, and there's always a compromise or solution to be found.

“The logical conclusion of procedural generation in some cases could be an automated process, but on the way there is where most of the fruit is found. » Click here to view this embedded content. That's where proceduralism comes in; it's finding the redundance and mundane aspects of the job and streamlining those by making machines do the work.”

On SSX, Howard says that buy-in from all the key stakeholders was key to making the project successful, trying to invest in procedural techniques as much as possible but maintaining a level of pragmatism.

Workflow and ROI

The final production pipeline on SSX includes a significant portion of procedural tools (based on Houdini), however, it was also necessary to include more traditional tools such as Maya for artists to finalize the levels just before shipping.

“A major challenge of SSX which was non-technical was the introduction of a large crew of people to new methods and getting comfortable with them, while at the same time developing a game. » Click here to view this embedded content. It's a tribute to the artists that they were able to cope with this workflow, being thrust into this situation without a couple of years to get used to the ideas.”

On SSX, the challenges and benefits of the procedural pipeline were emphasized by a change in direction in the middle of the project, switching from a more realistic look and feel to something much more extreme with old-school gameplay. Howard mentions how the tools managed to cope well with the situation, and still provide orders of magnitude quicker results.

Of course, the workflow could be taken even to further reduce turn-around times.

“If we had to develop the tools again, we'd bring the artists in much sooner and develop the tools directly with their participation. » Click here to view this embedded content. Previously, it took two weeks of designer work before they could had it to the artists, and they would spend three and five weeks polishing that track up. I'm confident we could build a track from scratch to something relatively polished in the space of a few days.”

Electronic Arts, like many other publishers, has been relying on business practices such as in-sourcing (to other EA studios) and outsourcing (to external companies), but Howard sees the potential for procedural to help here:

“I can't speak to EA's business practices, but the types of demands that we have met in the past with outsourced labor could very easily be met with in-house labor and more efficient tools.”

Going Next-Generation

When asked about the interest in procedural techniques, Howard mentions there's huge demand from within Electronic Arts from all the different content-creation departments.

“As EA moves into the future with new hardware on the horizon and new methodologies to accomodate that, we've realized we're going to need a lot more content! The business model doesn't change so we can charge 10x as much. » Click here to view this embedded content. All of the domain leads (character, environment, lighting) have been talking to the procedural crew to see how they can get the most advantages out of a procedural workflow.”

As Howard mentions online games, it's clear to see how procedural techniques could help generate new tracks or levels that can be purchased for small amounts from within the game. As EA transitions into a mostly engineering-driven business model where games act as a service, procedural workflows will play a key role.

Further Details

In the remainder of the interview about SSX, Howard discusses many of the technical details about the generation of the mountains including:

• What were the major design decisions for a procedural workflow that made it work.
• How the track is generated for varying levels of difficulty and player skill according to high-level parameters.
• What tools are used to manage the procedural generation code and how they combine together in a pipeline.

If you have any questions or comments about the use of procedural techniques on SSX, or their benefits for Electronic Arts as a publisher, don't hesitate to post them!