For the most part, my gamedev experience has been based around FPS games and the like. So, now I find myself doing a strategy game, and I'm a little flummoxed.

We've determined that for this project we're going to do a hex-grid, tile-based map. It will be rendered in OpenGL.

But, how do I deal with the *huge* maps we're envisioning? With a 1-meter tile size, a 10km by 10km map comes to 100,000,000 tiles (which is very many polys and verts and floats)! For an FPS hacker, the obvious answer is paging.

Except, the player can very unexpectedly come to view many pages by zooming out or by clicking on the minimap. It's essentially random-access. And although LOD algorithms help with zooming, they don't solve it completely. The player can click randomly on the minimap, and I suddenly need to page in an entire new subsection of the map; and she can just as immediately click back to where he started (this is a common occurrence, in fact). All of this is going to thrash the disk.

What's the best practice approach here? Is it really just to limit the map size to what can fit comfortably into RAM on the lowliest of in-spec computers? Procedurally generate the actual display mesh from map data (unit/terrain-type/elevation) in real time after each camera movement?

Do you need such an homongous map? How 'detailed' is a tile in this case? Just a polygon? How many tiles do you expect the player to view at a time during 'normal play'? 10x10km is a huuuge map. Most strategy games are more akin to 150x150 tiles at max (ie. Civilization, Starcraft 2, Company of Heroes). If you want a map like that, you ought to do something like Rome: Total War where zooming out switches to a map-like view and the you click on a region on a map and it loads that instead, with loading bar if necessary. How are you even going to populate a map that huge with detail?

Obviously you would want to create a couple of LOD's for a larger portion of hexagons, and render that when further away. You could have all the basic visual data in ram, even on a low-end system, assuming a couple of bytes per tile. Naturally, one vbo for the entire map in high detail would be close to impossible, but divide the map into patches and you're good.
100000000 tiles shouldn't be that difficult.

Here's a couple thoughts, although I dunno how well they'll work.

You might be able to fix some of it with an "areas of interest" scheme. It could keep stuff loaded that the player spends a lot of time jumping between, areas immediately around where the player is (your paging), and areas where lots of player-relevant stuff is going on.

If this is 2D isometric (you're drawing pre-orientated images as tiles) and you have access to geometry shaders, you could load less map info and simultaneously clear up some gpu bandwidth if you pass in a list of points and transform them into quads. You could get away with just passing in single points and a texture to draw. You'd be storing a lot less vertex info. That would make loading the new bits of map a bit faster, but that scheme would become at least a little harder with variable sized tiles though. >_>

For further out levels of zoom (the ones that encompass the whole map), you could render the entire map to a render target, save the texture, and just draw the picture instead of worrying about the individual tiles. You'd still have to render the dynamic elements, but at least the smaller individual bits of the map wouldn't be a problem anymore. You may even be able to do a scheme like that with medium-zooms and a patch system, but it becomes less space efficient the further in you get.

Procedural map generation might help, but damn that takes a while to get looking decent.