An Egocentric Motion Management System - article excerpt from Game Engine Gems 2

Google Books has provided a generous preview of my chapter from Game Engine Gems 2 describing a character movement solution - aspects of which I used in World of Zoo (PC & Wii). The character movement solution was also used in several demos - including a prototype of a non-zoo type game. The chapter contains a detailed write-up of how how to integrate the character movement system with a behavioral model that conveys perceived intent (section 19.9 A Single Agent Behavioral Response Algorithm and Example). The link to the article is below - enjoy!

An Egocentric Motion Management System Summary

The egocentric motion management system (ECMMS) is both a model for agent movement and an application of a behavioral theory. Any game that features agents (e.g., animals, soldiers, or tanks) that move around in a 3D scene has a need for an agent movement solution. A typical movement solution provides mechanisms that allow for an agent to move through a scene, avoiding geometry, all the while executing some sort of behavior. This article discusses not only how focusing on the agent drives the immediate interactions with the environment but also, more importantly, that by gathering some information about the environment during locomotion, we gain the ability to generate spatial semantics for use by the agent’s behavior system. Portions of the ECMMS were used in a cross-platform game entitled World of Zoo (WOZ). WOZ is an animal simulator that requires various zoo animals to move through their environments in an incredibly compelling manner while the  players constantly alter the environment. So the proving ground for this system was in an environment that could be changed around the agents at any particular moment. In addition to detailing ECMMS I also discuss how to build a unified behavioral model that utilizes technology from all three of my character movement articles.


 
An Egocentric Motion Management System - Theory and an Implementation

Qualitative Improvements of Biasing a Routes Starting Position

In this note I'll be discussing how biasing an entities starting position before providing it to the pathfinder, can improve the qualitative behavior of your game's characters. This technique was used on a multi-platform game [Ramsey 2009a].

Generating a route to destination can be parametrized in many ways, but one of the most fundamental parameters has a trickle down effect attune to an avalanche with observable repercussions on an entities motion - if selected incorrectly.

What I'm suggesting is that the start position provided to the path finder is one of the most important parameters to get correct. It almost seems intuitive to suggest that the starting point is "where your at." Well, maybe not so - we need to think temporally. Consider not only our thoughts, but our movement - it's always changing, adapting and what's appropriate at this moment in time is not necessarily appropriate 5 seconds from now, probably not even one second in the future. This applies to selecting a starting position for our animating penguin. We are more interested where it'll be rather then where it's at currently.

The picture below illustrates a simple environment where we have a penguin that wants to move from position A to position B. A typical pathfinder would be supplied with the penguins current position as the start position, and position B as the end point. The problem with this seemingly correct solution is that it fails to factor in any forward momentum of the penguin. Whether the forward momentum is implicit in the animation driving the penguin or an associated movement rate of a simple sprite where the penguin is at (t) is not where it'll be at (t+1).

The penguins directional vector is represented by the light blue line, the pink segments is the path returned if the penguins current position is used as the starting point, and the green segments is the route when we factor in not only the penguins directional vector, but also it's velocity. The yellow bidirectional connections is the graph representation of the navigation mesh.

Depending on how fast the penguin is moving, we bias the start position of the penguin farther and farther away. A simple technique is to attain the penguins heading and magnitude of translation over one frame (t). And then using a standard unit of measurement (r) - I used the diameter of the penguin, you multiply (r*t) = (s). I also experimented with the radius and this worked as well for animals that didn't translate too fast. (s) then becomes a scale that we can apply to the penguins directional vector, with a resulting point in the environment that serves as the starting point for your path finding algorithm. Straightforward and it allows for the continuation of the penguins motion with out any jarring hitches caused by the pathfinder (I had coded up a modified version of A-Star that supported our modeling methods) .

This technique is not only useful in this directed graph representation, but also on typical grids and navigation meshes. I hope you find it useful as using this technique had a qualitatively positive impact on the movement of the animals in World of Zoo.

References

[Gibson 1986] James J. Gibson. The Ecological Approach to Visual Perception. Hillsdale,

NJ: Lawrence Erlbaum Associates, 1986.

[Ramsey 2009a] Michael Ramsey. “A Unified Spatial Representation for Navigation

Systems.” Proceedings of The Fifth AAAI Artificial Intelligence and Interactive

Digital Entertainment Conference, 2009, pp. 119–122.

[Ramsey 2009b] Michael Ramsey. “A Practical Spatial Architecture for Animal and

Agent Navigation.” Game Programming Gems 8, edited by Adam Lake. Boston:

Charles River Media, 2010.

