class Strategy::Utils

Defined in:


Class Method Summary

Class Method Detail

def self.a_star(a : BattleSnake::Point, b : BattleSnake::Point, context : BattleSnake::Context) #

Implementation of A* Search Algorithm (read more).

It receives Point a (start) and b (objective), along with a BattleSnake::Context to access the game state. It returns a hash with :route (Array(BattleSnake::Point)) and :moves (Array(String)). They represent the points in the route and the moves ("up"/"left"/etc.) to take that path from point a to b. Both arrays will be empty if the context makes it impossible to find a valid route.

NOTE Implemented using the spider-gazelle/priority-queue project on GitHub

NOTE Naive Manhattan Distance used for estimation function of the algorithm

NOTE Performance can be optimized on data structure lookups and instance initializations when using helper methods, i.e. BattleSnake::Context#valid_moves

[View source]
def self.flood_fill(a : BattleSnake::Point, context : BattleSnake::Context) #

Implementation of Flood Fill (read more).

It receives a BattleSnake::Point a and a BattleSnake::Context context to start off a Flood Fill and returns a Set(BattleSnake::Point) with all the points reachable to that area on the board

[View source]
def self.possible_collisions(context : BattleSnake::Context) #

Implementation that returns all moves that could cause a collision with another snake which would result in death.

[View source]