4d Snake

Discuss interdimensional programming, Java applets and so forth.

4d Snake

Postby Pella86 » Tue Oct 04, 2011 12:36 pm

Hi everybody,

I have recently discovered this forum, it's amazing how people on here can percieve the 4th dimension!
I have seen the 4d car and it looks amazing!

I am a biologist and some while ago I wanted to learn how to program. And since I am fascinated by 4 dimensional objects, I tried to program a little game.
Snake in 4 spatial dimensions. The game is perspectively projected.

I wrote the first version in python, but was extremly laggy, so I rewrote it in C++ and OpenGL, now the game works smoothly:
here is the explanation of the game:
http://www.youtube.com/watch?v=qCCjH3Xdw4s

here is the source code (it requires the qt libraries):
http://www.mediafire.com/?x2bjhblt1114cuq

Here I unsucseffully tried to explain how to see the 4th dimension:
http://www.youtube.com/watch?v=8IUnqm8j4BE

any comments or suggestion are appreciated!
cheers Pella
Pella86
Nullonian
 
Posts: 2
Joined: Tue Jun 28, 2011 4:16 pm

Re: 4d Snake

Postby quickfur » Thu Oct 13, 2011 11:42 pm

Welcome to the forum!

We're so glad to have new blood here... the forum has been kinda stagnating for the past while. I'll have to check out your 4D snake game! (Finally! An opengl 4D game!)

As for visualizing 4D, here's my shameless self-plug: 4D visualization. I've to admit that I'm quite limited in my free time (or to be more precise, I have too many hobbies to divide my finite free time over), so it hasn't really be updated as often as I wish and isn't as polished as I'd like it to be, but at least it does encapsulate the fundamental method I use for dealing with 4D objects.
quickfur
Pentonian
 
Posts: 2435
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: 4d Snake

Postby Pella86 » Wed Oct 19, 2011 5:36 pm

quickfur wrote:Welcome to the forum!

We're so glad to have new blood here... the forum has been kinda stagnating for the past while. I'll have to check out your 4D snake game! (Finally! An opengl 4D game!)

As for visualizing 4D, here's my shameless self-plug: 4D visualization. I've to admit that I'm quite limited in my free time (or to be more precise, I have too many hobbies to divide my finite free time over), so it hasn't really be updated as often as I wish and isn't as polished as I'd like it to be, but at least it does encapsulate the fundamental method I use for dealing with 4D objects.


When I looked at your link I was like "omg is that guy!", your pages were of great inspiration for me, I think almost all links in your page are underlined in violet in my browser. Your site is very well structured and very well explained! Compliments!


I tryied to emulate your 4d visualization but I'm not so good at writing efficent algorithms.

For example eventhought is not needed for the game, there isn't a clipping algorithm. And one thing I noticed in your renders is that you used a 4D hidden surface removal, that's really cool, but I couldn't implement it :( I tried but is difficult for me to abstract the concept from the 3d world.

There are many little mistakes in the game that doesn't affect the overall structure but anyway bother me. For example the rotations. to rotate the camera I used these functions:

Code: Select all
V4 rot_to_coord(V4 v){
    double r = v[0];
    double theta1 = v[1];
    double theta2 = v[2];
    double phi = v[3];

    double x = r*cos(theta1);
    double y = r*sin(theta1)*cos(theta2);
    double z = r*sin(theta1)*sin(theta2)*cos(phi);
    double w = r*sin(theta1)*sin(theta2)*sin(phi);

    return V4(x,y,z,w);
}

V4 coord_to_rot(V4 v){
    for(int i=0; i<4; i++){if(v[i] == 0.){ v.set_cooord(i,0.000001);}} //if it is zero to avoid a zero division later on, set with 1*10^-6
    double x = v[0];
    double y = v[1];
    double z = v[2];
    double w = v[3];
    double r = v.module();
    //source wikipedia.com
    double theta1 = atan(1/(x/sqrt(pow(w,2)+pow(z,2)+pow(y,2))));//arc_tan(1/(x/sqrt(w^2+z^2+y^2))) = arc_cot(x/sqrt(w^2+z^2+y^2))
    double theta2 = atan(1/(y/sqrt(pow(w,2)+pow(z,2))));
    double d = ((sqrt(pow(w,2)+pow(z,2))+z)/w);
    if (d == 0){d = 0.000001;} //avoid zero division
    double phi =  2*atan(1/d);
    return V4(r,theta1,theta2,phi);
}

so actually I convert in hyperspherical coordinates, and I add the needed angle displacement and I calculate back the cartesian coordinates. Which gives a wierd gimbal lock in points such as <1,0,0,0>. The rotations would be better managed by quaternions, which I tried but I'm not able to write the code for them, I think because my mathematical knowledges are limited to simple vectors geometry.

