Points and Shapes in Wandersong


Points and Shapes in Wandersong

Todays tech blog is courtesy of Greg Lobanov and discusses the use of triangles to generate the unique aesthetic used in his game Wandersong, which launches 27th of September on Steam and the Nintendo Switch.


Wandersong is a musical adventure game, and it has a LOT of different scenes! From the get-go I knew this was going to be a game about exploring lots of places, so I wanted to make a system that simplified the process of building new unique scenes, with lots of different kinds of shapes (no tiles!!!)… and that’s how the game ended up looking like this!


POINTS

These are the building blocks of geometry itself, and our starting point for making shapes. AND, our first stumbling block, because… GameMaker doesn’t have anything like them built in! In theory, for 2D, a point is basically just a position in the world… an X and a Y. To use them in Wandersong, I basically had to make up my own “point” system from scratch. I’ve done it many different ways for many games in the past, but the system I’m using now has been the most stable for me.

I use a built-in GameMaker data structure called a grid to represent a point. A grid is basically a table of information, like a 2D array if you’re familiar. But grids are messy to deal with, so I wrote a bunch of helper scripts that do all the work with grids, but let me work with them as if they were points. This is something that in programmer-terminology is called an Interface. Here are all the building blocks of my “point” system:

point(x,y)

This makes a new point with the x,y position that I specify! This returns the new point, which you have to make sure to keep track of. Because they are secretly grids, they follow the same rules. Once made, a point exists in memory forever, until it is manually deleted. So you have to be sure to delete them yourself when they aren’t being used anymore!

point_destroy(point)

That’s what this does.

point_set(point,x,y)

This changes the position of an existing point to a new position.

point_add(point,x,y)

This moves an existing point by x,y units!

point_x/y(point)

And these tell you the x and y position of an existing point.

Not actually that much code, but it forms the basis of everything, and makes all the code that deals with points much easier to follow and understand! Now we can say something like:

This makes a new point at 100,100, moves it by 50 on the x axis and 50 on the y axis, shows its x position, and then deletes it. The message should say “50,” the same as 100 + 50. Makes sense so far? It’s going to get more complicated now.


SHAPES

A shape is just a list of points! GameMaker has a data structure for this, helpfully named list already. This terrifying ugly diagram shows shape might look like, theoretically:

To the left is (a pretty version of) how it exists inside the computer’s memory. Just a list of points, one after another. On the right it shows how you might visualize that same shape. Although it isn’t specified anywhere, it’s useful to imagine that each point has an imaginary arrow to the next one, and the last point has an arrow back to the first one… that’s what forms the edges that make up the “shape” (!).

A note about GameMaker: "positive" Y actually goes DOWN, and "negative" Y goes UP, which is contrary to the standard in other engines… something to keep in mind).

And here’s the pieces that would make an interface for shapes. To be perfectly honest, there is so little code in these and they’re so close to just being regular dslist functions that I hardly ever use them… I’m comfortable working with lists directly, so I just do that. But they might be helpful to you.

shape_create()

Creates and returns a new empty shape!

shape_create_ext(point, point, etc)

This makes a new shape, but with points in it! So for example, you could say something like:

newShape = shape_create_ext(point(50,50),point(100,100),point(100,0),point(50,0));

To make the shape I showed in the above diagram…

shape_add_point(shape,point) 

Add a point to an existing shape.

shape_point(shape,index) 

A way to find out the contents of the shape. For “index” you give a number, starting from 0. So for example, to find out the first point in a shape called "coolShape", I would say firstPoint = shape_point(coolShape,0)

shape_size(shape) 

This tells you how many points are in the shape! Because you count from 0, shape_size(shape) - 1 is the index of the last point in shape. For example, if a shape has 3 points in it, they will be at indices 0, 1 and 2… there is no index 3!


TRIANGULATION

So now you can make points and shapes of any kind you want! Great! But so far they only exist as numbers and data. What if you actually want to show what they look like on the screen? This is where things get really abstract. To actually display these shapes on the screen, there is a very important middle step that has to happen called triangulation, as in, “to make into triangles.”

Why do you have to do this? You might be familiar with the way a pixel is the building block of a digital image. Well, there’s two basic standards we can think of with digital rendering… raster and vector. A “raster” image is made up of rectangles, or pixels… but to render shapes like this, we are really thinking in “vector,” which is to say, an image computed through points and lines. It’s a much more mathematical way to structure visual language, and the basis of all 3D rendering. The way computer standards are designed, to render shapes to a screen, you break them down into triangles… they’re basically the visual building blocks of a vector image, just like pixels are for raster.

Image is here solely to break up all the boring text with something nice

I’ll save you a lot more boring explanation, and say that there’s plenty of existing solutions for this problem. I adapted this code written by xot to handle my shape-and-point system. It’s way too long to paste here and already has comments to explain itself, so you can just get it here!: http://pastebin.com/asCE3NcA

It uses two other scripts written by xot: http://www.gmlscripts.com/script/point_in_triangle and http://www.gmlscripts.com/script/lines_intersect, so make sure you have those too to use it.

This script takes a shape, and returns a new list. It re-uses the points in our original shape, but arranges them in sets of 3 that form triangles. It’s actually a fairly slow (not perfectly optimised) process, so I always make sure to do it once when the shape is first made, and then store that new triangulated list and don’t touch this script again unless/until the shape changes.

One thing to keep in mind forever is that the order of points matters. Not just because their arrangement forms the shape, but because they have to be ordered in a counter-clockwise fashion as standard for this triangulation math to work. There is really no reason why it’s counter-clockwise instead of clockwise; but you have to be consistently one or the other so you can do math on them quickly! I do counter-clockwise because it seems to be more standard.

This might be the hypothetical “Create” event for a box shape object:

So much explanation, but as you can see the use is actually pretty easy… just two functions and we have a box shape, triangulated and ready to render! (Notice how the points we define for the box are made in a counter-clockwise order…).


RENDERING THE SHAPES

“CAN I MAKE A KRABBY PATTY NOW???”

Yes. We’ve arranged all the ingredients and organised everything nicely, so the job of rendering is now pretty straightforward. GameMaker comes with a very nice set of functions to render basic shapes to the screen given a bunch of points. In GameMaker, they’re called primitives (as in “primitive” or “basic” shapes). And the act of putting something on the screen is called drawing.

The way it works in GameMaker (as it does fundamentally in most engines) is you start or initiate the drawing of a primitive. You supply it a bunch of points, one by one. Then you tell it you’re done drawing the primitive. It takes all those points you gave it, does some math, and makes a shape appear! Nice!

Here is what we might put in the draw event of the above box object:

Actually, we could change the shape in the create event to basically anything, and this code would work. Because our “triangulated” list is just a list of points, we can use the same shape functions to get information from it, even though they are not arranged in the usual way I described above. As you can see, we just loop through every point in the “triangulated” list and draw its position to the screen. It’s important to note that when we draw_primitive_begin we specify the pr_trianglelist type to let GameMaker know we’re going to give it sets of 3 points that form triangles. There’s other ways to organize our points, but this is the only general-purpose one that can be used to draw ANY SHAPE.

If we put our box object in an empty black room, it would look something like this:

So much work and explanation to do something so simple!!! But once you get the hang of it, this system can be built upon to make very elaborate stuff. Like the entirety of Wandersong!

That’s a wrap for now. Take this knowledge and make awesome games with it!!!



Written by Mark Alexander

Mark Alexander is the former GameMaker technical writer. He’s moved on to pastures new, but still hangs around as admin on the GameMaker Community forum and makes his own indie games as Nocturne Games.