The spherical map problem

[diablovision]

This has been discussed in several threads and I know that many people have various opinions.

I'd like to weigh in with my current thinking on the possibility of a 3d spherical map. Many of us have thought about it, and there are certainly some problems.

I think the principal problem is Tiling, and that nearly all problems descend directly from this. Either hexes or squares or anything else, it is geometrically impossible to tile a globe and make each tile the same size and shape. This has been known to geometry for thousands of years: there are only five: and none of them have enough tiles to make an interesting game of Civilization.

There are ways to tile the globe with distorted hexagons, squares, trapezoids, etc, but all such methods fail either in area representation (tiles are not exactly the same area across the globe, punishing some civ's based only on geographic location), or in distance calculations (i.e. shortest path isn't an arc as expected, but depends on geographic position).

I have been doing some serious thinking the past few days on this problem, and I think I am becoming more in favor of the idea of a tile-less map.

This boils down to the question: what are tiles good for, anyway? And here I think, are the principal points of tiles:

1. Breaks movement into increments, which matches well with the turn-based nature.
2. Break landscape into increments and classes such as mountain, water, hill, grassland, etc.
3. Break improvements into increments.
4. Simplify road / railroad connection network.

All of these, in turn, simplify the game engine and related calculations, as well as make it easier for humans to reason about the landscape, improvements, etc.

But the more I think about it, the more I really want a spherical map. I have tried hard to resolve the geometric difficulties of tiling such a map and have not found a satisfactory solution.

So I spent some time considering the possibility of a tileless map, and here are some problems and possible directions for their resolution:

1. On a tileless map, units can have non-integer locations, which eventually leads to the problem of collision detection (i.e. armies from two nations clashing). This problem has been solved in games like Warcraft for some time: each unit can have a bounding cylinder centered at their current location with some small radius. Other units cannot occupy the same space. That leads to the subproblem:

1a. If all units have bounding cylinders, then friendly units can get jammed up. Two possible solutions are allowing pass-through for friendly units or to allow multiple friendly units (either of the same type, or mixed types) to coexist in the same cylinder. By "getting close enough" to the bounding cyclinder, the unit could join it. Units in a bounding cylinder together would act as a group, or could be split upon movement.

2. Distance calculations. With no integer coordinates, units might move a non-integer distance; this extra complication can be annoying, as it might not be clear when a unit has "just a little" extra movement left for this turn. One possible solution to this problem is to change how unit movement is controlled. For example, when a unit is selected, pressing G would pop up on the map a display of the radius left for that unit to move within the current turn. Clicking on a spot within the circle will move the unit to that point while retaining the left-over movement credit. Clicking on a point outside the circle will cause the unit to take the shortest path to the outside of the circle in that direction and end its turn there. Making a "go-to" point will route the unit to its destination over multiple turns.

3. City radius. Without too much problem, I think that city radius and cultural calculations can be handled as curves around the points where the city is founded. A built-in minimum distance restriction would disallow building cities too close together. Cultural borders could be handled either with a finite-element circle around the city center (and handling overlap) or with a continuous function (curve). Cultural borders would then be curved and blobular, rather than square.

4. Improvements. Terrain improvements could be handled similarly to city radii, where an improvement will affect a radius around the point where it was built. A minimum spacing requirement would disallow overloading hills or mountains with mines. The center of the improvement would determine the terrain "type" for the bonus calculation. The computer may also be able to help by displaying on the map these best candidate locations for the improvement you are wanting to build within a certain distance.

5. Roads. Roads would be built between two points of interest, rather than on a tile. Two points of interest could be two cities, a city and a resource, etc. For Y-type connections between 3 or more cities, a finite number of connection points along one of the roads could allow offshoots to go to other cities, so that there isn't the NxN road connection problem. The interface would help you considerably by helping you build a plan of your road system to minimize distances; after all, this is a computer game, so the computer should help you design the most efficient routes.

6. Combat. Getting close enough (within the bounding cylinder of an opposing unit or group) would initiate combat. The losing unit or group would be destroyed and removed from the map.

7. Supply lines and trade routes. This is independent of the discussion of tileless maps, but it could still be supported with tileless maps; my idea being that the territory traversed by your army when it is outside your borders is your supply line and it must connect you back to one of your cities, or you lose health or fighting power, etc. The supply lines and trade routes would be visible on the map and could be broken by enemy forces rampaging through. To prevent accidentally cutting your allies' trade routes, normal movement would not break supply lines or trade routes but a "rampage" or "pillage" movement would. Also, that "conquered" territory that you passed through with your army on your way to wherever you are going would net you a small fraction of the gold and resources that it would had that territory been within your actual borders. Also, some special units such as marines or explorers would not require supply lines.

