We’re rewarding the question askers & reputations are being recalculated! Read more.
236

Preamble: A few objections have been raised in the comments, and I think they largely stem from a misunderstanding of what we mean when we say "premature optimization" - so I wanted to add a little clarification on that. "Don't optimize prematurely" does not mean "write code you know is bad, because Knuth says you're not allowed to clean it up until the ...


106

With regards to Java vs C++, I've written a voxel engine in both (C++ version shown above). I've also been writing voxel engines since 2004 (when they were not vogue). :) I can say with little hesitation that C++ performance is far superior (but it is also more difficult to code). Its less about the computational speed, and more about memory management. ...


44

But my impression is that in game development, unless you have a reason to do otherwise, everything should be nearly as fast as possible. Not necessarily. Just like in application software, there is code in a game which is performance-critical and code which is not. If the code is executed several thousand times per frame, then such a low-level ...


43

The two key benefits that I constantly hear lauded about entity systems are 1) the easy construction of new kinds of entities due to not having to tangle with complex inheritance hierarchies, and 2) cache efficiency. Note that (1) is a benefit of component-based design, not just ES/ECS. You can use components in many ways that do not have the "systems" part ...


42

note: this answer began as a comment on DMGregory's answer, and so doesn't duplicate the very good points he makes. "Would it not be incredibly difficult to change some of the core structures of the game at the end, rather than developing them the first time with performance in mind?" This, to me, is the crux of the question. When creating your original ...


40

Deferred shading is only a technique to "defer" the actual shading operation for later stages, this can be great to reduce the number of passes needed (for example) to render 10 lights which needs 10 passes. My point is regardless of the rendering technique you are using there are certain possible rendering optimizations that reduce the number of objects (...


37

Having a single big file has a few benefits for performance, regardless of platform. Many PC games use big files too. You can manually cache the offset of each file within the big file, to avoid the need to read file system directory entries (which can involve multiple seeks per file opened if you miss the cache). You get full control of the order of the ...


30

Most of the size used by any game lies in its assets, most notably, audio, video and (to a slightly lesser degree) images/textures. Binaries and game data is typically much smaller than any of those. Then, all of these assets may or may not be compressed, may use different compression schemes, may have different formats, and even have different resolution/...


29

If you need something that stays linear over any distance (unlike distance^2) and yet appears vaguely circular (unlike the squarish Chebyshev and diamond-like Manhattan distances), you can average the latter two techniques to get an octagonally-shaped distance approximation: dx = abs(x1 - x0) dy = abs(y1 - y0) dist = 0.5 * (dx + dy + max(dx, dy)) Here is ...


26

This sounds like a job for a grid. Divide your game space into a grid and for each grid cell keep a list of the objects currently in it. When objects move across a cell boundary, update which list they're in. When updating an object and searching for others to interact with, you can look at just the current grid cell and a few neighboring ones. You can ...


26

TL;DR; Your problem is not with performing the distance function. Your problem is performing the distance function so many times. In other words you need an algorithmic optimization rather than a mathematical one. [EDIT] I am deleting the first section of my answer, because people are hating it. The question title was asking for alternative distance ...


25

Agner Fog's optimization guides are excellent. He has guides, tables of instruction timings, and docs on the microarchitecture of all recent x86 CPU designs (going back as far as Intel Pentium). See also some other resources linked from https://stackoverflow.com/tags/x86/info Just for fun, I'll answer some of the questions (numbers from recent Intel CPUs)....


24

"Do not optimise early" doesn't mean "pick the worst possible way to do things". You still need to consider performance implications (unless you're just prototyping). The point is not to cripple other, more important things at that point in development - like flexibility, reliability etc. Pick simple, safe optimisations - choose the things you limit, and the ...


22

The first tip you'll get is this - don't. Modern compilers are actually really really good at optimizing code, and will be much more likely to do a better job of it than any self-rolled assembly language you may write. The exception would be any specific case where you have determined for certain that the compiler is doing a bad job of optimizing, so that'...


21

