**1**

# The Intriguing Problem with Map Wrapping

###
#1
Members - Reputation: **102**

Posted 27 November 2012 - 09:25 PM

Anyway, this is where the simplicity ceases, as the next step I wanted to make involved creating weather and climate. (Keep in mind, I'm attempting to keep this to a 2D map; think Dwarf Fortress.) I decided first to start with temperature: I planned on doing so by combining the altitude of the generated land with the latitude, and create a formula to calculate the temperature based on these two things.

Here's the problem: If I create a map on a two-dimensional plane that wraps around both vertically and horizontally, it is literally near impossible to figure out where the poles go.

My first idea was to delineate the top and bottom of the map as the poles. Problem is, this results in only one pole, as the map wraps and both ends meet.

My second idea was to have a second pole in the middle of the map. The problem with this scenario is that if I were to travel left directly from this pole all the way across the map, I would end up back at the same pole, without meeting the other pole as I should.

Now, I can't think of any way to possibly make this work without completely rethinking how the map generation works. So I delve into another idea: a randomly generated map in the style of a Mercator projection, a map design in which the world is laid out as though it were a cylinder.

But this also seems to be a trap, because if I were to keep generating to a rectangular map, it would be impossible to wrap if the player goes past the top or bottom borders of the map.

This may sound confusing, and if I have time later, I may include some pictures helping to illustrate my point. Until then, please feel free to help me solve the mystery of the Single-Pole Planet.

Thanks,

Selenaut

###
#2
Crossbones+ - Reputation: **14279**

Posted 27 November 2012 - 09:30 PM

If you don't want to deal with the degeneracy, you can try to use cube maps instead. They are still flat, but instead of one rectangle now you have 6 squares.

###
#3
Crossbones+ - Reputation: **9610**

Posted 27 November 2012 - 09:33 PM

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- *Pessimal Algorithms and Simplexity Analysis*

###
#5
Members - Reputation: **102**

Posted 27 November 2012 - 09:59 PM

Basically, what I'm saying is, if I'm on the equator and I move east, and IF I somehow managed to map both the north and south poles to the rectangular map, then the North Pole would appear to rotate counterclockwise, and the South Pole clockwise. Right?

...

Right?

...I have a feeling this is going to start a REALLY long debate...

###
#6
Members - Reputation: **102**

Posted 27 November 2012 - 10:05 PM

Why not just have two squares with each holding one of the poles in its center, and laying one on the bottom of the other (ignoring the obvious deformation)?

So like, the edges of the squares would be the equator, and moving east and west would rotate the tiles on the square...

Though to be perfectly honest, at this point I'm beginning to wonder if it's possible to map this with circles.

###
#7
Prime Members - Reputation: **1172**

Posted 27 November 2012 - 10:59 PM

I've never actually tackled this problem from a programming standpoint, but I did conclude that utlizing euler angles to represent coordinates (and radius-field points describing the planet's surface) would just be plain sloppy, as the angle-space is still rectangular. Eg: a pitch of 90 or -90 (where 0 is the equator) both still have 360 degrees that represent the same exact point, and would complicate physics and motion along the surface of the planet equally as much as anything else.

The best I can come up with essentially divides the spherical space into the four corners of a cube, as in top/bottom/front/back/left/right, representing everything as a sort of octal sectorization, including origin and velocity. This translates well if you always rely on a 'gravity' to pull everything toward the center, so that if something is moving linearly, and the pseudo-gravity force is applied, it will naturally 'adjust' the linear motion to follow the surface spherically, like a spline.

I figure the goal to be one where XY represent a point on the planet's surface, within a space that is uniformly distant between each point spatially and numerically (as in they correspond 1:1) and Z to be altitude, or radius. The 2D square heightfield allows this to translate easily to current graphics API directly, but as Bacterius says, you cannot map a square to a sphere.

###
#8
Members - Reputation: **270**

Posted 28 November 2012 - 01:01 AM

http://en.wikipedia....lidean_geometry