[Ramsey 2009c] Michael Ramsey. “An Egocentric Motion Management System.” Game Engine

Gems 2, edited by Eric Lengyel. Natick: A.K. Peters, 2011.

Further Reading

1. “On the Nature of Things” Lucretius, translated by Ronald Melville is wonderful book expounding the atomic theory first presented by Epicurus. Book I covers the two principles of beingness: that nothing ever came from nothing and that nothing ever returns to nothing. Book 2 discusses the principles of continual motion and how collisions shape the free will. Book 3 covers the nature of the mind, while Book 4 explains the nature of vision, hearing, taste, smell and how aspects of the environment enter the mind. Book 5 and 6 wrap covering mortality and environmental effects.

Noumena Philosophical Canon

While the last post attempted to cover the more concrete canon, this post will list the books that comprise my Noumena philosophical canon. Every project needs an underlying set of principles that help guide the development of not only the final product, but arguably the process in which these systems were built. These books represent some of the core books that provided ideas that contributed to Noumena's process.

1.  The Complete Works of Aristotle, ed. Jonathan Barnes
2.  The Human Touch, Michael Fray
3.  Michel De Montaigne The Complete Works, Translated by Donald Frame
4.  The Phenomenom of Life, Alexander
5.  On the Nature of Things, Lucretius
6.  Being and Time, Heidegger
7.  The World of Perception, Merleau Ponty
8.  Experience and Prediction, Hans Reichenbach
9.  The Phenomenology of Perception, Merlau Ponty
10. The Origins of Knowledge and Imagination, Jacob Bronowski

Noumena Canon

It's been a while since I posted, so here are a few of the books that I consider canon for the development of Noumena. There are literally hundreds of other books that have influenced Noumena in some form or another (I actually posted several years ago an initial list of some of the books) but these few here are the pillars on which a number of my ideas are based upon.


1.  The Philosophy of Animal Minds, ed. Robert Lutz
2.  Animal Cognition, Clive Wynne
3.  Mental Leaps, Keith Holyoak and Paul Thagard
4.  Mindreading Animals, Robert Lutz
5.  Incomplete Nature, Terrence Deacon
6.  Creating a Memory of Causal Relationships, Michael Pazzani
7.  Who Needs Emotions?, ed Jean-Marc Fellous and Michael Arbib
8.  Behavior: The Control of Perception. William T. Powers
9.  General System Theory. Ludwig von Bertalanffy
10. The Principles of Psychology, Volumes 1 & 2, William James.

Hopefully in the not too distant future, I'll be posting an outline for the manuscript entitled, "Fellow Creatures: A Referential Intelligence." It's a book that covers the development of the referentially based cognitive engine, Noumena.

AI Papers, Books, and Conference Publications

I've received some emails from individuals looking for some of my work (specifically my articles and papers on character motion management), so here is a list of some my published works with a brief note and what books/journals/conferences they can be found in - as well as a few extra early game programming works.

The chapters in Game Engine Gems 2, Game Programming Gems 8, and the paper presented at the Artificial Intelligence and Interactive Digital Entertainment Conference 2009 form the three major sources for the some of my work on character movement systems. Together they form a unique approach that combines AI, animation and physics into a unified architecture that provides a description of the background to, principles of, and the development of an approach to implementing a character behavioral system.

For Game Engine Gems 2, I provided a chapter entitled, An Egocentric Motion Management System. The egocentric motion management system (ECMMS) is both a model for agent movement and an application of a behavioral theory. Any game that features agents (e.g., animals, soldiers, or tanks) that move around in a 3D scene has a need for an agent movement solution. A typical movement solution provides mechanisms that allow for an agent to move through a scene, avoiding geometry, all the while executing some sort of behavior. This article discusses not only how focusing on the agent drives the immediate interactions with the environment but also, more importantly, that by gathering some information about the environment during locomotion, we gain the ability to generate spatial semantics for use by the agent’s behavior system. Portions of the ECMMS were used in a cross-platform game entitled World of Zoo (WOZ). WOZ is an animal simulator that requires various zoo animals to move through their environments in an incredibly compelling manner while the  players constantly alter the environment. So the proving ground for this system was in an environment that could be changed around the agents at any particular moment. In addition to detailing ECMMS I also discuss how to build a unified behavioral model that utilizes technology from all three of my character movement articles.

In Game Programming Gems 8, I've written an article detailing the World of Zoo's navigation system's architecture; as well as provided some general thoughts on developing a motion management system. The article is entitled, A Practical Spatial Architecture for Animal and Agent Navigation. This article is a nice bookend to the AIIDE 2009 paper (the Game Gems article provides more concrete insights, while the AIIDE paper is more algorithmic).

Here's a brief introduction to the article: Game literature is inundated with various techniques to facilitate navigation in an environment. However many of them fail to take into account the primary unifying medium that animals and agents use as locomotion in the real world. And that unifying medium, is space [Lefebvre97]. The architectonics of space relative to an animals or agent’s motion in a game environment, is the motivation for this article. Traditional game development focuses on modeling what is physically in the environment, so it may seem counterintuitive to model what is not there, but one of the primary reasons for modeling the empty space of an environment is that it is this spatial vacuum that frames our interactions (be it locomotion or a simple idle animation) within that environment. Space is the associative system between objects in our environments.

This article will discuss this spatial paradigm and the techniques that we used during the development of a multiplatform game, entitled World of Zoo (WOZ). WOZ was not only a challenging project by any standard definition of game development, but also because we desired our animals motion to be credible.


An important aspect of any animal’s believability is that they are not only aware of their surroundings, but that they also move through a dynamic environment (Color Plates 1 and 2 contain examples of WOZ’s environment) in a spatially appropriate and consistent manner. This maxim had to hold true whether the animal was locomoting over land, water or even through air! To help facilitate the representation of our spatial environments we used several old tools in new ways, and in conjunction with a few inventions of our own, we believe we accomplished our goals.




This peer reviewed paper outlines the general philosophy of a unifying paradigm for navigation systems. The paper is entitled, A Unified Spatial Representation for Navigation Systems and was presented at the Artificial Intelligence and Interactive Digital Entertainment Conference 2009 held at Stanford University.


Abstract

The purpose of this paper is to outline the core components of a practical navigation system which uses a novel technique for spatial representation in a commercial entertainment product. This paper is based upon thenavigation system developed for The World of Zoo (WOZ) by Blue Fang Games, LLC and published by THQ. WOZ placed the following requirement on our in game agents
(which are animals, such as tigers and penguins): depending on the animals species they were required to locomote across land, water, exhibit the ability to climb and eventually to fly all in a seamless manner. Animal locomotion in WOZ is driven by accumulating the root motion of multiple blended animations; this required a unique approach to the spatial representation of our environments. The system needed not only to take into account the defacto static environments that were created by
the level designers, but also the dynamic structures that the animals use (depending on the players interactions at that particular moment).


There was also the extra challenge of a system that was as straightforward as possible for level designers to work within. As Anthony J.D' Angelo so succinctly stated, "Don't reinvent the wheel. Just realign it." It is with this sage advice in mind that we reevaluated traditional navigable representations, in conjunction with how our animals should move through their environments. As important as the navigation framework was to the development of WOZ, the way the thought processes developed preceding the implementation is also of interest; as the re-understanding of what navigation is composed of (in virtually any environment) guided our decisions through the design and implementation stages.


In Game Programming Gems 7, I've written an article detailing the architecture of a multi-platform threading engine. The article is entitled, The Design and Implementation of Multi-Platform Threading Engine. One of the most important aspects of designing a multi-threaded program is spending the time upfront to design and plan your game architecture. Some of the high-levelissues that need to be addressed are: task dependencies, data sharing, data synchronization, acknowledgement and flow of data access patterns, decoupling of communication points to allow for reading but not necessarily writing of data, and minimizing event synchronization. This article details the GLRThreading Engine and also provides a lot of practical advice for either using the GLRThreading Engine or writing your own. Other topics include dealing with cache issues, thread pools, execution properties and more.
 
In Game Programming Gems 6, I've written an article about the Quantified Judgement Model (QJM) and it's usage and application to strategic game development. The article is entitled, Using the Quantified Judgement Model for Engagement Analysis. The Quantified Judgment Model (QJM) is both a model and a theory of combat. Originally developed to simulate historical battles and then later upon further refinement, used for modern engagement prediction; it is an ideal system for predicting potential victors in a game. In this gem I describe the base QJM formula. The base QJM formula can then be furthermore expanded upon, by adding models calculating attrition factors, spatial effectiveness of units and casualty effectiveness.

There is also some notes on the difference between the Lanchester equation and the QJM.




In AI Programming Wisdom Volume 2, I've written an article on Multi-Tiered AI Frameworks (MTAIF). This is the new framework used in the current iteration of Master of the Empire. The article is entitled, Designing a Multi-Tiered AI Framework. The MTAIF allows an AI to be broken up into three concrete layers, strategic, operational and a tactical layer. This allows for an AI programmer to have various AIs focus on specific tasks, while at the same time having a consistent overall focus. The MTAIF allows for the strategic layer to be focused exclusively on matters that can affect an empire on a holistic scale, while at the operational level the AI is in tune with reports from the tactical level. A differing factor from many other architectures is that the MTAIF does not allow decisions to be made on a tactical scale that would violate the overall strategic policies. This in turn forces highlevel strategic policies to be enforced in tactical situations, without the AI devolving into a reactionary based AI.


In Game Gems 5 I've written an article entitled, Advanced AI Framework Development with a Parallel Virtual Machine (PVM).
Its forms the fundamental understanding that is needed to start developing a parallel AI system. The article had to fit into 12 pages or so, so that meant a lot of actual implementation details had to be left out, as well as information on potential
design fallacies that may occur.



Early papers.

This is an article I wrote for OS/2 Developer entitled, Advanced Game Design with OS/2. The use of was the editor's idea. The article provided a basic summary of doing fast GPI updates - the technique I used for Master of the Empire. Obviously a super dated article (as it was published in 1997), but nonetheless it provides an interesting cross-section of my background.






Genericized Object Management (GOM). Todays games have huge AIs, being worked on by multiple programmers. Unless a new technique is introduced when the project begins, it becomes difficult to add any new type of methodology to the framework. This comes from the concern of breaking a currently implemented system or the real world fact that the new technique is just too complex. What the Genericized Object Manager (GOM) allows for is a simple way to register multiple objects through a parameterized functor [Alexandrescu02], which can then be easily accessed at runtime through one central core routine. A benefit of GOM is that the implementation can fit into almost any preexisting framework, so your game can have the immediate gains without refitting your framework to a particular solution. The GOM technique allows for setting up a specific AI, such as a particular Field Manager (see Designing a MultiTiered AI Framework), input managers, state machines that need to deal with multiple behaviors, or just a central system that is needed because the programming team is large. GOM also serves as a good technique while refactoring a large codebase.

Emotions and Goals within Noumena

Emotions and Goals within Noumena

Started working on what in essence can be viewed as the emotional system for Noumena.

Appraisal module defined:

1. Relevance of event
2. Implications or consequence of event
3. Can I cope w/the event?
4. What is the significance of the event? To me? To allies?

Event defined: An externally observed phenomenon or an internally generated construct. E.g An opponents critter on your island – it's an event because it violates your perceived "ownership" of the island.

Events generated from violated self evident principles, e.g. A sense of ownership is definitely psychological in nature – another attribute for the RI psych profile. Ownership increases the perceived value of an object and this would actually be an excellent attribute of an RI to exhibit, because it not only factors into the immediate decisions but it would also allow for the RI to essentially want to exhibit behaviors such as: protect it's owned areas, retake objects taken by an opponent, and this could play into the more emotional aspects such as revenge, distrust, irritation etc. All emotional characteristics we want the RI to exhibit – naturally, if possible.

Goal Creation

Initially I'll create goals through the use of the concept of ownership – in MOTE this is initially the guide to goal creation.

A sense of ownership is one potentially just one element of an RI's personality.

Through the application of personality filter I could define other "desirable" personality components, e.g. Experimental or curious. These components could influence exhibited behavior – disproportionately.

Ownership questions:

1. What do I currently own?
2. What do I need to own?
3. What should I own next?

As a game progresses from an opening mode, to a mid-game and finally to an endgame mode, the area of focus for these questions moves from an immediate focus to more distal concerns (e.g. Complexes, resources, farther away from the starting area).

Creating and Evaluating Goals With Respect to Ownership

Evaluation of tanks takes into consideration spatial relativity of the goal, with respect to concerns. E.g If a goal is at the bottom of the map – the RI should factor in strategies and tactics using that space, as well as the relational links of the cogents in between the start and destination when determining an appropriate response or series of responses.

Evaluation defined means a potential response or means to achieve that goal (perhaps suggesting that this is a plan) -> I dislike using the word plan as it has too much baggage.

The RI will need multiple methods of evaluating for and generating ownership.

Also need to establish why this region belongs to me, perhaps simple rules such as: my complex is on the island, or I need to expand – basically forms of justification.

Also need to be able to generate a concern for "trespassers" in an owned region. A couple examples should help here: An enemy simpleton on a large island would most likely cause little military concern, however a large group of tanks offloaded onto your island would probably matter! An aspect that would need to be considered is also the size of the land mass as that would influence the immediacy of the response as well as the overall strength of the response.

This is interesting because at a very fundamental level this seems a lot like an influence map – still, the influence map needs to be analyzed and evaluated to determine a response.