Graph Theory Synchronicity
Of course, the drama is always at the finish line. Building Hypotenuse, obviously, involves tons of Math and Computer Science tricks but one important feature, a major // TODO, which is really what makes the game, that feature of detecting whenever a player constructed a regular polygon so that I can properly keep score, I saved for the end. Of course, it wasn’t intended to be squeezed into the app in the final days before the launch but… well… ok, this is how it happened:
After getting accepted to AmazeFest and Berlin Games Week 2018, I decided that I would make that my goal for launching Hypotenuse. There were still a few things to do here and there but I was feeling pretty good about the state of the game. So I decided it was time to clean up (refactor in programmer lingo) my ShapeFinder algorithm, or rather PolygonFinder algorithm. I had had something working to detect drawn polygons but, as I had written most of math utility classes last summer while visiting Munich and after reflecting on those long hot days in the Englischer Gartens unquestionably followed by a few bavarian-sized Hofbräus, I thought that I should probably do a once-over of that code before launching in time for the Berlin Game festival week. My temporary technique was to just loop backwards through the array of lines and check if the last few lines had matching lengths and angles. That’s easy, right? All polygons have matching sides and share the same angles. But this approach only allows for the player to score polygons by drawing lines in sequence. It wasn’t a very good algorithm but it worked as a placeholder and was pretty isolated in the code, so I just kept knocking off other features hoping that it wouldn’t cost me too many evenings of work once I got around to it taking a stab at it again. But now, with the dead line approaching, I rolled up my sleeves and got coding.
So the problem I needed to solve was to optimally find the best way to loop through all my drawn points and lines and discover all the possible shapes or polygons therein.
Enter Graph Theory.
As I was speeding reading through Minko Gechev’s recent awesomeness in the JS web world, I expanded, obviously, the section titled Mathematical Background and behold, the Basics of Graph Theory. Oh, right, I remember seeing that a while ago on Mathigon and wait, don’t I have a kindle pdf version of Graph Theory Book? My intuition told me I was on to something. So I began reading as much as I could about Graph Theory and suddenly I felt as though I had walked through the Wardrobe into Narnia. There’s just so much cool stuff in Graph Theory. Euler’s formula, no, not that one, nope, not that one either, oh, yes, that one one about the faces in a Graph; all those cool bridge problems; networks and search algorithms and it’s myriad of applications for Computer Science… but wait, let’s not get distracted, we’re doing Geometry here. So how does Graph Theory solve my geometry problem? Well, remember those innocent and pure geometrical definitions of Point and Line (see previous post)? It turns out they have undercover aliases in the graph theory underworld. They’re known as Vertex and Edge and together they form the Graph gang. And, as it goes, every time someone creates some cool geometrical design, they’re also constructing a Graph which the rules of Graph Theory can be applied to.
Well, to make a long story short, I spent many many nights trying to roll my own quasi Depth-First-Bently-Ottman-Dijkstra’s-Recursive-Nightmare-Polygon-Search algorithm wishing dearly for more Hofbräus when, in the end, it turned out I was sitting on the solution the whole time.
GameplayKit’s pathfinding tools saved the day, and that folks, is why this game is made for iOS. See the article below.
Finally, I could replace my ugly inelegant Hofbräu influenced solution (“if it isn’t beautiful it isn’t mathematics”, an axiom which also applies to programming) with some beautiful Mathematics worked out by some amazing engineers behind GameplayKit. Sometimes it is satisfying to write your own solution but other times it’s just as satisfying to use a hammer someone else made in order to smash in those pesky nails. And, as always, I learned a ton along the way.
Here are a few of the many sources I stumbled upon that really got me excited about this amazingly cool branch of mathematics.
And check out the Swift Algorithm Club and Polygon detection with the Bently-Ottmann line intersection algorithm.