(Or:

http://www.youtube.com/watch?v=zHh9q_nKrbc)

The maths is different in non-euclidean geometry.

For example, go look at the earth's atlas. When you said that wrapping around from the south pole gets you to the north pole, that's wrong. The wraparound will keep you in the north pole except it will displace you 180 degrees to either side. For example if I am going up along the 20 degree longitude ill wraparound to the 180+20 = 200 degree longitude, then ill keep going forward and reach the south pole then wrap around back to 20 degree longitude.

Another thing is that the distance between the two ends keeps on changing depending on the latitude. If you are at the equator, and if you go east along the equator and come back to the same point you will travel 2*Pi*earth's radius distance. As you go up this distance(to keep going east until you reach the same point) keeps decreasing and at the poles, its 0.

So when you said you want to go east from the poles, you will keep standing at the same point because the pole's 'radius' is 0. (Because non-euclidean east is not the same as euclidean east)

What you actually meant to say was "I go to the north pole, turn 90 degrees to one side, then start walking" in which case, you will just switch longitudes.

So if you went to the pole along 20 degree longitude and turned 90 degrees and started walking, you would end up moving down along (20+90+180) = 290 degrees longitude. Moving along that longitude you eventually find the south pole as expected.

If you don't understand anything I am saying, get a globe of earth and an atlas of earth(which is essential a 2D representation of the earth - what you want to achieve) and move your finger around the globe and plot the path your finger takes on the atlas. Try to do the things you talked about(moving east from the pole etc.) and see how it plots on the atlas.

**Edited by MathAddict, 28 November 2012 - 01:16 AM.**

###
#9
Members - Reputation: **340**

Posted 28 November 2012 - 02:48 AM

Jeez, I'm an idiot.

Why not just have two squares with each holding one of the poles in its center, and laying one on the bottom of the other (ignoring the obvious deformation)?

So like, the edges of the squares would be the equator, and moving east and west would rotate the tiles on the square...

Though to be perfectly honest, at this point I'm beginning to wonder if it's possible to map this with circles.

Yes, using two squares is a very good way to map the sphere as it removes the coordinates singularity which is present with polar representation. You map each half of the sphere with a Stereographic projection from [-1,1]^2. Then you stitch your two mappings on the boundary of [-1,1]^2 (this is a fairly trivial step).

You can do the same with two circles (with polar mapping), but this way you'll loose the absence of coordinates singularity. So in my opinion, using two circles has no advantages.

**Edited by max343, 28 November 2012 - 04:06 AM.**

###
#10
Members - Reputation: **270**

Posted 28 November 2012 - 04:56 AM

You can try that but it won't be a very accurate simulation of a planet.Jeez, I'm an idiot.

Why not just have two squares with each holding one of the poles in its center, and laying one on the bottom of the other (ignoring the obvious deformation)?

So like, the edges of the squares would be the equator, and moving east and west would rotate the tiles on the square...

Though to be perfectly honest, at this point I'm beginning to wonder if it's possible to map this with circles.

It all depends on how accurate you want to be. If you are making a game it's fine, but it's not good for making a simulation.

To see an example of the possible inaccuracies, take a look at this picture(taken from wikipedia):

If you were to try to represent that triangle on a flat surface, you will see that the angles of the triangle will be different than the ones shown(more specifically, the angles will sum up to 180 degrees, they should not).

###
#11
Members - Reputation: **102**

Posted 28 November 2012 - 06:06 AM

Anyway, I'm only making a game, not necessarily a simulation, so distortion, however much it may occur, won't really matter much; as the planet is randomly generated, the map will look nothing like earth and so no distortion could be detected in the representation of the map.

At this point, working with two squares seems to be my best bet, but here's the new question: how would I navigate east to west and represent that on the map?

I'll explain in greater detail later, but I'm quite busy at the moment.

Thanks again,

Selenaut

###
#12
Crossbones+ - Reputation: **14279**

Posted 28 November 2012 - 07:57 AM

I think the cleanest thing to do for planet-wide terrain generation in a game is to impose any mesh you want on the sphere (I would start with a cube map) and then use 3D noise to generate elevation.

I don't know why you want to rotate the map as the player moves. Moving the camera seems a lot easier.

###
#13
Members - Reputation: **102**

Posted 28 November 2012 - 11:55 AM

So, to recap so far: Squares don't make spheres; I'm going to need a LOT more help trying to figure out how to even begin wrapping something like this; and 2D objects projected to 2D planes is nigh impossible.

Hm.

I have been thinking on and off about this all day; perhaps I could create two circles and wrap those, but the problem is loss of precision near the equator, and much more noise towards the poles. Is it possible to create an equidistant grid of sorts on a circle?

Also:

The provlem with making a cube UV is the wrapping mechanics of all of the edges. Also, I'd have to generate each face independently, and stitch them together, since the resulting UV shape isn't rectangular.I think the cleanest thing to do for planet-wide terrain generation in a game is to impose any mesh you want on the sphere (I would start with a cube map)...

What do mean by 3D Perlin noise? I'm completely familiar with the concept, but I'm confused as to how I would use it in this circumstance.and then use 3D noise to generate elevation.

I know this. That's why I'm having my problem. The land I'm generating looks like this. As you can see, it wraps in both the x and y direction; this may solve any confusion as to what exactly I meant by wrapping. If any of you are familiar with Java (I'm assuming so), here's the code for generating this:For example, go look at the earth's atlas. When you said that wrapping around from the south pole gets you to the north pole, that's wrong.

