Gerrymandering

Recently launched in the App Store, Gerrymandering was originally a class project for my Casual Game Development course. It became a side project after I graduated in 2016. I created the UI for the game as well as all logic for game state and puzzle creation during the course, later working on all aspects of the game. However, a major roadblock emerged during the course of development; Although we could detect all of the possible loops of nodes that would create a "District" of voters, there was an expnential increase in the amount of districts it would detect, most of them false positives. Our original implementation for the class was creative and gave us the correct results to filter our list to only include the smallest districts that didn't overlap voters, it was incredibly slow. This limited puzzle complexity to a roughly 4x5 grid or smaller, and even this could result in stoppages of multiple seconds while the cycle search ran. After graduation, using an algorithm by Hongbo Liu and Jiaxin Wang, detailed "A new way to enumerate cycles in graph," I was able to provide a better solution for the detection of all possible cycles. This still left the task of filtering all of these cycles to provide the best list. My eventual solution was to guarantee the "winding" of the cycle to always be in the same direction, so that I could group them by starting vertex, and utilitze the new Unity Job System to multithread the sorting of each of these groups to find the smallest cycle in terms of area for each. This results in our desired set of districts, in a much faster time frame.

Links