Draw A Stickman Epic is a game full of amazing art designed by our amazing design team but, let’s be honest, the most important art in the game is the art that you, the user, creates to interact with the fantastic world our designers have designed.
Now, every time you draw something new in the world, you do so with one of Stickman’s magic pencils. Each new pencil requires new algorithms and a lot of programming to make it behave the way you’d expect it to behave.
The most recent pencil I finished coding was the Cloud pencil, and it was quite a challenge. I’d like to explain, as best I can, how we managed to make the clouds you draw, produce rain or lightning, according to how you draw them. I’ll try to use simple English to do so but (fair warning) at times the post may get a bit technical. So let me start by explaining what didn’t work at all.
The request was fairly simple. Make a cloud pencil where the user can draw a light fluffy cloud that rains, but when the user fills it in it becomes dark and emits bursts of lightning. At first, this might seem easy. Presumably, the longer the user draws the darker the cloud, right? Not necessarily. Watching different people play this game, I noticed some people will carefully sketch out their drawings (designers), while others will draw straight lines of fire or quick scribbles for their stickman (programmers).
That said, there was no good benchmark for the amount of time a user should have to spend drawing their cloud to make it thunder. If it were too short, people who take their time drawing would get nothing but lightning clouds. If it were too long, ADD types like myself would quickly grow frustrated waiting for a dark cloud. In addition, we also have monsters in the game that require you zap them with lightning fairly quickly to stun or disable them and other puzzles where you need to deliberately create rain. It seemed that looking at drawing time wasn’t really an option. So what about “how much” the user draws?
In stickman, when the user is drawing, we record where their finger is each frame as an X,Y coordinate in a list of points that make up a line. When the user lifts their finger, that line is stored in another big list of lines. So every drawing is a big list of lists of points, and when your drawing is rendered to the screen the computer tells your graphics card to redraw those lines very, very quickly each frame. We have to do a little more work beyond this, looping over these lists to determine the drawing’s width and height and its relative position in the game world, not just on the screen, but essentially that’s process.
So, for our cloud it would seem that we could determine “how much” cloud the user has drawn by comparing the number of points they’ve drawn to the area determined from the cloud’s width and height. A lot of points in a small area make up a thunder cloud. A few points in a big area make up a rain cloud. Unfortunately, it’s not that simple.
To make your drawing manageable for the computer we have to ignore some of the points you draw. Imagine if you were to hold your finger on your touchpad or the button of your mouse for 5 seconds in the same place. If we were to store all of those in our drawing list, that would be the same point 300 times (60fps x 5 seconds). That’s a lot of unnecessary work for your tablet or computer, so of course, we don’t do that. And that’s good for our cloud, because it means we’re not accounting for a ton of points that don’t actually affect the clouds size.
But now, imagine drawing the same line, taking 5 seconds the first time you draw it and 1 second the next. Even though the lines look the same, one would have 300 points and the other only 60. So to account for that and to make things easier on your device’s graphics processor, we check to see if the points you’re drawing share the same slope (or at least a very similar slope) to the last points you drew, as you’re drawing them. We look at the point you’ve just drawn, the point before that, and the point before that point, and if the slope of the two line segments made up of those points are similar, we remove the middle point from our list.
This seems good for our (points drawn / area) cloud algorithm as well, doesn’t it? A slowly drawn line won’t have any more points than a quickly drawn line, so a cloud drawn slowly won’t have more points than the same cloud drawn quickly. But now imagine someone draws a cloud that’s perfectly square. It would only have four points. Yet, if someone drew another cloud, a circular cloud, that could fit inside that square cloud it would have... a lot of points. Infinite points were it a perfect circle. Now, I didn’t expect many of our users to draw square clouds or perfect circles, but it proves the unfortunate point that curvier clouds are going to have more points than less curvy clouds.
Our points/area algorithm simply won’t work. The numbers of points aren’t an accurate representation of the objects size, let alone its density, which is really what we’re concerned with. Dense clouds need to be lightning clouds, and less dense clouds need to be rain clouds. But density is mass per volume and clouds drawn on a computer don’t have mass. The closest thing to mass is maybe the number of points in the drawing and we just determined that won’t work.
Other than the points, what makes up the cloud? Lines. And, like the number of points, the length of these lines can be quantified. So if we look back at our square and circle again, and we measured the perimeter of both, the square’s perimeter is greater than that of our circle. That’s a good way to look at our cloud. So if we could somehow measure the length of all the lines scribbled inside one of those clouds can compare it to that cloud’s perimeter we would have a pretty good idea of how scribbly that clouds was and whether or not it should produce lightning.
But how do we know which lines the user drew are inside the cloud, and which lines make up the outside? We have to find what’s called the Convex Hull of the drawing. The convex hull is the smallest convex shape that can enclose the points that make up your cloud drawing. There are a lot of different algorithms that can find this shape given a set of points, like our drawing, but we needed an algorithm that’s very, very fast and efficient as your device needs to perform this algorithm in real time, hopefully in 1/60th of a second, if we want the game to not noticeably lag every time you use the cloud pencil.
The fastest algorithm I’ve found that can determine this convex hull is called “Andrew’s monotone chain convex hull algorithm”. If you’re still reading, and really want to fully grasp how this algorithm works, I suggest you do some further research on your own, but I’ll attempt to quickly explain it below.
To implement this algorithm with the very long, literal name we first sort the list of points in the list of lines in your drawing into a single list ordered first by their x coordinate, then by their y. We then split this list into two lists, the first representing the upper half of the cloud, the second representing its lower half. After that we can then loop over all the points in each half and compare them in groups of three using what’s called a determinant. Trying not go into too much detail, the determinant of a set of three points can tell you whether the third point of the set makes a counter-clockwise turn relative to the angle of the first two points. Here’s the formula and two examples:
determinant = (startPoint.X - midPoint.X) x (endPoint.Y - midPoint.Y) - (endPoint.X - midPoint.X) x (startPoint.Y - midPoint.Y)
determinant ((0,4),(1,3),(2,3)) = (0-1) x (3-3) – (2-1)*(4-3) = -1 (clock-wise)
determinant ((1,3),(2,3),(3,1)) = (1-2) x (1-3) – (3-2)*(3-3) = 2 (counter-clockwise)
If the value that formula spits out is greater than zero, we know the mid point is jutting into our cloud, and we remove it from our list of points that make up the outside of the cloud.
After we do this for both halves, we simply stick the halves back together by combining the two lists. If we then measure the distance between each of these points, we have the perimeter of our cloud.
Finding this convex hull is the most difficult and demanding part of seeing if the cloud you drew is a lightning cloud. After we have the perimeter of this hull, we can compare it to the length of all the lines you drew for your cloud and know that if that length is much larger (1.5 times is our current lightning threshold) than the perimeter of your cloud, you’ve drawn a very scribbly cloud.
Then we use magic to make it lightning (or rain if it isn’t very scribbly).