btw: most of the 4d representation I copied from the master thesis of Steve Hollasch, is freely available on the internet (and brings along the code for the OpenGL).

Best regards
Pella86
Pella86
Nullonian
 
Posts: 2
Joined: Tue Jun 28, 2011 4:16 pm

Re: 4d Snake

Postby quickfur » Thu Oct 20, 2011 6:21 pm

Pella86 wrote:[...]When I looked at your link I was like "omg is that guy!", your pages were of great inspiration for me, I think almost all links in your page are underlined in violet in my browser. Your site is very well structured and very well explained! Compliments!

Wow, thanks! I never expected my little site to generate that much interest. I hardly ever get any feedback, you see, so I've no idea what people think of it. It's only this very month that I finally put up a contact email. :lol: (I don't know why I was so paranoid about spambots...)

I tryied to emulate your 4d visualization but I'm not so good at writing efficent algorithms.

That's what this forum is for. :)

For example eventhought is not needed for the game, there isn't a clipping algorithm. And one thing I noticed in your renders is that you used a 4D hidden surface removal, that's really cool, but I couldn't implement it :( I tried but is difficult for me to abstract the concept from the 3d world.

4D clipping is hard. The only reason I could do it easily is because so far I've only rendered individual convex 4D objects. In this case it's relatively easy; you just take the halfspace inequalities and test to see if your viewpoint is above or below; if it's below, then the corresponding facet is facing away from you, so you skip it.

As soon as there are multiple objects (like multiple cubes), however, it becomes a lot harder. You can end up with arbitrary CSG operations in the resulting projection image. And once you have non-convex objects, it's much harder (in addition to CSG you need to decompose the object itself into convex chunks).

Interestingly enough, John McIntosh's 4D maze game does do clipping, but according to what he says, it's a quick-n-dirty hack that only works for cube-based mazes. I'm not sure how well it will generalize to your snake game. But it's probably worth a look: 4D maze.

There are many little mistakes in the game that doesn't affect the overall structure but anyway bother me. For example the rotations. to rotate the camera I used these functions:
[...]
so actually I convert in hyperspherical coordinates, and I add the needed angle displacement and I calculate back the cartesian coordinates. Which gives a wierd gimbal lock in points such as <1,0,0,0>. The rotations would be better managed by quaternions, which I tried but I'm not able to write the code for them, I think because my mathematical knowledges are limited to simple vectors geometry.

Camera placement in 4D is not trivial. In 3D, you can fully specify an orientation with 3 angles; in 4D, you need six angles. To simplify this somewhat, you can fix a single direction as the "vertical", and assume you will always be in an upright orientation. Suppose you choose the Z axis as vertical. Then that reduces the problem to 3 angles of rotation in the WX, WY, and XY planes, corresponding with the principal rotations in 3D. Suppose your projection is along the W axis. So that means you have a horizontal rotation in XY that looks like a 3D rotation, and two horizontal rotations (WX and WY) that look like "inside-out" rotations.

The two "inside-out" rotations change your camera's direction but the XY rotation doesn't. This means that there is an additional degree of freedom in 4D camera placement; so to fully specify a camera location, you need to fix two vectors in addition to specifying the direction of the camera (lookat-lookfrom). One of these can be fixed as the "vertical" axis; the other one is free to rotate. When any two of these vectors are parallel, you end up with the "gimbal lock" that you described.

The easiest way to work with 4D camera placement is the use matrices. Use a 5x5 homogenous matrix to incorporate translation and projection automatically. Basically, each matrix can be thought of as either a transformation of the object, or more usefully, as a mapping from one coordinate reference frame to another. To work with a camera that the user can freely rotate, one method is to set things up as follows:

  • Set up the initial camera position and orientation. To make this as simple as possible, you can just begin with a translation matrix T that corresponds with translation by some chosen vector, say (5,0,0,0), assuming you want to place your camera 5 units away from the object you're looking at. Then T would be something like:
    Code: Select all
        (1 0 0 0 5)
        (0 1 0 0 0)
    T = (0 0 1 0 0)
        (0 0 0 1 0)
        (0 0 0 0 1)

    This matrix represents a mapping from the camera's coordinate system to the object's coordinate system, so if you want to calculate the coordinates of a point P on the object in terms of the camera's coordinate system, you write P as a homogenous column vector:
    Code: Select all
        (p_1)
        (p_2)
    P = (p_3)
        (p_4)
        ( 1 )

    (The last coordinate is always 1, except if you're doing projections.) Then you compute P' = T-1*P, where T-1 is the inverse of T. This gives you the coordinates of the point P relative to the camera.
  • To rotate the camera, the most intuitive way is to perform the rotation relative to the camera's current coordinate system. However, the rotation must be relative to the object's location, since you want to always be looking at the object, just from different viewpoints. In other words, if the player wants to rotate the viewport by an angle of A in the XY plane, then you want the rotation to happen in the XY plane of the camera's coordinate system (not the object's coordinate system, since that could be in any orientation, and it will appear as a completely random rotation from the player's POV). However, the center of rotation must be the object's current location. So first you need to take the object's location L, and calculate L' = T-1*L. L' will be the center of your rotation in the camera's coordinate system. Now to rotate something relative to L' is equivalent to translating your current reference frame (the camera's reference frame) to L' such that L' is now the origin, perform the rotation, then translate L' back to where it was. So you set up a translation matrix U that corresponds to a translation by -L' (which will move L' to the origin), and then a rotation matrix R in the XY plane, rotating by the desired angle A:
    Code: Select all
        (1 0      0     0 0)
        (0 sin A -cos A 0 0)
    R = (0 cos A  sin A 0 0)
        (0 0      0     1 0)
        (0 0      0     0 1)

    The new camera's reference frame will now be represented by T' = U-1*R*U. Subsequently, you will use T' for computing the coordinates of points on the object in terms of the camera's coordinate system.
  • To perform projection, you just multiply T' by a projection matrix that projects along the vector (5,0,0,0) - the initial vector we used for placing the camera. For the purposes of projection, you can treat the vector as (1,0,0,0), so that the relative proportion of things don't change. The projection matrix is simply:
    Code: Select all
        (1 0 0 0 0)
        (0 1 0 0 0)
    P = (0 0 1 0 0)
        (0 0 0 1 0)
        (1 0 0 0 0)

    When you multiply P with a column vector, you will end up with a column vector whose last coordinate is not 1. To obtain the projected coordinates, divide the resulting vector by the last coordinate then discard the X coordinate. This simulates the scaling by distance in perspective projection. For example, if you get a column vector (1,2,3,4,5), then the projected vector is (2/5, 3/5, 4/5, 1), which corresponds to the 3D point (2/5, 3/5, 4/5).

    Now, you can actually combine the whole thing into a single matrix so that for each point in the object, you just multiply by a single matrix to place the object relative to the camera and project it at the same time. You just compute J = P*T', and then use J to do placement and projection simultaneously.

    In fact, you can even combine the projection from 3D to 2D screen coordinates by setting up a screen projection matrix S, then compute J' = S*P*T'. Then you can get directly from the object's 4D coordinates to 2D screen coordinates by multiplying J' with the object's 4D coordinates, then dividing the resulting vector by the last coordinate, and discarding the projected coordinates. The matrix algebra automatically takes care of all the details for you.

btw: most of the 4d representation I copied from the master thesis of Steve Hollasch, is freely available on the internet (and brings along the code for the OpenGL).[...]

Ah, Steve Hollasch. When searching online for 4D visualization, he inevitably comes up. His thesis has one comment which immensely helped me in visualizing 4D, and that is, that 4D spheres under illumination by a 4D light will have a 3D specular spot. This was what gave me the initial realization that 4D objects are bounded by 3D surfaces - to understand 4D objects I needed to think in terms of 3D bounding volumes, not merely 2D surfaces. That one comment was, indirectly, the inspiration for chapter 8 of my 4D visualization document. :)
quickfur
Pentonian
 
Posts: 2435
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: 4d Snake

Postby gonegahgah » Thu Nov 10, 2011 10:48 am

What is a 3D specular spot?
gonegahgah
Tetronian
 
Posts: 431
Joined: Sat Nov 05, 2011 3:27 pm
Location: Queensland, Australia

Re: 4d Snake

Postby Mrrl » Thu Nov 10, 2011 12:41 pm

I think that it's a point in the 3D image of the object where we see the reflection of the light source assuming that our object has mirror surface. For example, if we look at the hypersphere and light source is behind us then we see its reflection (and our own image) near the center of 3D ball (that is our view of the hypersphere). If sphere is not reflective but just smooth enough then we'll see bright point (or small area) near the center of the ball.
If light source is somewhere else, its reflection wee be in some other point of the ball. But it will never be on the surface (that is analogue of contours of objects in our world). So if somebody will draw a reflection of something in hyperspherical mirror, he has to draw complete 3D image of the interior of the ball, not only its visible (for us) surface.
Mrrl
Trionian
 
Posts: 165
Joined: Sun May 29, 2011 7:37 am

Re: 4d Snake

Postby quickfur » Thu Nov 10, 2011 4:32 pm

A 3D specular spot is the 4D equivalent of a specular spot in 3D (which covers a 2D area). A specular spot is just that white spot on the surface of a ball caused by reflected light, that causes our eye to interpret the surface as a curved surface. In 4D, what a 4D being sees when she looks at a hypersphere is a 3D region on the surface that looks white due to reflection of the light source. That region is the 4D equivalent of the "specular spot".
quickfur
Pentonian
 
Posts: 2435
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest