Tag Info

Hot answers tagged

58

Yes. You should implement a system to load content outside your main engine. Headers for succinct answers. No. It does not consume too much time. I think the question of whether it is a valid allocation of your limited time is moot; even if only for the fact that it will be a small portion of total project time. You will spend hundreds (thousands) of ...


28

This excellent article covers a lot of the issues: http://www.gamasutra.com/view/feature/2029/developing_your_own_replay_system.php A few things that the article mentions and does well: your game has to be deterministic. it records the initial state of the game systems on the first frame, and only the player input during gameplay. quantize inputs to lower ...


27

This would depend on the game and the indexing structure used for the chunks. Though, at such a high level, it's not too likely it has much to do with memory or a specific performance enhancement. More than likely it's an arbitrary decision for sizing chunks in a predictable way. It allows for some counting and indexing tricks using bit shifting that ...


26

My rule of thumb, and I'm sure there will be debate on this, is to never use lists (unless you need to very, very frequently remove things from the middle of large lists). The speed you'll gain by having all your elements in your container in contiguous memory (and therefore more cache-friendly) is worth the offset of the additional costs of ...


17

Besides the "make sure the keystrokes are replayable" solution, which can be surprisingly difficult, you could just record the entire game state on every frame. With a little clever compression you can squeeze it down significantly. This is how Braid handles its time-rewinding code and it works pretty well. Since you'll need checkpointing anyway for ...


16

Google and Wikipedia tag team to the rescue: Tessellation and, more specific for 3D, Honeycomb is the term to look for. Cubes are indeed the only regular (all faces are congruent) AND space-filling (no gaps left as with sphere packing) polyhedra in 3D space. But they have the same problem as 2D squares - widely varying distances to its neighbors. A ...


15

First, multiplying by powers of two is much cheaper than multiplying by an arbitrary number, since you can do it by bit shifting. Most of the time the compiler can do this for you, so whenever you write "* 16" in your code, the compiler actually does a shift by four, and you don't need to worry about it - you just need to give the compiler the opportunity by ...


15

Test case of 500 players all communicating, that's 250K streams of information flying around at 20Hz. The internal bandwidth for that would be, assuming 100 bytes each message, about 500MB/sec. Sounds ambitious. Especially between processes. If you segregate players to groups of 100, that lowers to 20MB/sec, and so on. Which is why MMOs have zones, and ...


14

The common terminology is "structure of arrays" (SOA) and "array of structures" (AOS) which come from C and is most often seen in terms of SIMD work. Typically, the AOS approach is faster, if used appropriately, but SOA tends to be easier to work with (and hence optimizes for the more important quality - development time). SOA, especially in Java, means ...


13

Use one of the common space partitioning algorithms, such as a Quadtree, Octree, BSP tree, or even a simple Grid System. Each has their own pros and cons for each specific scenario. You may read more about them in these books. Generally (or so I've heard, I'm not too familiar with the reasoning behind this) a Quadtree or Octree is better fit for outdoor ...


13

Are associative arrays a good idea for games? Perhaps, depending on your needs. However, you need to differentiate between comments about "associative arrays" and specifically about the class std::map. Associative Arrays Associative arrays are just some kind of data structure that allows you to associate one kind of value with another, such that you can ...


12

I see no need for the complexity of a fully relational database. Relational databases exist to make complex searching operations easy, as well as handle searching over vast datasets. If all you're doing in-game is indexing one of these every time an enemy spawns, you are using an incredibly overcomplicated tool to do so. In short, SQLite is overkill. At ...


12

How are you moving Quad Tree objects? The simplest (and slowest) method is to remove the object and re-insert it. The open-source XNA Quad Tree me and a friend made does a little bit of logic when an object moves: If the object is still inside the same quad if the object fits into a child quad Add to child Else move the object to the ...


11

