Announcement

**Kanzid Stonebreath** · September 13, 1999, 00:57

World Shape ?

I don't remember this being discussed but has there been any thought on the shape of the world used for Clash will it be.

a) A Globe - my preffered option
b) A Cylinder e.g. Civ
c) A Torous - Call to Power
d) Flat Map

**shimmin** · September 13, 1999, 08:54

A year and a half ago, I was working on a software project involving a world map, and I was absolutely committed to finding a way to give the world a spherical shape. The result was I delved into geometry texts on polyhedra and tiling, and did eventually find a suitable answer. Problem was, by the time I found it, the project was long over (done with a toroidal map).

There are exactly five shapes that allow identical tiles, related by identical directions, to cover a spher-ish world. These are the five regular polyhedra, and they are all far to small for a civ-type game's map (4, 6, 8, 12, and 20 tiles). However, each of these shapes, along with a few others, can be subdivided an arbitrary number of times to produce a geodesic sphere, which contains mostly identical tiles, with a finite (4, 6, 8, 12, or 20) number of "corners" where the pattern breaks down. The regular repeating tile regions can be done with either square, triangular or hex tiles, as per your preference. The one real problem is a graphical one -- how to display the world map when you're near a "corner". One option is to keep the tiles as they are, and "unfold" the world, so that a wedge (90 degrees if you're basing the world on a cube, 60 if on an icosohedron, etc.) of blank space appears onscreen near the corners. The other option requires a polygon engine to display the terrain (1 polygon per tile -- units, cities, and the like can still be done with sprites -- the polygon engine is needed not because the surface looks 3d, although it is, but because each tile is a slightly different size and shape to close the "gap". Think if the Epcot center's GeoSphere had a world map painted on it. Now imagine yourself suspended about five feet away from the sphere looking at it. That's the view of the world the players will have.

If you're interested in more details on how to implent this, and what sort of modeling algorithms are easy / hard to do in this geometry, feel free to email me at shimmin@students.uiuc.edu for in-depth knowlege, or reply to this forum for a brief answer.

Robert Shimmin

**Paul Crocker** · September 13, 1999, 17:08

Shimmin: Sounds really interesting...I'm not sure, but it sounds like a lot of decisions (map AI, etc) have already been made based on using diamond-shaped tiles. It would be a unique twist on the traditional map if we could implement your ideas? Any comments on this from any of the Clash Dukes/gurus?

**Mark_Everson** · September 13, 1999, 18:46

Robert, Paul:

Cool Idea, but as Paul said we've already done some of the map AI and its all based on cylindrical maps. We've just had to lock in more and more as time goes by or we'd never be able to make any progress...

-Mark

**shimmin** · September 13, 1999, 19:19

I realize many of the map generation / AI / graphics decisions have been made, which is why I gave only the outline of how the geodesic sphere geometry works. But if anyone is interested for purely academic reasons or for a vaporware project of there own, here goes.

As I stated before, the biggest problem with the geometry is displaying it. In order to keep the diamond tiles, you'd need to base your geodesic sphere on the cube. No problems so far -- the corners of the tiles would still point toward the cardinal directions; two of the cube's corners would be at the poles, and the other six would lie staggered in two bands that would roughly correspond to where earth's tropics are. If you want to keep the world roughly the same size, your 320x200 cylinder becomes a cube, each side of which has been split into a 100x100 grid (103x103 if you want to be even more exactly the same size). Lets say the on-screen area is perhaps 20x20 tiles. Then, 96% of the time, you don't have a corner of the cube in the screen area, and the display looks identical to what it would under any other world geometry. The other 4% of the time, however, you have a corner in view, and you have to deside what to do with it. Every square on the board is adjacent to 8 other squares -- 4 orthogonally and 4 diagonally, but corner squares are adjacent to 7 -- one of the diagonal directions is missing. Look at a rubic's cube to convince yourself of this. The simplest thing to do is simply display it as blank space -- there is no there there. The problem with this is that crossing the blank space can be accomplished in a single move since it's really just travelling around the edge of the cube, which would be shown as adjacent tiles anywhere else on the map. Unless you can rely on the players to visualize the gap as not existing, it's definitely not an optimal thing to do.

The other tile-based option is to close the gap. This one could actually be implemented without severely changing any of your graphics plans. Get out a piece of paper. In the center of it, draw three lines radiating from the center, equally spaced apart. You now have the logo of a German luxury car manufacturer. Now, fit three diamond tiles around the center, so that the fat corners of the diamonds fit into the center, and their narrow corners lie against the lines you drew in the first part. Their outer edges should form a hexagon. You can radiate diamond tiles out from the center like this as a display when there's a corner in view, and when there's not, the display simply shows the same diamond tiles, except they're all pointing in the same direction. As long as the world is sufficiently large that there are never two corners on the screen at the same time (and it is), you have a system for showing the pseudo-spherical world that never has blank space and still lets you use tile based graphics. Downside: you need to be able to display the tiles in any of three orientations; not in itself a huge problem, but consider the sprites placed on the tiles: do their heads point in three different directions? This graphics solution is about the best you'll do with tiles, but it does obviously show the player the world is a cube, and that just around the corner, the rain falls perpendicular to the way it falls on your block (4% of the time).

The third option is to display the terrain using a polygon engine. Were this a new project, I'd say go this way: a very basic polygon display system can do what you need. But it's not, and so I don't recommend this road, even though it is the most graphically satisfying for the "corner problem."

Now, for map AI. Good news: the map AI algorithm for determining "geographical importance" outlined on the main Clash site works just as well in this geometry as it does on a flat / cylindrical / toroidal one. All it relies on is a fairly good pathfinding algorithm -- I'd recommend A*. A* doesn't care what shape your world is, since it relies on what squares are adjacent to a given square and how much it costs to get there, not whether the path there is north, south, up or down. You can run A* on a plane, a cylinder, a cube, or a moebius strip without it ever noticing. All you need is a distance heuristic, and this is nearly as simple on the surface of a cube as on a flat surface. To generalize: any AI algorithm that depends on concepts like adjacency, distance and the such needs minimal modification to go from diamond-grid to geodesic cube geometry. The concept you can't easily use on the geodesic cube is direction, since at the corners, one of the directions is missing. Most of the AI can be implemented without using direction, since as long as it knows what way to go, it doesn't need to know if that way is east.

The map generator, if you want to do realistic tectonic simulation, can't be implemented without using direction, and that will lead to problems. Consider a plate sliding northward over one of the corners of the world. Two southern hemisphere faces of the world converge here into a single northern hemisphere face. The result, as you move north, the center of the continent is pressed inward on itself, leading to a gigantic inland mountain range that really has no reason to exist.

If you don't have a deep internal need to do realistic tectonics simulation, things become easier. In fact, most of what I've read on the map generator thread is still valid.

I. Build landmass. The very granddaddy of the whole civ-type genre is a network game called empire that popped up on UNIX boxes at the University of Washington in the late 70's (I think). It started off this way (actually building several landmasses) by selecting a few "volcanoes" and then each click of the clock, assigning a certain probability that each square next to a volcano becomes a volcano. Once there's enough land, stop. I strongly suspect you're doing something very similar here. Since it relies only on adjacency, it doesn't matter what geometry you use.

Moving the landmasses around, and creating mountains where they collide gets a little bit more tricky, since it does rely on direction. You can probably acheive the same effects in the spherical geometry by
1. generating several smaller landmasses instead of a supercontinent. Use the method a described above, which I'm betting you've already implemented.
2. Pick five or six ocean squares, either completely randomly or weighting it so that squares furthest from shore (proximity, not direction) are favored. Designate each of these either opening or closing. Floodfill (adjacency) out from these centers, so that every ocean square is part of either an opening or a closing ocean. Coastal regions adjacent to an opening ocean are designated as coastal plains -- like the eastern seabord of the U.S. -- no real elevation change in game terms. Coastal regions adjacent to closing oceans are built up into coastal mountains like the Andes or Cascades.
3. Erode the mountains downward (adjacency). I saw something in the map thread suggesting this. As long as whatever method you use relies on adjacency for the downward spreading earth, it works identically in any geometry.
4. Repeat. This gives the effect of what we see on the real Earth, of several continent opening closing cycles, without having to go through all the work of actually moving continents around. Any "extras" you want to add -- volcanic islands, etc. work the same in this geometry as a cylindrical one.

II. Climate zones -- works the same in this geometry as on a cylindrical one, perhaps even better. This is because the converging and diverging "directions" you get when you try to assign N,S,E,W to the squares on the geodesic cube provide the chaotic effects that would never work with continental drift, but are exactly what happens with real weather systems. (BTW, at corners, one square is both N and NE, or some such, of another corner sqaure.)

III. Vegetation, resources, rivers, tribes. Vegetation depnends on climate / elevation, which you've already determined, so the change in geometry does nothing to any preexisting code (if you've done good OO code, which you should have, anyway). Rivers only flow downhill; this is an adjacency issue, not a directional one. No difference, that I can see. Tribal location shouldn't depend on what shape the world is in any way that will change your code. Same with resources.

