Slashdot Mirror
Mapping Techniques for (3D) Games?
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..."
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.
Meldroc, Waster of Electrons
Interesting - combining tile based games with a 3D engine to render the map. At one time I was pretty heavy into game coding, then I stopped - hopefully one day I will try my hand at it again.
BTW, what engine are you guys using for the 3D - licensed, free (and/or open source) or homebrew?
Worldcom - Generation Duh!
Reason is the Path to God - Anon
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 and GameDeveloper.net, and especially the game design category at 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 article discusses formats for a map file, and this 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
i-name =twylite [http://public.xdi.org/=twylite], see idcommons.net