• Advertisement
Sign in to follow this  

Creating a province style map (like in games like Risk, Hearts of Iron etc)

This topic is 3577 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to achieve a map as described in the topic. For someone not familiar with Hearts of Iron e.g here a screen to make clear what looks and functionality I am trying to achieve roughly. http://www.gamershell.com/static/screenshots/9219/198922_full.jpg Since I am not very experienced in 2d (or any) graphics programming I am not sure about the best approach to this problem. I'm going to describe what I am so far thinking of as a good approach to this, and I'd like you to comment on it, and tell me what's good or bad about it or how it could be done in a better way. First of all the map is split into provinces as can be seen. So in some sort of editor I'd have to be able to draw the map and specify what province is where, or what pixel belongs to what province. I was going to create a big bitmap of the entire world, using colors to draw each province. It would be easiest to simply use the 32bit color value as province ID but since it is very hard to optically see a difference between color value ARGB(hex) FF000000 and FF000001 I'd probably go for a little more obvious colors, since one would only need a few thousand provinces anyway and not the entire 32bit range for ids. So each province would be colored in a special color, that I might put into some lookup table to be able to link color to province ID. This big bitmap would be loaded into the game and stored in memory. If the player now clicks on the map, I would just look up the pixel coordinates he clicked at and look up the color in my map, and then can immediately look up the province id in my table to find out what province the player clicked at without the need for bounding boxes or other province organisation. For drawing the map I'd want to keep two additional bitmaps of the same size in memory. One would be the color map. I'd basically copy the original ID map and replace every ID-color with the real color the province should be rendered with. This copying and replacing would be done every time an even in the game changes lets say the owner of a province or something else, depending on what display mode is used at the moments. Hearts of Iron e.g. can colorize the map either in a political mode, coloring each province in the color of the country that owns it, or in a terrain mode, using a different color depending on what terrain the province has (forest, hills, mountains, plains, desert), or region mode, coloring the map so one sees which provinces belong to a certain region, like southern europe, middle east, scandinavia etc. This color map would then by multiplied by a lightmap (same size but grey scale) to give the map a little more looks, make the edges of the provinces distinct and display written names for each province on the map. On top of everything one could then render maybe an overlay map for rivers and other stuff and finally the unit sprites etc. Now.. may concern here is.. is this feasable and is this a good approach. First of all, a map like this would probably be somewhat like the HoI map, which is 18944x7296 pixels. Then I'd constantly store up to 4 of those maps in memory..the id map, the current color map, the lightmap and the overlay map. Is this too much memory wise or can a game engine handle this? Also, every time the colors in the color map change, I'd need to copy and replace, then multiply by the lightmap again.. would this be feasable and fast enough? I'm open for suggestion and comments on this. As I said, I'm no very experienced in graphics programming, so I'd be happy to get some input if my approach is total crap or if it can be done that way. If I didn't make myself clear at some point, please ask. I'll try to clearify things then. [Edited by - KeldorKatarn on April 2, 2008 9:42:15 AM]

Share this post


Link to post
Share on other sites
Advertisement
A 32 bit 18944 * 7296 uncompressed bitmap will weigh in at more than 500 megs... So it might be a good idea to use compressed formats instead. Also see if just 256 colors works for you. The game itself can be in 32 bit color, but the map would probably fare better at just 8 bits.

Cut up your large maps into square tiles, so you can allocate and deallocate them as the user scrolls. That way, you'll only have to load and handle (screen size X + 1 tile) x (screen size Y + 1 tile) tiles at any given time -- your maps can be of infinite size without much impact on memory. I recommend that you write a simple command line program that'll cut up the maps for you, so you can always work with your huge map directly and only the program will be working with "chunks".

I think perhaps the best approach for what you're trying to do is to have each province as a sprite, a bit like puzzle pieces that you lay on your map; it'll make it very easy to manipulate them individually.

You'll have to spend a lot of time cutting them up though!

The id mask idea is good... You could even use it to extract the provinces into sprites so you don't have to cut things up manually... But the issue you mentioned with similar-looking colors will be a problem. You might end up having to write a map editor. If you do that, you only have to worry about adjascent provinces being different colors. Then in your editor, you can implement something like a magic wand tool that allows you to select each province by clicking anywhere in one. I'm imagining a functionality where you basically highlight a province with your magic wand tool, click a "create province" button and can enter things like names and stats. Then when you save, the program saves a large bitmap mask with proper IDs for each region as well as a data file with the information you entered for each ID (the lookup table you mentioned). (to implement a magic wand tool, look up how to make a floodfill tool for a paint program)

Writing tools can be a pain, but it could be a good investment both to make your life easier when creating the game and to encourage contributors to create new maps in the future.

Share this post


Link to post
Share on other sites
Well, the final displayed map will be 32bit anyway so I'll have at least one full size 32bit surface all the time. It is true that I could split it up into chunks, but.. wouldn't that mean that I have to colorize those chunks nearly every frame?
I mean I can hardly colorize the chunks and save them on the harddisk every time, I'd have to load the id map from the harddisk (or the respektive tile) and colorize it before displaying it. That is a little much for each frame isn't it? i mean the user will scroll a lot, he will zoom in and out a lot, so the loading of the tiles will happen a lot, and everytime I load a tile I need to colorize it depending on what view the user has currently selected.

256 colors is not enough since I'll have thousands of provinces, so I need as many ID colors to make them distinct, so 16bit is a minimum.

The lightmap will probably work with just 256 grey scale values though.

