In this post I’m going to discuss what I’ve recently learnt on the topic of determinism in simulations and games. I’m going to cover ActionScript as well as C/C++, as much of the more in-depth information I found was for C/++ developers (it remains by far the most popular langauge for such applications).

Part 1: Overview of Determinism

Q: What is determinism?

A: Determinism is the proposition where every event is causally determined by an unbroken chain of prior occurrences. Similarly, Wikipedia defines a deterministic algorithm (or system) as one where, given a particular input, the same output will always be produced, and the underlying machine will always pass through the same sequence of states in producing that output.

NOTE: In the remainder of this article, I will use the term system interchangeably with engine or algorithm since some areas discussed are more general, and thus pertain to more than just engines.

Q: What are the advantages of a deterministic physics system in game and simulation development? 

A: Very often, the physics engine will be at the core of how your game or simulation operates, i.e. the physical world is of fundamental importance. The ability to move to any point along a timeline and replay physics accurately means that implementations which reside on top of your deterministic physics system can be debugged more reliably, for example:

• Networking implementation
• Rendering
• Extraneous (non-physics) game logic

…because, if we know that the underlying physics are correct, then any problems must lie with the layer we are currently working on, eg. the presentation layer.

Let us imagine using a perfectly deterministic engine. You might play a deathmatch on this engine with your friends, and save a recording of a battle. Because the actions of human players (the only uncertain thing) have already been recorded, and because your engine uses those recorded human inputs to produce predictable outcomes on every game cycle using it’s own perfectly deterministic physics model, the end result of this recording will always be the same (what would be the point of a recording if it changed every time you played it back?!). Ultimately, using determinism for debugging is a huge benefit. If you can reliably specify any point in time in the operation of your simulation, with no variability, you can very quickly determine the source of any bugs in other systems which work along with your physics. Without determinism, it can be very difficult to determine whether a bug is in your physical model of the world or in your game logic (as considered discretely).

Another useful aspect of game and sim development for which this can be useful is the ability to perform replays, or to actually allow the player to be able to affect time, eg. The Turtles of Time.

Part 2: Implementation considerations

Some common beliefs about so-called deterministic (physics) engines are that such a system:

1. is deterministic to infinity in either direction along the timeline
2. is deterministic no matter what hardware you run it on
3. is deterministic no matter what else is running on that system
   
4. must use fixed point instead of floating point math to be truly deterministic, because loss of accuracy due to computers’ limited storage space (16/32/64 bit) for floating point numbers necessitates truncations in results of mathematical operations (eg. in division and multiplication).

Part 3: Conclusions

In a high-level language like Flash, you cannot natively* have true cross-platform determinism. If your game is a multiplayer Flash game, you will have to have to go for the “frequent resynchronisation” approach, or do all calculation on the server. If your game is not multiplayer, but you want deterministic physics eg. for playbacks, you will have to settle for determinism on a platform-by-platform basis, i.e. deterministic within a given platform. Make sure your Mac players don’t get hold of your PC players’ replays, and vice-versa!

In languages with lower-level access to hardware, you will have greater control over your choices, however the road will not be easy. In the links in Part 2, I’ve provided a couple of solutions I’ve come across for C/++.

Ultimately, no matter what language/platform you are using, you may be wise not to be too idealistic in regards to determinism due to the immense amount of work and understanding required. You may be better off opting instead for a “reasonable” level of determinism, using tricks dependent on your needs, eg.:

• limiting the duration of a simulation so as to limit derivative “drift” in physics values
• using resynchronisation methods for multiuser/networked scenarios
• storing a full backlog of player/entity inputs rather than trusting the derived (i.e. current) physics state as being an accurate input.

* By natively, I mean that there may be non-proprietary solutions but they would either be very slow to implement, very slow to execute, or would require an external shared library in a lower level language like C, but this would only be a possibility if you were writing a desktop game — as of this writing MDM Zinc supports .dll access for Windows, but not .dylib for Mac or .so for Linux, while AIR supports none of these.

This is something I’ve just finished with and wanted to post on while it’s still clear in my mind, particularly as a follow up to my last post on the topic of composition in games.

I’m presently building a game framework which favours composition over inheritance for good reason: the possible permutations of object types are basically limitless, meaning that inheritance is ruled out — a classic case of a “has-a” relationship vs. the “is-a” relationship which is portrayed by inheritance.

My composed (”aggregator”) and composing (”aggregee”) objects are all defined by interfaces, i.e. in terms of the services they provide, since actual implementation will change from case to case. The aggregees I am presently dealing with are what I call processors. These processors *only* provide a service (they “process”), and do not store any long-term state information (their diametric opposite would be a VO).

Think of a car wash: in order for you, the person who needs car washing services, to wash your car, you do not need to own a car-wash — you can simply go and request someone else’s car-washing service at their car-wash facility. The car-wash facility in this example is the object; the washing service it provides is the sole function within that class. 

Similarly in my case, because every aggregator doesn’t need it’s own exclusive copy of the service it wishes to utilise, all aggregators can share these aggregee instances (which are requested through a singleton manager class which I will be posting soon).

OK… where do function closures come into this? We’re getting there…

Because I suspected that my aggregator did not need an actual reference to the object, but rather just to the sole function it contained (why pass the whole object?), I realised that all I needed to do was to trick a function into believing that it’s “this” scope was actually a different class (the aggregator), rather than its original class in which the function was defined (the aggregee). So in other words, using a function I’d pulled from another class, I could make it act on members/methods of the local class as though they were within the native scope of that function.  (IIRC, something like this would be trivial in C/C++ using function pointers).

(Side note: Why did I want to do it this way? It was to avoid tight coupling. Since every aggregee can “belong” to many different aggregators, I could not have the aggregees pointing back to their owners, as that would require an array of references — what a pointless exercise. And since the processors had to operate on their owners’ data, they would be forced to have a reference back to them in order to work at all).

So I checked LiveDocs, and what I found looked promising. The Function.call() and Function.apply() methods both looked as though they could do exactly what I wanted. Unfortunately, after trying these without success, I eventually found this , debunking what I’d found on LiveDocs, which was actually out of date and was only true for AS2… AS3’s call() and apply() do not, in fact, change the value of thisObj (Adobe-speak for the var which holds the reference to ‘this’ in any object) as LiveDocs states. So I had to find another way make it happen.

That was when I had a flash of insight. I had read that function closures had a unusual way of resolving their scope. Unlike AS3’s call() and apply() , a function closure’s thisObj resolves to global rather than object scope. Aha…

By creating the aggregee like this:

package
{
	public class SimpleMoveProcessor implements IEntityProcessor
	{
		public function getProcessorFunction():Function
		{
			return function()
			{
				//'this' *is* necessary to set scope to the outside caller.
				this.mx += 4;
				this.my += 4;
			}
		}
	}
}

…I could allow the aggregator to simply call the aggregee’s function it had been pointed to in it’s construction process (which I do using the Abstract Factory pattern), like so:

package
{
	public class BasicMovingEntity implements IEntity, IMovableEntity
	{
		//entity ID
		private var _id : String;

		//map position
		private var _mx : Number = 0;
		private var _my : Number = 0;

		//the motion function
		private var _mf : Function;

		//following accessors are required for IEntity implementations
		public function get mx():Number
		{
			return _mx;
		}
		public function get my():Number
		{
			return _my;
		}
		public function set mx(__mx:Number):void
		{
			_mx = __mx;
		}
		public function set my(__my:Number):void
		{
			_my = __my;
		}

		//this is used during the factory construction process
		//to set the anonymous function closure we'll be passing
		//back for use as a processor
		public function set moveFunction(__mf:Function):void
		{
			_mf = __mf;
		}

		//and for every entity, we simply call this method from the main game loop
		public function move():void
		{

			_mf(); //and here's the magic, just apply parentheses and we're calling our external function!
			trace(_mx); //will show that the local member has indeed been updated.
		}
	}
}

For the sake of completeness, here are the interfaces used:

package
{
	public interface IEntity
	{
		function get mx()							: Number;
		function get my()							: Number;
		function set mx(__mx:Number)				: void;
		function set my(__mx:Number)				: void;
	}
}
package
{
	public interface IMovableEntity
	{
		function set moveFunction(__mf:Function):void
		function move():void;
	}
}
package
{
	public interface IEntityProcessor
	{
		function getProcessorFunction():Function
	}
}

You’ll notice with the interfaces that I am not extending one interface from another even when there is a clear “is-a” relationship — this again reflects favouring composition, allowing for a more flexible whole.

Also note that the IEntityProcessor interface exists because you can basically do any kind of logic you like at different steps of your game loop, for example generating AI desires, using those desires to generate input, using input to generate movement and other actions, and doing collision detection, among others. Each of these would be represented by its own implementation of IEntityProcessor.

UPDATE 2009/02/16: I just found this paper which seems to outline the same or a similar process to what I’m performing here. They refer to the composing functions as “traits”. Some excerpts:

“We propose a compositional model as a solution to the problems illustrated in the previous section. Our model is based on lightweight entities called traits, which serve as the basic building blocks for classes and the primitive units of code reuse. Thus, traits satisfy the needs for structure, modularization and reusability within classes.

Traits … are implemented in the Squeakdialect of Smalltalk-80 … but we believe that traits could also be applied to other single inheritance languages such as Java.

…

A trait contains a set of methods that implement the behaviour that it provides. In general, a trait may require a set of methods that parameterize the provided behaviour. Traits cannot specify any state, and never access state directly. Trait methods can access state indirectly, using required methods that are ultimately satisfied by accessors (getter and setter methods).”

I just answered a question on CheezeWorld, which I thought was worth reposting on it’s own here.

QUESTION:

Iain asks:

How do you get around the fact that an object might be, say, both a “moving object” with speed and position and a “killable object” with health and armour, without having one extend the other, so that they can be used separately? Just an example of course, in practice you’d never really want something killable that can’t move. Flash doesn’t have multiple inheritance, so I’ve thought about making a “movable” behaviour object that is owned by an entity and is responsible for the entity’s position, and a “killable” behaviour object that controls health etc. Any thoughts?

