Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Gamasutra: The Art & Business of Making Gamesspacer
Sponsored Feature: Data-Oriented Design - Now And In The Future
View All     RSS
May 25, 2019
arrowPress Releases
May 25, 2019
Games Press
View All     RSS

If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Sponsored Feature: Data-Oriented Design - Now And In The Future

April 13, 2011 Article Start Previous Page 2 of 3 Next

Splitting Things Up

Have we really gained much by reorganizing the code this way? We're doing two full passes over the AI entities, so wouldn't that be worse from a memory point of view? Ultimately you need to measure it and compare the two. On modern hardware platforms, I would expect performance to be better because, even though we're traversing through the entities twice, we're using the code cache more efficiently and accessing the entities sequentially (which allows us to pre-fetch the next one too).

If this is the only change we make to the entity update, and the rest of the code is the usual deep tree-traversal code, we might not have gained much because we're still blowing the cache limits with every update. We might need to apply the same design principles to the rest of the update function to start seeing performance improvements. But at the very least, even with this small change, we have made it easier to parallelize.

One thing we've gained is the ability to modify our data to fit the way we're using it, and that's the key to big performance boosts. For example, after seeing how the entity is updated in two separate passes, you might notice that only some of the data that was stored in the entity object is touched on the first update, while the second pass accesses more specific data.

At that point we can split up the entity class into two different sets of data. Then the most difficult task is to name these sets of data in some meaningful way. They're not representing real objects or real-world concepts anymore, but different aspects of a concept, broken down purely by how the data is processed. So what before was an AIEntity has now become an EntityInfo (containing things like position, orientation, and some highlevel data) and an AIState (with the current goals, orders, paths to follow, enemies targeted, and so forth).

The overall update function now deals with EntityInfo structures in the first pass and AIState structures in the second pass, making it much more cache friendly and efficient.

Realistically, both the first and second passes will have to access some common data such as the entity's current state: fleeing, engaged, exploring, idle, etc. If it's only a small amount of data, the best solution might be to simply duplicate that data on both structures, which goes against all "common wisdom" in Computer Science. If the common data is larger or is read-write, it might make more sense to give it a separate data structure of its own.

At this point, a different kind of complexity is introduced—keeping track of all the relationships from the different structures. This can be a particular challenge while debugging because some of the data that belongs to the same logical entity isn't stored in the same structure, making it harder to explore in a debugger. Even so, making good use of indices and handles helps this problem become much more manageable (see "Managing Data Relationships" in the September 2008 issue of Game Developer).

Conditional Execution

So far things are pretty simple because we're assuming that every AI entity needs both updates and some ray casts. That's not very realistic because entities are probably very bursty—sometimes they need a lot of ray casts, and sometimes they're idle or following orders and don't need any for a while. We can deal with this situation by adding a conditional execution to the second update function.

The easiest way to conditionally execute the update would be to add an extra output parameter to the FirstUpdate() function that indicates whether the entity needs a second update or not. The same information could then be derived from the calling code depending on whether there were any ray cast queries added. Then, in the second pass, we only update those entities that appear in the list of entities requiring a second update.

The biggest drawback of this approach is that the second update went from traversing memory linearly to skipping over entities, potentially affecting cache performance. So what we thought was going to be a performance optimization ended up making things slower. Unless we're gaining a significant performance improvement, it's often better to simply do the work for all entities whether they need it or not. However, if on average less than 10 or 20 percent of the entities need a ray cast, then it might be worth avoiding doing the second update on all the other entities and paying the conditional execution penalty.

If the number of entities to be updated in the second pass were fairly small, another approach would be to copy all necessary data from the first pass into a new temporary buffer. The second pass could then process that data sequentially without any performance penalties, which would completely offset the performance hit that comes from copying the data.

Another alternative, especially if the conditional execution remains fairly similar from frame to frame, is to relocate entities that need ray casting together. That way, the copying is minimal (swapping an entity to a new location in the array whenever it needs a ray cast), and we still get the benefit of the sequential second update. For this to work, all your entities need to be fully relocatable, which means working with handles or some other indirection, or updating all the references to the entities that swapped places.

Article Start Previous Page 2 of 3 Next

Related Jobs

Dream Harvest
Dream Harvest — Brighton, England, United Kingdom

Technical Game Designer
Insomniac Games
Insomniac Games — Burbank, California, United States

Director, Art Management
Pixar Animation Studios
Pixar Animation Studios — Emeryville, California, United States

Animation Tools Software Engineer
Disbelief — Chicago, Illinois, United States

Senior Programmer, Chicago

Loading Comments

loader image