procedure getNextDirection
headCell = get cell of position of head of the snake
seedCell = get cell of position of the seed
for every cell in board do
computeCost of cell
end for
-- build a graph-like structure of the board,
-- connecting every cell with cost computed above
adjacencyMap = initialize empty array of list
for every cell in board do
for every neighbour of cell do
add to adjacencyMap[cell]
an edge to neighbour
with as weight the cost of neighbour computed above
end for
end for
-- compute shortest path from every cell to every cell
-- using dijkstra's algorithm and the data structure above
dijkstraMinDistance, dijsktraPreviousCell = run dijkstra Shortest Path algorithm on adjacencyMap for headCell
-- get distance in shortest path from headCell to seedCell
minDistance = dijkstraMinDistance[seedCell]
cellTravelList = NULL;
if no path has been found then
-- we have a partitioning (unconnected graph) of the board
return dummy random direction
else
-- build the path form headCell to seedCell
cellTravelList = path to follow using dijsktra's computed dijsktraPreviousCelli> above
return next cell from cellTravelList
end if
end procedure
procedure computeCost (on cell)
-- if cell has a body part on it or the head of the snake
-- then return a ridiculously big value
if cell is not free then
return 99999999;
end if
-- we want the snake as close as possible to its body
-- as a way to avoid partitioning of the board as much as possible
bodyPartNearCount = count of parts of body in nearby cells
if bodyPartNearCount > 0 then
-- dynamic cost
return 10000 / ((bodyPartNearCount * bodyPartNearCount) + 1);
end if
-- also favoring long walks on the border seems a good idea
if cell is close to the border then
return 9000
end if
-- default value
return 10000;
end procedure