Skip to main content

Questions tagged [data-structure]

An entity for organizing data in a specific way so it can be used efficiently. Examples are arrays, objects, records, structs.

Filter by
Sorted by
Tagged with
77 votes
11 answers
26k views

How to design a replay system

So how would I design a replay system? You may know it from certain games like Warcraft 3 or Starcraft where you can watch the game again after it has been played already. You end up with a ...
scable's user avatar
  • 821
36 votes
3 answers
6k views

When should I hard-code data versus load external data?

I'm a thousand or so lines of code into making my own 2D space-based game, which creates networks of randomly generated star systems and populates them with a random selection of planets, stations, ...
Singular1ty's user avatar
35 votes
4 answers
16k views

Is there a 3D equivalent of hex tile maps?

Probably the biggest advantage of a hex-based versus square-based map tiling is that the center of each hex has the same distance to all its neighboring hexes. Is there a similar shape that tiles this ...
Hackworth's user avatar
  • 2,823
31 votes
5 answers
7k views

Use an instance or a class for game resources (wood,iron,gold)

So I'm making a game where you can send ships to locations to sell or buy resources like wood, iron, gold, etc. Now I was wondering how the resources should be created in de game. I came up with 2 ...
melledijkstra's user avatar
23 votes
3 answers
4k views

Command Ordering Architecture of Dwarf Fortress

What is the most elegant way to implement a command ordering system for AI? for example in dwarf fortress when you mark a forested area for wood cutting, the dwarfs then would do the following ...
jedt's user avatar
  • 333
23 votes
4 answers
5k views

What data structure should I use for a Diablo/WoW-style talent tree?

I'm considering implementing a talent-tree system for an online RPG, similar to that seen in World of Warcraft, where acquiring a skill unlocks the next "tier" beneath it in the tree. Does anyone ...
Rory Harvey's user avatar
  • 1,422
22 votes
1 answer
37k views

How to edit key-value pairs (like a Dictionary) in Unity's inspector?

I have a spell system I am creating, the principle is as follows: Each spell is an autonomous prefab. It contains a script with some properties (base damage, duration...) that can be modified in the ...
nialna2's user avatar
  • 920
19 votes
4 answers
20k views

Which data structure should be used to represent voxel terrain?

According to the Wikipedia page about voxels, "[...] the position of a voxel is inferred based upon its position relative to other voxels (i.e., its position in the data structure that makes up a ...
anthonyvd's user avatar
  • 1,350
18 votes
2 answers
5k views

What are the pros and cons of these voxel data file formats? [closed]

.VXL .VOX .KVX .KV6 .V3A .V3B I am trying to decide whether it's worth going with any of the above, or some other, or if I should roll my own. The deciding factors in order of importance are: ...
Engineer's user avatar
  • 30k
17 votes
5 answers
13k views

When should vector/list be used?

I can understand when to use lists, but I don't understand when it is better to use vectors than using lists in video games: when it is better to have fast random access ? (And I understand why it's ...
jokoon's user avatar
  • 5,253
15 votes
5 answers
2k views

Why is chunk size often a power of two?

There are many Minecraft clones out there and I am working on my own implementation. A principle of terrain rendering is tiling the whole world in fixed size chunks to reduce the effort of localized ...
danijar's user avatar
  • 5,741
14 votes
2 answers
11k views

Comparing two tree structures

I'm having a hard time trying to describe this in correct terms so I will just give as much detail as possible and hopefully someone knows what I'm trying to do =-) I am trying to compare two node ...
Mungoid's user avatar
  • 1,229
14 votes
4 answers
6k views

How to continuously find all entities within a radius efficiently?

I have a very large number of entities (units). On each step, each unit needs to know the positions of all units near it (distance is less then given constant R). All units move continuously. This is ...
OCyril's user avatar
  • 304
13 votes
3 answers
2k views

Object of arrays or array of objects?

I'm making a management sim game, something along the lines of Roller Coaster Tycoon. I want to know what the best way to structure my world objects is so to maximise performance. Let's say I have 5,...
ali_goes_oosh's user avatar
13 votes
1 answer
6k views

How Do Shapes (Rectangles) Work in Quad Trees?

I've been told that a quad tree is the ideal data structure for my game, but I'm having trouble understanding how exactly shapes work within quad trees. I'm doing this in JavaScript, but I think ...
user2736286's user avatar
12 votes
2 answers
11k views

Quad Tree with a lot of Moving Objects

I have a Quad Tree implementation that is very useful for what I am trying to do. My problem is that when my viewport has a lot of objects, the Update for the Quad Tree takes a very long time. It ...
jgallant's user avatar
  • 8,424
11 votes
5 answers
2k views

Is there a way to make a dynamic world such as a MMORPG horizontally scalable?

