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

learn more… | top users | synonyms

59
votes
11answers
7k 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 ...
31
votes
3answers
2k 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, ...
21
votes
4answers
2k 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 ...
19
votes
4answers
1k 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 ...
17
votes
1answer
1k views

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

.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: ...
16
votes
5answers
6k 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 ...
15
votes
5answers
1k 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 ...
11
votes
4answers
2k 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 ...
10
votes
5answers
1k 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 ...
9
votes
4answers
785 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. ...
9
votes
3answers
329 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 ...
9
votes
3answers
489 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 ...
9
votes
3answers
5k 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 ...
9
votes
1answer
697 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 ...
8
votes
2answers
848 views

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

I'm making a tile engine for 2D games (seen from the top). 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 ...
8
votes
3answers
589 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 ...
8
votes
3answers
1k 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 ...
8
votes
2answers
209 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). class MyGameObject attr_accessor :x attr_accessor :y ...
8
votes
6answers
800 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 ...
8
votes
2answers
665 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 ...
7
votes
4answers
841 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 ...
7
votes
2answers
890 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 ...
7
votes
2answers
224 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 ...
7
votes
1answer
1k 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 ...
7
votes
2answers
556 views

How to 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 ...
7
votes
1answer
380 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. ...
6
votes
5answers
4k 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 ...
6
votes
2answers
772 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 ...
6
votes
2answers
1k 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 ...
6
votes
2answers
678 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 ...
6
votes
1answer
543 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 ...
6
votes
1answer
253 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 ...
6
votes
2answers
206 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 ...
5
votes
4answers
799 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 ...
5
votes
6answers
412 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 ...
5
votes
2answers
4k 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 ...
5
votes
3answers
1k 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 ...
5
votes
3answers
345 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 ...
5
votes
1answer
746 views

RPG game engine. Skill application calculations

Short preface I am a part of a small team which is entering game development. We're creating a new RPG setting with custom game system and mechanics based on dice rolls. I'm server-side java ...
4
votes
2answers
284 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 ...
4
votes
2answers
1k views

RPG Monster-Area, Spawn, Loot table Design

I currently struggle with creating the database structure for my RPG. I got so far: tables: area (id) monster (id, area.id, monster.id, hp, attack, defense, name) item (id, some other values) loot ...
4
votes
1answer
413 views

How does Starcraft 2 load its metadata?

Lets say you are playing Starcraft 2 melee map. The game loads the map. Melee maps have the following dependencies: Liberty (Mod) Liberty Multi (Mod) I think the game engine will load the data ...
4
votes
1answer
456 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 ...
4
votes
4answers
403 views

Storing data for a pokemon like game

The game I'm developing is close to Pokemon. How should I store the data? I am currently thinking of text files where I save the map and have a corresponding textfile for the trainers and their teams ...
4
votes
3answers
410 views

Finding closest coordinate of a pre-known set

Let's say I have a large number of conceptual objects of some kind, each of which occupies a pre-known set of points in a Cartesian 3-space. 1) What is the best combination of data structure (for ...
4
votes
1answer
913 views

Need info on creating a tile grid data structure in Java

I'm trying to create a game with a fixed size map (2D Tile array). I suppose I can inherit other tiles from this base Tile, e.g.: a BankTile. Placing and removing tiles is all too easy, but forming ...
4
votes
1answer
540 views

Is using a half-edge mesh structure feasible?

Is it feasible to use half-edge mesh in games instead of vertex-face structure? What comes to my mind is that it could be useful in mesh simplification (dynamic level of detail). But I'm worried it ...
4
votes
1answer
628 views

Most efficient way to handle coordinate maps in Java

I have a rectangular tile-based layout. It's your typical Cartesian system. I would like to have a single class that handles two lookup styles Get me the set of players at position X,Y Get me the ...
4
votes
2answers
358 views

Space-efficient data structures for broad-phase collision detection

As far as I know, these are three types of data structures that can be used for collision detection broadphase: Unsorted arrays: Check every object againist every object - O(n^2) time; O(log n) ...
3
votes
5answers
553 views

Saving data in games?

I'm soon going to make a game for the iPhone as a school project. My idea was to make a TLOZ remake, with Tiled Maps. However, I'm not quite sure how save the data. In TLOZ you have a lot of ...