Still.. cutting this up into tiles.. won't that force a lot (and I mean a lot) of allocations and hard drive loading.. won't that slow things down a lot? I know that keeping one huge 32bit surface in memory isn't exactly the most ressource saving solution either, but constantly reloading tiles and coloring them...
that doesn't sound very optimal either...

The idea with the sprites.. I don't know.. remember I don't have final color values.. I have basically just a picture in which every color represents a province ID (what the magic wand tool is needed for I don't know.. if I click on a pixel I know by the color which province is selected and can mark it by a color replace since only that province is of that color, I don't need any fill algorithm for that).
Cutting everything up into sprites is very strange especially since every sprite would need to be dynamically recolored, would need a bounding box and everything. Remember the final color is multiplied with the lightmap before anything is displayed. I think doing that with a single surface is a little easier than with thousands of different sprites that don't even have the same sizes.

So this brings me back to my original idea, including your suggestion to cut the map up into smaller tiles.
Question about that.. how will the many allocations and colorizations affect this..
I mean I will only have to colorize the huge map whenever either a province color changes, or the user switches to a different display mode. With tiles however I'll have to recolor those everytime they're loaded... and loading is a hard drive operation, which is a lot slower than working in system memory (as long as the memory isn't extended to hard drive of course)

About the color difference.. the ID difference is really not a problem, the only thing is that more distinct colors should be used for adjacent provinces, but that is not really a problem for the game, more for a possible map editor, which would be used only for assigning province stats, I guess the real map would be easier to draw in an actual graphics program like photoshop of something, especially since all the layers, color, lightmap, overlay can be displayed in one picture there, enabling the editor to really get a picture of the map before splitting it up into the respective files.
Recreating a graphics editing program as a map editing tool when existing tools can do that just as well would be a bit of an overkill I think.



So back to the original problem. I have a three pictures, basically huge bitmaps (compressed maybe as long as the compression algorithm is loss-free, meaning the exact pixel color remains intact).
One that looks like the final map but with strange colors, which really are no colors but province IDs, one greyscale light map which will be multiplied to the colored map, and an overlay containing rivers or whatever other stuff should be rendered on top of the map, besides the units.

Now how do I efficiently store, load, colorize and display all this.

The tile approach is probably good, but how will that affect speed?

Share this post


Link to post
Share on other sites
You may want to take a lower-overhead approach to this, and try either component graphics or vector graphics, instead of massive bitmaps.

Instead of one monstrous map stored to disk, have the output of your map editor be a "world set" of region data (id#, name, list of neighbours by id#, and world location of "southwest"-most point) and a set of either greyscale bitmap or vector graphics, named by their according region id#.

At runtime, if you are using greyscale bitmaps (good for if you have only a couple zoom settings; create your bitmaps for the highest detail zoom available), then you can keep its "pristine" copy and a colourized copy, or you can leverage your graphics library for a coloured blit (DirectX, OpenGL do this with no performance penalty these days). This way you can also have some details in the graphic, like mountains or softened edges and such. Remember to reserve a transparent colour (also cost-free in DirectX, OpenGL) for the part of these bitmaps that aren't the region they represent. To test click-hit, scan each region whose rectangle overlaps the mouse cursor, and find one that is not transparent at the pixel clicked on.

At runtime, if you are using vector graphics, you can do all sorts of things, depending on how complex you want your regions to be. "Vector graphics" here means anything from a basic polygon (triangulate it and render directly in the colour of your choice), to full SVG graphics whith objects holding a certain tag or property will be set to the region colour desired when rendering. To test click-hit, it'll depend on the vector graphic format, but it is basically a point-in-arbitrary-polygon test; very cheap.

As far as your performance concerns, regarding keeping thousands of small "sprites" in memory, and then drawing them to screen... you're worrying over nothing. You can keep thousands of small sprites or tiles in memory without any trouble; assuming each region is on average an 80x80 greyscale bitmap, coloured at blit, and you want to use no more than 32 MB of graphics memory, you've got room for 5000 regions, or about 5600x5600 pixels of regions at a time. You probably only need 1024x1024 pixels of map at a time, so consider your minimum normal load to be 163 regions, weighing in at almost exactly one megabyte of graphics memory.

If, however, you want to use one massive bitmap of 19000x7300, you need to load it all in, keep it all in, and it'll take up 132 MB per 8-bit channel you want to include. It'll take two channels (16 bits) for region IDs, another for a lightmap, another for a palette-based details map, and you'd have to colourize and composite the map as you draw it per-pixel to screen, leading to a very large CPU overhead on every redraw.

Share this post


Link to post
Share on other sites
Vector graphics are out of the questions, since the provinces are too complex and have written text in them. Vectorizing all that is not a good idea and colorizing it with gradients and stuff is also not something that sounds too easy.

The small sprite per province approach sounds interesting though.


What you described with the massive map is basically what the Hearts of Iron engine does. It has the entire map stored with IDs, lightmap data and other stuff, somehow it adds quadtree information to all that. Then it has a separate file for bounding boxes and again a separate bitmap with overlay data.
The only difference there is that the game organsizes the data in those huge file in 32x32 pixel chunks. How that is finally rendered I have no idea.
It also has 3 separate map files for the 3 separate zoom levels.


For your approach, I'd also have to create some kind of bounding area hierarchy, to check what province the clicked pixel is on. And that hierarchy can hardly be created from a bunch of sprites so this would have to be created and stored by the map editor too wouldn't it?
But if the clicking identification is solved this way, then why use the entire province id color code approach at all?
If the graphical representation of a province is given by a sprite containing just that province and transparence, and the location of the province given by its bounding area, then the entire province ID approach loses its sense.

What I don't like about the sprite approach is that I will store a lot more information on disk than when either storing one huge map or several equally sized chunks of it, since I will store a lot of extra transparent pixels for each province and the shape of several provinces will most likely result in quite a few sprites with more transparency than color.

With both solutions I see problems with the colorization.. how do I colorize them? If I use chunks I need the id again to identify which pixel to colorize with what color, and I need to multiply it afterwards with the lightmap.

If I use province sprites in greyscale, how I prevent the transparent area from being multiplied.. I could use the alpha channel for transparency of course, instead of a color key, that would solve that problem.

The overlay would have to be done completely different though and that's the problem I see with this sprite based approach.. the overlays are not just in a province.. rivers should only flow between two provinces and other stuff might also be not province based. So the overlay layer cannot be organized in the same sprites but would either have to be one huge map or split up into equally sized chunks again, which is radically different from what is done with the sprites and requires two different approaches for those two layers, while only one would be needed if I take the chunk approach for both, which in turn makes colorizing and slecting the provinces harder again.

So what do you think, what should I go for? (vectorized is out of the question, not practicable for this, neither is it needed since there will be only 3-4 zoom levels which are distinct and not flowing)

Share this post


Link to post
Share on other sites
Another thing.. I am not so worried about keeping thousands of sprites in memory as I am worried about continuously reloading and allocating them from the harddrive. That I consider a lot more of a performance problem than anything that has to do with the CPU..

Share this post


Link to post
Share on other sites
I would recommend against each province being its own sprite. Because they are irregularly shaped, there will be a lot of wasted space that is simply transparent, which will lead to even greater memory use. Of course, you could then devise an algorithm to only load what's visible, but the complexity is unnecessary.

Here is what I'd do.

Break the map down into sub-sections of a given width and height. Powers of two will be best, since graphics hardware works best with those dimensions. Repeat this technique for each map type -- geography, political, ID, overlays, etc. This will allow you to page in only the sections which are visible on the screen, and to cache near-by but off-screen sections as an optimization.

We use the ID map in order to select a specific province via mouse-click. As you described, the ID map is simply a bitmap where each pixel is an integer ID corresponding to a specific province. You can possibly get away with 8 or 16 bit images for the ID map (giving 256 and 65536 potential provinces respectively). I suggest that you reserve value 0 for the borders between provinces, and that borders do not "belong" to any province which they touch, in other words, you must click inside the province to register.

Rather than worrying about creating this bitmap by hand, I suggest instead that you write a tool to do this tedious task for you. This tool is very simple, and it takes in two things: 1) an image with only the borders drawn in black (color 0) and all else pure white (color 255 or 65535), and 2) a list of provinces and the coordinates of their centers. This tool produces a copy of the image and uses a simple flood-fill algorithm to assign an ID number to each province using the supplied coordinates as its locus, border pixels remain unfilled. You may make it so that multiple coordinates can be defined for each province to support, for example, a chain of islands to be a single province. You may choose to assign ID number sequentially, or define them as part of the province input file, which places some burden on you to assign them uniquely, but might make for more stable ID numbers if the map changes frequently.

We use the political map to display which faction has influence over a particular province. For this, you can use a map similar to the one used in the ID tool. Choose some color for border pixels (something that contrasts well with faction colors) and some color for provinces which are not yet under the influence of any faction. As a province comes under the influence of a faction, flood-fill the province in the color of that faction. With this image, you have several options on how it is displayed. You could do a color-keyed transparency, where uninfluenced provinces are not colored, showing the geography layer through, and provinces under influence display only the faction's color; you could also do alpha-blending, where uninfluenced provinces are darkened (for example), and influenced provinces' geography is blended with the color of their respective faction... or you could write a small pixel shader which blends influenced provinces, but doesn't changed uninfluenced ones at all.

Now, if you page in sections of the map, you'll need to keep a database of who has influence over what in order to re-generate it when it is paged away and back (such as when you scroll to the other side of the map and back), and you'll also need to support multiple shading locuses for things like islands (as before) or provinces which span 2 or more map sections (which is new).

Finally, the overlay is just that, a simple overlay image. Personally, I'd draw it last, over top of the optional political overlay, but you could draw it beneath -- just be aware that if you draw it beneath the political overlay, then it will also be shaded (or occluded, in the case of color-keyed transparency, which is why I would draw it last). In the case of color-blended political display, the choice is a matter of taste.

Share this post


Link to post
Share on other sites
Quote:
Original post by KeldorKatarn
For your approach, I'd also have to create some kind of bounding area hierarchy, to check what province the clicked pixel is on. And that hierarchy can hardly be created from a bunch of sprites so this would have to be created and stored by the map editor too wouldn't it?
But if the clicking identification is solved this way, then why use the entire province id color code approach at all?
If the graphical representation of a province is given by a sprite containing just that province and transparence, and the location of the province given by its bounding area, then the entire province ID approach loses its sense.


Correct. That's actually the point of it; there are no color-ID'd provinces. You can use a 1-bit-per-pixel bitmap, or a 8-bit greyscale map, whatever you want; the province ID is determined by its entry in the world data, not by colour. Further, you can colour it whatever you want, for any view you want; you don't need separate copies of it for each possible colour.

As far as detecting hits, you aren't looking for IDs when polling sprites; you're polling sprites for whether that province's sprite has a filled pixel at the clicked location or not. If it does, then that province is the one clicked. As far as the bounding area heirarchy, it is generatable at runtime using just knowing the positions and sizes of the sprites; you don't need to even load the sprites' graphics to build this structure.

Quote:
What I don't like about the sprite approach is that I will store a lot more information on disk than when either storing one huge map or several equally sized chunks of it, since I will store a lot of extra transparent pixels for each province and the shape of several provinces will most likely result in quite a few sprites with more transparency than color.


False. Run the arithmetic, if you like; using the number of 530 MB (four 8-bit channels at 19000x7300 pixels), which will be very incompressible, and which does not get any smaller when broken into blocks. This is 530 MB which must be kept in memory, and which must be read from disk to display the entire map. You may dispute this number with different assumptions if you like, but there's where it stands for now.

Now, let's say every province uses a monochrome bitmap to define its region (same graphical detail as your 16-bit province ID gives you), and that there are 3000 provinces with an average surface area, including "useless" transparent region to make each province sprite rectangular, of 40,000 pixels (200x200 pixels) at closest zoom. This is, uncompressed, 5 kB per province, giving 14.3 MB for the total province graphics data. Islands and other segmented areas count as their entire rectangular area, including the ocean around, and are included in that average above. Oceans, which include no provinces, consume effectively 0 bytes (aside from the border zone around island chains).

Next, we need the stitching data. Using a binary format, we need a 32-bit province ID for data-processing, the 32-bit integer for the sprite position of each province on the map, the sprite's width and height at 16 bits each, and for argument's sake we'll allow a given province to have up to 16 neighbours, giving a struct of 80 bytes. One entry for each of 3000 provinces gives a 230 kB world data file.

With our total data volume now reaching the unreasonably high area of 14.5 MB, you can see it will take you on the order of 100 milliseconds to allocate room for, and then read, all world data into memory. Let's add another half-megabyte for storing extra province data like region sets and names for each province, and another generous megabyte for information like production volumes and resource data for each province.

Your map-authoring tool and format will take up huge amounts of room, sure; quite possibly 530 MB for a large map like this. But once exported into a usable format, it gets quite compact. If we want greyscale instead of binary, multiply those 14.5 MB by eight, to get 116 uncompressed MB, which is by no means light, but shrinks linearly with the number of provinces stored. If you only have 1000 provinces, those figures shrink to 4.7 and 40 MB respectively. Greyscale compresses nicely if you don't mind a bit of lossiness (just don't allow lossy compression on the boundaries between transparent pixels and opaque; plenty of algorithms for this), you can probably chop 20% off the volume of greyscale pixmaps. I think you'll want to leave such graphical tweaks to the overlay layer, though, so monochrome province sprites will work more than well enough.

Quote:
With both solutions I see problems with the colorization.. how do I colorize them? If I use chunks I need the id again to identify which pixel to colorize with what color, and I need to multiply it afterwards with the lightmap.


No, you don't need the ID. Each sprite contains the bitmap data for exactly once province, so you just colourize it as-is, when drawing. All graphics libraries I can think of off the top of my head support color-keyed transparency right alongside colorization (even Allegro in 8-bit mode, where colorization would be done with palette-swapping).

Quote:
The overlay would have to be done completely different though and that's the problem I see with this sprite based approach.. the overlays are not just in a province.. rivers should only flow between two provinces and other stuff might also be not province based. So the overlay layer cannot be organized in the same sprites but would either have to be one huge map or split up into equally sized chunks again, which is radically different from what is done with the sprites and requires two different approaches for those two layers, while only one would be needed if I take the chunk approach for both, which in turn makes colorizing and slecting the provinces harder again.


Here, you do want a "tiles" approach. However, with all your province data removed, you can now create a single 16-bit (A1 R5 G5 B5, I suggest) highly-compressible palettized map, and break it into very small sections, say 128x128 pixels, so that it compresses easily. Empty tiles need not be stored at all. This is on a 1024x768 screen 9x7 tiles you need on-screen at once, and each tile will be 32 kB uncompressed. To cover 19000x7300 with these tiles, you need 149 by 57 tiles, or 265.4 MB total uncompressed data which can be streamed 2 MB at a time from disk; less if you're scrolling instead of jumping. Probably only 180 MB total if compressed.

You'll kill your game if it requires 2 GB of memory to run, and 90 seconds to load your map from disk at startup. If you only need to read 30 MB at first and then 2 MB every minute afterwards, your game will load in less than a second and take up maybe 64 MB of memory while running. Reading small bursts like those from disk won't even be noticed unless someone has a fire bell attached to their "disk activity" light.

What is this "lightmap" you keep referring to? If you're thinking a sort of darkening fog-of-war, that's either included in the colorization process or done with particle effects realtime, or else it is part of the overlay. If you're referring to day/night, do it only on visible portions of the map at runtime; you don't need to store a per-pixel lightcone in your map data.

Edits - revised last two paragraphs to be more informative.

[Edited by - Wyrframe on April 2, 2008 5:45:49 PM]

Share this post


Link to post
Share on other sites
Lightmap is the map that defines how the provinces are shaded, including written graphical province names in them, which are simply letters in a darkened color.

it is a greyscale map that will be multiplied to the monocolor province bitmap so it give it some shading and keeps it from looking like a color blob.

In your descriptions you also threw the two distinct possibilities sprites and chunks together.

By chunks I meant equally sized tiles, should have called em tiles instead probably but I explained in my above post what I meant, so you are wrong stating that with a chunk approach I wouldn't need IDs.

I still don't like the sprite per province approach. First of all, creating sprites from the map that I need to draw fist is complicated and as I said produced too many empty pixels.
There will also be provinces that may be set up out of two nearby but not-connected areas. (Like several small islands that represent one province)

Ocean btw is also split up into provinces (just a special kind of them and possibly bigger)

All in all I'm still not so sure about all this but so far I favor Ravyne's approach..
But.. Ravyne, there is no political map. there is one colored map.. what color the single provinces have is determined by the map mode the user selects.. this are up to 10 or 15 different modes ranging from political over terrain and region and stuff like that to making alliances visible and possibly many other things.. so I'd have to keep the color map pretty much neutral and it is colorized depending on what mode is selected.

I still see a lot of problems with the colorization here guys. YOu don't seen to understand the problem here.
The shading is going to be totally dependent on what lightmap overlay I put on top of it. The base map will consist only of a a lot of colored provinces, no borders no anything.
Now.. I will have to store at least 4 bitmaps for each tile.. color tile, id tile, shading tile and graphical overlay for nice stuff like rivers or terrain graphics or whatever graphical gimmics that have only optical meaning.

I'd have to possibly recolor the color tile every frame, at least every time something changes on the map, which could be done with event listeners.
the problem now is.. how the hell do I colorise the province.. If I use a fill algorithm or a color replace command I'll have to make sure only that one province has the color I'm going to fill/replace, so it would be good if I used the id tile as a basis for the color tile.. so far so good, but what happens if the color that I'm painting one province with is actually the ID of another province of that tile.. say the tile has two provinces, one with ID 000000FF and one with 00000001 (ARGB), now I fill the second province with the color blue and then the first with the color red.. well.. I'll end up with a completely red tile, since red is actually also the id of one of the provinces...
how do I prevent this from happening?
The only way that springs to mind right now is a pixel by pixel approach.. get the pixel color/id, check which color it should get, colorize the pixel and continue with the next pixel until the entire tile is colored..
correct me if I'm wrong but this doesn't sound very efficient..

Any ideas?

I'm really not having a lot of difficulties here with organizing the map, creating the map or loading the map and all that, so you don't really need to give me all too much info on that. Even if some approach I'll try won't work, I'll find another one.. what I DO have a lot of problems with is just what I described above.. how to colorize the map efficiently and effectively.

I will most likely use the ID map approach since that is the easiest to do from a map creation point of view, it doesn't waste space for transparent pixels and it makes it very very easy to determine which province has been clicked.

WHat I need now is a way of colorizing either the entire map or a map tile (which doesn't really make much difference).

The problem remains.. if I colorize a province with a color that could also be an ID (and no, I cannot exclude that since the colors will not be hardcoded but be totally data driven, so they could be any 24bit RGB color).
The only possible solutions I see for this are either do the pixel by pixel approach which sounds kinda slow especially since this will have to be done very often.. (if the user clicks a province it will be colored darker (or different, whatever), if the fog of war shifts the tiles will have to be recolored, if the user switches map modes, if tome unit conquers a province and we're in political mode..... all that.)
Or as a second solution I could use a 32bit ID map, take the IDmap tilea as a basis as mentioned and then do a simple color replace/fill and make sure this doesnt result in a color collide by making the ID use an Alpha value other than 0xFF (the fill colors will always have no transparency). THat way a 32bit color replace won't result in collisions.. but that will force me to use an ID map that has Alpha CHannel, meaning 32bit.

Comments? (Again, just about the colorization, the rest is really not an issue anymore)

[Edited by - KeldorKatarn on April 3, 2008 5:55:17 AM]

Share this post


Link to post
Share on other sites
I don't think the transparent areas around sprites are such an issue... Those pixels will be skipped when writing to the buffer and they compress easily... It's also the most efficient way (if not the only way) to isolate each province for pixel perfect collisions and manipulation...

Disconnected areas can be represented using sprites much more easily than through any other method, too...

About the colorization... If I take the screenshot you posted in your first post as reference, the provinces don't seem to use more than 16 colors... They are just a single color with a little linear gradient inside. To colorize, you could simply create a palette for each player color or even generate them automatically.

Anyway, I've thought more about the issue of actually getting the enormous task done, and I think I found a viable way to do it:

Make your map just black borders on a white background.
Open it in photoshop.
Set the color mode to indexed with 16 greyscale colors.
Use the magic wand tool to extract the borders to a new layer.
Select all provinces with the magic wand tool and add a gradient to their edge.
Select all oceans with the magic wand tool and add waves or whatever.
Use the magic wand tool to extract all areas into their own individual layer (there is support for up to 65535 layers per PSD file).
Save the file as PSD.

Then go fetch the PSD specification from the adobe website.

Make a small tool that opens your PSD file and processes each layer.
Each pass of a layer should:
- scan the layer horizontally and vertically (scan down until it finds a pixel, set that as the vertical top of the bounding box, scan up until it finds a pixel, set that as the vertical bottom, repeat for horizontal)
- copies the corresponding area to a file in the format you need it to be (don't forget to save the top left corner of the "bounding box")

What you will then have is files you can immediately use to draw all your provinces in the places they need to be. That should make it incredibly easy to make an editor. With all this data, you'll be able to create a map you can explore, and where you can select each province one by one very easily. That'll allow you to individually select provinces, give them a name and attributes, group them into regions, etc...
Plus you don't need to draw borders -- since the whole map is sprites, the borders can just be the black background seen through the creases in between sprites.


How does that sound?

Share this post


Link to post
Share on other sites
Again.. there are no borders, and there are no gradients on the map.

The map consists only of pixels belonging to provinces, there are no "border pixels".
There are also no gradients, those are created by multiplying the colored provinces with a lightmap that contains the gradients and other stuff, how those gradients are created and look is up to the designer and has nothing to do with the code. The code will simply multiply that map onto the colors of the provinces and not care how they look.

Please forget about map creation, that is not the issue here and has nothing to do with coding either.

The map consists of provinces, nothing else, no borders, no gradients nothing. Each province will have a distinct color no other province uses, that is the situation.

Loading the map is also not the issue.

The issue is how to effectively colorize is, and that means giving each province a color, WHAT color is determined by the game logic and also not the issue. Gradients and other stuff will be applied by the light map and is not part of the colorizing issue.

Forget about the screenshot and all the details on there. When I speak of a colorized map I speak of a map that only consists of shapes that are filled with one color. WIhtout the lightmap you won't even be able to distinct bordering provinces anymore if they have the same color. TO check which province they belong to I'll use the id map.

I won't go the sprite approach.. it wastes memory, it creates unnecessary many files, and cutting the sprites out of the map is too difficult a job, both by hand and code it up to be done automatically.

The tile approach is best for my purposes. All I need now is more options on how to effectively colorize each province in such a tile, given the basis is a tile which has each province colored with a distinct color only that province uses (the id map)

Share this post


Link to post
Share on other sites
We have established very early on in the thread that the method you seem to now want to use (having a map of several hundred megabytes) is not a viable option... This is what using an id map on top of a visual map will do, regardless of whether you're using tiles or not. If you have to add region-finding to that (i.e. equivalent to a flood-fill/magic wand tool in a paint program + color multiply operations), we'll all be driving flying cars by the time a personal computer that can run your game is created.

Share this post


Link to post
Share on other sites
Quote:
Original post by kiwibonga
We have established very early on in the thread that the method you seem to now want to use (having a map of several hundred megabytes) is not a viable option... This is what using an id map on top of a visual map will do, regardless of whether you're using tiles or not.


Well I tend to disagree. Why would I need to have several hundred megabytes in memory when I have both maps tiled? I only need the displayed tiles in memory and I can look up an ID in a tile just as well as I could look it up in a huge map.

Besides.. having two maps was always the only option anyway. How else would I colorize the thing. With the sprize approach I'd need the greyscale sprite plus the colorized one I'm displaying. With the tile approach I'll always need a base tale for colorization since if a tile is consisting of two provinces that have the same color those two provinces will stop to be distinguishable on that tile.

Besides.. if you think a tiled ID map is an approach that cannot run on a modern computer I will hint at the fact that mentioned game Hearts of Iron II and pretty much every other strategy game Paradox ever wrote uses exactly that technique.
I don't know exactly how they load and colorize the tiles, but I know their base map is stored as a tiled ID map.

Share this post


Link to post
Share on other sites
Ok... So the way you want to do things is take each tile that is being displayed, put it into a temporary tile buffer, look up the id of each pixel, check the status of the province it belongs to, and write the corresponding color each time. Once the tile is processed, copy it to the screen's buffer.

That's efficient enough and poses no problem. You don't actually need to use tiles to do that.

I'm curious to know how you'll implement the rest though... You'll probably get to a point where you're making way too many passes per redraw and it'll cause the game to stutter whenever the view changes...

Share this post


Link to post
Share on other sites
I think you're much better off simply drawing the province edges, and maybe do some overlay drawing (clipped by the province region) as texture.
The memory requirements for such a map would be pretty small and picking a province should be trivial!

Using tiles would be quite a waste of video-memory as well.

Share this post


Link to post
Share on other sites
I agree with the above poster, but since I know you don't want to do this...

Since you are going to have (I think), horizontal rows with just a few (in comparison to the size of your map in pixels) spans of different colors, why not use run length encoding.

like

red*80.blue*20.green*900.(etc...)

This should let you cut down memory alot.

Share this post


Link to post
Share on other sites
So, given the additional information you have provided, I would amend my suggestion to this...

Scratch my idea of the Political map if that is not what you are doing. Instead, generate the current view from the ID map. For each visible ID map tile, there should exist a corresponding View tile. You still have the database of coordinates for each province, which can also contain all the relevant shading info such as the influencing faction, alliances, etc.

You can still use the basic flood-fill algorithm to generate the View tiles, but it must be modified. Change the algorithm to write pixels to View tile, and also make it so that it checks the ID map for a value which matches the ID of the province (the usual behavior) and also that it checks the View map for a value that does not match the current shading color. This second check is required to prevent the flood-fill from infinitely over-writing itself.

Unfortunately, without a border, I don't see any way to make the tool I described work because, with the lack of borders you describe, the input map file it would need to work would be the map file it would output -- which would be rather pointless. You'll have to accept the burden of generating this map yourself.

Share this post


Link to post
Share on other sites
Let me explain why you're going about a few of these ideas all wrong, and you might see why we are posing these other ideas.

First, your map as-it-is-stored-on-disk, your map as-it-is-stored-in-memory, and your map as-it-is-displayed all have almost nothing to do with each other. Disk-to-memory, you read structures from a file and build structures in memory. Memory-to-display, you render just the visible portion of the map, and you can do a lot of processing, such as colorization, when you perform this step. As a programmer you probably understand all this already.


On Province IDs and Wasted Storage

Let us assume you are using a 32-bit province ID value for each pixel of your gargantuan map, leaving no bits left over for graphical details. And let's assume you've broken your map into digestible 128x128 pixel chunks. How much space are you wasting?

Let's assume in one particular chunk, there are 15 provinces, in whole or in part, and a corner of ocean. Realistically, you only need 4 bits (2^4 = 16) to provide IDs for this chunk, so you've already wasted 128*128*28 bits, or 56 kB wasted out of the chunk's 64 kB of storage.

On top of the 8 kB you really needed, we would have to add a local ID-to-global ID mapping table, so the 4-bit IDs can be turned into back-end real province IDs. That will take up 32 bits times 16 entries, or 64 bytes.

If your chunk had 16 or more provinces, you'd need 5 bits per pixel under this system, to get 32 possible values, always reserving one for areas that are not province; border pixels or ocean.

The most efficient route, assuming your provinces are mostly contiguous (few island chains, etc), is to spend exactly one bit per pixel, on rectangular and overlapping chunks, to tell you if that pixel is that province or not, and then resolve the overlap at runtime (a very inexpensive operation). This is why I posed the suggestion of using 1-bit sprites. It also gives you just the necessary shape data for that province, so you could show thumbnails of just that province on other screens or stuff like that.

Quote:
Besides.. if you think a tiled ID map is an approach that cannot run on a modern computer I will hint at the fact that mentioned game Hearts of Iron II and pretty much every other strategy game Paradox ever wrote uses exactly that technique.
I don't know exactly how they load and colorize the tiles, but I know their base map is stored as a tiled ID map.


Let's work from that assumption, then. The map stored on disk is a tiled ID map. First, it must be broken into tiles to be manageable. You'll have to accept that the disk activity needed to read tiles into memory for display is necessary, even if you won't acknowledge that it is a trivial process.

Second, you will need to consider alternatives to a giant pixelmap of 32-bit or even 16-bit province IDs to reduce the disk and memory footprint of the map; we have been suggesting to you reasonable ways to do this, and you have not been reworking your assumptions to see how possible it is.


On Colorization
Quote:
The tile approach is best for my purposes. All I need now is more options on how to effectively colorize each province in such a tile, given the basis is a tile which has each province colored with a distinct color only that province uses (the id map)


Assuming you use a color, whether 32, 16, 8, or 1 bits, to represent each province, you are not going to be doing a find-and-replace on the map's representation in memory and then copying that to the screen. You are going to be taking that representation, and drawing to the screen using that representation and some context information.

The color on-screen has nothing to do with what "color" you assigned it in the map chunk, other than that it is a representation of that province. So when you draw the province of Norther Flumbscrumble, you'll look up what color it should be based on day/night, fog of war, current display mode (political, region, control, military strength, etc), etc. Then you'll draw to the screen; when you see a Norther Flumbscrumble pixel, you'll draw a Current-Visual-Representation-Of-Norther Flumbscrumble pixel instead. This applies to all pixels on-screen, no matter what method of breaking up your map you use; sprites, chunks, or vector art.

Share this post


Link to post
Share on other sites
Wyrframe brings up a good optimization opportunity that totally slipped my thought process. IDs only need to be unique *within* a particular tile. Tile-bounds are easy to check for and consider during selection via mouse clicks. The only issue this introduces is that the province database now also has to remember which tile its in, and in the case of a province which spans across a tile boundary, which other tiles it appears in and what it's ID number is inside the other tile(s).

You *can* make a tool to perform the process of breaking up the large map into tiles, changing the bit-depth, and assigning "local" (per-tile) ID numbers. BTW, I still say that having a 1 pixel border between provinces will make the job of generating the overall map immensely easier. In fact, you may want to draw the map with borders, and just add a top-left fill rule to the flood-fill algorithm in the tool which breaks it down to tiles.

You can easily cut memory use by 75% by simply going from 32 to 8 bit IDs. You can cut that in half if you can get away with only 16 indices per tile, but that seems uncomfortably low to me... but I don't know how big your average provinces are. then again, just find the balance that works for you... perhaps given the size of your provinces, having tiles of 256x256, with 8 bits of ID each is optimal.

Share this post


Link to post
Share on other sites
Quote:

You can easily cut memory use by 75% by simply going from 32 to 8 bit IDs. You can cut that in half if you can get away with only 16 indices per tile, but that seems uncomfortably low to me... but I don't know how big your average provinces are. then again, just find the balance that works for you... perhaps given the size of your provinces, having tiles of 256x256, with 8 bits of ID each is optimal.
The easiest and by far most efficient way to solve this problem if your linked example map is representative (both province identification and map display) would be to partition into tiles and run-length encode them. That'd work efficiency wonders on your example map.

To display a portion of the map at a given resolution, decode and downsample the involved tiles.

To build the clickmap at a given resolution, decode and downsample the involved tiles. You can be as naive as you want to be in building the map; RLE takes care of the efficiencies within a factor of two of the display map cost unless you want to get fancy and optimize more.

In this case, you only need a minimum memory = display_size * display_resolution + display_size * province_resolution + RLE_display_representation + RLE_click_representation. *

On scroll, you'd have to decode newly-visible tiles; RLE decode is silly fast, maybe as fast as a memcpy if written properly.

*By resolution here I mean the allowed values a pixel may take; ie 2 bytes, 16 bytes...

Share this post


Link to post
Share on other sites
Certainly on disk they would be encoded in some capacity, RLE would likely be very effective, though it's not entirely a safe bet to be the best compression method in this case.

However, I was speaking of the in-memory representation of tiles which are visible or cached as an optimization (surrounding, recent tiles, etc), which you would certainly want in a readily usable form. Memory use for these tiles (even assuming 2x the display resolution is in this form) is not an issue; a few megabytes at most, at appropriate bit-depth.

I see no reason to justify the added complexity of decoding with every camera movement.

Share this post


Link to post
Share on other sites
Quote:
Certainly on disk they would be encoded in some capacity, RLE would likely be very effective, though it's not entirely a safe bet to be the best compression method in this case.
Size on disk is secondary, avoiding disk seeks is important, decompression speed is important.

A braindead RLE scheme using golomb bytewise coding for run lengths, say on a 64 * 64 tiling, would compress a solid tile to 4 + 2 + 2 = 8 bytes, a frontier tile between two provinces would take around (depending on configuration) 4 + 64 * (2 + 4) = 388 bytes. That's 1/1024 and 1 / 21 ratios for two of the most common tile configurations (second case can be halved by being just a little clever). That means the whole representation should easily fit in main memory.
Quote:

However, I was speaking of the in-memory representation of tiles which are visible or cached as an optimization (surrounding, recent tiles, etc), which you would certainly want in a readily usable form. Memory use for these tiles (even assuming 2x the display resolution is in this form) is not an issue; a few megabytes at most, at appropriate bit-depth.
You'd want the visible tiles in a completely uncompressed form, of course, so your logic for mouse clicks and drawing of different views looks exactly as if your uncompressed bitmap were in memory.

Optimizing the visible representation is likely a waste of effort; uncompressed and assuming a 1920 * 1200 display and 4 bytes per pixel, the map takes only 10 megs.

Caching makes little sense unless your working set fits in cache; given that scrolls across the whole map are a common use case, caching is a waste of effort, as it won't help whole-map scrolls.

If your RLE representation fits in memory, supporting a 640 pixel per second scroll on a 1920*1200 monitor entails decoding at most 300 64 * 64 tiles per second, no self respecting processor will even break a sweat.

Contrast that with an approach that requires disk seeks for scrolling over the whole map because it keeps part of its state on disk...

Quote:

I see no reason to justify the added complexity of decoding with every camera movement.
What added complexity? Tiles need to be fetched and retired at some point anyway; you only have to add a decompression step to the fetching, it's invisible to the rest of the code. THAT'S IT. No mucking around with bitmapped per-province bounding boxes or local-id vs global-id stuff or caches.

The logic for colorizing different views and associating mouseclicks to provinces is exactly as it would be if your whole bitmap sat in memory somewhere.

Not to mention the avoidance of superfluous caching schemes, and the avoidance of the whole local-id global-id per tile homebake compression quagmire.

The mouse logic only needs to interact with the visible display, which acts exactly as if the whole bitmap were sitting in memory.

I'd say it removes quite a bit of complexity when contrasted with other approaches.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous P
Quote:
However, I was speaking of the in-memory representation of tiles which are visible or cached as an optimization (surrounding, recent tiles, etc), which you would certainly want in a readily usable form. Memory use for these tiles (even assuming 2x the display resolution is in this form) is not an issue; a few megabytes at most, at appropriate bit-depth.

You'd want the visible tiles in a completely uncompressed form, of course, so your logic for mouse clicks and drawing of different views looks exactly as if your uncompressed bitmap were in memory.

Agreed, only the visible set need be uncompressed, which is exactly what I was getting at.

Quote:
Optimizing the visible representation is likely a waste of effort; uncompressed and assuming a 1920 * 1200 display and 4 bytes per pixel, the map takes only 10 megs.

Certainly, However there also needs to be the ID layer in the background that needs to be uncompressed as well, plus the overlay the OP wanted for roads and such, so now we're at 3x that amount. These background maps lend themselves to lower bit-depths since they convey a known amount of information and don't have to spread the whole color gamut nor does the ID map have to be in a form readily worked by a graphics API.

Quote:
Caching makes little sense unless your working set fits in cache; given that scrolls across the whole map are a common use case, caching is a waste of effort, as it won't help whole-map scrolls.

You can't presume to know what a typical use-case is though. I know that when I play an RTS or a game like the OP describes I switch between a couple locations via hotkeys, I don't scroll between locations and I certainly don't scroll the entire map without cause.

You can't say out of hand that caching does or does not have a benefit.

Quote:
If your RLE representation fits in memory, supporting a 640 pixel per second scroll on a 1920*1200 monitor entails decoding at most 300 64 * 64 tiles per second, no self respecting processor will even break a sweat.

Contrast that with an approach that requires disk seeks for scrolling over the whole map because it keeps part of its state on disk...

Thats all well and good, I don't believe I ever stated that you should keep reading from disk. Personally, I would load the whole file in in some compressed form which also lends to speedy per-tile access.

Quote:

Quote:
I see no reason to justify the added complexity of decoding with every camera movement.
What added complexity? Tiles need to be fetched and retired at some point anyway; you only have to add a decompression step to the fetching, it's invisible to the rest of the code. THAT'S IT.

Not sure what you're on about. I didn't suggest that anything be decompressed on the fly. Decompression should be done exactly and only when you say: When the tile is fetched.

Quote:
No mucking around with bitmapped per-province bounding boxes or local-id vs global-id stuff or caches.

The logic for colorizing different views and associating mouseclicks to provinces is exactly as it would be if your whole bitmap sat in memory somewhere.

Not to mention the avoidance of superfluous caching schemes, and the avoidance of the whole local-id global-id per tile homebake compression quagmire.

The mouse logic only needs to interact with the visible display, which acts exactly as if the whole bitmap were sitting in memory.

I'd say it removes quite a bit of complexity when contrasted with other approaches.

It probably is simpler just to have global IDs in some compressed form, but the ID map is not beholden to all the constraints (such as bit-depth) that the geography map is.

having both local and global IDs probably is a poor idea since it doesn't compress as well and introduces issues with cross-tile provinces, I'll concede that point.

The mouse logic, however, doesn't interact at all with whats visible on-screen, not directly anyhow -- It doesn't care what color you see, only what coordinates correspond to a particular province. You can't just read this as if the whole thing were in a big frame-buffer; you have to decide what tile the click belongs to and then index into it for the proper coordinate's value.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement