Mapping Techniques for (3D) Games? 14
John Kelley asks: "I'm a developer for a new company that is developing a new moderately multiplayer real-time strategy Game and I've been charged with finding a data structure to effiently store map data. Does anyone have any experience with this? I have no clue what kind of data structure would be ideal for this but I'm sure someone does. We plan on having 1024x1024 sized maps and the game is slotted to hold 25 players in a 3D world akin to Age of Empires 2. Keep in mind that there are approximately roughly 256 different buldings, 32 different terrain types, etc..."
Possibly more helpful... (Score:1)
http://www.flipcode.com (good game code site, forums are pretty active)
http://www.gamedev.net (less content IMHO than flipcode, but forums are pretty good)
http://www.gamasutra.com (website run by Game Developer mag)
quadtrees (Score:1)
more concretely what i have is all the vertex data objects stored in an array, and then a quadtree where every node has nine pointers to the nine vertex objects that describe it, and other info such as it's bounding box (even though you can recalculate them every time you need them instead of storing them if you want to save memory at a cost of more computational time), plus some other stuff. during the rendering fase first i reject all the nodes that are not visible to the player (pretty fast, as i said you only need to test for visibilty the bounding box of a higher level node in order to reject all of its child nodes), and then starting with the higher level visible nodes i determine wether they should render themselves or have it's children handle it, depending on how far away it is from the viewer (the more far away a node is from the viewer, the more likely it is that it's enough to render it instead of having to go deeper into the tree and have its children rendered). when rendering a node itself you can also do some vertex simplification depending on it's distance.
i find this quite efficient in computing terms for very large maps, the main problem being of course the huge amount of memory these maps eat
you can find some more info on http://www.gamasutra.com (there's a very nice article on using quadtrees there in a different way as i've described) or http://www.vterrain.org, where they have links to several papers describing different techniques and data structures
Sparse array, maybe? (Score:2)
It looks like you're using a very large tile grid - 1024x1024. Games like Starcraft tend to use much smaller tile sets. In any case, It would seem to me that only a small set of the tiles would have "interesting" stuff on them, the rest can be generic terrain. Think about using a sparse array - where you make space to store the interesting elements, with their coordinates, but the uninteresting stuff doesn't need to use space.
Are you going true 3-D or are you using an isometric 2-D view, like Starcraft? You might want to take a look at the Flight Gear source code - they have some cool algorithms for storing 3-D terrain data if you were going for true 3-D.
Re:What works for us (Score:2)
BTW, what engine are you guys using for the 3D - licensed, free (and/or open source) or homebrew?
Worldcom [worldcom.com] - Generation Duh!
What works for us (Score:1)
The world consists of multiple planes. Planes are disjoint areas.
Each plane consists of multiple layers.
- All planes have a "surface" layer that describes the terrain visuals.
- Almost all planes have an elevation layer of signed shorts. For our 3D client we use 1/20" increments with 0 considered sea level.
- Planes can have any number of additional layers, some of which are kept secret. Planes can be used to model underground minerals, pollution levels, walkability flag, etc.
When rendering tiles, you probably should render the intersections of 4-tiles, rather than independantly rendering each tile. That way you can define border tiles, corner tiles, etc., without building explicit grass-meets-path kind of tiles. Look carefully at the paths on "Oasis Island" in the screenshots sections of http://www.ataleinthedesert.com [ataleinthedesert.com] - they are all made of square tiles, but have a fairly gentle look.
Elevation maps don't compress well, making for long downloads in online games. Make these coarser, and use bezier splines when it's time to render.
To draw 1024x1024 tiles you'll need a LOD algorithm. Take a look at the screenshots with mountains in the distance - notice how they are a bit angular. We use a ROAM-like algorithm (easy to find online), but with geomorphing (again easy to look up).
Hope this gets you started.
Generating game content and maps. (Score:1)
My suggestion would be...
look at random map generation algorithms.
I've found iterated fractal systems to be great inspiration for this sort of thing.
Most of your time will be invested in actually generating the game content (Maps) so why not have the computer do most of the work for you?
Now once you have the algorithm down just save whatever you need to recreate the same results later... most likely random seeds.
So imagine this.. you don't need to store some huge detailed map. Just store a detailed map for whatever is on the screen (or whatever is needed for processing offscreen) and generate the detailed data on the fly from a bunch of non-detailed data. (like random seeds.. or developer chosen hotspots.. whatever)
now for a handy tidbit of advice...
MAKE GOOD EDITORS FOR YOU CONTENT CREATORS.
One of the programmers for a large high profile game once told me this, "The reason all of these games are coming out late is that all the artists are sitting in a dark room tweaking texture coordinates with a text editor"
So whatever you end up doing.. invest most of your time developing the tools to handle the data. Design the data structures so that they can be managed/edited easily. it will pay off a thousand times in the end.
Where's your source? (Score:1)
Check the graphics programming black book (Score:1)
I don't want to spoil the party, but... (Score:1)
Now, if you could make a turn-based First Person Shooter, you'd have a hit.
Re:How about... gasp! An array? (Score:1)
Arrays aren't all they are cracked up to be. The first thing to consider is that every consideration for a relative position involves a calculation: X = X + 1 to look at the tile to the right, for example. The second thing to consider is that the entire array must reside in memory (or you can use nasty caching algorithms).
An alternative is to use an object scenario where each tile is an object (okay, I'm not actually advocating an OBJECT object here, just a discrete instance of a data structure). There are separate fields for left/right/up/down/above/below, to allow for a dynamically sized and shaped, truely 3D map. In effect this is a 6-way linked list. Although your storage overhead is higher (since you store pointers), you can more easily swap pieces of the map into and out of memory.
The bounds checking is precalculated to some extent, in that there is simply no link for absolute boundaries. You can easily do funky stuff link linking the "move right" for one tile to a non-adjacent tile, effectively creating a "teleport" zone, without special logic. A "map within a map" scenario is fairly easy too - a whole lot of tile have their right side (say) linked to the left side of a single tile, so that moving right would "exit" to a larger map (think Wasteland). A few additions to the tile data structure can control the logic in a more fine-grained manner, to apply only to certain units or local/global conditions.
Conditions themselves can be made more modular - a weather condition for example can be represented as a layer linked above the ground level tile.
Units comprise a separate yet linked structure. All units are placed in one huge linked list. This list must be parsed at every tick to account for unit actions. Each unit then forms part of three other doubly-linked lists: the team (side, faction, whatever), group, and map. In other words, the unit will be linked in to the map, above the ground layer (or below, if applicable). Moving the unit will change its linking in the map. Regrouping, defection and all the rest should be obvious.
Under this system, a unit is in fact a tile, but with additional information. That is to say the unit must be compatible with the tile data structure (in object terms a subclass or implementor of the map tile interface).
Twylite
A little research goes a long way (Score:3)
It always amazes me how supposedly qualified and skilled people can ask questions before making any effort to do background research. Not only does it show an inability to solve problems, but also prevents the questioner from supplying all the relevant information.
I asked Google a couple of questions and came up with GameDev.net [gamedev.net] and GameDeveloper.net [gamedeveloper.net], and especially the game design category at dmoz.org [dmoz.org]. Needless to say these link to a wealth of information on the topic.
I could be mistaken, but you seem to be referring to Isometric Mapping, which is a 2D, not a 3D technique. A little Googlification of that keyword should produce more interesting stuff. this [gamedev.net] article discusses formats for a map file, and this [gamedev.net] one considers data structures and memory.
Of course, the most important question is: how are you going to USE the data? Your choice of a data structure must be based on data use, especially in a real-time game where effeciency is important. Memory requirements will become a third factor for consideration.
In general when dealing with isometric maps, you model a flyweight multilayer grid. This means the basic map is broken into a 2D grid of tiles (rectangular or hexagonal), each tile is split into several ordered layers, and the information about each tile is for the most part shared with all other tiles of the same nature (the flyweight design pattern).
The most common question about data structures is whether to use a 3-dimensional array (tile-x, tile-y, layer) or to a 2-dimensional array (tile-x, tile-y) with the tile itself holding an array of layer information.
When working with very few layers, or in a situation where the information in a particular layer must be accessessed in an iterative fashion, the 3-d array tends to be better. For many layers, or a case where the information for a particular layer does not need to be filtered out as a separate grid, a 2-d map with dynamic data structures for the layer information will keep memory requirements down, and follow good design principles (don't keep multiple data structures in sync - split the data into objects).
Good luck ... now go and do your own work before asking more questions.
Twylite
Re:Check the graphics programming black book (Score:1)
While I haven't read the entire book, a scan through its contents pages doesn't reveal anything about storing or handling map data.
By "efficient" I presume you mean "uses little memory". If you have to store only one level in memory at a time, I wouldn't worry too much about it. You can store the map as a raster image - an array of 1024*1024 bytes - and it will occupy only 1Mb. This is not a huge amount for a modern machine. To store data about buildings as well as terrain types, I would use a separate array, as this simplifies access to it.
If your buildings are small compared to the size of the map, and there aren't a huge number of them, you could use a quadtree to store their coordinates. A quadtree is the two-dimensional equivalent of a binary tree, and is a reasonably efficient way of answering the question "What objects exist within this range of coordinates?" Given that a player's location determines what they can see and interact with, you'll need to answer this question a lot. I don't know you'd go about implementing a quadtree, but Google is your friend ;-)
If you're concerned about how much space the raster form of the map will take up on disk (or it has to be downloaded from a server), then just compress it with gzip or a similar algorithm. Most maps of terrain types tend to have large areas of the same value, and so will compress quite well.
Solved this problem before (Score:1)
Re:A little research goes a long way (Score:2)
Often these "Ask Slashdot" questions sound like "do my homework for me"...
Perhaps we could cut out the middle-man if SlashCode simply redirected the text of an Ask Slashdot submission to a Google search.
Not that I think asking questions is bad or anything... it's just this particular question, as you've pointed out, is easily answered with 1 minute of research.
Finally, speaking as one who also works in the games industry, I can add that such a lack of research skills is often looked upon most unfavourably.
Flame on...
Ryan T. Sammartino