243

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 ...


54

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 ...


54

No high-performance voxel renderer draws individual cubes or cube faces. To get good performance, groups of voxels are assembled together into a single mesh, called a "Chunk". A chunk is typically something like 16x16x16 voxels, but might be larger or smaller as you need. It contains only the visible faces of voxels in that chunk, stitched together into a ...


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

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 (...


43

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 ...


30

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 ...


28

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)....


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 ...


24

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 ...


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 ...


23

Yes, it generates more chunks (or at least more of the village tree) than you think it does. This is what I call "area of interest" in my voxel code. There are two kinds of area of interest: Logical (which is what we're discussing here) Rendering (which is typically be smaller in radius than the logical area) Remember that the only way your renderer can ...


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 ...


18

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

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. ...


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

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 ...


13

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 ...


13

Like so much of gamedev, the answer to how city sim games accomplish this seemingly-impossible feat is: they probably don't. They're just faking it well. ;) Sims like these will typically operate on a "chunked" level, modelling groups of people, neighbourhoods, traffic corridors, or other city dynamics as a whole, rather than processing AI for ...


11

I suspected OP already knew this approach so I mentioned it in a comment as just a starting point, but I'll try fleshing it out a bit more... Most physics engines divide dynamic objects into two groups, "awake," and "sleeping." Objects sleep when they sit at rest, and wake when moved or accelerated by some outside influence. A sleeping object behaves like ...


10

You can do this purely in a vertex shader. You'd want to apply this shader to everything you render. One trick though that you can do is weight it so that the nearby objects are flat out to say 100 meters. I'd recommend this because in an FPS game the distortion on objects requires you to change things. (Players will aim at things wrong). If you keep the ...


10

A lot of the answers seem to be focusing a lot on the performance aspect of "optimization" while I myself like to look at optimization and the whole ordeal of optimizing too early at a more abstract level. Humor me as I attempt to elaborate on my perspective with the help of polyominoes. Suppose we have some fixed boundaries set by the framework or engine ...


10

When in doubt, use best practices. You are in doubt. That was the easy answer. Reality is more complex, of course. First, there's the myth that game programming is ultra super high performance programming and everything has to be as fast as possible. I classify game programming as performance aware programming. The developer must be aware of performance ...


9

Games will not benefit that much by having 4 cores instead of two. Here's why. Basic Game Engine: 1 Thread The problem with graphics API like DirectX and OpenGL is that it must be runned on one thread, and one thread only. So a basic game engine will run all of the logic and render logic into a single thread. These engines will often use a time delta to ...


9

This is a complex question with a lot of small details that really matter, the performance will vary based on platform and application. So you should profile for possible bottlenecks before investing in optimizations. That said, firstly, I assume you should reduce uploads and updates as much as you can, for example use instancing. Secondly, note that GPUs ...


9

Technical stuff During Minecraft's chunk generation a chunk passes several stages before it is done and can be rendered. These stages, in order, are as follows: EMPTY: Just as indicated, the chunk barely exists and is empty. STRUCTURE_STARTS: Here world generation decides whether a chunk might be the origin of a structure, and if so, it also generates the ...


8

Lot of math here for a very simple problem, assume that we have 4 points determined for a rect, top, left, bottom, right... In the case of determining whether 2 rects collide we need only look that all possible extremes that would prevent collisions, if none of these are met, then the 2 rects MUST collide, if you want to include boundary collisions, simply ...


8

Just ignore any actors which are far away from the player(s). Don't update them and don't allow active actors to interact with them. Most games divide the game world into zones, and only update the actors in the zones the player is in and the adjacent zones. Many even despawn the actors and respawn them at their initial positions when the zone becomes ...


8

You can optimize this to be branchless actually, however for seeing if it's faster you always want to profile it: vec4 Overlay(vec4 v1, vec4 v2, vec4 opacity) { bvec4 less = lessThan(v1, vec4(0.5)); vec4 blendHigh = vec4(1.0) - vec4(2.0) * (vec4(1.0) - v1) * (vec4(1.0) - v2); vec4 blendLow = vec4(2.0) * v1 * v2; vec4 blend = mix(blendHigh, ...


8

The real implications in performance here depend 100% on the platform used. Say you have written code as in option 2. When using a statically compiled language such as C++ the compiler will presumable not notice that container.left + offset.x is constant for as long as the object lives and it will not optimize it. When using a language that uses Just-In-...


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