Package ai.nettogrof.battlesnake.treesearch

Class AbstractSearch

java.lang.Object

ai.nettogrof.battlesnake.treesearch.AbstractSearch

All Implemented Interfaces:

Runnable

Direct Known Subclasses:

AbstractBestFirstSearch

public abstract class AbstractSearch
extends Object
implements Runnable

This abstract search class is the based of all search class, provide basic method use in any search.

Version:

Spring 2021

Author:

carl.lajeunesse

Field Summary

Fields

Modifier and Type	Field	Description
protected boolean	cont	Control variable to continue the search or not
protected int	height	Board height
protected AbstractNode	root	Root node for the search
protected GameRuleset	rules	Object containing Game Rules
protected long	startTime	Starting time for the search in millisecond
protected int	timeout	Time allowed for the search
protected int	width	Board width

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractSearch()	Basic Constructor

Method Summary

Modifier and Type	Method	Description
protected void	addMove(int newhead, List<SnakeInfo> allSnakes, SnakeInfo snakeInfo, AbstractNode node, List<SnakeInfo> listNewSnakeInfo)	This method add move to the list if the snake can move in the new head position.
protected void	checkHeadToHead(List<ArrayList<SnakeInfo>> moves)	This method check if there's a head-to-head collision.
protected abstract SnakeInfo	createSnakeInfo(SnakeInfo snakeInfo, int newHead, AbstractNode node)	Create new SnakeInfo based on the current node and the new head square
protected abstract boolean	freeSpace(int square, List<SnakeInfo> allSnakes, SnakeInfo currentSnake)	Check if the snake can move on the square
void	generateChild()	This method is used to generate child node from the root.
protected void	generateChild(AbstractNode node)	Expand / Generate child from a node
protected List<SnakeInfo>	generateSnakeInfoDestination(SnakeInfo snakeInfo, AbstractNode node, List<SnakeInfo> allSnakes)	Generate all moves possible for a snake given.
protected AbstractNode	getSmallestChild(AbstractNode node)	Get the leaf from the smallest branch
protected abstract void	kill(SnakeInfo death, List<SnakeInfo> all)	This abstract method will be use to "kill" a snake
protected List<ArrayList<SnakeInfo>>	merge(List<ArrayList<SnakeInfo>> list, List<SnakeInfo> snakes)	This method merge previous snake move (list) , with new snake move
protected void	moveSnake(SnakeInfo snakeInfo, AbstractNode node, List<SnakeInfo> allSnakes, List<SnakeInfo> listNewSnakeInfo)	Generate move of a snake
void	stopSearching()	This method is used to stop the search

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Runnable

run

Field Detail

cont

protected boolean cont

Control variable to continue the search or not

root

protected AbstractNode root

Root node for the search

height

protected int height

Board height

width

protected int width

Board width

timeout

protected int timeout

Time allowed for the search

startTime

protected long startTime

Starting time for the search in millisecond

rules

protected GameRuleset rules

Object containing Game Rules

Constructor Detail

AbstractSearch

protected AbstractSearch()

Basic Constructor

Method Detail

stopSearching

public void stopSearching()

This method is used to stop the search

kill

protected abstract void kill(SnakeInfo death,
                             List<SnakeInfo> all)

This abstract method will be use to "kill" a snake

Parameters:

death - SnakeInfo of the snake to kill

all - List of all snakeinfo

generateChild

public void generateChild()

This method is used to generate child node from the root. Mostly used for multithreading

checkHeadToHead

protected void checkHeadToHead(List<ArrayList<SnakeInfo>> moves)

This method check if there's a head-to-head collision. Shorter snake die, and if both snakes are the same length both dies

Parameters:

moves - List of all possible move

merge

protected List<ArrayList<SnakeInfo>> merge(List<ArrayList<SnakeInfo>> list,
                                           List<SnakeInfo> snakes)

This method merge previous snake move (list) , with new snake move

Parameters:

list - Previous list

snakes - New move list

Returns:

List of List of move

createSnakeInfo

protected abstract SnakeInfo createSnakeInfo(SnakeInfo snakeInfo,
                                             int newHead,
                                             AbstractNode node)

Create new SnakeInfo based on the current node and the new head square

Parameters:

snakeInfo - previous snakeInfo

newHead - New head square

node - Previous node

Returns:

new SnakeInfo

generateSnakeInfoDestination

protected List<SnakeInfo> generateSnakeInfoDestination(SnakeInfo snakeInfo,
                                                       AbstractNode node,
                                                       List<SnakeInfo> allSnakes)

Generate all moves possible for a snake given.

Parameters:

snakeInfo - Information about the snake

node - Parent node

allSnakes - List of all snakes

Returns:

list of snakeinfo

moveSnake

protected void moveSnake(SnakeInfo snakeInfo,
                         AbstractNode node,
                         List<SnakeInfo> allSnakes,
                         List<SnakeInfo> listNewSnakeInfo)

Generate move of a snake

Parameters:

snakeInfo - Current snake

node - Current node to add child node

allSnakes - List of all snakes to check body collision

listNewSnakeInfo - fill that list with new snake position

addMove

protected void addMove(int newhead,
                       List<SnakeInfo> allSnakes,
                       SnakeInfo snakeInfo,
                       AbstractNode node,
                       List<SnakeInfo> listNewSnakeInfo)

This method add move to the list if the snake can move in the new head position.

Parameters:

newhead - New head

allSnakes - List of all snakes

snakeInfo - Information about the snake

node - Parent node

listNewSnakeInfo - Current list of snakeinfo

freeSpace

protected abstract boolean freeSpace(int square,
                                     List<SnakeInfo> allSnakes,
                                     SnakeInfo currentSnake)

Check if the snake can move on the square

Parameters:

square - the int sqaure

allSnakes - List of all snakes

currentSnake - current Snake

Returns:

boolean free to move on that square

generateChild

protected void generateChild(AbstractNode node)

Expand / Generate child from a node

Parameters:

node - the Abstractnode to be expand

getSmallestChild

protected AbstractNode getSmallestChild(AbstractNode node)

Get the leaf from the smallest branch

Parameters:

node - Root node

Returns:

leaf node