Well, that's the geodesic cube model as best as I can describe it. Conclusions:
1. The geodesic cube's biggest shortcomings are in displaying it. The best tile-based solution is to use tiles with up to three different orientations. This won't change the art. It will change the display loops in the code.

2. Map AI should not behave differently between the two geometries.

3. Map generation needs minor tweaks, mostly in continental drift. If you've written more than 40% of the code, it's not worth going back, probably. Otherwise, the model I presented above is quick to implement and should give reasonable results. In general, any algorithm than can be reduced to matters of adjacency and distance translates perfectly to a pseudo-spherical world, while those that require movement in a specific direction while retaining the shape of a large region does not.

I'm not trying to push this model onto the project; it's just random thoughts I've had over the last year or so ever since I missed my chance to make a spherical world work due to not learning the right geometry in time. If you feel Clash isn't cemented enough to use them, go ahead. Feel free to contact me if you want more advice on how to make it work. Otherwise, I appreciate the chance to vent, and if anyone wants to know more for Clash reasons or any other, contact me

Robert Shimmin

**Ron** · September 15, 1999, 15:08

Hey Robert.

Thought you might be interested to know that a spherical tiled world can and has been done, by us . I too was committed to finding a solution to the spherical world tiling problem. For a while, I was also looking at a geodesic design. What turned me off about it was the "corners". We are doing a hex tiling, and, as you probably know, the subdivisions of the triangles in a geodesic can easily be hexes, except at the points, where they turn into pentagons. Since I didn't want our poor artists to have to draw special tiles just for those spots, we dropped the geodesic model.

We finally ended up going with a true sphere, and no specialty tiles at all (which is good for the artist). In order to get a sphere to tile with hexagons, it requires a bit of tricky distortion work in the map drawing routines. These took me about a year to perfect, and is the main reason our game wasn't released a year ago.

Anyway, I'd be really interested on your thoughts about spherical worlds, especially as regards AI and unit movement and things like that.

Ron

------------------

**shimmin** · September 15, 1999, 19:22

The way you describe your solution makes it sound like although the user's display uses tiled graphics, the underlying world (a "true sphere") isn't really tiled, and whenever you want to display a given portion of the world, you project the area you want to disply (which if the world is large enough, is more or less flat) onto a hex grid.

If this is the case, the units face the interesting problem of navigating a floating-point world throgh a tiled interface. If the unit only needs to move to a nearby point, the distortion is minimal, but when moving halfway around the world, it needs to periodically retile the world to reflect its new position to correct for distortions.

Is this anything close to the sort of challenges you're dealing with, or did I completely misinterpet what you said.

Robert Shimmin

**Ron** · September 15, 1999, 20:42

Well, you're sorta close. Actually, that method was indeed one I worked on for quite some time, but finally gave it up as unworkable (I think I tried just about every method in existance, hehe). The basic problem I had with it was that, even though a very small portion of the sphere was actually being shown at any given time, and was thus fairly close to a flat map, the distortions were still showing up where the user could see them if they got anywhere near one of the poles, and it got to be pretty ugly. Also, if a unit needed to move across long distances, I could already see significant problems dealing with exactly what tiles (or pixels, for that matter) were adjacent to others, again, especially when you got near the poles.

