Jump to content

  • Log In with Google      Sign In   
  • Create Account


Data structure for DF-like map.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 ObsidianBlk   GDNet+   -  Reputation: 130

Like
0Likes
Like

Posted 28 February 2014 - 08:18 PM

Hello there.

 

For a little bit now I've been coding a game. The basic idea is I want it to have a general Dwarf Fortress aesthetic, set on a starship. Basically, where Dwarf Fortress simulates dwarves within a fortress, I want to simulate a crew aboard a starship.

 

While I've spent most of my time thus far reaquinting myself with C++ (I've been away from it for almost a decade) and getting what I think are the core system elements written (uses SDL2, a nice Handle system based on std::shared/weak pointers, Game State Manager, etc etc)... but now I'm kinda past the preamble and want to get to the actual simulation.

 

Here's the deal... obviously, I'm planning a tile map for the ship interior. Structures such as walls, doors, floors, all included... but I want them to be destructable. I'm also planning that the ship will have full system layouts too... such as power conduits leading from a main reactor and distributing that power across the ship, and I want these overloadable and destructable. If power is lost, components attached further down the grid go dark. Furthermore, the power conduits will have a voltage limit and can "burn out" or even overload leading to explosions, etc. Other similar subsystems like water and waste management systems I'm thinking about as well.

 

What I'm trying to come up with is a decent structure to handle that kind of information without it being overwhelmingly large (for sizable ships) in memory or on the file system. My current idea is to create an entity list which will hold every possible structural item and all of the base values of those items. Then, each tile in the map would be an index into that entity list and a vector/map containing information regarding state change. For instance, if a Wall entity has a base structure value of 5, and is damaged for 2, then the map tile containing that wall will store "structure":3 in it's vector/map. If the wall looses all structure, then I would simply wipe the tile's vector and change the tile index to the "rubble" entity instead. The way I'm thinking, this should keep the size of the map (both in memory and on disc) rather small because only those values that deviate from the baseline would need to be stored. Does this sound reasonable, or am I missing something obvious in my logic?

 

In case someone may ask about how big I plan on making these maps...

I want multiple z-levels (decks) and, while this may be way too ambitious, having a ship with the same interior space as... say... the Enterprise NCC-1701-D ... *cough* ... is sort of a hopeful goal.

 

Oh... yes... and I'd like to allow ship-to-ship combat on a tactical map as well. As one ship damages another, that will lead to the walls taking damage and power overloads, etc, etc. As that effects the crews of the ships, the performance of the ships in the tactical game go down (very directly). Therefore... yeah... eventually I'm hoping the game could support 2+ Enterprise-D sized simulations going at the same time.

 

Any thoughts or suggestions?



Sponsor:

#2 frob   Moderators   -  Reputation: 19841

Like
2Likes
Like

Posted 28 February 2014 - 10:34 PM

Inside the ship you probably want to treat it as individual levels. There is no common data structure for such things, it is a collection of game objects, collision objects, models, meshes, wall segments, or whatever your game engine wants it to be. Each floor or region would likely be a separate level. The size of each level would be constrained by your engine, but other than disk space there is no practical limit on the number of levels you could build.

For outside the ship, the entire ship is a single model or potentially a collection of models with different geometries based on damage or other factors. That is just the shell of a ship and not all the internal details.

You will likely have two different game modes. One is a 2D or platformer or FPS style gameplay for inside the space ship. The other would probably be a 3d flight simulator or EVE style or descent-style gameplay for outside the space ship. (Personally I would love the descent-style where you have six axis freedom to move, but the game-playing public tend to dislike all the freedom...)
Check out my personal indie blog at bryanwagstaff.com.

#3 Paradigm Shifter   Crossbones+   -  Reputation: 5235

Like
0Likes
Like

Posted 01 March 2014 - 02:55 AM

Well you should look at FTL as well... it's simple (unlike DF) but the combat and mechanics are good.


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#4 Waterlimon   Crossbones+   -  Reputation: 2442

Like
0Likes
Like

Posted 01 March 2014 - 03:07 AM

A 3D grid containing common data, with cells being able to point to outside data that doesn't fit in the cells, such as the contents if an inventory. Moving entities might be better off stored separately with only a flag/entity ID in a cell to indicate it contains such a thing.

Apply hierarchical structure for optimization if necessary.

Although DF like maps are shown as 2D levels, the processing is definitely fully 3D so you shouldn't separate different levels too much.

This is mostly a question of what is stored directly in the grid cells and what in eg. a vector pointed to by other stuff, and whether to use a hierarchical data structure or not.

o3o


#5 ObsidianBlk   GDNet+   -  Reputation: 130

Like
0Likes
Like

Posted 01 March 2014 - 09:15 AM

Well you should look at FTL as well... it's simple (unlike DF) but the combat and mechanics are good.

In some ways what I have in mind will be similar, but I'm planning the crew in my game to be more numerous (possibly in the hundreds) and far more autonomous (like the dwarves in Dwarf Fortress). Also, the player will have control (via "Captains Orders") over what the ship is doing in combat (course, target locks, etc)

 

A 3D grid containing common data, with cells being able to point to outside data that doesn't fit in the cells, such as the contents if an inventory. Moving entities might be better off stored separately with only a flag/entity ID in a cell to indicate it contains such a thing.

Apply hierarchical structure for optimization if necessary.

Although DF like maps are shown as 2D levels, the processing is definitely fully 3D so you shouldn't separate different levels too much.

This is mostly a question of what is stored directly in the grid cells and what in eg. a vector pointed to by other stuff, and whether to use a hierarchical data structure or not.

 

