Devlog 3: From In-Game Shape to JSON File

Progress on the terrain generation is continuing to move along.  The triangulation algorithm for breaking up terrain shapes into took quite a bit of work, but I was eventually able to iron it out so that it works well enough for my purposes.  The source code for my ear clipping triangulation algorithm is attached below.  It does not work perfectly, but it works well enough for the purposes of this game.

function Triangulate_Terrain_Shape(shape)    
{
    
    var triangles = []    //array to hold all the triangles created from the point list, this will be returned at end of function
    
    var cp = 0;    //current point around which to check if the surrounding two points will form a valid triangle 
    
    shape = new Circular_Array(shape);    //make a circular array out of the shape
    
    var points_in_shape = shape.size    //get the number of points in the shape
    
    while (points_in_shape >= 3)    //while there are still enough points in the shape to make a triangle...
    {
        
        var curr = shape.get(cp);    //get the current point
        var next = shape.get(cp+1);    //get the next shape
        var prev = shape.get(cp-1);    //get the prev shape
        
        #region determine if triangle falls entirely within the shape    (triangle_in_shape)
        //check if the three consecutive points form a valid triangle
        var pd1=point_direction(curr.x, curr.y,
                            prev.x, prev.y);    //get direction to previous neighbor point
        var pd2=point_direction(curr.x, curr.y,
                            next.x, next.y);    //get direction to next neighbor point
        var angle_between=angle_difference(pd1, pd2);    //get angle between the two points
        
        var triangle_in_shape = angle_between > 0;    //whether the angle formed by the three points is positive, which will tell if the triangle hypotenuse is in the spape
        #endregion
        
        #region ensure no other point lies within this triangle            (point_within_triangle)
        
        var point_within_triangle = false;
        
        for (var i = 0; i < points_in_shape; i++)    //go through each other point still in the shape
        {
            var point = shape.get(i)
            if (point != prev and point != curr and point != next)    //if the currently examined point is not one of the three points being considered for this triangle...
            {
                //TODO: add handling for end and beginning of list to above condition
                if (point_in_triangle(shape.get(i).x, shape.get(i).y,
                    prev.x, prev.y,
                    curr.x, curr.y,
                    next.x, next.y))    //if the current point falls inside the triangle formed by the current three points...
                {
                    point_within_triangle = true;    //then flag the triangle as having a point within it
                    break;                            //and break from the loop
                }
            }
            
        }
        
        #endregion
        
        if (triangle_in_shape and !point_within_triangle)
        //^ if the triangle is inside the terrain shape, and there is no other terrain point withing the triangle formed by these points
        {
            //if this is reached, a valid triangle has been found
            show_debug_message("Triangle found!");
            
            var triangle = new Triangle(prev, curr, next);    //make a new triangle object from the three points
            
            shape.del(cp);    // delete the current point from the array, since it has been used to make a triangle
            
            array_push(triangles, triangle);    //add the new triangle to the triangles array
            
            points_in_shape--;    //subtract one from the number of points in the array, since a point was deleted
        }
        
            
        else // current point should only be incremented if the triangle was not valid, because if it was the removal of the point from the array will move the algorithm to the next point!!!s
        {
            if (cp >= points_in_shape)    //if the end of the points array has been reached
            cp = 0;    //go back to the beginning of the points array
            else    //otherwise...
                cp++    //increment current point
        }
        
        
        
    }
    
    return triangles    //return the array of triangles
    
}

The way the algorithm works is it loops through the points in the shape in a counter-clockwise order while there are still at least three points left using a circular array I programmed.  As it goes, it checks to see if the current point, along with its two neighboring points form a triangle that lies entirely within the overall shape.  If they do form a valid triangle, those points are made into a triangle struct, that struct is added to the array of triangles, and the current point is removed from the array of points in the shape.  If no valid triangle is formed, the algorithm simply moves on to the next point.  This continues until the shape has been completely triangulated.  Once the shape has been triangulated, the function returns a list of triangles that, when combined, make up the full shape.

After completing the triangulation algorithm, the next step was being able to save a terrain shape so that it could be rebuilt in a level of the game later.  To do this, I decided to use json to store the list of triangles for each shape into a text file, which will then be able to be read from later to rebuild the shapes in different levels.  The first step is clicking the save key, [S] in the terrain editor.  Upon clicking the save key, the game asks for a name for the shape.  This name serves as the key that will be used to access that terrain shape later.  After entering a name and clicking "OK", a function converts the list of triangles into a json string, and associates it with the key.  This string is then saved to a file called terrain.json.  The json string that gets saved to the file ends up looking like this:

{ "star": [ { "p1": { "x": 540.0, "y": 404.0 }, "p2": { "x": 488.0, "y": 311.0 }, "p3": { "x": 472.0, "y": 399.0 } }, { "p1": { "x": 540.0, "y": 404.0 }, "p2": { "x": 472.0, "y": 399.0 }, "p3": { "x": 369.0, "y": 420.0 } }, { "p1": { "x": 540.0, "y": 404.0 }, "p2": { "x": 369.0, "y": 420.0 }, "p3": { "x": 475.0, "y": 458.0 } }, { "p1": { "x": 540.0, "y": 404.0 }, "p2": { "x": 475.0, "y": 458.0 }, "p3": { "x": 509.0, "y": 564.0 } }, { "p1": { "x": 540.0, "y": 404.0 }, "p2": { "x": 509.0, "y": 564.0 }, "p3": { "x": 538.0, "y": 462.0 } }, { "p1": { "x": 540.0, "y": 404.0 }, "p2": { "x": 538.0, "y": 462.0 }, "p3": { "x": 659.0, "y": 434.0 } } ] ,}

Data from this file will be loaded later by terrain objects, which will use a key assigned in their creation code to access the data they need to generate their appropriate shapes.  These coordinates are currently room coordinates, so one change that will need to be made is converting them to coordinates whose values are offsets from the first point in the shape, rather than the room origin.  

Progress on Pogo Bouncer is moving along steadily.  Stay tuned for more!