The first post in the series walked through the code of my current strategy. This one will share a few of the learnings from writing the utility algorithms in the project (as examples for) where I used Crystal’s standard library modules.
Parsing JSON in Crystal
This is a common task that has to be dealt with on every language. Crystal provides the JSON::Serializable module for you to include in your class. That way you get to_json and from_json methods based on properties & annotations. The module’s usage instructions (docs) are great.
It might be cumbersome to work through a nested object hierarchy when first setting it up, but it’s pretty neat to parse Battlesnake’s context and then work with all objects (i.e. @context.board.snakes.head, @context.board.width, etc). Pretty neat to have instant feedback against typos when working with these thanks to the compiler thereafter too.
The classes in the /src/battle_snake directory are the representation of the game that comes in as JSON payload on each turn.
A* Search Algorithm
a_star.cr is the utility method (docs reference) that will find the shortest path from a point A to a point B. In this context, a point is a BattleSnake::Point that represents a coordinate (x, y) on the board.
The history and how it works is explained in wikipedia. My implementation is on GitHub (here).
I’m sure there are potential optimizations, but I did my best to make it efficient with things like using the recommended priority queue data structure with spider-gazelle/priority-queue. After all the server needs to respond quick (<500ms) for it to play the game and we need to trust we can call utility methods many times on a single turn to make a decision.
Comparing points (distance)
In order to compare and sort custom classes on data structures Crystal provides the Comparable module/mixin. The formula to know the distance between two BattleSnake::Point looks like this (class code here):
def <=>(other : Point)
(x - other.x).abs + (y - other.y).abs
end
Known as Manhattan distance and by a few other names, this is the basis of how we can tell how far away two points are from each other. This is key in being able to implement A* on a board, which could be thought of as a graph with equal distance (1) from each node.
Now our class automatically gets the conventional comparison operators (<, <=, ==, >=, and >) populated based off it and data structures like arrays can sort them too.
Flood fill
This is an algorithm that determines all the possible area that can be reached, as oppossed to what all the empty points on the board because a section might be blocked off and unreachable (docs reference).
My own (summarized) way of explaining it would be “an iterative processing of all valid nearby spaces”.
More about flood fill on wikipedia. My implementation is on GitHub (here).
This comes in handy when making a decision between different valid moves on a strategy. Consider if you had to choose bewteen (a) move to the right and end up with a flood fill area of 3, or (b) move to the left and end up with a flood fill area of 12. Option (a) sounds like the best one.
That’s how CautiousCarol decides to take a left instead of running into an enclosed area (dead end): By calculating what those flood fill results are and picking the largest one.
Conclusions
There are other modules/mixins that can be included or used to extend classes (i.e. Enumerable), so these are just two situations applied to this specific project.
I had flashbacks to university memories when working on these. Nostalgic and fun. The cool thing is that now every new strategy I can work on will be able to use any of these if need be.
Kudos to the BattleSnake team for the resources they upload, like the Deep Learning: Useful Battlesnake Algorithms YouTube video, where I learned a lot about how these and other algorithms can be applied in BattleSnake.
Pura vida.