Actually, what we do is lay down the entire hex grid map, before any graphics are ever displayed. Then we distort this huge beast at the pixel level into a shape which will wrap around a sphere (it's sort of an oval with pointy bits at the top and bottom) and store that. Because the distortion required for each row to go from a hex tiling to the ovalish graphic is fairly small, adjacent rows don't get out of synch in any noticable way. Then we display whatever portion of that map the user is currently at. It's a pretty simple idea, though a real bear to implement in practice.

Once the initial hexes are layed down and distorted, we forget all about tiling. Everything from that point on is done at the pixel level. Thus, we have tiles to make things easy on the artists, and yet a spherical world to make things more realistic for the players. It ain't perfect though. The tiles get pretty distorted around the polar regions, but at least the land masses are all continuous. I'm working on minimizing this effect now, hopefully to the point where it's not quite so bad (I don't think it is possible to eliminate it entirely, based on our algorithm). But in any case, I happen to think it's a vast improvement on the cylindrical world, hehe.

Ron

------------------
Manifest Destiny - The Race for World Domination
http://www.RJCyberware.com
news:alt.games.mdestiny

**Peter Dobrovka** · September 16, 1999, 04:59

Hi Ron!

I knew you would show up in this topic, hehe.
I am still unable to understand your solution. Unfortunately I am also unable to ask my question in a way that you could understand (or anybody on earth). But I will try once more:

Do you have tiles? If yes, how big are they and how do you arrange them?
If you work on "pixel level" a pixel may be a tile. A very small one.
The map data are still based on this "ovoid map" I think. If you subdivide this into smaller pieces you have still tiles.

My remaining problem would be still: who is the neighbour of who and is this constant?

Peter

**Ron** · September 16, 1999, 20:13

> I knew you would show up in this topic, hehe.

How could I resist with a topic so near and dear to my heart, hehe?

>Do you have tiles?

Yes. I believe you have seen them. They are in the GameArt subfolder of the download, and are straight bitmaps (you can view them with any paint program, at least for now. Eventually I will be compressing them into a single WAD-like file, so it won't always be possible).

> If yes, how big are they and how do you arrange them?

Well, they are hexes, so the shape is irregular, but in general, they are about 50x50 pixels with the blending graphics all attached. They are arranged in what I believe is called a beehive pattern. The flat sides of the hexes are to the north and south (as opposed to the pointy parts).

> If you work on "pixel level" a pixel may be a tile. A very small one.

Indeed.

> The map data are still based on this "ovoid map" I think. If you subdivide this into smaller pieces you have still tiles.

Sure, you could look at it that way. But I don't think you can divide it into a series of regularly shaped tiles. Remember, we're after a single shape for the artist to work with, rather than a bunch of them. Any distorting needs to be done by the program rather than the artist, IOW.

> My remaining problem would be still: who is the neighbour of who and is this constant?

Neighbour pixles are determined by the ovoid map, and yes, they are constant. In fact, they cannot be otherwise, since the portion of map drawn to the screen comes straight off of the ovoid map, which is static. The only calculating which is done is what part of the map to show, and at what rotation.

Another way to look at it is that the routine I am using to show the map is very similar to what D3D uses to show a texture on a sphere (like the globe map in our program). You give D3D a rectangular texture. It distorts it at the poles such that the texture wraps smoothly around a sphere mesh (and, not coincidentially, the shape it distorts the texture to is the same ovoid one we use). Then, based on the rotation of the mesh, it displays a particular portion of the texture on the screen. Pretty much the same thing we are doing, only on a very much bigger scale. The one major difference is that D3D starts off with a rectangular texture, so there is a lot of distortion around the poles, while we do not. Our initial shape is pretty close to the ovoid map to begin with, only with jagged edges due to the hex shapes, so our distortion is pretty minimal.

Does that help?

I didn't really mean for this to turn into a discussion of how the map works in MD, hehe. I don't want the Clash folks to feel like I'm trying to take over their forum. I'm more than willing to answer questions about the workings of the map, Peter, but perhaps we ought to take it over to the NG?

Really what I was interested in talking about was anyone's views (but especially Robert's, since he's spent a considerable amount of time thinking about this stuff)of unit movement on a sphere, and also how being on a spherical world affects the AI routines, since this is an area I'm getting close to working on.

Ron

------------------
Manifest Destiny - The Race for World Domination
http://www.RJCyberware.com
news:alt.games.mdestiny

**Paul Crocker** · September 18, 1999, 10:27

Hi Ron,

As a cartographer, I understand well the dilemmas you face when trying to implement a spherical map on a flat monitor screen. The solutions you pose seem quite valid, without actually seeing them implemented. One question: How do you display large areas at once? FE a player controls a large country (like Russia or the US) and wants to view the whole thing at once? I would suspect you'd need to use a Mercator (cylindrical) type projection for that (unless you showed the "globe" on-screen and had him rotate it about to view the whole area of interest.) It's kind of ironic, though that the "globe" method would have it's own distortion effects as well.

Each projection has its pros and cons. It's important to remember that it's just a projection, too, and that doesn't mean that the map is invalid just because it's cylindrical. A Mercator projection is quite valid for showing the position of one point relative (direction) to another at various scales, but is not appropriate for determining areas or distances. Albers Equal Area Projections (conical) utilize several zones (similar to UTM, except the zones are typically much larger) that allow one to fairly accurately measure area and distance, especially on the E-W axes.

Bottom line: When selecting a projection, it's important to ask what are your primary goals (direction, area, or distance), because you can't have all 3! I'm sure you're aware of this Ron, since you have apparently done your homework I just wanted to make the point for those less familiar with cartography.

**Ron** · September 18, 1999, 13:18

> One question: How do you display large areas at once?

We don't. There are actually two maps on our main screen. The big one, which is used to move units about and examine cities and such, and a globe, upon which the players can get an overall view of the world. If players want to look at large stretches of land, that's what the globe is for If they want to look at large stretches of land in detail, well, that's what the scrolling buttons on the main map are for, hehe.

Like you say, there's a limit to what you can do when showing a curved surface on a flat screen. In our case, we sacrifice distance in favour of area and direction. If you zoomed out far enough from our main map, the routines would begin to break down and distortions would begin to appear (which is why we don't let you do that, heh).

Hey, since you are a cartographer, maybe you know the answer to this question. I've been hunting around forever trying to find the name of that shape which is an oval with a pointy top and bottom. I know it has an official name, since it is one of the recommended ways of showing a sphere's topography on a flat surface. But I have never come across it, so have been reduced to calling it an ovoid map, which I know is wrong :-)

Ron

**Blade Runner** · September 19, 1999, 04:52

I think the official name of this: Mercator projection. Maybe I am wrong, but I am just a programmer not a cartographer.

Blade

**Peter Dobrovka** · September 19, 1999, 07:39

At this point I should mention that Mercator lived and worked in Duisburg, Germany. Many streets and buildings are named after him here.

Peter

------------------
3DTT - the 3D sequel to Transport Tycoon - demo 4.0 now available on http://www.digitalprojects.com/way-x
Path of Mankind. Turnbased Civ-like game - demo 15 coming soon

Announcement

World Shape ?

World Shape ?

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment