Kreation’s Edge

Most games always have a GameObject base class which represents any object that can exist independent of the world. On a more concrete level, there also usually exists the concept of an Actor in which exists within the game world. Most game engines most likely still don’t multithread on this level but if they did, some thought would have to be given to weigh the benefits / efforts expended to bring this about.

Discussed this concept awhile back with a friend also interested in this topic and we arrived at this conclusion. Essentially, the Actor will buffer any calls that can alter runtime state. So, all incoming events will essentially be stored into a message queue. To keep the public interface functions for Setters familiar to callers, they will generate the corresponding event type. So, a setPosition() will create a “SetPosition” event and buffer that.

You can expose a lot of ‘outputs’ (aka getter functions). Such as you’d return cached position/rotation data etc. This will likely be all information computed the last known frame. Who knows, the data is probably relatively fresh depending on how well the “Actor Job Manager” keeps up with the main thread.

Call me conceited, but I really don’t see this being too hard to pull off as long as you introduce this of course early in the project.

Here’s a breakdown:

- Actors gets created by the World/Level and will be assigned to an Actor “Job” whose task is basically to tick these guys within the local thread loop

- The only public interfaces will return cached data such as Position, Rotation, Translation matrix, and so forth. Any calls that can possibly change the runtime state of this object will be funneled through a message queue. The Actor will receive Events and process these when it gets a chance.

- When the Actor gets ‘Ticked’ by the Job that owns it, it will proceed to perform its calculations inside its void doTick(float deltat) function

- The only tricky part is how to deal with variables that need to be returned to other callers. So possibly at the end of its’ Tick, you copy over the new updated position/rotation into a cached version which essentially has synchronized protected access to it. This way we reduce the time we have to stall other threads as we update our former state. At the begining of the tick, you pull off events from the message queue just incase an external source wants to update your position and so forth.

—————————————————–

I do not anticipate very many other major differences between a Concurrent Actor system and a Traditional one. The Level can still maintain a list of Actors it owns as usual. External callers can still store pointers and references to these Actors as normal as well.

The benefits should be pretty huge of course since the majority of gameplay code CPU costs will be expended within the main game loop. Often times AI, Pathfinding, and scripted actors will all be ticked along the main game loop and cause spikes here and there making it hard to perform optimization passes. Doing things this way you build for the future, constructing dynamic software that can analyze client hardware and distribute Actors to various Job Threads as needed.

The beauty of such a system is that you can handle various problems that occur dynamically. Is Script code burning too much CPU? Well distribute that to another thread. AI? Distribute all of your NPCs to a thread. Basically, the goal is to perform runtime analysis of the software and perhaps move around Actors dynamically to linearize CPU costs fully leveraging Quad core CPUs and beyond.

The average game experiences a lot of bottlenecks due to AI & Pathfinding. And it might be tricky trying to get programmers to only write big things and put that on Jobs. Instead, this approach encourages games to put everything on the Job queue.  Yes, everything. This way, you can move around processes as desired to optimize runtime performance

——————————————————–

Benefits:

• All incoming events are buffered making it easier to debug how an Actor arrived at a certain state
• Since we are buffering events, we can store them for playback later. So we automatically gain the ability to replay scenes and ingame cinema
• Makes the game engine fully scalable allowing us to fully leverage the logical processors on the local machine
• Depending on the CPU Load, we can evenly distribute Actor Jobs to maintain steady, reliable performance
• Gameplay programmers do not have to worry about writing Jobs. Essentially, you are doing this for them brute force

Pitfalls

• In Actor subclasses, programmers might have to become aware of multithreaded programming paradigms. Any data they access within their game tick obviously cannot be manipulated by other threads at that time. So, outside callers can only access cached information.
• More memory is consumed. Every actor will also require cached versions of data that is protected by synchronized access
• Additional layer of complexity due to the asynchronous nature of the beast
• Collision detection code will also need to be updated to deal with Concurrent Game Actors

Concurrency

Was planning on completing Herb Sutter’s 2 hour presentation he made on C++ Futures and multicore technology before I wrote my next blog entry. However, I’ve been real busy working on various things so haven’t had time to finish watching the presentation. However, I’ve attended a few lectures and presentations based on the material so I’m pretty sure what the whole thing is about.

Was really just curious in particular how he setup his C++ Future templates. Personally, the way I write my Futures is a bit similar to Java 1.4+ API style whereas you can pass a reference/pointer to a non-copyable Future object into a thread. The thread populates the future with the requested resource. Since the future has atomic locks, another thread can at anytime query the Future to determine if it’s done and then retrieve the data.

Very cool concept it’s very multithread platform friendly. Click here to download the C++ sources.

Concurrency

Interesting, I gave a talk at EA-Los Angeles a few months ago about a similar topic. And since that time, my thoughts on parallel programming patterns extended to such concepts as Futures, Jobs, Agents, and Atomics. This talk appears to discuss this issue on a more higher level.

I like a lot of the comments he gave during the presentation such as “You learn by making mistakes” and many of the other unique viewpoints Ralph had. I also agree with one of the comments someone posted on Herb’s site whereas he would like to see more great books like Effective C++ (ah I see people discussing an upcoming Effective Concurrency book from him). I read that book cover to cover many years ago and I recall Design Patterns was the next book I planned to acquire (but forgot). So it was nice watching this presentation which helped toggle my memory

One of the main points he hit upon around Slide 13 (40:00) was avoiding data race conditions. That is one my biggest fears personally when I sit down and architect a parallel system. I think about what data needs to be shared, how to avoid locking access to this data, etc. So it’s always interesting to hear other viewpoints on this issue

Concurrency Parallel Programming Patterns

Lately I’ve been thinking about playing around with integrating multicore physics. Currently, the physics system I coded occurs in the main game thread pass. You know the routine. Multicore physics or rather in my case, Multicore Collision Detection would involve the main thread passing collision volumes to a concurrent physics thread. The physics thread takes the velocities of the objects and watches for collisions. When a collision is detected, this information is propagated to the main thread

The gains for the average title might not be all that huge but for a title with hundreds of entities in the physics world the savings might be worth it. In my case though I mostly interested in leveraging more cores.

I’m a little hesitant though to go rip apart my engine yet again to introduce another layer of complexity. Actually, what I really dread is the thought of having to chase a potential read/write data race issue.

But if I do decide to pursue this my thought is that I would write this as a “Job” that runs asynchronously, running the physics simulation on its’ own Core. Essentially it would work like this:

- Loop

– Check queue for collision volume updates

— Run the physics simulation

—- Copy current state into a list of events that the main thread can query at anytime for current status of the physics world

The only bottleneck here is the last step, when the main thread queries “Physics World” for the current state. But it shouldn’t really be a bottleneck if this is handled properly.

Should be a fairly straight forward thing really unless I’m missing something. The main game thread and physics really shouldn’t be sharing much information beyond the current state of the physics world. If I do implement this will make sure to keep it all configurable so I can switch between single threaded and multi-threaded physics.

Concurrency, Projects

Recently, I made a presentation about “Agents”. This is a unique, distributed technology that can be used to tackle huge workloads and decompose these tasks into localized problem chunks. Agents act based on local information to solve their problem then produce a result if I were to explain it simply.

You can find a wealth of information on Agents at wikipedia and other sites. There are many different types. In real life, you can think of an Ant as an Agent. Ants all act on local information to work together as a huge cohesive unit. Decisions are not made globally by one particular Ant but rather, each decision is made locally.

This paradigm is not really employed heavily in Video Games- at least on the Client side. In the business and R&D sectors in which I worked in Agents were much more common which is no suprise the level of CPU complexity required was very demanding.

But what if games were to try to leverage this more wouldn’t that be interesting? The average gaming desktop nowadays is probably just a Dual Core Computer at best. But the key- most gamers have other computers laying around. The Wife and kids are no doubt using hand-me-downs to play games and are probably not pushing their computer to the max. Even so, they are probably not using them 24/7.

So why not write games to not limit themselves to just multi-core/multi-CPU but think more about utilization of local networks. After all, internally threads communicate with each other using message protocols in any case that can be fairly easily ported to networks

What processes can we stream? Well, obviously AI is a candidate. If you have a lot of realistic Agents running around in the game then it might be feasible to try to utilize other systems on the network to help make realtime decisions. The other Agents in the network can all connect to the main game client like other Clients, inputting in the results of their computations. Communication on local networks (LAN) is really fast in any case.

Anyway, all of this might sound pretty far fetched but think about rendering farms like 3d Studio Max, Maya, Incredibuild, etc. They all think this way- utilizing idle PCs on the network. This way- our software is truly scalable- no longer bound by local constraints of the host machine (at least not fully). This can even be taken up another notch too- if we allowed gamers to connect to each other over the internet and Idle PCs can be utilized in a very dynamic way to produce a dynamic world governed by the Computers connected to this network. Imagine the possibilities. People are already doing this in other fields- but it would be great to see this in video games

“Gaming” Agents I like to call them (even though they are identical to Software Agents but merely utilized for our Domain)- holds interesting potential.

Concurrency, Programming, Projects Agents, C++, Games, Programming, sandbox

I coded all three implementations this weekend. The Job Manager is a basic bare bones implementation in which accepts Job requests and delegates these services to various worker threads. It tries to fully leverage the target platform by analyzing the hardware and counting the logical processors. Next, as jobs come in the Job manager begins to delegate these tasks to the appropriate threads.

Job Managers are the way to go for multi-core architectures they really help software fully leverage the underlying hardware plus it abstracts some of the nitty details from programmers.

The first test for the Job Manager this weekend was to fire off an Async File Job in which handles streaming a package. Works pretty well aside from some issues with Resource management (problems in other parts of the codebase). My engine was already split into separate render/game logic threads so it wasn’t too painful of an addition to include support for asynchronous file loading.

Also implemented an Atomic Class which is a lock-free programming paradigm. Lastly I took a crack at writing a C++ Future templated type in which employs an Atomic that can be accessed by different threads concurrently to mark when data is ready for consumption.

Steps:

• Caller sends in a reference to a Future they created locally. Like Future<Package*>&. This reference is stored within the Async Job
• The Job manager ensures that all package dependencies have been loaded first. If not, it goes to load them (create a Job to load it).
• If a child Job task was spawned, we check back in a few frames to see if it’s complete. If so, we register the package in the main thread.
• Once all dependencies are resolved we proceed to spawn a Job to concurrently stream the content
• Once loaded, we populate the Future<Package*> reference with the PAckage we just loaded
• The caller from the main thread will wait until the package has been loaded if it’s not ready. So far the Job is always ready for me by the time I need it though. So I havent had to pause the main thread yet

Concurrency, Programming, Projects atomic, C++, future, job manager