An entity for organizing data in a specific way so it can be used efficiently. Examples are arrays, objects, records, structs.
55
votes
11answers
4k 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 ...
19
votes
3answers
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
4answers
1k 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 ...
16
votes
5answers
3k 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
1answer
828 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:
...
14
votes
5answers
911 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
1k 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 ...
8
votes
3answers
419 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 ...
8
votes
3answers
554 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
6answers
680 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
3answers
3k 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 ...
8
votes
2answers
582 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 ...
8
votes
1answer
378 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 ...
7
votes
4answers
440 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. ...
7
votes
4answers
764 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
3answers
914 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 ...
7
votes
2answers
739 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 ...
7
votes
2answers
210 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
296 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 ...
6
votes
2answers
624 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
199 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 ...
6
votes
2answers
574 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 ...
5
votes
5answers
3k 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 ...
5
votes
3answers
868 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
2answers
632 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 ...
5
votes
3answers
313 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
468 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 ...
5
votes
1answer
288 views
Settlers-like terrain representation
Remember this beauty? I'm playing it now on my old Amiga 1200.
Settlers 1
My question is: How do you think they represented the terrain, data structure wise? Obviously it's some kind of points, with ...
4
votes
2answers
2k 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 ...
4
votes
2answers
998 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
372 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
4answers
209 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
1k views
Collision Detection Structure
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 ...
4
votes
3answers
374 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
352 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
373 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
183 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
2answers
314 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 ...
3
votes
4answers
184 views
Associate a texture to an object (from a data-model, not graphical point of view)
I'm writing a roguelike where objects and floor can be made of different materials. For instance, let's say we can have a wooden chair, an iron chair, a golden chair, and so on.
I've got an Object ...
3
votes
1answer
223 views
Storing game objects with generic object information
In a simple game object class, you might have something like this:
public abstract class GameObject {
protected String name;
// other properties
protected double x, y;
public ...
3
votes
1answer
352 views
Tic-Tac-Toe game AI
I'm looking into creating a simple tic tac toe/noughts and crosses game in Actionscript3 and am trying to understand the ideas behind the AI used in a game like this.
I've seen some simplistic ...
3
votes
1answer
325 views
Better data structure for a game like Bubble Witch
I'm implementing a bubble-witch-like game (http://www.king.com/games/puzzle-games/bubble-witch/), and I was thinking on what's the better way to store the "bubbles" and to work with. I thought of ...
3
votes
1answer
147 views
Storing items in external data files
My project, in its current state, keeps all of the info for each inventory item in script files. That means, inventory items and their properties are part of the codebase. This works well, but I'm ...
3
votes
1answer
531 views
Best practice for organizing/storing character/monster data in an RPG?
Synopsis: Attempting to build a cross-platform RPG app in Adobe Flash Builder and am trying to figure out the best class hierarchy and the best way to store the static data used to build each of the ...
3
votes
1answer
340 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 ...
3
votes
1answer
705 views
Implementing a tile-based game
Which data structure should be best used to store a pile of tiles from which a player can pick a random tile?
3
votes
1answer
441 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 ...
3
votes
1answer
109 views
What data structure to use to implement ocean currents and trade-winds
I'm creating an RPG/simulation game which is similar to the Uncharted Waters Series. The game allows the player to control a fleet to explore and navigate the world on the world map. My Game stores ...
