Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm creating a tower defense game and I'm having logistical issues trying to figure out how to best have all of the enitites do their apporiate task.

I have considered just constantly looping through a list of all the game entities calling a onAction() method, but I'm not sure if that is effective.

I have also considered having each entity be a thread, but when I am dealing with hundreds of entities, some of which don't need thread time, I'm back to square one.

Can I get any suggestions on a solid approach? Am I on the correct track with my first idea?

Thanks for any help ~Aedon

share|improve this question
add comment

5 Answers

up vote 9 down vote accepted

First of all, using a thread per entity (talking about OS threads here, not language specific cheap co-routines) is insane. A thread is expensive, for example it needs a stack which by default uses 1MB of address space. Thread switching is expensive costing thousands of CPU cycles.

I wouldn't use multi threading at all in your main game logic. It adds a lot of complexity. First write it single-threaded and later perhaps multi-thread some hot-spots like path-finding and collision detection.

Tim Sweeney[The Unreal Engine guy]: For multithreading optimizations, we're focusing on physics, animation updates, the renderer's scene traversal loop, sound updates, and content streaming. We are not attempting to multithread systems that are highly sequential and object-oriented, such as the gameplay.

Implementing a multithreaded system requires two to three times the development and testing effort of implementing a comparable non-multithreaded system

From http://www.anandtech.com/show/1645/3


Just iterating over all entities is usually fast enough. You'll have a few thousand of them, so iterating over them by itself takes fractions of a millisecond. Benchmark first before worrying about such stuff.

When I wrote an RTS (which from the technical side is not that far from a tower defense game) the top performance killers with a naive implementation were:

  • Collision detection, you need to use some spatial partitioning to make this fast.
  • Pathing can be very difficult, depends on your demands and the topology of your level
  • Finding opponents in firing-range. Once again needs spatial partitioning. And in my experience separate partitions for different factions are a must(you have many friendly units in firing range typically, but few hostiles). Locking on to a target, once you found one, until it get out of range/dies saves a lot too, since you don't need to search again all the time.

The cost of simple looping and local entity behavior typically pales compared to these few expensive tasks.

share|improve this answer
    
Thank you for your highly detailed answer. This really gave me a lot of insight. –  AedonEtLIRA Jul 18 '11 at 14:39
add comment

This came up on Stack Overflow a while back.

share|improve this answer
add comment

Most games use scripts for controlling much of their entities' logic. That should tell you how much the game's overall performance will be coming from the basic entity loop (ie: precious little).

The entity loop is not the low-hanging fruit of performance. Use whatever makes making your game easier.

share|improve this answer
add comment

First steps: write something and measure the performance.

If the performance is not good enough then use the measurements you made to drive your optimization.

Naively threading hundreds of entities is probably not the way to go. A scheduling queue might be, but only if you determined by your measurements above that the big OnAction() loop is tying you down.

So yes you are on the right track with the action loop and that is, in fact, how many titles work.

share|improve this answer
    
Kudos for suggesting measuring things before worrying about performance. –  jheriko Jul 16 '11 at 2:06
add comment

I'm creating a tower defense game

If this is your game you shouldn't have performance problems with entity updates unless something else is wrong. If you have a performance problem and you've measured it to be coming from your entity loop you need to cull the number of entities being updated, either by simply having less or by looking at architectural/algorithmic optimisation e.g. if projectiles are entities make them something else, and make them in a nice, flat, array or ring buffer you can iterate over quickly instead of instances scattered in memory, inline their updates, or if they must be function calls make sure they aren't virtual

I have considered just constantly looping through a list of all the game entities calling a onAction() method, but I'm not sure if that is effective.

This is how all of the fastest and best solutions I have seen work fundamentally. There is lots of micro optimisation and threading potential for this approach, but even without it all its fine - you can ship a AAA FPS with something like this at its core, iterating over instances scattered in memory by using virtual calls and have 1000s of entities just fine (in C/C++ at least).

I have also considered having each entity be a thread

That is fairly insane - stay single threaded until you are comfortable and experienced enough with threading to not have such ideas

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.