Well, here's the thing I wanted to avoid. Obviously walls and floors are relatively simple. They have a structural max, a current structural value, and perhaps some durability and resistance ratings. Other components, such as power conduits, water control systems, etc, would contain more complex data. If I placed a full instance of these entities in every tile that contains an entity, that could lead to a fairly large data file (and memory footprint) for even a lower to mid-range map size. This is why I'm thinking have an entity list containing one instance of each entity with all of their baseline values, and have the map tile store only an index and vector of value differences.

 

As for the map itself, I was thinking a 3D vector data structure.



#6 Waterlimon   Crossbones+   -  Reputation: 2442

Like
0Likes
Like

Posted 02 March 2014 - 04:48 AM

I've thought about this problem of unevenly distributed data complexity for my own 'game' which has tile based environment.

 

Some solutions:

-Try to use unions such that you have some amount of bytes which you interpret differently depending on the type

-If the data complexity of some object is very high, just store it in an external data structure and point to it

-If the data complexity has spatial coherence, have:

*The "basic" grid, containing the common data

*An "overlay" sparse grid (chunked, or quad/octree) which can have chunks existing in places where there are complex cells, and chunks not existing where only simple cells exist. Eg. in an area with only walls, only the basic grid exists, while if you have lets say water simulation needed around some area, the overlay sparse grid can be used to get some extra bytes for storing the water data

*Possibly even a method of choosing between using such an overlay when many complex cells exists in a location, or simply pointing to external storage if its only a single cell or 2 (because the overlay provides extra storage for ALL cells in the area, which is a waste when only few cells actually need extra storage)

 

Basically the optimal solution is to combine multiple methods of storing the data, taking into account the nature of the data (how big is the data, is there spatial coherence, does it benefit from implicit grid arrangement like liquid simulation, access patterns etc.)

 

This, however, can be pretty complex to set up, so i advice you to just dump everything in the simple grid and then start moving data to more specialized external storage as needed.

 

EDIT:

This is a very interesting problem that really requires you to think about different data structures and their properties.

Just to clear it up, you have data that:

1. Is common -> store for every cell that exists (if many cells dont exist, consider using a sparse representation of the map)

2. Is not common but does not take much space -> add an extra data section to common data, which you can use for different arbitrary small extra data

3. Is not common and takes space

3a. Has spatial coherence and/or benefits from spatial partitioning for processing reasons -> store using a sparse grid of some kind that only covers parts of the map (quad/octree, sparse chunk grid, a relocatable grid of some kind (like if the data had the kind of spatial coherence that it always exists within X cells of the player, you could create a grid of some kind that you keep approximately centered on the player))

3b. Is just randomly distributed around the world and benefits from access through the containing cell-> add some indirection (index/pointer in common data?) and store in a vector somewhere, or a hashmap with the world position as a key

3c. Is just randomly distributed around the world and doesnt greatly benefit from access through the containing cell-> store in a vector somewhere along with its position in the world. (this would include players and other moving objects in some cases. In others, you might want to see what a cell contains by looking at the cell, so you would go with 2. or 3b. instead)


Edited by Waterlimon, 02 March 2014 - 05:05 AM.

o3o


#7 ObsidianBlk   GDNet+   -  Reputation: 130

Like
0Likes
Like

Posted 03 March 2014 - 09:28 AM

I've thought about this problem of unevenly distributed data complexity for my own 'game' which has tile based environment.
 
Some solutions:
-Try to use unions such that you have some amount of bytes which you interpret differently depending on the type
-If the data complexity of some object is very high, just store it in an external data structure and point to it
-If the data complexity has spatial coherence, have:
*The "basic" grid, containing the common data
*An "overlay" sparse grid (chunked, or quad/octree) which can have chunks existing in places where there are complex cells, and chunks not existing where only simple cells exist. Eg. in an area with only walls, only the basic grid exists, while if you have lets say water simulation needed around some area, the overlay sparse grid can be used to get some extra bytes for storing the water data
*Possibly even a method of choosing between using such an overlay when many complex cells exists in a location, or simply pointing to external storage if its only a single cell or 2 (because the overlay provides extra storage for ALL cells in the area, which is a waste when only few cells actually need extra storage)
 
Basically the optimal solution is to combine multiple methods of storing the data, taking into account the nature of the data (how big is the data, is there spatial coherence, does it benefit from implicit grid arrangement like liquid simulation, access patterns etc.)
 
This, however, can be pretty complex to set up, so i advice you to just dump everything in the simple grid and then start moving data to more specialized external storage as needed.
 
EDIT:
This is a very interesting problem that really requires you to think about different data structures and their properties.
Just to clear it up, you have data that:
1. Is common -> store for every cell that exists (if many cells dont exist, consider using a sparse representation of the map)
2. Is not common but does not take much space -> add an extra data section to common data, which you can use for different arbitrary small extra data
3. Is not common and takes space
3a. Has spatial coherence and/or benefits from spatial partitioning for processing reasons -> store using a sparse grid of some kind that only covers parts of the map (quad/octree, sparse chunk grid, a relocatable grid of some kind (like if the data had the kind of spatial coherence that it always exists within X cells of the player, you could create a grid of some kind that you keep approximately centered on the player))
3b. Is just randomly distributed around the world and benefits from access through the containing cell-> add some indirection (index/pointer in common data?) and store in a vector somewhere, or a hashmap with the world position as a key
3c. Is just randomly distributed around the world and doesnt greatly benefit from access through the containing cell-> store in a vector somewhere along with its position in the world. (this would include players and other moving objects in some cases. In others, you might want to see what a cell contains by looking at the cell, so you would go with 2. or 3b. instead)


You've given me quite a bit to mull over. Thank you.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS