Multi Threading

[TechSY730]

Now that >2 core computers are becoming much more common, are there any plans to make your game engines multi-threaded (or at least parallelize some easily split apart loops that are used often). In the case of AI war, could this also be done for the AI thread?

I know this would be a lot of work, thought, and debugging (though there are libraries that can ease this pain some), but it may help those with high end PCs overcome some of the performance challenges that you running across, and make previously laggy tasks much less laggy. And as they say, you are going to have to do it to take advantage of the newer hardware that is coming out.

One thing I don't know is how well you can enforce consistency across multiple runs with current multi-threading techniques and libraries. For your multi-player games, getting the same results across multiple runs and platforms is very important no matter what system you are running on.
For completely separable loops (loops where each iteration is completely independent from the others), this is not an issue, but I suspect that some of your CPU intensive loops that are not so nice that way.

[x4000]

This has been beaten to death in some older threads on this forum, somewhere in the AI War forum.  At any rate: no, there are no plans to ever make AI War more than single-threaded for the main thread, as that's basically technically impossible because of the required network model.

In terms of the AI thread, using more threads would be worse than useless, because it doesn't need to run any faster and so that would just be a waste of your RAM and extra cores.   The AI thread is already faster than the network can handle, so it has to be throttled to only so many commands per second to avoid flooding the network with too much data (and in the case of single player, it gives the AI at least a slightly more human-like reaction time, and keeps the reaction time of the AI from varying too much by host.

In terms of Tidalis: that's ridiculously lightweight already, and there's no point.

In terms of AVWW: that's somewhere in between AI War and Tidalis in terms of load, but it's still not likely to require multiple threads or even benefit much from them.  It won't have a separate AI thread, so, like Tidalis its game logic will be purely single-threaded. (Things like networking, sound, music, and so forth do have their own threads in all these games, but the load there is so trivial that they don't even really register on the other cores compared to the main game thread).

The network model of AVWW doesn't present any technical barriers to multithreading (unlike AI War or other strategy games), though.  So if we wound up needing to have worker threads for long-running processes, those could be set up for AVWW.  I just strongly doubt that will ever be needed, given the game design.  After AI War, we're used to writing such highly efficient code that it's likely to run on one core, anyway.  And it's a catch 22, because any computer with a weak enough processor to need more than one core... probably only has one core anyway.

So, no, there are no plans for this for AVWW unless it becomes down the line, and it's completely out of the question for AI War for reasons that have been discussed in extreme length and detail (that was a massive forum thread last year, and nothing's changed since then) before.

[TechSY730]

Yea, I was suspecting that the pretty much all current multi-threaded algorithms and data-structures that would be useful to you guys don't provide good enough consistency guarantees for what you need. I just thought it was worth a shot.

I really hope that such consistent parallel algorithms and data structures will be developed soon.

[x4000]

I really don't think that it's mathematically possible to get the same result from parallel operations as you would in non-parallel operations, honestly.  That's because each operation depends on the one before it to some extent, and so if you change the order you change the result.  It's quite an insurmountable problem, I think.  Last I heard IBM is offering $1 million to the programmer or team who solves the problem, but nobody has won it or even come close from what I know in the last 5 years or whatever it was they've been running this.

[TechSY730]

I really don't think that it's mathematically possible to get the same result from parallel operations as you would in non-parallel operations, honestly.  That's because each operation depends on the one before it to some extent, and so if you change the order you change the result.  It's quite an insurmountable problem, I think.  Last I heard IBM is offering $1 million to the programmer or team who solves the problem, but nobody has won it or even come close from what I know in the last 5 years or whatever it was they've been running this.

Without absurd amounts of locking, it may not be possible to have a consistently reproducible paralell algorithm that is running with a non-deterministic (from the program's point of view) thread scheduler (like you have with most OSs)

Again, for operations that do not depend on order (like those independent iteration loops I mentioned), this is of course trivially possible. Also, if there is only one correct answer, then a correct parallel aglorithm will of course give the same results too.

But for parallelizing dependent operations, approximation, probabilistic, or "find one solution that works of a possible many" algorithms, who knows...

And really, a measly 1 million? Yes that is a lot, but proving that parallel algorithms can be made to give consistently reproducible results outside of those limited cases I mentioned seems MUCH more valuable to the industry than 1 million dollars.

[RogueDeus]

This has been beaten to death in some older threads on this forum, somewhere in the AI War forum.  At any rate: no, there are no plans to ever make AI War more than single-threaded for the main thread, as that's basically technically impossible because of the required network model.

...

Disregarding your intentions for your games, past and current, at what point would you say a game would need to be multi-threaded? Number of units? Level of detail (physics, stats calculation, AI)? etc.... Based on current mainstream hardware.

I am currently in the throws of conceptualizing a unique turn based game that has the potential to grow geometrically to extreme numbers of operations, using a uniquely iterative form of game play... As a result of this, I know I will have to build into the foundation of it a way to break it up into multiple threads, once it has reached a critical mass, and continue to do so as required until the hardware becomes strained.

My fear is that I may end up over engineering it as a result...

[x4000]

Disregarding your intentions for your games, past and current, at what point would you say a game would need to be multi-threaded? Number of units? Level of detail (physics, stats calculation, AI)? etc.... Based on current mainstream hardware.

I am currently in the throws of conceptualizing a unique turn based game that has the potential to grow geometrically to extreme numbers of operations, using a uniquely iterative form of game play... As a result of this, I know I will have to build into the foundation of it a way to break it up into multiple threads, once it has reached a critical mass, and continue to do so as required until the hardware becomes strained.

My fear is that I may end up over engineering it as a result...

That's really impossible to quantify in a general sense; it depends on how complex each turn is, and what sort of hardware you are targeting.  If you are targeting normal current-day computer hardware, most people have two cores but not more than that.  If you want to scale this to n number of cores, then you just need a way to break up the processing.

Anything that doesn't need to have a deterministic result, and anything that is easily compartmentalized with logic without relying on prior steps from other logic branches, is is a great candidate for being able to scale from 1-n cores.  In those sort of cases, there's really no reason not to try to split it up from the start.  But trying to retrofit that in belatedly is a bad idea, so it's good you're approaching this from the start.

In the case of AI War, the only thing that really meets the requirements are things like sound, disk loading of assets, and AI.  So all those things run on different threads.  But because our simulation has to be both deterministic (for multiplayer) and because each stage of the simulation affects future steps (on a per-planet basis in particular, but also in larger senses including economic calculations, etc), that's why we can't split the simulation itself up.

I mention the above because even in a turn-based game, I think you will run into the same challenges.  If your units take on action, then they cannot take another.  If X resources are spent on Y activity, then there are fewer resources for Z activity.  That creates interdependence that is hard to break apart into multiple threads, because then you have both X and Z trying to spend the same resources, or both of them trying to move the same unit.  Of course if you have multiple distinct AI players all acting at once, and they share no resources, then that's less of an issue.  Unless their units block one another on the map, for instance, in which case you get things like a unit moving to a tile and then another unit not being able to despite the fact that the second unit actually would have been the best choice all around for that tile.


Multithreading can be done, but it has to be the starting premise of any strategy game simulation if it's going to work gracefully, in my opinion.  And that's very hard to design, as most traditional strategy game simulations aren't well suited to it.

[RogueDeus]

I mention the above because even in a turn-based game, I think you will run into the same challenges.  If your units take on action, then they cannot take another.  If X resources are spent on Y activity, then there are fewer resources for Z activity.  That creates interdependence that is hard to break apart into multiple threads, because then you have both X and Z trying to spend the same resources, or both of them trying to move the same unit.  Of course if you have multiple distinct AI players all acting at once, and they share no resources, then that's less of an issue.  Unless their units block one another on the map, for instance, in which case you get things like a unit moving to a tile and then another unit not being able to despite the fact that the second unit actually would have been the best choice all around for that tile.


Multithreading can be done, but it has to be the starting premise of any strategy game simulation if it's going to work gracefully, in my opinion.  And that's very hard to design, as most traditional strategy game simulations aren't well suited to it.

Thanks for the quick reply. I had not expected that.

You are correct. I have spent a very large amount of my time (lately) tackling the realities of current game/programming canon vs. what I see might actually allow me to make the game I see in my mind. Part of that involves abstracting a very large part of the combat mechanic, in order to facilitate multi-threading.

[x4000]

Yep, I went through a lot of the same thing with AI War.  I thought it would be a pipe dream to have 10,000 units in realtime.  I thought that I might be able to squeak that out on some of the very best computers around.

Of course, after actually implementing it, I found that even old computers by the standards of two years ago pretty much laughed at 10,000 units in my engine.  And I was only starting to stutter at 40k to 50k units, and really lagging horribly at 60k.  Then fast forward another two years, and it can easily run 60k on the same machines, and a few people had it up to 300k to 400k on overclocked monster machines.

All that isn't just cleverness on my part, it's a matter of structuring the game code around the sort of result I wanted.  I wanted lots of units and great AI and large multiplayer.  So that's what I got.  That means that certain things, like 3D graphics or various other things -- multithreading, for one -- become out of the question as a consequence.

[RogueDeus]

Of course, after actually implementing it, I found that even old computers by the standards of two years ago pretty much laughed at 10,000 units in my engine.  And I was only starting to stutter at 40k to 50k units, and really lagging horribly at 60k.  Then fast forward another two years, and it can easily run 60k on the same machines, and a few people had it up to 300k to 400k on overclocked monster machines.

All that isn't just cleverness on my part, it's a matter of structuring the game code around the sort of result I wanted.  I wanted lots of units and great AI and large multiplayer.  So that's what I got.  That means that certain things, like 3D graphics or various other things -- multithreading, for one -- become out of the question as a consequence.

Did you gain or lose ground shifting from XNA to Unity3D?

[x4000]

I never used XNA, I used SlimDX.  I lost and gained ground shifting to Unity 3D.  That was done with AI War 4.0, over a year after AI War had already been out (and sold 50k copies already).  Unity has a heap size limit of about 800mb, and it runs Mono, which is less efficient on some things than .NET.  For instance, never ever use foreach statements as they waste an enormous amount of transient heap usage.  Just as one example.  On the other hand, while we lost some in the edges of our performance, we gained a lot of functionality as well as cross-platform support.  And using some of that functionality we improved the graphics while reducing the GPU load and putting in other optimizations to maintain sim speed automatically in poor framerate conditions, etc.

In Unity I think that more than about 180k realtime ships is just infeasible now, mainly because of the heap size limit, but that was never part of the design goal anyhow.  On the other hand, general performance is better, graphics are better, yadda yadda yadda.  XNA is nowhere on my list of platforms I'd want to use at this point.

[RogueDeus]

I never used XNA, I used SlimDX. 

Sorry, I knew you used SlimDX I just typed XNA for some odd reason. :p
(maybe because I recently tried coding with it.)

From what I gather from you, here and in the Unity thread, I should probably reconsider my use of Unity, if I am looking to make a large multi-threaded game. Graphics are not important for me at this, or any, stage in my game, as I am almost dogmatically dedicated to making the most 'game' possible NOW, and then improving graphics later (if, it becomes necessary).

I had actually started to write a basic engine recently, but ran into some issues with the camera code, and couldn't get a straight answer from anyone in the XNA crowd over at StackOverflow. So I started exploring the idea of using an established engine.

Of course, your opinions have probably changed my mind back to making my own engine... It is just the idea of having to spend all that time coding it that is making me wish I could find a good 2D Engine in C# ready to run.

[x4000]

Well, the thing to understand is that with anything big and complex and new you're going to be doing most of the work yourself.  If you just want to make a simple FPS clone or simple mario clone or a one-screen platformer or an adventure game or basic JRPG, there are lots of engines out there to let you do that easily.  All sorts of things all over the place.  But if you're wanting to do something more involved, that involves so many tricks of memory management and project organization that you wind up writing an entire engine that basically uses the render framework of... something.  Either raw DX/opengl, or else something like Unity so that it's cross platform.  You might try looking at some of the other 2D frameworks out there, like Love or similar.

I really adore Unity, and my engine that previously sat on SlimDX (which was just a very thin DX wrapper) now resides on the thinnest slice of the Unity engine that I can make it run on.  That's given me the power to do a lot of things I could not do before, plus the cross-platform bit, plus I can still code in C# which is my preference.  But it's not free to use in that way, for sure.  Something like Love would be.

[RogueDeus]

Well, the thing to understand is that with anything big and complex and new you're going to be doing most of the work yourself.  ... 

But if you're wanting to do something more involved, that involves so many tricks of memory management and project organization that you wind up writing an entire engine that basically uses the render framework of... something.  ...

I really adore Unity, and my engine that previously sat on SlimDX (which was just a very thin DX wrapper) now resides on the thinnest slice of the Unity engine that I can make it run on.  That's given me the power to do a lot of things I could not do before, plus the cross-platform bit, plus I can still code in C# which is my preference.  But it's not free to use in that way, for sure.  Something like Love would be.

Thank you.

I think you are right, I need to realize that I can't re-invent a game genre over night, and not without first inventing the tools to do it myself. So if I am going to get into this (game development), I need to start at a realistic level of expectation. This means starting small, and maybe customizing a key feature of an already established genre rather then the entire game. That way I can pull from whats already been done, and learn, learn, learn in the process.

Might I start a new topic soon that involves just questions about using Unity3D with C#? I will do my best not to burden you with too many simple ones. For those I will utilize already established Q&A forums like UnityAnswers. But however infrequent I am sure I will want to pick your brain more regarding how you would handle something in Unity. That is, if you are not already busy. I can not imagine the kind of schedule that is required for what you are doing currently. I know that any time I get from you is a gift.

Also, assuming this works out, I have no qualms purchasing Unity Pro. As a matter of fact the only reason I didn't just up and buy it today was my fear of ending up not using Unity in the end and having already spent the money!

[x4000]

Sure, no worries.  And I can understand being reluctant on spending money until you know you're going to use it.  And I agree that starting smaller is good.

I started out doing fan levels and content for various games (platformers, adventure, FPS, RPG, dungeon crawler, action), then moved on to doing some more in-depth mods that were still relatively small, then I did a few total conversions of a few simpler games, and I coded some simple text-based adventure games.  This was basically ages 9-18 for me.  Then I moved into doing mario clones in college, and I did two really in-depth ones of those.  Then after college I worked on an adventure/puzzle game called Alden Ridge that started simple and then grew huge.  Then after about 8 months of that, I sat down and did AI War as a side project.  I year and a half after I started that project, bam -- I was a fulltime indie developer.  It only took me 18 years to do.

But in all seriousness, I never considered this even as a feasible job until I was working on AI War as my hobby.  That's when I realized I had something, and that there was actually a market for the sorts of games I might be able to make.

My advice: start with reasonable expectations, and make the sort of games you want to play.  If you enjoy doing it, then it doesn't matter what happens beyond that.  And if you enjoy doing it, and put in the time and effort, then that's when success is more likely to come in the first place.  AI War wasn't my first project -- it wasn't even my twentieth, if you count everything.  If you count just the projects I coded from scratch and put substantial effort (as in more than 6 months of concentrated time into), then it was my 5th project.

There's no easy way to just be an overnight success, or else everybody would be doing it.  But it definitely can be done!