Map Generator Model

[Gary Thomas]

Laurent:

We could use hexagons, they can map both planes and spheres (sphere: 1hex 6hexes 1hex/1 6 12 12 1/etc as you grow), and I like the old hex-based wargames. Plus you don't have to worry about perspective.

Couldn't follow this. Actually hexes can't cover a sphere. There will always be bits that don't fit. The only polygons that can form a regular solid (an approximation to a sphere) are triangle (tetrahedron ot icosahedron) square (cube) and pentagon (dodecahedron), none of which are suitable. The nearest is the icosadahedron, in which the 20 big triangles can be subdivided into smaller triangles, 6 meeting at each vertex. However, at the vertices of the larger triangles, only five meet at a point.

Mapping onto a non-square based terrain really isn't difficult. The terrain is divided into polygonal areas of a uniform type, and texture mapped. Lest it is thought that this is a novel thought, ALL the 3D shoot-em-ups work this way. Personally I don't see why a strategy game can't do the same, with an enormous improvement in visual appeal. If that is combined with automatic micro-generation which I described elsewhere, we can get a very realistic simulation of a world.

Cheers

[LDiCesare]

About polyhedra: You're right if you consider regular polyhedra (all the same lengths). Topologically, you can pave with hexagons. You'll just get bigger hexagons at some points, which may or may not be catastrophic.
Triangles would be good too.
As Mark said, however, we can hardly change squares by now.

[Gary Thomas]

As Mark said, however, we can hardly change squares by now.

I was thinking about D439.

Cheers

[Lord God Jinnai]

Ultimatly i think we should go with triangles, but atleast for the time being it'll be squares.

I know mark, that there had been a lot of time spent working on the graphical design of what the tiles would look like, but it's small compared to what the end result would be. The more signifigant part would be the recoding, but i think if it makes an overall better quality game its worth rewritting it. And not everything would need to be rewritten that had to do with movement eithr i beleive, depending on how it was programmed.

[Gary Thomas]

And not everything would need to be rewritten that had to do with movement eithr i beleive, depending on how it was programmed.

It certainly wouldn't require a rewrite.

I would code it using the pretty well understood texture mapping techniques used in shoot-em-ups. That is, there would be no terrain tiles, exactly as there are no terrain tiles in an atlas. Geographic features would be point features (less than 100 m²) or extended features (everything else). Extended features would be stored as polygons. Believe me, all this is really well understood, and has a huge literature. I have around fiflty books on this and closely related subjects.

As far as memory is concerned, it will require less than the present system. It will also be hugely configureable.

But above all, for a strategy game, it hasn't been done before!

Cheers

[Richard Bruns]

Continuous Mapping

This tile-less mapping sounds like a good idea for the display, but I have a few concerns about how it interacts with the guts of the game, especially economy model and the movement of units.

For example, assume that we decide in the military model that a city garrison can react to threats in all areas around the city that can be reached in 20 days' travel for that unit. With squares or hexes, it is pretty easy to define and display the area that the unit protects. But would that cause problems in this system? It seems that calculating and displaying the response radius might be very hard in such a system, especially when you throw in the effects of roads, rivers, hostile terrain, and so on.

Also, how hard would it be to calculate the economic productivity of a certain region? Since provinces can be redrawn by the player, what do we do when a province might have dozens of chunks of discrete terrain, each with different attributes for farming and manufacturing productivity? Also, what happens when the player improves a certain area by adding irrigation or a better road system? Will that case problems in updating the display?

The terrain in flight simulators, shooters, and other action games is essentially static. It exists only to be looked at; the player is not interacting with it in any way except possibly using it as cover. I think that Mark's objections make a lot of sense; it seems like abandining squares would at minimum require a huge rework in all existing models that depend on interaction with the land, even if displaying the tiles is easy.

That said, it may be possible to superimpose a discrete display on top of the existing tile system. The models would still use tiles, but the display would be as Gary says. But that seems ot be one of those "Demo 17" things.

[Sancio]

I always wanted a "continuous" map but never suggested it cause I knew that we would have to rewrite most of the current models ( Don't like suggesting something unless I am willing to do it ).

There are a couple of solution to the modifying terrain problem. It is like constructing buildings and such in most strategy/war games.

The basic map (the topography of the world) could be generated using "continuous" space. The modification (farms, cities, etc) could be treated as titles (polygons) within the 2D space.

Such thing as deserts, plains, forest, mountain could also be defined using polygons. The different models that need to know the terrain type can check if a point is within the polygon.

This might also require having different layers (or a z-coord) so that the different polygons are drawn correctly.

Sancio
PS. Happy coding Gary

[Gary Thomas]

For example, assume that we decide in the military model that a city garrison can react to threats in all areas around the city that can be reached in 20 days' travel for that unit. With squares or hexes, it is pretty easy to define and display the area that the unit protects. But would that cause problems in this system? It seems that calculating and displaying the response radius might be very hard in such a system, especially when you throw in the effects of roads, rivers, hostile terrain, and so on.

Actually it is harder with squares, simply because there are more of them. The A* path-finding algorithm is not restricted to a grid.

Also, how hard would it be to calculate the economic productivity of a certain region? Since provinces can be redrawn by the player, what do we do when a province might have dozens of chunks of discrete terrain, each with different attributes for farming and manufacturing productivity?

Isn't this what happens now? With polygonal areas, again there would be far fewer areas to worry about. Each homogeneous area would be treated exactly as a square is treated now. Where is the problem?

Also, what happens when the player improves a certain area by adding irrigation or a better road system? Will that case problems in updating the display?

What happens when a square is improved?

The terrain in flight simulators, shooters, and other action games is essentially static. It exists only to be looked at; the player is not interacting with it in any way except possibly using it as cover.

This is simply not true, and is hardly worth countering. The terrain in a strategy game is essentially static, it isn't at all in shooters, depending as it does on its location relative to the player, as well as lighting, damage and so forth.

I think that Mark's objections make a lot of sense; it seems like abandining squares would at minimum require a huge rework in all existing models that depend on interaction with the land, even if displaying the tiles is easy.

Not true. The models are based on squares. If you think outside the squares, many of the models need no modification at all. Technology is an example. Strangely enough, economics is another.

That said, it may be possible to superimpose a discrete display on top of the existing tile system. The models would still use tiles, but the display would be as Gary says. But that seems ot be one of those "Demo 17" things.

Now that would be a truly bizarre combination, with the worst of both methods.

Cheers

[Lord God Jinnai]

Well i think after we finish with a few more models and get them up and running a bit more on their feet, someone should, if they have time, code both to see what differance it would make...right now all i can see is with the art and the art section was using stuff we would not use in the final version anyway, just nice-looking placeholders.

[Richard Bruns]

Originally posted by Gary Thomas
With polygonal areas, again there would be far fewer areas to worry about. Each homogeneous area would be treated exactly as a square is treated now. Where is the problem?

My concern is that the number of polygonal areas can increase dramatically as the game progresses. Consider what might happen to a big forest polygon. At the start it is a vast uniform polygon. But then minor tribes start to settle on it. These tribes capture game or farm the land in different ways, thus splitting the big polygon into maybe 8 or 9 smaller land features, all different. Then the big civs start to come in. Assume the player and another civ each conquer part of the area of a few minor tribes, and that the tribes they displace conquer areas that were formerly in another tribe. Since the civ conquered half a polygon and will develop it defferently than the tribe, what was once one polygon will have to be split again. This happens for each different land area each time it changes hands, so after teh big covs move in the 9 polygon forest could be split into maybe 20 different polygons as the people move around.

This can continue throughout the game. Each border war between the civs would cause land to change hands, altering a small part of the terrain so that it needs to be tracked seperately. If the different provinces of the civ have different land management practices, the characteristics of teh terrain will diverge within the civ. Eventually that one forest might be split into hundreds or even thousands of different terrain types, creating a headache for the player. The discrete terrain model results in far more, not far fewer, chunks of land to worry about.

My point is that there has to be some indivisible unit of land. Right now that indivisible unit is the square. I once suggested defining those indivisible units as semi-polygonal provinces, but Mark shot that idea down. Maybe with your help I can revive the indivisible province idea, which was discussed here:

http://apolyton.net/forums/showthread.php?s=&threadid=12177

My posts about fixed provinces start halfway down. Ever since they changed the forums I can't link to individual posts anymore.

What happens when a square is improved?

The entire square changes. The change cannot split the square into two mini-squares, the way they could in the discrete model.

This is simply not true, and is hardly worth countering. The terrain in a strategy game is essentially static, it isn't at all in shooters, depending as it does on its location relative to the player, as well as lighting, damage and so forth.

I think we are talking about different things. My point was that in a shooter, grass will always be grass and trees will always be trees. I know that the viewpoint changes and that the player sees the grass from different lighting and angles, but it is still grass. But in a strategy game, the terrain changes constantly, even if the view stays the same. The player builds roads, farms, canals, and factories. The terrain is no longer "grassland" but "grassland with 40% road coverage, 3 factory sites, 43 farming sites, and a level 2 irrigation system." And those numbers change all the time. That's what I mean by dynamic. I am talking about the quality and attributes of the land, not the view that the player sees.

Not true. The models are based on squares. If you think outside the squares, many of the models need no modification at all. Technology is an example. Strangely enough, economics is another.

The models are currently based on some indivisible unit of production. For example, farms are defined in terms of farming sites per square. I don't like that; I preferred a system of quality and percentages, but that's what we have. The concept of divisible polygonal units is at odds with the measuring of farming as "sites per square." I think there are other examples too.

Now that would be a truly bizarre combination, with the worst of both methods.

Not really. The only thing we really need is an indivisible unit of land to work with. If we had a system of indivisible squares as teeh core of the model, then your continuous display would be very good at hiding the checkerboard appearance.

[Gary Thomas]

My concern is that the number of polygonal areas can increase dramatically as the game progresses.

How can it be better to start with the maximum number? There certainly needs (as you suggest) to be a minimum size.

Also, there is no reason why polygons have to be split when political control changes for part of it. I envisage a separate, overlying set of polygons for political control, anothe rone for weather, and so forth. There has to be a physical change in the terrain for a terrain polygon to be split.

Forest clearance would do it. However, I did not think that forest clearance would be a political decision (it is in Civ, but that is extremely inaccurate). It would take place as a result of population growth, regardless of political control.

I think we are talking about different things. My point was that in a shooter, grass will always be grass and trees will always be trees. I know that the viewpoint changes and that the player sees the grass from different lighting and angles, but it is still grass.

This simply isn't so. There are many situations in a 3D game in which changes take place, The simplest and most obvious is in opening a door or window.

But in a strategy game, the terrain changes constantly, even if the view stays the same. The player builds roads, farms, canals, and factories. The terrain is no longer "grassland" but "grassland with 40% road coverage, 3 factory sites, 43 farming sites, and a level 2 irrigation system." And those numbers change all the time. That's what I mean by dynamic. I am talking about the quality and attributes of the land, not the view that the player sees.

If the player cannot see it, then it isn't displayed, and no problem arises.

The models are currently based on some indivisible unit of production. For example, farms are defined in terms of farming sites per square. I don't like that; I preferred a system of quality and percentages, but that's what we have. The concept of divisible polygonal units is at odds with the measuring of farming as "sites per square." I think there are other examples too.

"Farming sites per square" is eqivalent to "farming sites per 100 km²". How do polygons change this?

[Richard Bruns]

Re: Continuous Mapping

Originally posted by Richard Bruns
This tile-less mapping sounds like a good idea for the display, but I have a few concerns about how it interacts with the guts of the game, especially economy model and the movement of units.

Ok, you shot down my concerns. Next step: convince Mark to allow the change.

I am starting to see some interesting possibilities with this system. First, roads and rivers can now be drawn as vectors, in whatever pattern we choose. That would make the place look a lot more realistic.

Second, it lends itself to incredibly easy zooming. If everything is polygons with vector graphics, then the player could zoom the view in and out at will. This would allow the player to start by controlling with a tiny tribe on a zoomed-in map, and then zooming out as teh civilization expands. If done right, this would mean that the screen size the player deals with and the task of management remains constant throughout the ages.

But I think that, in order to prevent fragmentation as the game progresses, there has to be some mechanism for joining the polygonal areas. For example, what may have started as two different terrain types would join to become one after the civ has been farming them for a few centuries. That way, the number of polygons would stay about the same as the game prgresses.

Also, I have a few concerns about the attractiveness of the board. If everything is simply vector graphics and shaded areas, it might seem unapproachable. The graphics need the human element in order to make the game appealing. I think that people want to see little huts and skyscrapers and trees and airport runways and people on the map. We have to have some way to cleanly overlay these bitmaps over the vector-generated terrain so that they look good and accurately display the conditions of the area. I don't know how hard that would be.

About a year ago, I proposed systems of "fixed provinces" and "ecological provinces." It seems that this plan combines the benefits of these with the flexibility of the tile model. I still think it would be a pain to program, but if the programmer wants to do it who am I to argue?

[Simon Loverix]

What will the smallest unit of terrain be? If it is a polygon, what kind of polygon? If it is not a fixed form, how will the form be set?
The models are assuming a massive area, no various shapes. Wouldn't that give odd results? I think of one unit of terrain with a long, small shape: it could lie in several climatic zones. It could be a coast of significant length, so you could control shipping of a nation very easily with minor efforts.

I think there should be some kind of regular base for a map, so you know what you can expect. Otherwise, where does the splitting of polygons end? Also, different overlapping polygons sound confusing.. with base units its seems clearer.

But it has never been done before for a strategy game, and its surely offers interesting possibilities, such as tileless movement. I'd like to see it, so I add my voice to the chorus : 'if the programmer wants to do it...'
On the other hand, the three Clash goals are already ambitious. Good AI (also to do the micromanagement) as well as historical accuracy (instead of a boardgame) are already very worthy goals, and it might not be desirable trying to outclass the commercial gameproducers on their strongest point: graphics.

[Richard Bruns]

Originally posted by Simon Loverix
Wouldn't that give odd results? I think of one unit of terrain with a long, small shape: it could lie in several climatic zones.

I think that the map generator would automatically split the polygons based on climate and any other factor that affects the ecology. I don't think that would cause problems.

It could be a coast of significant length, so you could control shipping of a nation very easily with minor efforts.

But it would be possible to split this shape into smaller polygons. Some military force could move in to one part and force a split.

I think there should be some kind of regular base for a map, so you know what you can expect. Otherwise, where does the splitting of polygons end? Also, different overlapping polygons sound confusing.. with base units its seems clearer.

The good thing about Gary's plan is that, if I interpret it correctly, a normal system of squares, hexagons, or any other form can easily be created as a subset of the model. We have the option use irregular polygons, but it would be just as easy to make a system of regular, immobile polygons as well. It's all about options and cistomization.

And yes, I too am worried about excessive splitting of polygons. That's why we need to make a way to merge the polygons. As empires grow and apply the same land use policies to larger areas of multiple polygons, these polygons could merge. For example, many parts of Europe once had a variety of terrain but now vast chunks have been converted into mostly identical farmland.

it might not be desirable trying to outclass the commercial gameproducers on their strongest point: graphics.

Have you seen the Civ3 graphics? They are hideous. Those are not the graphics of a 21'st century computer game. We can do better. Roads in Civ 3, for example, are simply bitmaps placed on top of whatever terrain there is. We already have plans for clearing off little tree tiles wherever roads are built, and this vector system can make the game look far better then Civ 3, if we do it right.

[Gary Thomas]

From Richard:

First, roads and rivers can now be drawn as vectors, in whatever pattern we choose. That would make the place look a lot more realistic.

This, of course, is one of the biggest advantages of the continuous map system. Note that the comment also applies to coastlines, edges of deserts, and so forth.

Another thing made possible (which I didn't mention before for fear of scaring people off) is altitude contours, leading to proper mountain ranges, plateaus, and similar landofrms that are difficult to do with a grid.

Second, it lends itself to incredibly easy zooming. If everything is polygons with vector graphics, then the player could zoom the view in and out at will. This would allow the player to start by controlling with a tiny tribe on a zoomed-in map, and then zooming out as teh civilization expands. If done right, this would mean that the screen size the player deals with and the task of management remains constant throughout the ages.

Richard, I don't know if you saw my post (which caused Mark to have a fit and start talking about version 50) about micro terrain. The idea is that the terrain actually goes down to some minimum size (my suggestion is 100 m²). However, this terrain is not stored. It is generated as needed using a repeatable pseudo-random number sequence. Thus, going back to the same location has the same landscape. So, in effect, the whole map becomes a grid of 1 hectare plots.

Also, I have a few concerns about the attractiveness of the board. If everything is simply vector graphics and shaded areas, it might seem unapproachable.

Actually map square tiles are just that anyway. With a continuous map, you can let the drawing code have a bit more intelligence.

As an example, suppose that, instead of having a "forest tile", you have individual trees which are then ramdomly scattered (using the same repeatable pseudo random nymber system so they alway reappear in the same place) over the polygon. This adds several factors not presently available:

• You can see the underlying terrain, so you do not need different tiles for hill forest, flat forest, etc.
• The density can be adjusted for open woods, forest, dense growth.
• The type of tree can reflect the altitude or climate of the area.
• Trees can avoid things they should not overwrite like roads, towns, farms or whatever.

I still think it would be a pain to program, but if the programmer wants to do it who am I to argue?

If approached correctly, it is no more difficult to program than the present system. Wait until people hit the intricacies of a movement system where there are only eight directions, four of them being 100km per square and four being 141.529km per square (this really is programmed into the system).

As a program design issue, a reasonably comprehensive set of polygon management classes will be needed. There is a large literature on the topic.

So far I have refrained from mentioning the step after continuous maps. This is three dimensional spline based polygonal surfaces, so a unit will know if it is moving uphill...

From Simon:

What will the smallest unit of terrain be? If it is a polygon, what kind of polygon? If it is not a fixed form, how will the form be set?

I would see the limit as being something like 100 km² in area, and no linear dimension greater than 200km. Within these limits, the shape doesn't matter. In effect, the same as the current squares. You understand that this is just a first guess, but it would seem to fit.

Also, splitting a polygon would not, I think, be as common as people seem to think. For example, if a civilization takes control of an area, it is likely that they will take control of whole polygons.

I did not envisage very large polygons - perhops no larger than around 20 squares.

I think there should be some kind of regular base for a map, so you know what you can expect. Otherwise, where does the splitting of polygons end? Also, different overlapping polygons sound confusing.. with base units its seems clearer.

Don't understand the first part of this comment. The splitting of polygons ends when the program says that there is no more splitting (see my comments above).

We already have overlapping polygons: a province contains (and hence overlaps) many squares, and a civilization contains a number of provinces. After all, a square is a polygon.

Splitting the polygon into smaller units, then assigning those smaller units to different larger polygons (as is done now) is at least as confusing as the system I propose. In my proposed system, there is hardly any confusion arising from the concept that the southern half of a mountain range is in one province and the northern half in another. As I said above, chopping the range up into little squares, then assigning the squares does not make things clearer.

, and it might not be desirable trying to outclass the commercial gameproducers on their strongest point: graphics.

My suggestion does not have anything to do with graphics as such, it is all to do with realism, including a realistic looking terrain.

Richard again:

The good thing about Gary's plan is that, if I interpret it correctly, a normal system of squares, hexagons, or any other form can easily be created as a subset of the model. We have the option use irregular polygons, but it would be just as easy to make a system of regular, immobile polygons as well. It's all about options and cistomization.

This, of course, is the point. The present system is based on polygons. Just unnecessarily limited one. There are fragments in the existing code that have implications of where, in a square, a unit is. It is pretty silly to suggest that all the units in a square are lumped in the middle.

Second, it lends itself to incredibly easy zooming. If everything is polygons with vector graphics, then the player could zoom the view in and out at will.

This is certainly one of the greatest advantages of the system. However it would not be implemented as a straight magnification. For example, no matter what the level of zoom, the trees would remain the same size on the screen.

We already have plans for clearing off little tree tiles wherever roads are built, and this vector system can make the game look far better then Civ 3, if we do it right.

See my comments above about not planting trees on roads.

And as a general comment: I see the continuous terrain model, and the microterrain model as being essentially complementary. The combination would, in my view, take strategy gaming to a new level.

And I see no reason why we shouldn't be the ones to do it.

Quite an exciting prospect.

Cheers