What's the deal with Deno? We talk with a major contributor to find out. Listen now.
239

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


52

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


49

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


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

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


42

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


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


27

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


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

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

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


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


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

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 every one of ...


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


9

When you have mobile objects and you want to get their draw order, there are two possible approaches how you can preprocess them before drawing: Add a list of objects to each map tile. Iterate all objects and add them to the object list of the tile they are on. When you draw each tile, you first draw the tile itself, then sort its object list, then draw the ...


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

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


9

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


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