Even in the 16-bit days, game consoles were basically just small, embedded computers running realtime software, and the data structures we used are the same ones you'd find anywhere in computer science: arrays, matrices, heaps, trees. Not many linked lists because they're so slow (indirect lookups have a long latency). The difference is that before the STL, ...


11

First. Lets write what do we know about each voxel : voxel = (x, y, z, color) // or some other information General storage General way is simply this: set of voxels = set of (x,y,z, color) Note, that triplet (x,y,z) identify each voxel uniquely, since voxel is point in space and there is no way two points occupy one place (I believe we are talking ...


11

Why not both? There are times when you'll want to look to see if there's any NPC on a specific tile (such as for collision detection, as you mentioned), and other times when you'll want to iterate over all the NPCs in the world (such as for running their AI methods every frame). A pointer per tile is not that much memory unless you're working on a ...


10

Use a structure like this to represent a tree in a database: #Talent id parent description 1 0 Tackle 2 1 Kick 3 1 Punch 4 3 Fire Punch And another table to represent acquired talents per user #UserTalent id user talent 1 4 1 2 4 3 3 4 4 You can check for talent dependencies programatically by ...


10

Here are your conditions: Other objects may still be dependant on your removed entity, after it is removed. You want only the entity to specify it's own removal. You can't have both. Why? Because code at a higher level than your entity itself (see examples below) decides when that entity needs to be used. Consequently, only code at that same level can ...


9

One thing I've done for an RPG style map - that is, houses you can enter, dungeons, etc is have 4 main structures: a Map, an Area, a Zone, and a Tile. A Tile is obviously a tile. A Zone, or a chunk, or whatever, is an area of X by Y tiles. This has a 2D array. An Area is a collection of Zones. Each Area can have different Zone sizes - the overworld may use ...


9

try using boost serialize! other than that what you are asking for is how to implement serialization and that's a real complicated thing! I've recently implemented an implementation for serialization and it's no easy case to talk about. there is also another way to only save one class into file which contains all the information you need, which makes ...


9

My answer to this question would be the same as my answer to this other question: When should vector/list be used? Basically, cache-coherency-related performance gains from having everything be contiguous in memory is more valuable than "Big O" algorithm theoretical performance from linked lists.


9

To be honest, I'd take the simple solution. Make a matrix that defines the structure. Whenever a block is changed, attempt to apply that matrix to all locations that might have created the new structure. That's going to be width*depth*height locations, since the player could have finished any point on the structure, but it shouldn't be too bad because most ...


9

I don't think a path finder is necessary, just ray cast to each AI in the area, if there's a wall in the way, they don't hear it. This would work best with some sort of scene graph + spacial partitioning


9

The real answer is just this: On a binary computer, powers of two are nice round numbers. When a normal person needs to pick an arbitrary number for some purpose, they typically choose nice round numbers in the number system they're comfortable with, base 10. So they'll pick 10, 100, 1000, etc. Because they're simple and easy and don't require much ...


9

This is a good question and the best answer I can give is that only experience can really tell you when it's a good idea to take the path that is more difficult/time-consuming. If anyone tells you you should ALWAYS do it the 'proper' way, then they are simply wrong. You already understand that it is a tradoff. On one hand, hardcoding is so tempting because ...


8

Use a list when iterator invalidation caused by modifying the middle of your data structure is going to cause a problem, or you need to keep your elements sorted so the swap and pop trick for quick middle collection deletes won't work and you have a large number of mid collection deletes. You may also want to consider using a Deque. It has similar ...


8

If your argument against an array is "The world will be huge", then it's not about the data-structure, but rather about memory constraints. If your world is so large, that it doesn't fit into memory with a 2D array, then it won't fit into any other data-structure. Instead you would have to implement a (file-)format, that allows loading chunks (or sectors) ...


8

What you are looking for is Rooted Tree Isomorphism, which is a specialised version of the Graph Isomorphism, except for trees and the root node is fixed. The explanation given in this assignment uses two properties: Have the same number of levels (distance between root and leaf nodes) Each level has the same number of nodes Using these two properties, ...



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