Handmade Hero » Forums » Code » Movement on spherical vs toroidal tile map
d7samurai
69 posts

innovation through innovation™

#1914 Movement on spherical vs toroidal tile map
3 years, 7 months ago Edited by d7samurai on Jan. 26, 2015, 4:32 p.m.

EDIT: Added illustration to make the concept easier to grasp: http://i.imgur.com/YnfT3uE.png
------------------------------------------------------------------

Wouldn't a point in explaining the difference between toroidal vs spherical topography with regards to "what happens at the edges of the tile map" be that with a spherical mapping, there is no vertical wrapping at all*? Rather, there would be a "flipping" of the vertical movement direction at the poles**: When you continue past the top of the sphere, you don't end up at the bottom of the map - you'd still be at the top of the map, but "teleported" to a new x position (i.e. shifted half the map width over), and continuing further would mean walking down along the new x coordinate***.

*Horizontal movement on a sphere would wrap like on a torus, provided the mapping is done in the traditional projection with the equator = y = HEIGHT / 2.

**If you translate "physical" movement on a sphere in such a way that moving across the pole means that you continue down on the other side, onto the "intuitively corresponding" tile map coordinates directly opposite.

***In tile map terms, this would imply negating the vertical movement speed as the pole is crossed - otherwise moving "up" would just flip the position back and forth over the pole indefinitely.

..assuming that no tile is IN a north/south pole singularity (but just "touching it" with its upper/lower edge and if we are being nice and ignore the "stretching towards infinity" along those edges), the size of the tiles as they get squashed/stretched on the torus/sphere is irrelevant. Space and time inside each tile is relative and warped to match it so it appears homogeneous to a locally positioned observer (i.e. the player).. Also, the tile map IS the local representation. The toroidal/spherical topography is a purely abstract guideline, with no implications outside the tile map edge wrapping.

To (clumsily) illustrate in the context of our tile map:

Toroidal mapping:

If you're at tile map position (X, HEIGHT - 1) and move up 1 tile, you'll find yourself at position (X, 0).

If you continue (moving up) another tile, you'll be at (X, 1) and so on.

Spherical mapping:

If you're at tile map position (X, HEIGHT - 1) and move up 1 tile, you'll find yourself at position ((X + WIDTH / 2) MOD WIDTH, HEIGHT - 1).

If you continue (moving UP) another tile, you'll be BACK at (X, HEIGHT - 1).

Unless you flip the vertical movement direction as you cross, in which case you'd find yourself at position ((X + WIDTH / 2) MOD WIDTH, HEIGHT - 2). And so on.

software development should be a creative exercise, not a technical ordeal
cmuratori
Casey Muratori
810 posts / 1 project

Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.

#1917 Movement on toroidal vs spherical map
3 years, 7 months ago

I'll have to defer to a better topologer to answer :) I think the answer is "it depends on how you unwrap the sphere". It may be that you can still get most of the wrapping to work, but you can never get rid of the singularity that collapse all wrapping down to a single point at some location, which technically would allow the player to walk to any tile in one of the tile rows at that point, etc.

- Casey
d7samurai
69 posts

innovation through innovation™

#1919 Movement on toroidal vs spherical map
3 years, 7 months ago Edited by d7samurai on Jan. 13, 2015, 7:18 p.m.

Well, in a proper spherical topology, you can't get rid of the singularity, but a tile map that is merely *inspired* by a certain topology in order to handle its edge-of-map interpretation is far simpler to.. wrap.. one's head (and algorithm) around :)

Theoretically speaking, yes, a singularity collapses the meaning of 'direction' and so the player would thus, in a sense, be "allowed" to walk to any tile. But in an implementation like this, where the world is divided into discrete tiles (or pixels) we never really reach that singularity. We sort of "teleport" from the tile just ahead of it to the tile just past it.

So in this context, I'd say that the "natural" position to end up in is the x position / longitude directly at the "opposite side" of the globe, just as if you were approaching and then crossing the real world North Pole in a straight line. And *that* is easily determinable.

Anyway, I merely wanted to mention a less theoretical way to illustrate the difference between toroidal and spherical mapping in terms of "our" (oh, the sense of community!) tile map situation - and perhaps how a spherical mapping, although implementable, would be more confusing and less practical than a toroidal one - both from a programming perspective and a gameplay perspective :)

software development should be a creative exercise, not a technical ordeal
cmuratori
Casey Muratori
810 posts / 1 project

Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.

#1925 Movement on toroidal vs spherical map
3 years, 7 months ago

But I don't think that is actually true in topological terms. If you imagine taking our tile map and wrapping it onto the sphere such that you basically "drop the sphere onto the tilemap and let it fall through", such that all edges of the tile map eventually wrap up into the singular point at the top, I think that is a valid topological way of unwrapping the sphere and highlights the fact that the only real difference is that there is one point where you can go from any edge tile in the map to any other. I think that may be the real "topological difference" - ie., it is not that the map "has to invert" or any such thing. It's just that in a spherical topology, a 2D map eventually has one point that can "teleport". But that's about it.

Again, though, I don't really know a damn thing about topology, so maybe that's not the right way to think about it!

- Casey
joeld42
Joel Davis
20 posts
#1927 Movement on toroidal vs spherical map
3 years, 7 months ago

This is, of course, all related to the most giggle-inducing name in all of mathematics, the "Hairy Ball Theorem"
khahem
4 posts
#1928 Movement on toroidal vs spherical map
3 years, 7 months ago

If you want to try alternative topology, you can find a few games here (Torus Games, Curved Spaces, Hyperbolic Games) : http://geometrygames.org/index.html.en

Another "interesting" topology for grid movements is the one used in the Befunge programming language (an esoteric language, similar to brainf***, but with a two dimensional instruction pointer).

Since the instruction pointer can move in any direction, and the memory space is conceptually infinite (but full of no-op instructions, so you don't need to traverse the infinite space to run the code), a toroidal wrapping isn't well defined when you move diagonally.
Instead it uses a topology where no matter the direction you go, you will end up where you started : http://quadium.net/funge/spec98.html#Wrapping
d7samurai
69 posts

innovation through innovation™

#1930 Movement on toroidal vs spherical map
3 years, 7 months ago Edited by d7samurai on Jan. 14, 2015, 5:01 a.m.

I see what you mean. You are thinking in terms of having only one pole - which is like having a balloon with a *rectangular opening* (that you then attempt to close up). That's perhaps trickier to land neatly.

But if you instead *choose* to have two poles - like Earth (and which probably makes more intuitive sense to a video game player anyway) - you'd essentially turn the tile map's rows and columns into a latitude / longitude grid and be much closer to a toroidal mapping.

If you took a [soft] globe and pressed a finger into each pole until your fingers touched each other, you'd almost have a torus right there.. like the top row in this picture illustrates:

http://www.cs.rutgers.edu/~decarlo/img/sphtor.jpg

Imagine the tile map being a rectangular (rubber) sheet that we fold horizontally into a tube. If we *bend* that tube so that the top rim makes contact with the bottom rim, we'd (obviously) have a torus.

But if we instead carefully "shrink" both ends of the tube [blue] (with gradually increasing intensity towards the rims) until they close up - we'd end up with a sphere [red]:

http://upload.wikimedia.org/wikip.../566px-Esfera_Arqu%C3%ADmedes.jpg

Like with the torus, *that* spherical mapping would map each pair of horizontal and vertical edges onto 'themselves' separately (avoiding the problem of "crossing dimensions" you get with a single pole).

Since we're not actually trying to *visually* map our rectangular world onto a sphere, but simply using the topology as an intuitive guideline to determine what happens if a player walks off an edge - in a world of discrete tile / pixel units - we can cheat and avoid having singularities altogether by simply imagining we're not "closing up the poles" fully.

One could picture a game where a rectangular tile map (scrolling or not) indeed was supposed to mimic a topology / topography like that of Earth, with the top and bottom rows representing the North and South pole, respectively (though being area-disproportionate).

Then, each time the player walked off the map at the top or the bottom, you would *flip
the whole map upside down* along with the player's Y position (and, importantly, with the X position shifted by half the map width and modulated):

So if the player walked off at the top of the map, he would be placed at the bottom of it, but *the map itself* would be vertically mirrored (and perhaps changed to display the "back side" of all the landscape sprites), essentially keeping him on the North pole rather than having him suddenly appear on the South pole.

That way, the player could just keep on walking in the same on-screen direction and walk all around Earth in a consistent manner.

Not saying it wouldn't be a potentially confusing mechanic (you'd need a HUD compass for sure, since "north" would change between being "up" and "down"..), but it's doable.. :)

software development should be a creative exercise, not a technical ordeal
Pseudonym
Andrew Bromage
184 posts / 1 project

Research engineer, resident maths nerd (Erdős number 3).

#1931 Movement on toroidal vs spherical map
3 years, 7 months ago

Interestingly, the Hairy Ball Theorem ("you can't comb a hairy ball smooth") has a 3D analogue, formally known as Brouwer's Theorem, but which can be stated as "every storm in a teacup must have an eye".

sub f{($f)[email protected]_;print"$f(q{$f});";}f(q{sub f{($f)[email protected]_;print"$f(q{$f});";}f});
mhristov
Mirolyub Hristov
6 posts
#1971 Movement on toroidal vs spherical map
3 years, 7 months ago Edited by Mirolyub Hristov on Jan. 15, 2015, 9:03 p.m.

You can in fact have a normal square grid which has a spherical topology instead of toroidal. The way to do it is to use the fundamental polygon:

http://en.wikipedia.org/wiki/Fundamental_polygon

If you look at the images on Wikipedia for spherical topology you can easily write a function which normalizes a coordinate to the range [0,1] such that coordinates outside are mapped as if you're on a sphere.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
struct v2 {
    float x, y;
};

v2 normalize_to_spherical_grid(v2 p) {
    int max_iterations = 10; // to avoid a loop when right on the boundary
    while ((p.x < 0.0f || p.y < 0.0f || p.x > 1.0f || p.y > 1.0f) && max_iterations-- > 0) {
        if (p.x < 0.0f) {
            p = v2{ p.y, -p.x };
        } else if (p.y < 0.0f) {
            p = v2{ -p.y, p.x };
        } else if (p.x > 1.0f) {
            p = v2{ p.y, 2.0f - p.x };
        } else if (p.y > 1.0f) {
            p = v2{ 2.0f - p.y, p.x };
        }
    }
    return p;
}


Of course, if you actually try to map this to a real 3D sphere you will find that it has severe distortion. Even when you stay in 2D some tiles behave in a weird way. For example, if you go up from the tile at (0, 0) you will end up on (0, 0) again, but your character will be rotated to the right.

Here's a small example. Just click on the grid and control with the arrow keys:

http://jsfiddle.net/fg5bLh6e/
d7samurai
69 posts

innovation through innovation™

#2087 Movement on toroidal vs spherical map
3 years, 7 months ago

This just in..

"Physicists Conjure Curves From Flat Surfaces Using Japanese Folding Art"

http://www.wired.com/2015/01/quanta-curves-from-flatness-kirigami

software development should be a creative exercise, not a technical ordeal
Fred
22 posts / 1 project

None

#2173 Movement on toroidal vs spherical map
3 years, 6 months ago Edited by Fred on Jan. 25, 2015, 1:22 a.m.

Simulating rigid body physics on a spherical world accurately is very tricky, unless your objects are really tiny compared to the curvature of the sphere (in which case the topology is locally flat).
A spherical world induces effects very similar to what's described by Einstein's theory of general relativity.

A straight line on a sphere is a great circle. When you start at a given point and want an infinitely small point to drift in a given direction, it has to follow a great circle.
But no 2 paths can be parallel on sphere - if you follow two different directions from a given point (i.e. you follow two great circles), eventually the paths will meet again.
An interesting consequence of this is when you try to imagine what it means for a finite object to "drift" on a sphere:
First picture a triangle drifting in flat space. Its three vertices simply follow 3 parallel straight lines, and the distances between them stay constant.
That's not possible on a sphere. If the three vertices of the triangle were to move each on a straight line, the triangle would stretch and/or contract, it's as if the curvature of the space is inducing some sort of pseudo force.
If you want the triangle to maintain its shape, it requires that at least 2 of the 3 corners follow small circles instead of a great circle. A small circle on a sphere is the equivalent of a curved path in flat space. And a force is required for a point to follow a curved path (you need to turn).

Einstein saw that bodies moving in a positively curved space (properties similar to a sphere) would be subjected to pseudo-forces. Once he assumed that that mass itself is curving space, he was then able to identify those pseudo-forces with gravity itself.

Negatively curved spaces, like a torus, don't have that problem. Triangles can drift freely on the surface without experiencing stretching/contracting (there are no pseudo-forces). The surface of a torus also defines true parallel paths (they never meet).

None
d7samurai
69 posts

innovation through innovation™

#2184 Movement on toroidal vs spherical map
3 years, 6 months ago Edited by d7samurai on Jan. 25, 2015, 2:15 a.m.

Although the footnotes are interesting, may I be so blunt as to remind us all that what is being discussed here is not 'proper' spherical mapping, but the approximation - the inspiration - of spherical [vs toroidal] mapping in the context of a tile map such as handmade hero's.

software development should be a creative exercise, not a technical ordeal
Fred
22 posts / 1 project

None

#2191 Movement on toroidal vs spherical map
3 years, 6 months ago Edited by Fred on Jan. 25, 2015, 1:58 p.m.

There's really no way to tile a sphere with rectangles without introducing annoying distortions and singularities at the poles.
Maybe using a cube as a base is the easiest way:
http://wiki.blender.org/uploads/t...ced-To_Sphere_cubes-spherical.png
With this you could "zoom out" from a normal rectangular 2D tile view to a 3D view showing the whole world as one big sphere.

Or you could tile a sphere properly like a soccer ball or using triangles:
http://martongaray.50webs.com/WhitePaperPolyhedronComparison.jsp.html

What's interesting too is how to do vector math in a toroidal space to deal with the wrapping. Casey seemed to think that would be too much of a pain, but I hope he will revisit this.

None
d7samurai
69 posts

innovation through innovation™

#2192 Movement on toroidal vs spherical map
3 years, 6 months ago

The point here isn't to [visually] map a rectangle onto a sphere in the geometrical sense, but merely to decide what happens at the edge of a rectangular tile map when it is encountered / crossed (I guess you could call it a "logical" mapping). Then there are ways, as explained earlier.

software development should be a creative exercise, not a technical ordeal
Fred
22 posts / 1 project

None

#2193 Movement on toroidal vs spherical map
3 years, 6 months ago

But let's say you do

http://en.wikipedia.org/wiki/File:SphereAsSquare.svg

Consider the area that's at the very top/left of the world.
At that point, when you exit the world at the top, you re-enter it on the left side!
How would you even represent that on screen when the upper-left corner of the world is where the hero stands? You would end up duplicating some of the tiles, rotated by 90 deg?

None