Imagine a open-world of 500+ players with data changing as fast as 20 updates/player/second. Last time I worked in a similar MMORPG, it used SQL, so obvioulsy it couldn't query the DB all the time. ...
MaiaVictor's user avatar
  • 1,180
11 votes
3 answers
37k views

How can I implement fast, accurate 2D collision detection?

I'm well aware of how to detect if two or more 2D objects collide but I'm interested in how to decide whether to check for a collision. In previous projects, I just had every object check against ...
Mike Cluck's user avatar
  • 1,274
11 votes
5 answers
2k views

Data Structures for Logic Games / Deduction Rules / Sufficient Set of Clues?

I've been cogitating about developing a logic game similar to Einstein's Puzzle , which would have different sets of clues for every new game replay. What data structures would you use to handle the ...
taserian's user avatar
  • 211
11 votes
1 answer
2k views

How to represent cliff faces in terrain?

I'm trying to figure out the best way to programmatically represent terrain in my game. I've been considering using a heightmap (or grid of evenly spaced vertices) to represent the surface of the ...
Robert Fraser's user avatar
10 votes
2 answers
3k views

Data structures in older games

I'm curious about the data structures used when programming older games like Super Mario Brothers for NES and Super Mario World for SNES. My understanding is that games of this period were written in ...
MrDatabase's user avatar
  • 1,951
10 votes
3 answers
744 views

How to add a sound that an enemy AI can hear?

Given: a 2D top down game Tiles are stored just in a 2D array Every tile has a property - dampen (so bricks might be -50db, air might be -1) From this I want to add it so a sound is generated at ...
Chris's user avatar
  • 516
10 votes
3 answers
8k views

Why can't I get a bool packed and aligned into a D3D constant buffer?

Alright, I'm having a hard time getting a bool packed and aligned into a hlsl constant buffer and I'm not sure why. Here is the buffer in hlsl ...
KlashnikovKid's user avatar
10 votes
3 answers
2k views

Proper way to handle destruction of game entities

Imagine a game world where loads and loads of entities are dynamicly loaded all the time, I would represent that as a list of entities perhaps, but what about removing them? While when adding i ...
Grimshaw's user avatar
  • 3,121
9 votes
2 answers
1k views

In a 2D tile-based game, how should NPCs and tiles reference each other?

I'm making a tile engine for top-down 2D games. Basically the world is composed of a grid of tiles. Now I want to put for instance NPCs that can move on the map. What do you think is best: each ...
lezebulon's user avatar
  • 1,402
9 votes
2 answers
288 views

When should I represent points and sizes as structures?

As part of my simple Ruby 2D game development framework, my game objects have position (x and y values) and size (width and height). ...
Saturn's user avatar
  • 1,771
9 votes
1 answer
5k views

Why are 16×16 pixel tiles so common?

Is there any good reason for tiles (e.g. Minecraft's) to be 16×16? I have a feeling it has something to do with binary because 16 is 10000 in binary, but that ...
Ben Hollier's user avatar
9 votes
1 answer
1k views

Appropriate level representation / data stucture for a 2D platfrom game?

I'm about to program a copy of Mario in Java. I'm thinking on 2 representations/data structures for the levels but I'm not sure which one should I choose: A 2D integer array. A quadtree to divide the ...
Rama's user avatar
  • 193
9 votes
2 answers
2k views

How can I define areas filled with water?

I would like to enhance my little game engine with nice looking water simulation. To start working on that I need to find a proper way to represent water in the game. Unfortunately I don't know much ...
danijar's user avatar
  • 5,741
8 votes
2 answers
4k views

Custom extensible file format for 2d tiled maps

I have implemented much of my game logic right now, but still create my maps with nasty for-loops on-the-fly to be able to work with something. Now I wanted to move on and to do some research on how ...
Christian Ivicevic's user avatar
8 votes
2 answers
1k views

Data Structure (or algorithm) for fast distance-based entity lookups

For example, your game has 100 enemies (on different teams) running around and their AI wants to inspect the nearby entities to see which it should attack. What is a fast way to organize those ...
khayman218's user avatar
8 votes
3 answers
741 views

Should I share the same tile structure for display and pathfinding?

I know how to display a 2D map with tiles. I know how to make a pathfinding algorithm using A*. Those two things demand a structure or a class. My question is : do you use the same structure for ...
Raveline's user avatar
  • 771
8 votes
2 answers
299 views

Determining if player-created structure matches a template in a 3D block-based game

Disclaimer: this is one of those dreaded Minecraft-style questions, but I feel it's more a data structures and algorithms question I'm really new to 3D data structures and am wondering what the best ...
WillP's user avatar
  • 145
8 votes
1 answer
1k views

Component arrays vs. entity structs? [closed]

Two of the main systems I've seen in entity system tutorials are: An Entities class with one array / [hash]map for each component, with indices corresponding to ...
Shien's user avatar
  • 257
8 votes
6 answers
1k views

How can I store all my level data in a single file instead of spread out over many files?

I am currently generating my level data, and saving to disk to ensure that any modifications done to the level are saved. I am storing "chunks" of 2048x2048 pixels into a file. Whenever the player ...
jgallant's user avatar
  • 8,424
8 votes
2 answers
1k views

Where do I store strings? What's an efficient way of loading them?

I'm making a top-down RPG for iPhone. I'm using tilemaps (CCTMXTileMap) and the cocos2d-iphone engine. I've made a class that can handle loading maps and NPCs onto the screen, a class that handles ...
Moshe's user avatar
  • 231
7 votes
6 answers
11k views

Alternative to 2D array in a tiled-map structure

After searching for a long time, I'm surprised this question was not asked yet. In a 2D, tiled-map game, how do you handle the map ? I'd be glad to have your point of view in any languages, though I'm ...
Raveline's user avatar
  • 771
7 votes
4 answers
2k views

How can I improve this enemy database implementation?

I'm developing an RPG and I'm at the point where I need to start building an enemy database. There's a couple challenges associated with this and a few solutions I've been considering. Here's what I ...
user127817's user avatar
  • 1,853
7 votes
1 answer
5k views

How to create a game save file format in c++ using STL

Hey so i just learned about the i/o part of the STL, more specifically fstream. Although I can now save binary info and classes i've made to the hard drive, i am not sure how to define how the info ...
Griffin's user avatar
  • 630
7 votes
1 answer
684 views

Settlers-like terrain representation

Remember this beauty? I'm playing it now on my old Amiga 1200. My question is: How do you think they represented the terrain, data structure wise? Obviously it's some kind of points, with a height. ...
Olle's user avatar
  • 73
7 votes
3 answers
2k views

How should I store dynamic game entities for efficient area-based selection?

In my 2d block-based game I'm trying to implement a data structure that would store entities entities in a way that's capable of: Direct selection based on coordinate. Iteration Iteration limited to ...
DifferentPseudonym's user avatar
6 votes
3 answers
1k views

How to store relations between NPCs?

For an RPG I want to generate a world with lots of NPCs, and the NPCs all have relations to eachother. They can be eachothers parents, children, siblings, friends, bosses, lovers, lieges, vassals, etc....
PaulMag's user avatar
  • 163
6 votes
1 answer
602 views

Managing complicated RPG character data

For a detailed survival RPG, the data that needs to be managed can easily become overwhelming if approached in an ad hoc manner. First, you may want to do away with HP and instead have a system of ...
Geo's user avatar
  • 161
6 votes
2 answers
942 views

How do I simplify terrain with tunnels or overhangs?

I'm attempting to store vertex data in a quadtree with C++, such that far-away vertices can be combined to simplify the object and speed up rendering. This works well with a reasonably flat mesh, but ...
KKlouzal's user avatar
  • 252
5 votes
4 answers
2k views

Do associative array data structures have a place in game development?

Is it a bad idea to use a map data structure (an associative array or dictionary) in game development? According to this flowchart, the ideal container for storing game object's container would ...
user avatar
5 votes
6 answers
2k views

Data structure for random outcome from a hit probability table

The basic idea of a hit-table is carried over from pen & paper role playing games. You roll a die or a number of dice representing your ability to attack an opponent. Your opponents defense is ...
Patrick M's user avatar
  • 298
5 votes
3 answers
3k views

Why aren't linked lists more common data structures for enemies?

I was recently listen to a talk that Jonathan Blow gave, you can find it here. In the talk, he was talking about what data structures he (and he seemed to imply many others) use, and why. Which is ...
Leif Andersen's user avatar
5 votes
2 answers
2k views

a flexible data structure for geometries

What data structure would you use to represent meshes that are to be altered (e.g. adding or removing new faces, vertices and edges), and that have to be "studied" in different ways (e.g. finding all ...
AkiRoss's user avatar
  • 411
5 votes
3 answers
527 views

How can I store information about what cells are connected to others in a 2D array?

I have a 10x11 array in my game. What is the best structure and way to store the connections between the elements of the array? Some info about the connections: they are simple (2 elements are ...
e-MEE's user avatar
  • 165
5 votes
2 answers
535 views

What are the technologies that makes physics engines so good for raycasting?

again. This question is strictly related to this one so, what is the technology that makes physics engines suitable for raycasting? It is a particular data structure? Has it to do with the engine's ...
tunnuz's user avatar
  • 644

1
2 3 4 5
7