tile

package module
v1.3.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 17, 2022 License: MIT Imports: 10 Imported by: 6

README

Tile: Data-Oriented 2D Grid Engine


Go Version PkgGoDev Go Report Card License Coverage

This repository contains a 2D tile map engine which is built with data and cache friendly ways. My main goal here is to provide a simple, high performance library to handle large scale tile maps in games.

  • Compact. Each tile value is 4 bytes long and each grid page is 64-bytes long, which means a grid of 3000x3000 should take around 64MB of memory.
  • Thread-safe. The grid is thread-safe and can be updated through provided update function. This allows multiple goroutines to read/write to the grid concurrently without any contentions. There is a spinlock per tile page protecting tile access.
  • Views & observers. When a tile on the grid is updated, viewers of the tile will be notified of the update and can react to the changes. The idea is to allow you to build more complex, reactive systems on top of the grid.
  • Zero-allocation (or close to it) traversal of the grid. The grid is pre-allocated entirely and this library provides a few ways of traversing it.
  • Path-finding. The library provides a A* pathfinding algorithm in order to compute a path between two points, as well as a BFS-based position scanning which searches the map around a point.

Disclaimer: the API or the library is not final and likely to change. Also, since this is just a side project of mine, don't expect this to be updated very often but please contribute!

Grid & Tiles

The main entry in this library is Grid which represents, as the name implies a 2 dimentional grid which is the container of Tile structs. The Tile is essentially a cursor to a particular x,y coordinate and contains the following

  • Value uint32 of the tile, that can be used for calculating navigation or quickly retrieve sprite index.
  • State set of T comparable that can be used to add additional information such as objects present on the tile. These things cannot be used for pathfinding, but can be used as an index.

Granted, uint32 value a bit small. The reason for this is the data layout, which is organised in thread-safe pages of 3x3 tiles, with the total size of 64 bytes which should neatly fit onto a cache line of a CPU.

In order to create a new Grid[T], you first need to call NewGrid[T]() method which pre-allocates the required space and initializes the tile grid itself. For example, you can create a 1000x1000 grid as shown below. The type argument T sets the type of the state objects. In the example below we want to create a new grid with a set of strings.

grid := tile.NewGrid[string](1000, 1000)

The Each() method of the grid allows you to iterate through all of the tiles in the grid. It takes an iterator function which is then invoked on every tile.

grid.Each(func(p Point, t tile.Tile[string]) {
    // ...
})

The Within() method of the grid allows you to iterate through a set of tiles within a bounding box, specified by the top-left and bottom-right points. It also takes an iterator function which is then invoked on every tile matching the filter.

grid.Within(At(1, 1), At(5, 5), func(p Point, t tile.Tile[string]) {
    // ...
})

The At() method of the grid allows you to retrieve a tile at a specific x,y coordinate. It simply returns the tile and whether it was found in the grid or not.

if tile, ok := grid.At(50, 100); ok {
    // ...
}

The WriteAt() method of the grid allows you to update a tile at a specific x,y coordinate. Since the Grid itself is thread-safe, this is the way to (a) make sure the tile update/read is not racing and (b) notify observers of a tile update (more about this below).

grid.WriteAt(50, 100, tile.Value(0xFF))

The Neighbors() method of the grid allows you to get the direct neighbors at a particular x,y coordinate and it takes an iterator funcion which is called for each neighbor. In this implementation, we are only taking direct neighbors (top, left, bottom, right). You rarely will need to use this method, unless you are rolling out your own pathfinding algorithm.

grid.Neighbors(50, 100, func(point tile.Point, t tile.Tile[string]) {
    // ...
})

The MergeAt() method of the grid allows you to atomically update a value given a current value of the tile. For example, if we want to increment the value of a tile we can call this method with a function that increments the value. Under the hood, the increment will be done using an atomic compare-and-swap operation.

grid.MergeAt(50, 100, func(v Value) Value {
    v += 1
    return v
})

The MaskAt() method of the grid allows you to atomically update only some of the bits at a particular x,y coordinate. This operation is as well thread-safe, and is actually useful when you might have multiple goroutines updating a set of tiles, but various goroutines are responsible for the various parts of the tile data. You might have a system that updates only a first couple of tile flags and another system updates some other bits. By using this method, two goroutines can update the different bits of the same tile concurrently, without erasing each other's results, which would happen if you just call WriteAt().

// assume byte[0] of the tile is 0b01010001
grid.MaskAt(50, 100,
    0b00101110, // Only last 2 bits matter
    0b00000011 // Mask specifies that we want to update last 2 bits
)

// If the original is currently: 0b01010001
// ...the result result will be: 0b01010010

Pathfinding

As mentioned in the introduction, this library provides a few grid search / pathfinding functions as well. They are implemented as methods on the same Grid structure as the rest of the functionnality. The main difference is that they may require some allocations (I'll try to minimize it further in the future), and require a cost function func(Tile) uint16 which returns a "cost" of traversing a specific tile. For example if the tile is a "swamp" in your game, it may cost higher than moving on a "plain" tile. If the cost function returns 0, the tile is then considered to be an impassable obstacle, which is a good choice for walls and such.

The Path() method is used for finding a way between 2 points, you provide it the from/to point as well as costing function and it returns the path, calculated cost and whether a path was found or not. Note of caution however, avoid running it between 2 points if no path exists, since it might need to scan the entire map to figure that out with the current implementation.

from := At(1, 1)
goal := At(7, 7)
path, distance, found := m.Path(from, goal, func(v tile.Value) uint16{
    if isImpassable(v) {
        return 0
    }
    return 1
})

The Around() method provides you with the ability to do a breadth-first search around a point, by providing a limit distance for the search as well as a cost function and an iterator. This is a handy way of finding things that are around the player in your game.

point  := At(50, 50)
radius := 5
m.Around(point, radius, func(v tile.Value) uint16{
    if isImpassable(v) {
        return 0
    }
    return 1
}, func(p tile.Point, t tile.Tile[string]) {
    // ... tile found
})

Observers

Given that the Grid is mutable and you can make changes to it from various goroutines, I have implemented a way to "observe" tile changes through a View() method which creates a View structure and can be used to observe changes within a bounding box. For example, you might want your player to have a view port and be notified if something changes on the map so you can do something about it.

In order to use these observers, you need to first call the View() method and start polling from the Inbox channel which will contain the tile update notifications as they happen. This channel has a small buffer, but if not read it will block the update, so make sure you always poll everything from it.

In the example below we create a new 20x20 view on the grid and iterate through all of the tiles in the view.

rect := tile.NewRect(0, 0, 20, 20)
view := grid.View(rect, func(p tile.Point, t tile.Tile){
    // Optional, all of the tiles that are in the view now
})

// Poll the inbox (in reality this would need to be with a select, and a goroutine)
for {
    update := <-view.Inbox
    // Do something with update.Point, update.Tile
}

The MoveBy() method allows you to move the view in a specific direction. It takes in a x,y vector but it can contain negative values. In the example below, we move the view upwards by 5 tiles. In addition, we can also provide an iterator and do something with all of the tiles that have entered the view (e.g. show them to the player).

view.MoveBy(0, 5, func(p tile.Point, tile tile.Tile){
    // Every tile which entered our view
})

Similarly, MoveAt() method allows you to move the view at a specific location provided by the coordinates. The size of the view stays the same and the iterator will be called for all of the new tiles that have entered the view port.

view.MoveAt(At(10, 10), func(p tile.Point, t tile.Tile){
    // Every tile which entered our view
})

The Resize() method allows you to resize and update the view port. As usual, the iterator will be called for all of the new tiles that have entered the view port.

viewRect := tile.NewRect(10, 10, 30, 30)
view.Resize(viewRect, func(p tile.Point, t tile.Tile){
    // Every tile which entered our view
})

The Close() method should be called when you are done with the view, since it unsubscribes all of the notifications. Be careful, if you do not close the view when you are done with it, it will lead to memory leaks since it will continue to observe the grid and receive notifications.

// Unsubscribe from notifications and close the view
view.Close()

Save & Load

The library also provides a way to save the Grid to an io.Writer and load it from an io.Reader by using WriteTo() method and ReadFrom() function. Keep in mind that the save/load mechanism does not do any compression, but in practice you should use to a compressor if you want your maps to not take too much of the disk space - snappy is a good option for this since it's fast and compresses relatively well.

The WriteTo() method of the grid only requires a specific io.Writer to be passed and returns a number of bytes that have been written down to it as well if any specific error has occured. Below is an example of how to save the grid into a compressed buffer.

// Prepare the output buffer and compressor
output := new(bytes.Buffer)
writer, err := flate.NewWriter(output, flate.BestSpeed)
if err != nil {
    // ...
}

defer writer.Close()            // Make sure we flush the compressor
_, err := grid.WriteTo(writer)  // Write the grid
if err != nil {
    // ...
}

The ReadFrom() function allows you to read the Grid from a particular reader. To complement the example above, the one below shows how to read a compressed grid using this function.

// Prepare a compressed reader over the buffer
reader := flate.NewReader(output)

// Read the Grid
grid, err := ReadFrom(reader)
if err != nil{
    // ...
}

Benchmarks

This library contains quite a bit of various micro-benchmarks to make sure that everything stays pretty fast. Feel free to clone and play around with them yourself. Below are the benchmarks which we have, most of them are running on relatively large grids.

cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
BenchmarkGrid/each-8                 868    1358434 ns/op           0 B/op   0 allocs/op
BenchmarkGrid/neighbors-8       66551679      17.87 ns/op           0 B/op   0 allocs/op
BenchmarkGrid/within-8             27207      44753 ns/op           0 B/op   0 allocs/op
BenchmarkGrid/at-8             399067512      2.994 ns/op           0 B/op   0 allocs/op
BenchmarkGrid/write-8          130207965      9.294 ns/op           0 B/op   0 allocs/op
BenchmarkGrid/merge-8          124156794      9.663 ns/op           0 B/op   0 allocs/op
BenchmarkGrid/mask-8           100000000      10.67 ns/op           0 B/op   0 allocs/op
BenchmarkState/range-8          12106854      98.91 ns/op           0 B/op   0 allocs/op
BenchmarkState/add-8            48827727      25.43 ns/op           0 B/op   0 allocs/op
BenchmarkState/del-8            52110474      21.59 ns/op           0 B/op   0 allocs/op
BenchmarkPath/9x9-8               264586        4656 ns/op      16460 B/op   3 allocs/op
BenchmarkPath/300x300-8              601     1937662 ns/op    7801502 B/op   4 allocs/op
BenchmarkPath/381x381-8              363     3304134 ns/op   62394356 B/op   5 allocs/op
BenchmarkPath/384x384-8              171     7165777 ns/op   62394400 B/op   5 allocs/op
BenchmarkPath/3069x3069-8             31    36479106 ns/op  124836075 B/op   4 allocs/op
BenchmarkPath/3072x3072-8             30    34889740 ns/op  124837686 B/op   4 allocs/op
BenchmarkPath/6144x6144-8            142     7594013 ns/op   62395376 B/op   3 allocs/op
BenchmarkAround/3r-8              506857        2384 ns/op        385 B/op   1 allocs/op
BenchmarkAround/5r-8              214280        5539 ns/op        922 B/op   2 allocs/op
BenchmarkAround/10r-8              85723       14017 ns/op       3481 B/op   2 allocs/op
BenchmarkPoint/within-8       1000000000      0.2190 ns/op          0 B/op   0 allocs/op
BenchmarkPoint/within-rect-8  1000000000      0.2195 ns/op          0 B/op   0 allocs/op
BenchmarkStore/save-8              14577       82510 ns/op          8 B/op   1 allocs/op
BenchmarkStore/read-8               3199      364771 ns/op     647419 B/op   7 allocs/op
BenchmarkView/write-8            6285351       188.2 ns/op         48 B/op   1 allocs/op
BenchmarkView/move-8               10000      116953 ns/op          0 B/op   0 allocs/op

Contributing

We are open to contributions, feel free to submit a pull request and we'll review it as quickly as we can. This library is maintained by Roman Atachiants

License

Tile is licensed under the MIT License.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Direction added in v1.2.0 

type Direction byte

Diretion represents a direction 

const (
	North Direction = iota
	NorthEast
	East
	SouthEast
	South
	SouthWest
	West
	NorthWest
)

Various directions

func (Direction) String added in v1.2.0 

func (v Direction) String() string

String returns a string representation of a direction

type Grid 

type Grid[T comparable] struct {
	Size Point // The map size
	// contains filtered or unexported fields
}

Grid represents a 2D tile map. Internally, a map is composed of 3x3 pages.

func NewGrid 

func NewGrid(width, height int16) *Grid[string]

NewGrid returns a new map of the specified size. The width and height must be both multiples of 3.

func NewGridOf added in v1.3.0 

func NewGridOf[T comparable](width, height int16) *Grid[T]

NewGridOf returns a new map of the specified size. The width and height must be both multiples of 3.

func ReadFile added in v1.2.2 

func ReadFile[T comparable](filename string) (grid *Grid[T], err error)

Restore restores the grid from the specified file. The grid must be written using the corresponding WriteFile() method.

func ReadFrom 

func ReadFrom[T comparable](src io.Reader) (grid *Grid[T], err error)

ReadFrom reads the grid from the reader.

func (*Grid[T]) Around 

func (m *Grid[T]) Around(from Point, distance uint32, costOf costFn, fn func(Point, Tile[T]))

Around performs a breadth first search around a point.

func (*Grid[T]) At 

func (m *Grid[T]) At(x, y int16) (Tile[T], bool)

At returns the tile at a specified position

func (*Grid[T]) Each 

func (m *Grid[T]) Each(fn func(Point, Tile[T]))

Each iterates over all of the tiles in the map.

func (*Grid[T]) MaskAt added in v1.3.0 

func (m *Grid[T]) MaskAt(x, y int16, tile, mask Value)

MaskAt atomically updates the bits of tile at a specific coordinate. The bits are specified by the mask. The bits that need to be updated should be flipped on in the mask.

func (*Grid[T]) MergeAt 

func (m *Grid[T]) MergeAt(x, y int16, merge func(Value) Value)

Merge atomically merges the tile by applying a merging function at a specific coordinate.

func (*Grid[T]) Neighbors 

func (m *Grid[T]) Neighbors(x, y int16, fn func(Point, Tile[T]))

Neighbors iterates over the direct neighbouring tiles

func (*Grid[T]) Path 

func (m *Grid[T]) Path(from, to Point, costOf costFn) ([]Point, int, bool)

Path calculates a short path and the distance between the two locations

func (*Grid[T]) View 

func (m *Grid[T]) View(rect Rect, fn func(Point, Tile[T])) *View[T]

View creates a new view of the map.

func (*Grid[T]) Within 

func (m *Grid[T]) Within(nw, se Point, fn func(Point, Tile[T]))

Within selects the tiles within a specifid bounding box which is specified by north-west and south-east coordinates.

func (*Grid[T]) WriteAt 

func (m *Grid[T]) WriteAt(x, y int16, tile Value)

WriteAt updates the entire tile value at a specific coordinate

func (*Grid[T]) WriteFile added in v1.2.2 

func (m *Grid[T]) WriteFile(filename string) error

WriteFile writes the grid into a flate-compressed binary file.

func (*Grid[T]) WriteTo 

func (m *Grid[T]) WriteTo(dst io.Writer) (n int64, err error)

WriteTo writes the grid to a specific writer.

type Point 

type Point struct {
	X int16 // X coordinate
	Y int16 // Y coordinate
}

Point represents a 2D coordinate.

func At 

func At(x, y int16) Point

At creates a new point at a specified x,y coordinate.

func (Point) Add 

func (p Point) Add(p2 Point) Point

Add adds two points together.

func (Point) DistanceTo 

func (p Point) DistanceTo(other Point) uint32

DistanceTo calculates manhattan distance to the other point

func (Point) Divide 

func (p Point) Divide(p2 Point) Point

Divide divides the first point by the second.

func (Point) DivideScalar 

func (p Point) DivideScalar(s int16) Point

DivideScalar divides the given point by the scalar.

func (Point) Equal 

func (p Point) Equal(other Point) bool

Equal compares two points and returns true if they are equal.

func (Point) Integer 

func (p Point) Integer() uint32

Integer returns a packed 32-bit integer representation of a point.

func (Point) Move added in v1.2.0 

func (p Point) Move(direction Direction) Point

Move moves a point by one in the specified direction.

func (Point) MoveBy added in v1.2.0 

func (p Point) MoveBy(direction Direction, n int16) Point

MoveBy moves a point by n in the specified direction.

func (Point) Multiply 

func (p Point) Multiply(p2 Point) Point

Multiply multiplies two points together.

func (Point) MultiplyScalar 

func (p Point) MultiplyScalar(s int16) Point

MultiplyScalar multiplies the given point by the scalar.

func (Point) String 

func (p Point) String() string

String returns string representation of a point.

func (Point) Subtract 

func (p Point) Subtract(p2 Point) Point

Subtract subtracts the second point from the first.

func (Point) Within 

func (p Point) Within(nw, se Point) bool

Within checks if the point is within the specified bounding box.

func (Point) WithinRect 

func (p Point) WithinRect(box Rect) bool

WithinRect checks if the point is within the specified bounding box.

func (Point) WithinSize 

func (p Point) WithinSize(size Point) bool

WithinSize checks if the point is within the specified bounding box which starts at 0,0 until the width/height provided.

type Rect 

type Rect struct {
	Min Point // Top left point of the rectangle
	Max Point // Bottom right point of the rectangle
}

Rect represents a rectangle

func NewRect 

func NewRect(left, top, right, bottom int16) Rect

NewRect creates a new rectangle left,top,right,bottom correspond to x1,y1,x2,y2

func (*Rect) Contains 

func (r *Rect) Contains(p Point) bool

Contains returns whether a point is within the rectangle or not.

func (*Rect) Intersects 

func (r *Rect) Intersects(box Rect) bool

Intersects returns whether a rectangle intersects with another rectangle or not.

func (*Rect) Size 

func (r *Rect) Size() Point

Size returns the size of the rectangle

type Tile 

type Tile[T comparable] struct {
	// contains filtered or unexported fields
}

Tile represents an iterator over all state objects at a particular location.

func (Tile[T]) Add added in v1.3.0 

func (c Tile[T]) Add(v T)

Add adds object to the set

func (Tile[T]) Count added in v1.3.0 

func (c Tile[T]) Count() (count int)

Count returns number of objects at the current tile.

func (Tile[T]) Del added in v1.3.0 

func (c Tile[T]) Del(v T)

Del removes the object from the set

func (Tile[T]) Mask added in v1.3.0 

func (c Tile[T]) Mask(tile, mask Value) Value

Mask updates the bits of tile. The bits are specified by the mask. The bits that need to be updated should be flipped on in the mask.

func (Tile[T]) Merge added in v1.3.0 

func (c Tile[T]) Merge(merge func(Value) Value) Value

Merge atomically merges the tile by applying a merging function.

func (Tile[T]) Range added in v1.3.0 

func (c Tile[T]) Range(fn func(T) error) error

Range iterates over all of the objects in the set

func (Tile[T]) Value added in v1.3.0 

func (c Tile[T]) Value() Value

Value reads the tile information

func (Tile[T]) Write added in v1.3.0 

func (c Tile[T]) Write(tile Value)

Write updates the entire tile value.

type Update 

type Update[T comparable] struct {
	Point       // The tile location
	Old   Value // Old tile value
	New   Value // New tile value
	Add   T     // An object was added to the tile
	Del   T     // An object was removed from the tile
}

Update represents a tile update notification.

type Value added in v1.3.0 

type Value = uint32

Value represents a packed tile information, it must fit on 4 bytes.

type View 

type View[T comparable] struct {
	Grid  *Grid[T]       // The associated map
	Inbox chan Update[T] // The update inbox for the view
	// contains filtered or unexported fields
}

View represents a view which can monitor a collection of tiles.

func (*View[T]) At 

func (v *View[T]) At(x, y int16) (Tile[T], bool)

At returns the tile at a specified position.

func (*View[T]) Close 

func (v *View[T]) Close() error

Close closes the view and unsubscribes from everything.

func (*View[T]) Each 

func (v *View[T]) Each(fn func(Point, Tile[T]))

Each iterates over all of the tiles in the view.

func (*View[T]) MergeAt 

func (v *View[T]) MergeAt(x, y int16, tile, mask Value)

MergeAt updates the bits of tile at a specific coordinate. The bits are specified by the mask. The bits that need to be updated should be flipped on in the mask.

func (*View[T]) MoveAt 

func (v *View[T]) MoveAt(nw Point, fn func(Point, Tile[T]))

MoveAt moves the viewport to a specific coordinate.

func (*View[T]) MoveBy 

func (v *View[T]) MoveBy(x, y int16, fn func(Point, Tile[T]))

MoveBy moves the viewport towards a particular direction.

func (*View[T]) Resize 

func (v *View[T]) Resize(box Rect, fn func(Point, Tile[T]))

Resize resizes the viewport.

func (*View[T]) WriteAt 

func (v *View[T]) WriteAt(x, y int16, tile Value)

WriteAt updates the entire tile at a specific coordinate.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.