What do you guys think about this?

[edit: corrected spelling errors and improved explanation of supply lines and trade routes]

[Optimizer]

Good thoughts.

[Max Sinister]

I agree. The only thing I'm wondering about: How does the computer calculate the shortest (i.e. most efficient) paths? Even with a tile-based system, that's not too easy (I once tried to program that myself, and my algorithm still has flakes). How would that work with your system?

[diablovision]

Sinister,

The computer calculates the shortest path by considering each tile on the map to be a node (point) with connections to each of its eight neighbors. By considering the terrain type, roads, and whether the tile is in your land or not, it computes a "score" for each of the connections to its neighbors, where the lowest score is better (railroad on your territory to railroad on your territory = 0).

It then applies Dijkstra's shortest path algorithm.

Here is more info:
http://www-b2.is.tokushima-u.ac.jp/~...Dijkstra.shtml

On a tileless spherical map, ignoring terrain, the shortest distance between two points is always an arc. With terrain, this can be handled by starting with an arc and then "bending" it around obstacles until a shorter path is found. Another approach, if terrain on the surface of the globe is represented as polygons, could be based on the idea of tracing the outline of these polygons to determine the best way through / around them.

That's only what I came up with off the top of my head, but I think there wouldn't be much problem in coming up with the shortest path calculation.

[realpolitic]

While a spherical map would be nice, it seems these solutions would make civ less playable, and civ is a GAME, so the first order of business is keeping it fun.

[Darkstar]

I like it. I've been saying we should be on a round world since posting about Civ2 wishlist.

If you can play on a spherical world in Populous 3, why not elsewhere?

[Sandman]

You can tile a sphere with hexagons if you throw in the odd pentagon. Alternatively, you could use a province based-system like EU.

[Chimura]

your ideas have some good points, but civ is a tile based game. the best way to get a spherical map is to base the sphere around the tile, not the other way around. I've got a proto-type sphereical map generator that i've made in visual basic (no terrain generation, no unit/bonuses, basicly just a blank map, and i haven't figured out how to scroll around the equator or in any direction) when i last worked on it, i was trying to get a map size in the thousands to be created under 60 seconds,

Edit: i was looking at an an old version, last one i make can make a 50 tile radius planet in 9.750 seconds. time to make the blank map is roughly radius squared... i'll plot some results and see what i can come up with.

If anyone is interested, i can post a compiled exe of it and write some descriptions/limitations of what it can do.

[General Ludd]

Originally posted by realpolitic
While a spherical map would be nice, it seems these solutions would make civ less playable, and civ is a GAME, so the first order of business is keeping it fun.

In order to keep something fun, it would have to be fun in the first place.


Civ hasn't been fun since 1999.

[Tomasz]

I really like your ideas Diablovision, for they would increase the reality and originality of every single game. The different situations and replayablity would be infinite.

I would also suggest that a grouping of an army should be done like in CTP 2, and if a battle is fought with numerous units on each side, the area on which they fight should take the entire screen together with all the roads, imrovemwnts, little villages randomly placed, etc, and the untis themselves changed into rectangles to reacreate a true battle plan. And then you should be able to fight the battle.

You can always replace the rectangles to whatever ud like

Also it would be neat if a battle took place on a larger than one area terrain ( ie: more manouvrability and possibilities ) especially later in the game when using modern units.


I posted some other thoughts in the political parties thread too

Tomasz

[petermarkab]

Yeah, you can tile a sphere using the buckyball, or football format.
see http://en.wikipedia.org/wiki/Buckminsterfullerene

[diablovision]

Buckyballs contain some pentagons and some hexagons. It was proven by the ancient Greeks using simple geometric principles long ago that there are only 5 platonic solids. Solids of this nature meet the requirements that: 1.) all vertices lie on the surface of a sphere, 2.) all faces are the same size and shape 3.) and all faces are regular polygons.

So, unless you are happy with 20 tiles on the whole map, a platonic solid will not do....

[Sandman]

Looks fine to me...

[General Ludd]

What's this fascination with tiles, anyways? They are an antiquated way of doing things.

[petermarkab]

Hey sandman, you are on the money!

I imagine they've already settled on a particular tile-notile system, judging by those hazily remembered screenshots.

[Styria]

I think it would be very easy to take an icosahedron (20 sides) or an irregular polyhedron with several or many more (but the faces are still congruent), and to divide the faces up into hexes. Then all you need to do is resolve the points and vertices. It would still appear spherical enough. You could also define the faces as arctic, temperate, and tropical as a factor in determining their terrain.