import java.util.Random; import java.awt.image.BufferedImage; import java.awt.image.WritableRaster; import java.io.*; import javax.imageio.ImageIO; public class Perlin { static int p = 8; static int size = (int)Math.pow(2,p)*4; //Multiply this by any power of 2 to get a good size image; you may be able to use other numbers, but I wouldn't reccomend it static int h = 0; public static void main(String[] args) throws IOException { Random rand = new Random(); BufferedImage image = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB); WritableRaster raster = image.getRaster(); int[][] height = new int[size][size]; int a = 0, b = 0, c = 0, d = 0, highest = 0, lowest = -1; for(int i = p-1; i > 0; i--){ int range = (int)Math.pow(2,i); int arraySize = size/range; int[][] current = new int[arraySize][arraySize]; for(int pointx = 0; pointx < arraySize; pointx++){ for(int pointy = 0; pointy < arraySize; pointy++){ current[pointx][pointy] = rand.nextInt(range); //Getting interpolation points; array gets more precise but less influential with each iteration } } for(int x = 0; x < size; x++){ for(int y = 0; y < size; y++){ int left = (x/range)%(size/range); //Getting corners; automatically wraps both horizontally and vertically using the modulus method int right = (x/range + 1)%(size/range); int up = (y/range)%(size/range); int down = (y/range + 1)%(size/range); a = current[left][up]; //Setting corners b = current[right][up]; c = current[left][down]; d = current[right][down]; h = (int)cosineInterpolate(cosineInterpolate(a, b, ((x%range)*1.0)/range), cosineInterpolate(c, d, ((x%range)*1.0)/range), ((y%range)*1.0)/range); //interpolates between the closest boundaries by interpolating horizontally on the top and bottom, then interpolating vertically height[x][y] += h; } } for(int x = 0; x < size; x++){ //Used to correct the contrast for(int y = 0; y < size; y++){ if(height[x][y] > highest){ highest = height[x][y]; } if(height[x][y] < lowest || lowest < 0){ lowest = height[x][y]; } } } } highest -= lowest; //Used to correct the contrast for(int x = 0; x < size; x++){ for(int y = 0; y < size; y++){ height[x][y] -= lowest; //Used to correct the contrast } } lowest -= lowest; //Used to correct the contrast for(int x = 0; x < size; x++){ for(int y = 0; y < size; y++){ int n = (int)(((height[x][y]*1.0)/highest)*255); //Correcting the contrast int[] green = {0, n, 0}; int[] blue = {0, 0, n}; int[] yellow = {n, n, 0}; if(height[x][y] > 128){ raster.setPixel(x, y, green); } else if(height[x][y] < 128){ raster.setPixel(x, y, blue); } else{ raster.setPixel(x, y, yellow); } } } File file = new File("perlinTest.png"); ImageIO.write(image, "png", file); } public static double cosineInterpolate(double a, double b, double x){ //Interpolates between the two specified points at a fraction x from 0-1 double ft = x * Math.PI; double f = (1 - Math.cos(ft)) * 0.5; return a*(1-f) + b*f; } }

Run that yourself, see if that gives you any ideas; I'll keep working on how I want to wrap it.

Thanks guys,

Selenaut

**Edited by Selenaut, 28 November 2012 - 11:56 AM.**

###
#14
Crossbones+ - Reputation: **14279**

Posted 28 November 2012 - 12:54 PM

What I meant by using 3D Perlin noise is something like this:

for (j=0; j<HEIGHT; ++j) { for (i=0; i<WIDTH; ++i) { longitude = 2*pi*(i/WIDTH-0.5); latitude = pi*(j/HEIGHT-0.5); x = sin(latitude)*cos(longitude); y = sin(latitude)*sin(longitude); z = cos(latitude); elevation[j][i] = perlin_3D_noise(x, y, z); } }

That will generate a map that comes from a well-behaved noise function on the sphere, and it will have all the right features, including constant values for the poles.