I'll be the one going against the grain here and say, it is never too early to learn about optimizations, especially assembly optimizations and more importantly, debugging in assembly. I believe that you will gain the maximum benefit of it if you are a student (because then you have very little to lose [i.e. time/money wise]) and everything to gain. If you ...


21

Sometimes this question can arise not because of the cost of performing distance calculations, but because of the number of times the calculation is being made. In a large game world with many actors, it is unscalable to keep checking the distance between one actor and all the others. As more players, NPCs and projectiles enter the world, the number of ...


20

Just in addition to what David already said in his answer: It is true, that up to 95-99% of almost every modern game size is constituted by its assets: video, audio, textures etc. If you are wondering why some games take only 4Gb whereas others much more having same level of graphics?? It can be also due to the fact that some game store their assets on the ...


20

Triangles, the reason is triangles' ratesrization algorithm is faster, and also natively supported in hardware. So it would be faster to convert one quad into two triangles and do the rasterization. Actually that is what happens when you draw a quad on modern graphics hardware. So the question is what makes it faster ? There are certain characteristics in ...


17

Using a bidirectional path finder usually solves this issue if the area the player is stuck in is small. They basically advance from the player's position and the destination at the same time and when they meet, the algorithm ends. If one of them gets stuck, then you can stop both.


16

It depends on the CPU in question, but for a modern CPU the list is something like this: Bitwise, addition, subtraction, comparison, multiplication Division Control flow (see answer 3) Depending on CPU there may be a considerable toll for working with 64 bit data types. Your questions: Not at all or not appreciably on a modern CPU. Depend on CPU. That ...


16

Generally, you don't handle out-of-memory. The only sane option in software as large and complex as a game is to just crash/assert/terminate in your memory allocator as soon as possible (especially in debug builds). Out-of-memory conditions are tested for and handled in some core system software or server software in some cases but not usually elsewhere. ...


15

Usually, solid optimisation doesn't depend on using Assembly, or doing micro-optimisations with code in higher level languages. If you read a lot of research papers (as I do -- or try to!), you'll see that oftentimes the improvements made to algorithms are at a broader conceptual, "qualitative" level, rather than at the more "quantitative" level of micro-...


14

Spatial division is always O(N^2) in worst case and that is what complexity in informatics is about. However there are algorithms that work in linear time O(N). All of them are based on some kind of sweep line. Basically you need to have your objects sorted by one coordinate. Let's say X. If you perform the sort every time before collision detection, the ...


14

getBodiesToCheck() There could be two problems with the getBodiesToCheck() function; first: if(!contains(bodiesToCheck, b)) bodiesToCheck.push_back(b); This part is O(n2) isn't it? Rather than checking to see if the body is already in the list, use painting instead. loop_count++; if(!loop_count) { // if loop_count can wrap, // you just need to ...


14

You should make a sort of connectivity map - by flood-filling all unconnected walkable areas and marking each one with a different tag, once at game start (and every time when terrain changes). Then, before even trying to make a path, check if source and destination locations belong to areas with the same tag, if not - path obviously can not be made. ...


13

Jovan's answer is great, but just wanted to add that there is sometimes hardware support for asking the question "Did this geometry actually render any pixels?" (your idea #1) These are called occlusion queries - these is a good GPU Gems article about them here This is pretty similar to your idea #1, except you don't need an invisible buffer, and can be ...


13

99% of the time, the compiler will produce better assembly than you will. That being said, its often very useful to be able to read assembly when working in performance critical environments for a couple of reason: Occasionally the compiler will do something that you're not expecting it to do, generating "bad" code, or otherwise non-optimal code. Debugging ...


12

1) Scene is rendered to a invisible buffer, using low resolution and low polygon count models (or even using only bounding volumes like cubes or spheres). The buffer is then checked to know what is visible or not. Before rendering the low resolution scene, some frustum culling could be applied, to already remove as much objects as possible. This ...


12

As you've already shown, there are a number of solutions to this problem, but none 100% ideal. Spheres are tricky. Cube-based One common route, used by Spore and quite likely other games (though it's hard to tell for certain without peeking under the hood), is to project the sphere onto a cube, and use a square grid over each cube face. (This is what Alec ...


Only top voted, non community-wiki answers of a minimum length are eligible