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.

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.

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.

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.