Blue: Crystal snake using Voronoi; Red: Ruby snake using DFS
As a sponsor in the Battlesnake event, each company is tasked with creating a bounty snake that participants can challenge for a potential prize. The variant we chose was a tron-styled game where the tail of the snake remains stationary and no food is available.
It's compiled! It's typed! It's fast! Also my background is in Ruby and Elixir. This was my first time using Crystal.
There are two phases:
Voronoi Analysis: maxmizing the area controlled by my snake
Survival Mode: using remaining space as efficiently and compactly as possible
The voronoi heuristic is useful for determining how much area a user controls. The basic premise is to use a flood fill algorithm (or however you want to do it) to find the minimum distance required for a snake to reach a point on the grid. In the case of two snakes, a border will exist between them (where the snakes reach a point on the grid at the same time).
Voronoi for two snakes (white is shared distances):
Visualization of the area controlled by each snake:
Applying the voronoi heuristic once isn't actually that useful. Here's the recipie for the magic sauce:
From the head of my snake, determine all the farthest paths it can take. In practice, there are too many possible paths to compute in a reasonable time. Instead find all paths up to distance X away. In my case, X=3 but can be changed via an environment variable. So to rephrase, find all paths up to 3 steps away from my snake's head.
Reapply the voronoi heuristic for each of the possibe paths that my snake can take (from step 1).
Choose the path that results with my snake having the most controlled area.
Note: It's worth acknowledging that I'm only accounting for where my snake moves, without considering the movements of other snakes on the grid.
Survival mode is super simple. Check all the points around my snake's head and go in the direction of the one that has the fewest open spaces next to it. This basically forces the snake to hug it's body and/or hug walls. Code here.
Instead of using a 2-D array (  of Array(T)) to represent the grid, I opted for using a 1-D array instead ( of T). The end result was around a 20-30 percent increase in speed I'd say.
Reducing iterations over the grid at any point was key.
Being conscious of memory allocation and creation of classes with identical states.
Reducing intermediary variables while leaving the code relatively verbose.
This part is for me.
Install Crystal off the website or just use:
brew update brew install crystal-lang
Then to install deps run:
For hotcode reloading, install sentry.
./sentry from the project directory to run it with hot reloading.
Otherwise, to run the server, run:
There is an example start request in: start.json
There is an example move request in: move.json
If you run into a libssl issue, try:
Thanks to my coworkers, especially Ian Clarkson for being a soundboard for ideas and feedback.
Thanks to AppColony for the chance to participate in the event as a sponsor (thanks Aaron!).