Godot - Procedural Terrain on Irregular Grid. Coding Adventure. Devlog.

i was experimenting with different approaches and it either didn't work well enough or completely didn't work adding some effects and here you go a beautiful terrain hello everyone my name is sergei lerg and i'm starting to work on my first commercial desktop game so welcome to the beginning of this devlog series when starting a new project one of the common mistakes is trying to make a game that is simply too big you really have to start small and carefully pick an idea you are certain you can finish participating in game gems totally helps with estimating your own abilities it helped me i participated in a number of game gems it was a lot of fun and i gained a lot of experience so i can only recommend everyone to participate in game gems as well the game i'm about to start making is going to be a mix of a real time strategy game and a village builder set in the scandinavian folklore so let's begin i started with creating a mind map for my game it's just a place with random stuff for inspiration and references my main inspirations are two games developed by oscar stohlberg bednars and townscaper also there is a very nice animation called hilda at this point i still don't have a definitive vision of my game but i have a feeling of it the feeling you should get playing it so i'm going to search for a gameplay that conveys such a feeling it's gonna be a 3d game and for the game engine i picked godot i could have used unity i've made several projects with it but i like good or better of course unity is more powerful but godot is way more convenient to work with at least for me so that's why i chose it after playing townscaper one of my inspirations i've decided that i want the same irregular grid in my game the obvious question is how to make it there are some details about the implementation of it in tweets by oscar so i took them as a reference for my own implementation as for the coding i started with learning how to create a small sphere in godot and using it as the visual representation of the grid nodes then i wrote an algorithm to construct a radial hex grid with several rings and that was the easiest part in the whole process of terrain generation further was only harder to anyone who wants to implement such a grid i am going to explain the algorithm in a loop for each grid ring create six main hex points hex corners just sinus and cosinus of 60 degree angle increments multiplied by the radius of the ring then you need to be aware of the edge nodes between the main hex corners simply linearly interpolate from the first corner to the next one by a fixed amount each next ring adds one extra node in between the main corners one two three and so on the next step is to triangulate the hex grid break it down into triangles this can be done in several ways to form a triangle you need to take three vertices i decided to take two vertices on the current ring and then by adding one vertex from the previous ring form the first triangle and by adding one vertex from the next string form the second triangle when we are on the first string there is no previous ring so i am taking the center vertex continue until all triangles are formed i had to operate with a lot of indices and vertices and numbers it helped to study the math inside such a grid see what number sequences are there and represent them with formulas to use in the code the number of nodes in a ring the number of triangles in a ring vertex indices of neighboring triangles the index of the first vertex for each ring and so on with solid math research coding becomes much easier after the triangulation i need to randomly merge triangles into quads and that was very problematic to implement for me because each triangle has shared edges with other triangles and i have to keep track of neighboring triangles and mark them as used i was able to make a list of neighboring triangles but merging was too hard to implement after trying for a couple days and failing i gave up and decided to rethink my approach the main problem was keeping up with all the shared vertices and edges i understood that my way of storing vertices as plain arrays of vectors was wrong what i needed is proper classes vertex edge and phase vertex is a pair of two thoughts x and y edge is a pair of two vertices face has either three or four edges and vertices but that's not all the crucial detail is that vertex and edge classes are singletons meaning that there could be only one instance of a vertex with a given coordinates and only one instance of an edge with a given pair of vertices this works by having a hash set object inside the classes or sometimes it's called a dictionary and storing their references to all the instances this way when i am coding my merging algorithm i simply don't care if edges are shared or not i write my code as if all faces have unique vertices but vertices themselves ensure i don't screw up because there are singletons after that change writing the rest of the merging algorithm was trivial this situation shows an important lesson for developers when we think about algorithms we mostly think about ways of processing data not ways of storing data but how you store data is very important and in my case it was crucial having a good data structure is the half of a solution there even exists a data-driven design or a data-driven approach you probably heard about it anyway after randomly merging the triangles into quads some triangles are left without a pair those triangles will give us this interesting irregular look of the grid later the next step is subdividing each phase again with the new data structure the code is trival for each phase find the centroid point and depending on the amount of vertices construct either one or another set of new faces in this process all solar triangles are converted into three quads and we end up with no triangular faces when subdividing is done the next step is the most interesting also the most challenging people call it relaxing the grid but in my mind it's more like squarifying the grid the main idea is to move vertices around so that each grid cell looks more like a square they can't be exactly rectangular but trying to be so results in a nice unified look of the grid i was experimenting with different approaches and it either didn't work well enough or completely didn't work resulting in a garbage meshes eventually in a few days i came up with a solution the algorithm is multi-step in my case i make 100 iterations on each step i calculate the average area of a grid cell from that area i can calculate the length of a side of the square with the same area actually for my algorithm i need the diagonal half the diagonal to be precise let's call this value d for each phase i calculate its centroid point from that point i cast array towards a vertex of the face and find a new point with the distance of d from the centroid with the centroid point and the new point i can construct a hypothetical square that this given face wants to become i repeat this process for each vertex of the face and out of four variants i pick the one hypothetical square that is closest to the current vertices of the face the one that requires the least amount of force to move to i calculate the force for each vertex and store it in a hash set accumulating forces while processing all faces after looping over all faces i loop over all vertices and apply accumulated force for each vertex nudging it by small steps towards hypothetical square shapes and after days of work the result is this beautiful grid isn't it gorgeous you can imagine right away streets hills and rivers on it i love how fluid the grid becomes during the process i ran the code over and over just to enjoy watching it move mesmerizing with the grid done i now need to create terrain for my game since all grid cells are almost square i decided to take a cube at the bases i took the built-in mesh of a cube in godom copied its vertices with some other mesh data and modified it to match my grid cells to my surprise the vertex array of the cube has quite a peculiar layout i was expecting that each four consecutive vertices would form a single phase but instead at the beginning for odd vertices form one face and even vertices form an opposite face so vertices 0 2 4 6 belong to one face and vertices 1 3 5 7 to another face if you know why it is this way please let me know in the comments here is the full list of what vertices form what faces for terrain generation i use parallel noise simply getting the noise value at x y coordinates of the centroid of each grid cell if the value is below some threshold i mark it up as water and if it's above some other threshold i mark it as rocks adding a simple camera controlling script that i wrote for my other prototype adjusting lighting shadows adding some effects and here you go a beautiful terrain all that is left is to add some native inhabitants here much better hello mr troll how do you like your new home mr troll enjoy it while you can mr troll at this point i've decided that this is enough progress for the first devlog and i started working on this video i hope you enjoyed it if so don't forget to subscribe to my channel and if you want to try the game in its current early state you can download it for windows or mac os on my patreon page patreon.com learg the link is in their description as well please consider supporting me on patreon the more support i get the more time i can devote to working on the game big thanks to all my current patreon supporters you guys truck you may also want to enable the notification belt for my channel i don't release videos often and with the notification you can be sure not to miss my next video in your subscription feed next i will be working on structures and villagers thank you for watching you

Channel: Sergey Lerg

Views: 11,036

Rating: 4.9425054 out of 5

Keywords: procedural, terrain, generation, devlog, godot, c#, gamedev, unity

Id: Jm3pLya3d9c

Length: 15min 29sec (929 seconds)

Published: Sun Sep 13 2020

Reddit Comments

[u/RosenrothGG]

That's a cool dev log! Some of the maths goes over my head though, what branch of Maths should one study in order to be comfortable with programming such concepts? Trigonometry?

[u/Spleen_Stealer]

This is so cool

[u/Im_Peter_Barakan]

How has this complicated other aspects, such as pathfinding?