ANSWER:

Iain,

Very good question. In response:

1. “Favour composition over inheritance.”
2. “Build to interfaces, not implementations.”

1. We make use of the “Single Responsibility Principle”: A class (and thus it’s instances) has one and only one responsibility. So you create a class Collidable that deals solely with collision detection, and you create a class Living that contains functionality solely pertinent to measuring life remaining. Now you create a third class which is the Entity, and at runtime it instantiates Collidable and Living, and holds references to them. It calls them at the appropriate times to deal with the appropriate logic. So you can see that we are *composing* the object, rather than deriving it’s functionality through inheritance.

2. Interfaces describe the *services which a class provides*, rather than how you implement those services. Say you have two different methods of collision detection. One is for circular objects, and one is for concave polygon objects.
So, let’s say you create an interface ICollidable (from which your class Collidable will extend) which accurately describes the services a “collision-detectable object” would expose, eg. “checkMyCollisionWith(someOtherObject)”. You can now split your Collidable implementation into two: One that manages collisions for object which need only simple collision detection, and another for objects which require more advanced collision detection (eg. for concave polygons).

This is useful because it means that, at runtime, you can dynamically decide how to compose your object… rather than using inheritance, because inheritance leads to an inflexible hierarchy, as you have realised. This is particularly true in ActionScript, because multiple inheritance is not supported. So you can use the same skeleton, Entity, for all your entities, but you can dynamically decide how to create each individual one according to it’s type, eg. player, AI-controlled, static objects, etc.

DISCLAIMER: The Gang of Four (Gamma, Helm, Johnson, Vlissides) claimed that one should always “Favour composition over inheritance”, but this is not quite true, and they later admitted as much. There are many cases (this article is a perfect example) where it is 100% the best way to go. But in many cases, inheritance is a lot more logical. Example: I’ve recently built a pseudo-3D rendering engine. At each step down the inheritance chain I have extended the functionality a little bit more. So I start out with an abstract renderer, I extend it to a 2d (flat) renderer, and then extend it further to my pseudo3D (perspective-based) renderer. This works because there is no branching of the inheritance chain — just three different classes, each of which does a little more than it’s parent class.

Best regards,

-Nick

I’ve been doing some work on my pseudo-3D tile engine, looking at ways to do efficient line-of-sight calculations. There are about as many ways to programmatically calculate line of sight as there are classes in Java. One can split these up into “mathematical” and “logical” methods. Mathematical LoS involves utilising vectors, linear programming and trigonometry in general to solve, geometrically, the line of sight problem. Because trig functions are in and of themselves expensive, and they imply a necessity to use floating points numbers as the basis of one’s application, the logical methods will often come to the fore as a more desirable option — in particular for those using platforms like Flash where speed is a crucial concern.

In searching for a good solution, I came across an article of interest through searching Rogue Basin, with an implementation written in Java (get the original Java files, I’m hosting them now as the original author’s link is broken — hope he/she doesn’t mind). Java being a short step from AS3, mostly just swapping around declaration keywords and fixing the display to work differently, I decided to have a go at porting this to AS3. Fortunately the author’s code was reasonably well-separated into model/controller and view, making things fairly simple. In the process, I’ve spiced it up. You can do multiple generations/runs without having to refresh the page. You can change the number of tiles you want, on the fly, bearing in mind that by the time you try a 20×20 tile map, it’s already getting extremely hard to read the values inscribed on each tile. You can pause during the algorithm’s run. You can also change the refresh rate on the fly, allowing you to slow down the scanning action.

Location colour key:

• Cyan: the origin, i.e. the location of the entity that is looking around
• Green: fully visible locations
• Red: obstructions
• Pink: Semi-obscured locations
• Grey: Completely obscured locations
• White: Also completely obscured, and these locations are culled from the search queue.

Note, the code currently generates 20 random obstructions if it can, at present (some may overlap though making for less of them). And the location of the origin is randomized each time, as well.

Here’s the source, back to the community from whence it came. Questions are welcome; I cannot claim to perfectly understand how the propagations work although I do have a rough idea, but everything else is straightforward. WRT propoagations, the author has essentially used integer instead of the FP variations (0.5 -> -0.5) seen in Bresenham’s and Xiaolin Wu’s line algorithms. This can be seen in Wikipedia’s example optimisations of Bresenham’s algorithm. The actual logic of the propagation code, I think, has been compounded/optimised, making it hard to comprehend, and since the original author’s code commenting left a lot to be desired (particularly in respect to propagation, the hardest part to grasp), I’ve done my best to give an idea of what is going on in those parts.

Another very important thing if you wish to use the code (and it is noted in the updated code comments) is to make sure you use a far superior option for queuing that Adobe’s pathetically slow “Array as a queue wannabe by using shift()”. Array is Array, and that means that by definition it does not do what linked lists, queues, stacks etc. do with anywhere near the same efficiency. I can suggest Mike Baczynski’s Queue implementation.

Lastly, just out of respect for the original author, whoever they may be, I have not changed the names of the classes or the original package (”raymulticast”).

Have fun, and I hope you can use the Flash app as a web reference to producing your own working implementation.