README
¶
HiveD - The Tiny Hive Board Game Engine
=======================================
Built as a tiny game engine with the purpose of providing a functional rules engine for hive.
The goal is to main a small portable library that can be imported into other projects such as
servers and clients.
Build Environment Prerequisites
-------------------------------
We recommend that you use the docker-container target if you're unsure of how to install or
maintain these tools.
- Build tools
- python-pip
- python-sphinx
- hub
- zip
- github.com/readthedocs/godocjson
- sphinx-autoapi
- sphinxcontrib-golangdomain
Execute Tests and Build Documentation
++++++++++++++++++++++++++++++++++++++
The following command will execute all tests in the project, generate documentation, and start an
nginx server on localhost:8080 that serves up that documentation.
make docs-server
Execute Tests and Build Documentation
++++++++++++++++++++++++++++++++++++++
Roadmap
-------
* [ ] Engine
* [ ] Rule Complete
* [X] Rule of Sliding
* [-] Rule of the Single Hive
* [X] Placement
* [-] Movement
* [-] Queen
* [-] Ant
* [-] Grasshopper
* [-] Spider
* [-] Beetle
* [-] Ladybug
* [-] Pillbug
* [-] Mosquito
* [ ] Rule of Sliding
* [ ] Path to Void
* [ ] No path discovered
* [X] Victory
* [-] Feature Flags
* [X] Tournament Rules
* [-] Pill Bug
* [-] Ladybug
* [-] Mosquito
* [X] Turn Management
* [X] Track Turn History
* [X] Track paralyzed pieces
* [ ] Project
* [ ] Hosting
* [X] Git Repo
* [ ] CICD
* [-] Documentation
* [ ] Descriptor Files
* [-] README
* [X] VERSION
* [X] COPYRIGHT
* [ ] Pipeline
* [ ] Pre-commit Hooks
* [X] Tests
* [ ] Formatting
* [X] Static Analysis
* [ ] Build
* [X] Binaries
* [X] Generate Documentation
* [ ] Release
F.A.Q.
------
1. How do I access the docker container after performing a build?
* docker run -it theshadow/hived:latest /bin/bash
2. How do I start the localhost docks server
* docker run -p 8080:80 theshadow/hived:latest
Documentation
¶
Overview ¶
Package hived is a tiny game engine of the Hive (c) board game that aims to be rule compliant with the base game plus the Ladybug, Mosquito, and Pill Bug expansions. A typical use of this library is to implement either a client and/or server pair for hosting your own games.
Basics ¶
The library consists of an engine for managing the rules and state of a single game instance. The engine attempts to be efficient and compact in its memory usage. It hides this behind a layer of data types. The most expensive algorithm implemented is A* which can be used for many things but is primarily used for validating the movement of pieces.
At the core you can instantiate a new Game instance and interact with the state of the game using one of the player actions, Place or Move. If either action being performed would be in violation of the game rules or state then the action will return an error. For more information about the types of errors the action interface will return see the Game type.
To support the game rules and manage the state the game instance will use a collection of types dedicated to tracking the location of pieces, player pieces, turn number, and turn history.
Types and Values ¶
Game maintains the state of an instance of the game engine and is where the rules are implemented. Board functions as the surface where a Piece is placed which is tracked with the Coordinate. All together, a Player may perform one action per turn and that act is recorded as an Action. A collection of Actions is stored in the state as the history.
Index ¶
- Constants
- Variables
- type Action
- type Board
- type Coordinate
- type Formation
- type Item
- type Piece
- func (p Piece) Bug() uint8
- func (p Piece) BugS() string
- func (p Piece) Color() uint8
- func (p Piece) ColorS() string
- func (p Piece) IsAnt() bool
- func (p Piece) IsBeetle() bool
- func (p Piece) IsBlack() bool
- func (p Piece) IsGrasshopper() bool
- func (p Piece) IsLadybug() bool
- func (p Piece) IsMosquito() bool
- func (p Piece) IsPieceA() bool
- func (p Piece) IsPieceB() bool
- func (p Piece) IsPieceC() bool
- func (p Piece) IsPillBug() bool
- func (p Piece) IsQueen() bool
- func (p Piece) IsSpider() bool
- func (p Piece) IsWhite() bool
- func (p Piece) Piece() uint8
- func (p Piece) PieceS() string
- func (p Piece) String() string
- type Player
- func (p *Player) Ants() (count int)
- func (p *Player) Beetles() (count int)
- func (p *Player) Grasshoppers() (count int)
- func (p *Player) HasLadybug() bool
- func (p *Player) HasMosquito() bool
- func (p *Player) HasPillBug() bool
- func (p *Player) HasQueen() bool
- func (p *Player) HasZeroPieces() bool
- func (p *Player) IsBlack() bool
- func (p *Player) IsWhite() bool
- func (p *Player) Spiders() (count int)
- func (p *Player) String() string
- func (p *Player) TakeABeetle() error
- func (p *Player) TakeAGrasshopper() error
- func (p *Player) TakeASpider() error
- func (p *Player) TakeAnAnt() error
- func (p *Player) TakeLadybug() error
- func (p *Player) TakeMosquito() error
- func (p *Player) TakePillBug() error
- func (p *Player) TakeQueen() error
- type PriorityQueue
Constants ¶
const ( Placed uint8 = iota Moved ActMask = 0b11111111000000000000000000000000 DstMask = 0b0000000000000000000000000000000011111111111111111111111111111111 )
const ( North = iota Northeast Southeast South Southwest Northwest Above )
const ( YMask = 0b00000000111111110000000000000000 ZMask = 0b00000000000000001111111100000000 )
const ( NoFormation = iota Chevron Spaceship Butterfly )
const ( NoBug uint8 = iota Queen Beetle Grasshopper Spider Ant Mosquito Ladybug PillBug BugMask = 0b0000000011111110000000000000000 NoPiece uint8 = 0 PieceA = 1 PieceB = 2 PieceC = 3 PieceMask = 0b00000000000000001111111100000000 NoColor uint8 = 0 BlackColor = 1 WhiteColor = 2 ColorMask = 0b1111111000000000000000000000000 )
const ( QueenMask = 0b0010000000000000 AntsMask = 0b0001110000000000 GrasshoppersMask = 0b0000001110000000 BeetlesMask = 0b0000000001100000 SpidersMask = 0b0000000000011000 MosquitoMask = 0b0000000000000100 LadybugMask = 0b0000000000000010 PillBugMask = 0b0000000000000001 AntABitMask = 0b0001000000000000 AntBBitMask = 0b0000100000000000 AntCBitMask = 0b0000010000000000 GrasshopperAMask = 0b0000001000000000 GrasshopperBMask = 0b0000000100000000 GrasshopperCMask = 0b0000000010000000 BeetleAMask = 0b0000000001000000 BeetleBMask = 0b0000000000100000 SpiderAMask = 0b0000000000010000 SpiderBMask = 0b0000000000001000 )
Variables ¶
var ( // Version tracks the API Version string // BuildID is used to track the source of the build BuildID string )
var ErrInvalidCoordinate = fmt.Errorf("the specified coordinate is invalid")
var ErrNoPieceAvailable = fmt.Errorf("attempted to take piece that has none left to take")
var ErrPauliExclusionPrinciple = fmt.Errorf("two pieces may not occupy the same coordinate")
var NeighborsMatrix = []Coordinate{ NewCoordinate(0, 1, -1, 0), NewCoordinate(1, 0, -1, 0), NewCoordinate(1, -1, 0, 0), NewCoordinate(0, -1, 1, 0), NewCoordinate(-1, 0, 1, 0), NewCoordinate(-1, 1, 0, 0), NewCoordinate(0, 0, 0, 1), }
var Origin = Coordinate(0)
var ZeroPiece = Piece(0)
var ZeroPlayer = Player(0)
Functions ¶
This section is empty.
Types ¶
type Action ¶
type Action struct {
// contains filtered or unexported fields
}
| Act | Piece | |11111111|11111111|11111111|11111111|
| Transition | | Source Coordinate | Dst Coordinate | |11111111|11111111|11111111|11111111|11111111|11111111|11111111|11111111|
func NewAction ¶
func NewAction(action uint8, p Piece, src Coordinate, dst Coordinate) Action
func (Action) Dst ¶
func (m Action) Dst() Coordinate
func (Action) Src ¶
func (m Action) Src() Coordinate
type Board ¶
type Board struct {
// contains filtered or unexported fields
}
TODO how do I marshall this type Board represents a 4D hex grid (x, y, z, height). It works by storing the contents of a hex coordinate ("cell") in a slice and using a map to quickly reference the memory.
func (*Board) Cell ¶
func (brd *Board) Cell(c Coordinate) (Piece, bool)
Cell will return true when there is a piece at that coordinate
func (*Board) Move ¶
func (brd *Board) Move(a, b Coordinate) error
Act will accept a source (A) coordinate and a destination (B) coordinate and attempt to move the piece to that location. It will return an error if a piece doesn't exist at the source or if a piece does exists at the destination.
func (*Board) Neighbors ¶
func (brd *Board) Neighbors(c Coordinate) (formation [7]Piece, err error)
Return an array with seven elements, each element represents one of the edges of the piece. We colloquially name these North, Northeast, Southeast, South, Southwest, Northwest, and Above respectively. By default it is always assumed that the top flat edge is always considered North and that the additional edges continue in a clockwise fashion around the piece.
formation := [7]Piece{
// North,
// Northeast,
// Southeast,
// South,
// Southwest,
// Northwest,
// Above,
}
Will return an error when the supplied coordinate isn't a valid location
func (*Board) Place ¶
func (brd *Board) Place(p Piece, c Coordinate) error
Place will return an error if there is already a piece at the specified coordinate.
Should the board know about the game rules?
With this definition the board will return an error if there is already a piece at the specified coordinate. This is due to the fact that I'm accepting a trade off. While there is merit and value in creating a more robust board that can manage multiple pieces at a given location we will loose a valuable and in my opinion cheap safety net that will help us validate game rules. Details about the two arguments are outlined below.
Hive doesn't allow two pieces to occupy the same coordinate, however, in a more generic sense a hex board could, in theory, have multiple pieces in a cell based on the game rules. To make a more generic board would require refactoring the cells of the board to be able to contain multiple pieces and then devising a system for exposing what pieces already exist and letting the game decide what to do. However, there are concerns about the increase in complexity for the memory management of the type.
By returning an error I make validating game rules drastically more reliable as the board will help guarantee the game rules don't do something stupid. It also greatly simplifies the memory management of the type. Tracking multiple pieces and deciding on a clear set of behavior when you Place or Act a piece sounds like a daunting task and really not worth the effort.
So, in conclusion, the value of making cells more robust at this juncture is out stripped by the value of having a safety net.
type Coordinate ¶
type Coordinate uint32
Coordinate represents a physical location on the board. The board maintains a hex grid with a four dimensional coordinate system. Three for the surface location and one for the height above the board.
We accomplish this by splitting an uint32 into four bytes and then encoding int8's into each of them. This does make the code a little more arcane as you need to know Go's bitwise operators and the type system rules but it also means we don't need to pull in Bits or some other lib to do the work for us. Which fits in with the project goal of being tiny.
Using an int8 does put a practical limit on the size of the world of -127 to 127 with a bit reserved for tracking the sign. This shouldn't be an issue if we assume that the world will wrap and if it does become an issue we can maintain the interface and modify the type to use an uint64 instead.
X Y Z H
11111111|11111111|11111111|11111111
int8 int8 int8 int8
func NewCoordinate ¶
func NewCoordinate(x, y, z, h int8) Coordinate
func (Coordinate) Add ¶
func (c Coordinate) Add(loc Coordinate) Coordinate
func (Coordinate) H ¶
func (c Coordinate) H() int8
func (Coordinate) String ¶
func (c Coordinate) String() string
func (Coordinate) X ¶
func (c Coordinate) X() int8
These functions rely on bit-masking to mask the required bits out and then bit operations to isolate and convert from the uint32 type to an int8
func (Coordinate) Y ¶
func (c Coordinate) Y() int8
func (Coordinate) Z ¶
func (c Coordinate) Z() int8
type Formation ¶
type Formation [7]Piece
Used to track the neighbors around a piece. Specifically adds functionality for quickly validating position of pieces around a center piece
Detecting Specific Formations ¶
There are four major formations that we're interested in, which are the Spaceship, Butterfly, Chevron, and Broken Butterfly. As all other formations are either easily tested for or are discarded as non-relevant
We can reduce our complexity at the start by ignoring the Above contact as any piece with something above it is already pinned. With the remaining six contacts if we took the six positions and represented them in base-2 then we'd see the following.
WHERE:
Cardinal Directions (N, NE, SE, S, SW, NW) are the six contact points around the center piece.
Ones represent a cardinal direction with a piece. Dec is the decimal representation of the formation.
N NE SE S SW NW DEC
Chevron: 1 0 1 0 1 0 42
Spaceship: 1 1 1 0 1 0 58 Butterfly: 1 1 0 1 1 0 54
We also know that each of these formations have multiple permutations where as long as the spacing between the pieces remains the same the formation still prevents the piece from moving. Below we can see the various permutations. An easy way to imagine this is to treat the bitfield as a matrix that we'll be performing operations against. Specifically we want to rotate the field through each of the available permutations.
A permutation is defined as moving either the first or the last element of the matrix and to the opposite end of the matrix. See the functional-pseudo example below:
M = [ 1, 0, 1, 0, 1, 0 ]
first = f(M) -> int = 1
last = f(M) -> int = 0
head = f(M) -> []int = [ 0, 1, 0, 1, 0 ]
tail = f(M) -> []int = [ 1, 0, 1, 0, 1 ]
∴
lRotation = f(M) -> []int = last(M) + head(M) = [ 1, 0, 1, 0, 1, 0 ]
rRotation = f(M) -> []int = tail(M) + first(M) = [ 0, 1, 0, 1, 0, 1 ]
By rotating each field through all of the permutations we can see the following options, numbers within parenthesis
represent the decimal form of the matrix.
CHEVRON SPACESHIP BUTTERFLY
010101 (21) 010111 (23) 011011 (27)
101010 (42) 011101 (29) 101101 (45)
101011 (43) 110110 (54)
101110 (46)
110101 (53)
111010 (58)
True to matrix math we can quickly identify that in each column all of the permutations contain reflections. That is, "101010" is the mirror image of "010101". We may be able to use this information during our checks to reduce the number of operations if we can find a cheap way to create the reflection of an integer Location. If we can't I believe we can simply create a map[int]int where the key is the decimal Location of the bitfield and the mapped to integer is the type of formation, be it Chevron, Butterfly, or Spaceship.
func (Formation) IsSuffocating ¶
type Item ¶
type Item struct {
Location Coordinate // The Location of the item; arbitrary.
Priority int // The Priority of the item in the queue.
// contains filtered or unexported fields
}
An Item is something we manage in a Priority queue.
type Piece ¶
type Piece uint32
Color | Bug | Piece | Unused
11111111|11111111|11111111|11111111
func NewBlackPiece ¶
func NewWhitePiece ¶
func (Piece) IsGrasshopper ¶
func (Piece) IsMosquito ¶
type Player ¶
type Player uint16
A Player tracks the color and remaining cells the player has.
. Unused (C)olor (Q)ueen (A)nt x 3 (G)rasshopper x 3 (B)eetle x 2 (S)pider x 2 (M)osquito (L)adybug (P)ill Bug .CQA|AAGG|GBBS|SMLP 1111|1111|1111|1111
func (*Player) Beetles ¶
Will return 2 or less for the count as there are only two beetles per player
func (*Player) Grasshoppers ¶
Will return 3 or less for the count as there are only three grasshoppers per player
func (*Player) HasLadybug ¶
func (*Player) HasMosquito ¶
func (*Player) HasPillBug ¶
func (*Player) HasZeroPieces ¶
type PriorityQueue ¶
type PriorityQueue []*Item
A PriorityQueue implements heap.Interface and holds Items.
func (PriorityQueue) Len ¶
func (pq PriorityQueue) Len() int
func (PriorityQueue) Less ¶
func (pq PriorityQueue) Less(i, j int) bool
func (*PriorityQueue) Pop ¶
func (pq *PriorityQueue) Pop() interface{}
func (*PriorityQueue) Push ¶
func (pq *PriorityQueue) Push(x interface{})
func (PriorityQueue) Swap ¶
func (pq PriorityQueue) Swap(i, j int)
Source Files
Directories