So, one of the unexpected-but-not-really effects of the whole scorched-earth thing with towns is that late in the game it takes a bloody long time for military guys to get from one town to the next. All this dead space in the middle of the board. So, a few thoughts on that worth considering:
1. Is this even a problem? Presuming that you are producing guys at a fixed rate at all of your towns, they will arrive at the enemy at a steady pace no matter what. The only thing that changes is the reactiveness of changes you make to production; rather than a change you make affecting the mix of units at the enemy town in a turn or two, it's in four or five turns. That's actually pretty cool. If anyone has played the game Killer Bunnies, that sort of "make a decision, then have a delayed effect from it" mechanic is pretty interesting. And it certainly makes the late game distinct from the early game.
2. If it is a problem, how do we help mitigate that? I have a few ideas, but you might have more.
3. The most obvious thing is to have some collapses in the middle of the board, and then the tiles move back together to make a smaller continent again. This has some problems, though, as it would be computationally very complex, potentially mess with what you are doing as a player, and potentially be unworkable anyhow depending on how you placed your towns (without REALLY messing with your continent). So I think that this one is pretty much Right Out.
4. The next idea is to have some form of Portals system, that basically work like those in Valley 2. Your guys can walk into any portal to get to any other portal. The pathfinding for that is easy, and they would still target enemy towns just like they wanted. Now, the problem here is that this is a little bit complex, and it could be frustrating if these portals are getting plopped down without your permission. So it could be a form of land tile that only you can place directly (except perhaps on a new portal-tastic new map type, which would be cool). This would solve the distance problem, but only if you WANTED it solved. But the question is: what if the distance problem should be solved against your will? Aka, to maintain balance? There's no way to handle this in a non-frustrating way.
5. The next idea is to have kind of a "moving floor" system -- think those things in airports. Your guys have a long way to go, so something accelerates them when they are on long stretches out in the middle of nowhere. This could simply giving a 0 AP cost to move across building ruins. And in fact, building ruins might gradually expand out from towns that are completely destroyed or something. Thus the middle of the map eventually becomes just this barren post-apocalyptic barren system of ruins. Kind of interesting, but maybe too much. Obsidian could also benefit from the 0 AP to cross idea. But how to justify this in terms of game themes? It seems kind of silly, although mechanically it works pretty well.
6. As each age progresses, on medium difficulty and up only, the AP of all your human units could go up quite a bit. Doubled in the second age, tripled in the third age? Perhaps their AP costs for attacks should also scale by that same amount, to keep things from getting crazy. Of course, then things that reduce the AP costs of attacks to 1 get even more insane. So this causes some balance problems pretty fast. This one would be easy to thematically justify, though.
Probably my favorite idea is #5, if this is even a problem at all. Although the portals thing would be the best idea if it's a matter of you WANTING less distance between towns but not being able to do that.
