How many types?!
Blitz3D Forums/Blitz3D Programming/How many types?!
| ||
| I've just started constructing the world map for my trading game, Merchantman. I want a lot of detail in it (including rivers of varying navigability) so the map image is pretty big (2355x1200 pixels). The plan is to build the map in Photoshop using various colours for terrain types and then read it into an editor to convert the BMP to a huge array of Types (each pixel will form one map square, data for which is stored in a type), allow a few other pieces of data to be added to each square and then save it as a game file. Each type in the array will hold 5 integers and two 2-character strings, ideally with 5 other integers to cover events that effect map regions. Before I go too far down this path does anyone know if an array of 2.8 million types is feasible? I can shrink the map if I have to but I'd rather not if I don't. 2.8 million is a lot though... Anyone got any helpful thoughts? |
| ||
| Well, let's figure it out. Each integer takes up 4 bytes, and let's assume 15 bytes for each string. Also, I'm not sure what overhead there is for the Type structure itself, but let's just say 3 integers each (self, previous, next). So... 2355 * 1200 * (5*4 + 2*15 + 5*4 + 3*4) = 220428000 bytes = 210 MB = Yikes! That is a lot of many required for ONLY the types! It's approximate, but at least it tells you that it's probably not feasible for what you want to do. That's probably not the answer you were looking for, but I hope it helps. |
| ||
| Thanks for that soja, it's exactly the kind of answer I was looking for. It occurs to me that a lot of the integer values I'll be storing don't need to be 32 bit, most really only need 8 or 4 bits so I should be able to get more than one piece of data in a single Blitz integer and mask off what I don't need when I come to extract what I do need. I can also get away with using 8 bit integers instead of those 2 strings. This should keep RAM per map square down by getting rid of a good bit of redundancy. Also, as about 65-70% of the map is open sea and requires no supporting data there's a massive saving to be made there, although I can't see a way of doing that with an array of types. Time to look into using a Bank instead I think. How short are the numbers that PokeShort pokes? |
| ||
| Whoa that's a lot of memory you are using there, is there any way you can buffer the data? e.g. I would suggest some method of area subdivision to lessen the load. XXX XOX XXX O is the current "cell" which is the size of the viewable area of the map, and you only keep in memory the surrounding 8 "cell", so if from my little ascii map the player moves north to stand on the top center tile then as he walks onto it you load the row above and discard the bottom row (below the O on the map) I realise loading while playing slows the game down but if you have such a massive level then I don't think you have much choice. Alternatively don't use types, if you know the data structure then what I suggest you do is you precompile your map data into a form of byte code and then compress it using some form of table compression, this is a technically more advanced solution but its the same way compilers compress their symbol tables, the idea is that many places on the map are going to be pretty much the same and so you replace said type with a single int that represents the type to fetch from a lookup table. Hope these ideas are useful - Luke PS if I am wrong anybody please let me know... |
| ||
| Yes, it would be good to "compact" the data as much as possible (i.e. storing bits instead of integers, if you can, etc). You can use bitwise operators like Shl, Shr, And, Or, etc to help with this. This may help: Byte = 1 Short = 2 Int = 4 Float = 4 String = var Type = size of contents + ? overhead Bank = size of bank + ? overhead Also, Luke has a good idea about only necessarily needing one Type of the same terrain. Instead of having one Type containing coords AND terrain data, you could have two separate types. One with coords (though I'm not sure why you would use Types here), and another set with terrain data. That way you wouldn't have to duplicate the terrain data at all (especially for all that water). What would probably make more sense than using types is something like this: Dim Map%(2355,1200) and then in each array cell you could store a Type reference: Map(0,0) = Water.Terrain etc ...though it would still require about 11 MB just for the array, which may be a lot, depending. But the good part about that is that if you might only need 100 terrain types instead of 2.8 million. (Note that there are more ways to optimize, but I'm just trying to offer clues as to what direction you MAY wish to go.) |
| ||
| Thats essentially how table compression works you have an array of indecies and a lookup table of data corresponding to those indecies. Precisely what I was suggesting although I didnt use code to explain it.. that way you dont need to use types you jsut need to know how the data is stored in a memory bank Ok you have the overhead of the table lookup but you have a massive improvement in memory usage. Thats the compromise, the trick now is to work out the best balance. - Luke |
| ||
| I've been plinking out a few ideas this afternoon and it's all starting to come together. I'm looking at compressing all the map-square properties as I was saying before, then storing them in a bank and using a reference array (2355x1200) to store the bank addresses for the contents of each square. As the editor builds the map file for the game it'll store all identical map squares (same terrain types, elevations, mineral deposits, owning nation etc) at the same bank address. There'll still probably be a few thousand combinations of data but, as you both say, that's considerably better than storing nearly 3 million separate squares. Merchantman isn't going to be a particularly fast-paced game so as long as it doesn't take too much noticable time to query a map square I think the time overheads on the lookups will be OK. Thanks a lot for the input guys, it's very helpful. I'll let you know how it works out. |
| ||
| How about generating map cells using some deterministic algorithm, and then only storing a map value if for some reason it is "different" than what is generated algorithmicly. For example, if you have large empty continents, with certain locations of interest, why bother storing all those empty spaces... Just generate it algorithmicly on the fly. Also, does every cell need all kinds of individual information??? I mean, couldn't you have a generic "desert" cell, or a generic "swamp" cell, or something like that... and only use specific individualized cells for critical areas? |
| ||
| Merchantman is going to be a trading/exploration game set against the sweep of 19th Century history, so the map has to be a reasonably accurate depiction of the world at the time, both in terms of commercial opportunity and the geo-political dynamics of the time. Consequently I need quite a bit of base data in each map square and it has to be placed according to how it was. The player will be able to explore the world and build settlements and plantations/mines/farms/ranches anywhere they want based on commercial and political viability. When a settlement is built, a load of extra data will be extrapolated on the fly from map square data. French-owned copper-rich mountainous desert squares which may fall to Bedouin tribesmen in 1839 aren't exactly generic but however many there are they'll all be stored in the same 10-12 bytes, which'll make them about as generic as they can be. The same goes for the vast jungles of South America, the remote mountain regions of the Himalayas and the huge arboreal forests of Northern Europe, Canada and Russia. By 'compiling' the map into a table compressed file/bank all combinations of cell data will become generic. It's a massive project but if approached right there's no reason why it shouldn't be doable and manageable. I've already got a lot of the main systems coded including a tight and flexible economic system and a system to determine NPC behaviour and more design notes and pseudocode than you can shake a stick at. The map has been a sticking point for a while. Hopefully this answers your questions Rex, and maybe work up a bit of interest among people who like Merchant Prince/Machiavelli and Civ type games. |
| ||
| You should consider using a quadtree. It recursively stores patches until a patch is homogenous. This is good if you have neighbouring areas that are identical. The quadtree stores detailed areas to the highest level of detail while storing homogenous areas at a lower resolution. yinch'03 |
   |