Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


The Intriguing Problem with Map Wrapping


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 Selenaut   Members   -  Reputation: 102

Like
0Likes
Like

Posted 27 November 2012 - 09:25 PM

Hello all, I have been working on a program for quite a while involving randomly generating a "planet." This may sound like quite a challenging task, but the initial stuff needed, like generating a wrapped height map, was simple. What I did was generate a 2D array of wrapped Perlin noise, or some sort of variation on it.

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

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13623

Like
0Likes
Like

Posted 27 November 2012 - 09:30 PM

The traditional parametrization of the sphere using latitude and longitude wraps only left-to-right. All the points at the top edge map to the North pole and the points at the bottom edge map to the South pole.

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 Bacterius   Crossbones+   -  Reputation: 9041

Like
0Likes
Like

Posted 27 November 2012 - 09:33 PM

Well, you cannot wrap a square or rectangle around a sphere, so your endeavour is already doomed to fail. One thing I can think of is a toroidal mapping, which is just a rectangle mapped around a torus (the edges of the rectangle wrap naturally) but it's not really a planet any more. Though if the planet is large enough the player might not even realise that if you are only concerned with close-range gameplay.

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


#4 Álvaro   Crossbones+   -  Reputation: 13623

Like
0Likes
Like

Posted 27 November 2012 - 09:48 PM

By the way, if you don't want things to end up looking different around the poles, you can try using 3D Perlin noise.

#5 Selenaut   Members   -  Reputation: 102

Like
0Likes
Like

Posted 27 November 2012 - 09:59 PM

I didn't really want to get into this idea before I had more of a chance to think about it, but what if (and I'm honestly not sure whether this is what the whole cube concept is) I had the map move rather than the player, and actually rotated the map according to how it would on an actual sphere?

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 Selenaut   Members   -  Reputation: 102

Like
0Likes
Like

Posted 27 November 2012 - 10:05 PM

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.

#7 radioteeth   Prime Members   -  Reputation: 1101

Like
0Likes
Like

Posted 27 November 2012 - 10:59 PM

I worked a project called Revolude (http://www.sourceforge.net/projects/revolude/) that features wrap-around procedural maps, using the 2D heightfield approach, but I knew from the very beginning that this would inherently prevent any 'spherical' landscapes from being produced. A torus is closer, but more of a cross between a wrap-around square and a sphere, where instead of poles you merely have a smaller diameter of space (unless your inner-diameter is zero, but still funky).

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 MathAddict   Members   -  Reputation: 270

Like
0Likes
Like

Posted 28 November 2012 - 01:01 AM

Look up non-euclidean surfaces and non-euclidean geometry.
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 max343   Members   -  Reputation: 340

Like
0Likes
Like

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 MathAddict   Members   -  Reputation: 270

Like
0Likes
Like

Posted 28 November 2012 - 04:56 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.

You can try that but it won't be a very accurate simulation of a planet.
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):
Posted Image
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 Selenaut   Members   -  Reputation: 102

Like
0Likes
Like

Posted 28 November 2012 - 06:06 AM

Thanks for the replies so far guys.

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 Álvaro   Crossbones+   -  Reputation: 13623

Like
0Likes
Like

Posted 28 November 2012 - 07:57 AM

Humanity has been dealing with this problem for a long time, because we have a round planet and flat paper to make maps of it. You can get an overview of the subject from the Wikipedia page on map projections. The more general problem of describing mathematical objects using charts is dealt with in Differential Geometry.

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 Selenaut   Members   -  Reputation: 102

Like
0Likes
Like

Posted 28 November 2012 - 11:55 AM

Since I'm going to be having the view act similarly to Dwarf Fortress, kind of like bird's-eye, moving the player and moving the camera are essentially the same thing. The reason I'd like to rotate the land around the player is to prevent confusion at the wrapping edges.

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:

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)...

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.

and then use 3D noise to generate elevation.

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.

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.

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:
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 Álvaro   Crossbones+   -  Reputation: 13623

Like
0Likes
Like

Posted 28 November 2012 - 12:54 PM

If your map is supposed to be a map of elevation on a sphere, the top edge of the map should have a single constant value (elevation of the North pole), and similarly for the bottom edge. So your map is obviously not that of a function on the sphere.

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS