Jump to content


Photo
* * * * * 6 votes

3D planet generation inc. geodesic hex tiling and window system


  • Please log in to reply
17 replies to this topic

#1 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 23 June 2015 - 03:26 PM

Juju's Planet Model v28

A project to explore procedural generation

 

NyxfCGY.png

 
  • Title: Planet Model
  • Description: Procedural generation example
  • GM Version:  Studio
  • Registered: yes
  • File Type: gmz and exe in a .zip
  • File Size: 2.3 MB
  • File Link:  here
  • Required Extension:  none
  • Required DLL:  none
Summary
Key features include:
  • Geodesic hex tiling - a first for GameMaker
  • Real-time procedural generation that doesn't freeze the game
  • Six-degrees of freedom using quaternions
  • Detailed terrain engine
  • Nifty little window system that allows for windows-within-windows
  • Smooth frame rate throughout
I'm using the latest version of GM:S, though it would probably work under earlier versions too. The project is YYC compatible and I strongly recommend you use the compiler.
 
In the spirit of open-source development, I'd like to share with you lot a project I've been working on for a few weeks. Ever since I laid eyes upon Planetarium, a closed-source pseudo-3D world generator made in GameMaker, I knew I wanted to make something experimental in the world generation area. I've been fascinated by world generation in general for years but only recently have had the confidence to approach something that not even the Civilization series has touched.
 
Geodesic domes are a way to tile a sphere with regular shapes, you may be familiar with them as they're used quite frequently for futuristic biodomes. It's not perfect but it's as close as you can mathematically get. The method is actually quite straightforward: you take a 20-sided polyhedron (i.e. a d20 die), you subdivide each triangle a few times, and then you gather up 6 adjacent triangles that share a point and call that a hexagon. Some locations (exactly twelve, actually) will be pentagons, unfortunately, but that's the price you pay. Thematically speaking, you can explain that away and simply block off those locations with big mountains! This web of hexagons can then be treated as a surface and standard procedural generation techniques can be applied to get the desired result.

 

Of course, this process of subdivision, collection and generation isn't instant. After the first subdivision, you have 60 triangles. Then it grows to 180, 540, 1620... at seven subdivisions, you have an eye-watering 43'740 triangles! The triangle collection and terrain generation algorithms take just as long. As a result, each step of the generation system is broken down piece by piece so that the frame rate doesn't drop crazy low. There's no awkward pause and no real loading screen - though in this stripped-down example, there's not a lot for the user to do whilst the generator is working its magic.
 

y7de9vmm.pngtMw9aVfm.png

It's tree-mendous!

 
Part of dealing with a fully 3D model, quite different to virtually every strategy game ever made, is that the player needs to be able to explore every nook and cranny of the world. This is where a mathematical tool knowns as quaternions come in handy. Now, I'm no expert on quaternions but fortunately an old example by a chap named Boris helped me out a lot. Links to his work are included in the comments on the quaternion scripts. The rotation around the globe is fluid and completely free. You can swoop down and check out my ropey modelling skills or lean back and look at the whole globe.
 
There's also a neat little window system that plays nicely alongside d3d functions, an accurate in-built system that finds what tile the player is pointing at (harder than it sounds), and the terrain generator itself. These things can be flipped around and used in other projects too - they operate quite independently and there is commenting throughout.
 
All this stuff is absolutely free for you to use and base your games off, no credit needed (though it is appreciated). If you'd like to keep up-to-date with this engine's development, hop on over to GameMaker's Reddit community at /r/gamemaker.

Edited by Juju, 23 March 2016 - 12:07 AM.
added template

  • 20

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#2 chance

chance

    GMC Member

  • Global Moderators
  • 8762 posts
  • Version:GM:Studio

Posted 23 June 2015 - 05:05 PM

This is lots of fun.  There's ton of useful stuff here.  :thumbsup:

 

Whether or not someone uses this entire engine, or just learns from certain parts of it, there's plenty of neat tricks and techniques.  So it's bound to be useful.  And the example is nicely divided into well-commented scripts.

 

It's not an example for beginners.  But experienced programmers with a good mathematics background should be able to follow it.


  • 0

#3 dadio

dadio

    Potato King

  • YoYo Games Staff
  • 2740 posts
  • Version:GM:Studio

Posted 23 June 2015 - 06:14 PM

Very, verrry tasty!

And as chance said, the scripts are all nicely commented!

Fantastic work! :)

Hope to see more from you in the future!


  • 0

AczgxAZ.png5aj9t5.jpg
 


#4 Dragon47

Dragon47

    Mytino

  • GMC Member
  • 687 posts
  • Version:GM:Studio

Posted 24 June 2015 - 05:57 AM

This looks amazing! :D


  • 0

wfoEubT.png       BNY6m3V.png       cfwjSDg.png       jermsLg.png       WqPXsGB.png

 

Games:   Blue Void (3D horror)   Icebound (2D puzzle platformer)


#5 SecularBaron

SecularBaron

    GMC Member

  • New Member
  • 3 posts
  • Version:GM:Studio

Posted 27 June 2015 - 02:00 PM

This is amazing. If only I had the knowledge to manipulate it. 


  • 0

#6 TheSnidr

TheSnidr

    Heavy metal viking dentist

  • GMC Elder
  • 3345 posts
  • Version:GM:Studio

Posted 27 June 2015 - 02:18 PM

This looks amazing. Fantastic work! Definitely gonna check out your code!

I was messing around with stuff like this myself a few years ago, but this beats anything I've ever made. Makes me pretty nostalgic seeing this actually!


  • 0

#7 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 27 June 2015 - 10:58 PM

I think the trick is abandoning textures and going full-on block colour. I've fixed quite a few bugs (especially with the window system) so I'll be rolling out an update soon.


  • 0

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#8 Joe H

Joe H

    GMC Member

  • GMC Member
  • 359 posts
  • Version:GM:Studio

Posted 04 July 2015 - 04:12 AM

This is an incredible piece of work and lots of fun just to look at. The commenting seems excellent and there is a bit of humor in there as well.

 

@Juju:

 

Would you take a moment to help me adopt your mouse system?

 

I can't seem to make the mouse vector coordinates useful. My goal is allow the player to click on objects that exist on a globe. I hope to do this by either checking the 3D distance between the object and the click or by comparing the Latitude and Longitude on the object and the click.

 

If I understand correctly, your mouse script finds a reference angle between the camera and the mouse position in reference to the origin. You then compare those angles to all of the hexes to find which is "closest" to the one derived from the mouse position. My description isn't very good, but basically you're finding and vector, transforming it and finding which hex matches up?

 

Does your script find actual coordinates that are used on the globe? Are the coordinates used in some other way?

 

I appreciate the time you took to post your example. I always love playing with GM when there is something interesting to explore.


  • 0

Independent Games by Joe and Matt:
evg_logo_header_125h.png

Spoiler

#9 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 04 July 2015 - 07:05 AM

Right! Yep, let's jump in. For the benefit of anyone who's lurking, we'll be talking about three_dee_glasses_obj and specifically the step event. We're in the third action, a code block named "Mouse controls".

 

The function get_3d_mouse_vector() is an adaptation of a wonderful script that Yourself posted on this very forum years ago. What it does is figure out the direction vector going from the centre of the camera, through the mouse pointer, and off to infinity (and beyooond). This is quite a strange concept compared to 2D games - the mouse on the screen as the user sees it is not actually a single definable point in 3D space. Because we treat the camera as a single infinitesimal observer, and because we don't define a plane that the mouse sits on, the mouse pointer has a somewhat indeterminate position. We're fortunate though because we can work out a direction vector (which is probably more useful anyway).

 

The globe is basically a sphere. There are some shenanigans relating to the different hex heights (modelled within the code as many nested spheres of different radii) but for now let's just say the globe is a sphere. If we take the camera's location and the direction vector, we can create a line that shoots off to infinity with meaningful parameters - we can say where is start, where it heads off to, and we can find positions along that line by incrementing a single parameter. get_line_sphere_intersection() takes this line described above, grabs the sphere (handily placed at the origin), and works out where (if at all) the line intersects the sphere. The function returns a position vector that goes from the origin to the point on the sphere where the mouse is pointing.

 

Hold on! We can't forget that the globe has been rotated. quaternion_rotate_vector_left() is used to ensure that the current transformation that's being used on the globe is appropriately applied to this position vector as well. Quaternions are a bit wacky, I don't understand them in depth so I won't be explaining why we use _left versus _right here. Needless to say there are only two options and, yes, I did just try both until it worked...

 

What can we do with this point on the sphere? You can turn that point into latitude and longitude if you'd like (see below) or use that position vector to work out the hex id of the position the user is pointing at. There are loads of ways of doing this but I happened upon what is probably the best piece of analytical geometry I've ever programmed. If you compare all the hex's position vectors with where the user is pointing, the selected hex is going to be the one where the angle between the position vector of the hex and the position vector of where the mouse is pointing is the smallest.

 

What makes any graphics computation slow is the necessary use of square roots and trigonometry. If at any point in your code, you can work out a way to chop out a square root or a trig function, even if it means doing some nasty pre-computation and using up a ton of memory, you will be gained extra CPU cycles to do other more interesting things. With a bit of a leap of faith, we can use the geometric dot product to do a lot of the heavy lifting without needing to use too much nasty computation.

 

The dot product is this:

A dot B = ( a_x * b_x ) + ( a_y * b_y ) + ( a_z * b_z );

You can see that this is going to be a fast operation. The dot product also has another definition:

A dot B = length( A ) * length( B ) * cos( angle );

If we want to find the smallest angle, and since cosine decreases from 1 to -1 with angular values from 0 to pi, then we want to find values of cos(angle) closest to 1. We do this by using the normalised dot product which turns (internally) the length of vectors A and B into vectors of length 1. This effectively removes the length() functions and gives us access directly to cos(). We can then chug through every single one of the hexes, quickly compute their normalised dot product, and find the largest value of cos() / the smallest angle. No need to even mention trigonometrical functions!

 

And we're done. We've gone from a lonely mouse pointer and camera position to a selected hex on the globe. Now, you may be wondering about latitude and longitude... I've not found that concept to be particularly useful in this implementation, truth be told. Because all the rotation transformations I'm applying use quaternions, it seems to be safer to me to work in Cartesian coordinates and let the clever maths do the hard work for me trig-wise. Regardless, you might want to use that coordinate system to add a certain kind of naval decal to the globe. Far be it from me to judge.

 

Err... Unfortunately, I kinda botched the coordinate system so you can't just read off a solution from MathWorld... This is down to use the wrong orientation of x, y and z. Here's an implementation that returns sensible results:

h = ds_list_find_value( world_obj.terrain_height_list, mouse_touch_id ) * 5;

xx = touch_x[h];
yy = touch_y[h];
zz = touch_z[h];

r = point_distance_3d( 0, 0, 0, xx, yy, zz );
phi   = arctan2( zz, xx );
theta = arccos( yy / r );

That having been said, and in my experience developing this project further, have your objects sit on hexes rather than be independently defined. If they're sitting ontop of hexes then you can just use mouse_touch_id to make quick mouse-over checks. If you really don't want to deal with that then go to Cartesian coordinates and liberally sprinkle quaternions on your code. Spherical coordinates will just cause you headaches because of the quaternion rotation system. I've not looked into applying quaternion transformations to spherical coordinates but - and I'm working from instinct here rather than explicit experience - it's not going to be pretty, it's going to involve a lot of trig, and it's going to be slow.


Edited by Juju, 04 July 2015 - 07:05 AM.

  • 1

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#10 Joe H

Joe H

    GMC Member

  • GMC Member
  • 359 posts
  • Version:GM:Studio

Posted 04 July 2015 - 05:06 PM

 

That having been said, and in my experience developing this project further, have your objects sit on hexes rather than be independently defined.

 

I knew you were going to say that! What I'm going for is more like an airplane that flies over the planet, that isn't locked into the hex grid. Using Lat and Long allow me to easily draw it's position in the sky (in relation to the planet). I'd like to be able to accurately click on that plane .

 

So, let me wrap my head around this and hopefully you can advise me in where I am going wrong:
We are finding a "Direction Vector" that runs from the origin of the camera (the camera's location), THROUGH the (hypothetical) mouse position, and finally (potentially) through the globe at some point.

We are finding a "Direction Vector" that runs from the origin of the camera (the camera's location), (potentially) THROUGH the globe, then finally THROUGH the (hypothetical) mouse position which is some location "beyond" the globe itself.

 

Therefore, if I have a sphere (my globe) at position 0,0,0 with a radius of 250, and my camera location is 1000px away from my origin (on let's say the X-axis), I would use the following code to find where the mouse is pointing:

 

For my camera: (note, I used the z adjustment for orientation as opposed to the y adjustment in your demo)

d3d_set_projection_ext(cam_x, cam_y, cam_z,   0,0,0,   0,0,1,   30, room_width / room_height, 1, 5000 );
// cam_x = 1000   cam_y = 0  cam_z = 0









In the step event to find the mouse vector (the "Direction Vector")

scr_get_3d_mouse_vector( cam_x, cam_y, cam_z, 0,0,sphere_radius, 0,0,1, 30, room_width / room_height );

// sphere_radius = 250

// The follow three values are calculated in the array result_coord by the script scr_get_3d_mouse_vector (for anyone else trying to follow along)
mouse_vx = result_coord[0];
mouse_vy = result_coord[1];
mouse_vz = result_coord[2];





 

Then, still in the step event I use the new mouse vector coordinates to generate a new vector that passes through the globe from INSIDE OUT ( I think...)

for( i = 0; i <= 1; i += 0.2 ) {
        if ( scr_get_line_sphere_intersection( cam_x, cam_y, cam_z,   mouse_vx, mouse_vy, mouse_vz,   0 ) <> 0 ) mouse_is_touching = true;
        touch_x[i*5] = result_coord[0];
        touch_y[i*5] = result_coord[1];
        touch_z[i*5] = result_coord[2];
    }

Because I have not rotated my globe at all I'm going to leave out the quaternion rotation for this example.

 

The coordinates touch_x, touch_y, and touch_z should be the point on the sphere where the mouse is touching. Therefore, if I drew a ellipsoid using those coordinates, it would be drawn on the sphere. Correct? What I've found is that my sphere sits at the origin of the globe.

 

I'm sure that I am doing something wrong here!


Edited by Joe H, 04 July 2015 - 05:14 PM.

  • 0

Independent Games by Joe and Matt:
evg_logo_header_125h.png

Spoiler

#11 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 04 July 2015 - 10:11 PM

I knew you were going to say that!

Damn, I hate being predictable :P

 

Let's sort out that first bit of code. The arguments for get_3d_mouse_vector() are broadly the same as the projection you're using, as defined by the internal function d3d_set_projection_ext(). Your code should be:

scr_get_3d_mouse_vector(cam_x, cam_y, cam_z,   0,0,0,   0,0,1,   30, room_width / room_height, 1, 5000 );

Grand. Next thing is that you don't need to worry about the for loop or using an array to store the touch coordinates or anything like that -  you've got one sphere and it exists at one defined radius.

if ( scr_get_line_sphere_intersection( cam_x, cam_y, cam_z,   mouse_vx, mouse_vy, mouse_vz,   sphere_radius ) != 0 ) {
    mouse_is_touching = true;
    touch_x = result_coord[0];
    touch_y = result_coord[1];
    touch_z = result_coord[2];
} else {
    mouse_is_touching = false;
}

That shooould sort you out.

 

Next up, time to look at your general conceptual statements:

We are finding a "Direction Vector" that runs from the origin of the camera (the camera's location), (potentially) THROUGH the globe, then finally THROUGH the (hypothetical) mouse position which is some location "beyond" the globe itself.

I prefer to think of the mouse pointer as the line itself but, yes, that's basically what's happening.

 

I used the z adjustment for orientation as opposed to the y adjustment in your demo

Please do! One of my biggest regrets is not doing the axes properly. One day, I'll have to go in and correct that.

 

a new vector that passes through the globe from INSIDE OUT

Yup, you've got it.

 

The coordinates touch_x, touch_y, and touch_z should be the point on the sphere where the mouse is touching. Therefore, if I drew a ellipsoid using those coordinates, it would be drawn on the sphere. Correct?

Should be, if everything's gone according to plan.


Edited by Juju, 04 July 2015 - 10:15 PM.

  • 0

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#12 Joe H

Joe H

    GMC Member

  • GMC Member
  • 359 posts
  • Version:GM:Studio

Posted 05 July 2015 - 02:18 AM

SUCCESS!

 

It works perfectly. Juju, you are a true scholar and have my most sincere gratitude! If I owned a "study" and had big leather chairs I'd invite you over for cigars and scotch (well, I suppose I'd have to own cigars and scotch too). But seriously, thank you for your help. I look forward to seeing what you do with this project. Write more tutorials! Your commenting reads like a (very entertaining) book and that's hard to do.

 

 

I prefer to think of the mouse pointer as the line itself but, yes, that's basically what's happening.

 

Woooahhh......

 

 

Please do! One of my biggest regrets is not doing the axes properly. One day, I'll have to go in and correct that.

 

I wouldn't worry too  much. I programmed an game using a negative z value because it worked for what I needed it to do!

 

 

 

Should be, if everything's gone according to plan.

 

And it has, thank you again.

 

This is a great tutorial and well commented. I haven't been around lately to see if there are any changes to the tutorial requirements, but this should be looked at for staff picks.


  • 0

Independent Games by Joe and Matt:
evg_logo_header_125h.png

Spoiler

#13 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 05 July 2015 - 07:01 AM

Woooahhh......

I know right?! Vectors and 3D spaces are a constant source of intrigue for me. To be perfectly honest, most of the clever stuff in this example comes from the hard work of other people and this'd be nowhere without Yourself, Boris and xot.

 

I haven't been around lately to see if there are any changes to the tutorial requirements

I'd consider this an example of something cool rather than a tutorial at the minute. I'd really need to do a step-by-step walkthrough to truly educate people.

 

Juju, you are a true scholar

If only I'd finished that science degree...


Edited by Juju, 05 July 2015 - 07:05 AM.

  • 0

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#14 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 08 August 2015 - 09:28 PM

v28

 

8WGkGjT.png


Edited by Juju, 25 August 2015 - 05:00 AM.

  • 2

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.


#15 local306

local306

    GMC Member

  • GMC Member
  • 104 posts
  • Version:GM:Studio

Posted 07 November 2015 - 05:20 PM

Whoa! This is absolutely incredible! So beautifully detailed and super smooth!


  • 0

#16 Ruub

Ruub

    Finn The Human

  • GMC Member
  • 762 posts
  • Version:GM:Studio

Posted 15 February 2016 - 01:52 PM

Hi JuJu, I thought why not suggest putting this on GameMaker's market? Even if you wouldn't ask a price, which would be fine, more people would enjoy it ;D


  • 0

#17 hippyman

hippyman

    Dirty Stinky Hippy

  • GMC Member
  • 837 posts
  • Version:GM:Studio

Posted 21 March 2016 - 03:00 PM

Is this gone? All the DL links are broken


  • 0

 badge.png?dl=0

HM Audio Soundcloud: https://soundcloud.com/hm-audio


#18 Juju

Juju

    GMC Member

  • GMC Member
  • 1109 posts
  • Version:Unknown

Posted 23 March 2016 - 12:08 AM

Thanks for alerting me to the broken link. Should be fixed now.
  • 1

Come find me @jujuadams

 

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.