diff --git a/.github/logo.png b/.github/logo.png new file mode 100644 index 0000000..9e0ac8f Binary files /dev/null and b/.github/logo.png differ diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml index fd9e2f4..f291423 100644 --- a/.github/workflows/test.yml +++ b/.github/workflows/test.yml @@ -11,7 +11,7 @@ jobs: - name: Set up Go uses: actions/setup-go@v1 with: - go-version: 1.19 + go-version: 1.23 - name: Check out code uses: actions/checkout@v2 - name: Install dependencies diff --git a/README.md b/README.md index 078e5a6..2e5c7a5 100644 --- a/README.md +++ b/README.md @@ -1,38 +1,44 @@ # Tile: Data-Oriented 2D Grid Engine +

- + +
+ Go Version + PkgGoDev + Go Report Card + License + Coverage

-![GitHub go.mod Go version](https://img.shields.io/github/go-mod/go-version/kelindar/tile) -[![PkgGoDev](https://pkg.go.dev/badge/github.com/kelindar/tile)](https://pkg.go.dev/github.com/kelindar/tile) -[![Go Report Card](https://goreportcard.com/badge/github.com/kelindar/tile)](https://goreportcard.com/report/github.com/kelindar/tile) -[![License](https://img.shields.io/badge/License-MIT-blue.svg)](https://opensource.org/licenses/MIT) -[![Coverage Status](https://coveralls.io/repos/github/kelindar/tile/badge.svg)](https://coveralls.io/github/kelindar/tile) - 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 is 6 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. +- **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! +_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 basically a byte array `[6]byte` which allows you to customize what you want to put inside. Granted, it's a bit small but big enough to put an index or two. The reason this is so small 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. +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`, you first need to call `NewGrid()` method which pre-allocates the required space and initializes the tile grid itself. For example, you can create a 1000x1000 grid as shown below. +In order to create a new `Grid[T]`, you first need to call `NewGridOf[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. ```go -grid := NewGrid(1000, 1000) +grid := tile.NewGridOf[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. ```go -grid.Each(func(p Point, tile Tile) { +grid.Each(func(p Point, t tile.Tile[string]) { // ... }) ``` @@ -40,7 +46,7 @@ grid.Each(func(p Point, tile Tile) { 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. ```go -grid.Within(At(1, 1), At(5, 5), func(p Point, tile Tile) { +grid.Within(At(1, 1), At(5, 5), func(p Point, t tile.Tile[string]) { // ... }) ``` @@ -56,36 +62,39 @@ 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). ```go -grid.WriteAt(50, 100, Tile{1, 2, 3, 4, 5, 6}) +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. ```go -grid.WriteAt(50, 100, Tile{1, 2, 3, 4, 5, 6}) +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. + +```go +grid.MergeAt(50, 100, func(v Value) Value { + v += 1 + return v +}) +``` -The `MergeAt()` method of the grid allows you to transactionally 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()`. +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()`. ```go // assume byte[0] of the tile is 0b01010001 -grid.MergeAt(0, 0, - Tile{0b00101110, 0, 0, 0, 0, 0}, // Only last 2 bits matter - Tile{0b00000011, 0, 0, 0, 0, 0} // Mask specifies that we want to update last 2 bits +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 ``` -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. - -```go -grid.WriteAt(50, 100, Tile{1, 2, 3, 4, 5, 6}) -``` - - # 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. @@ -95,8 +104,8 @@ The `Path()` method is used for finding a way between 2 points, you provide it t ```go from := At(1, 1) goal := At(7, 7) -path, distance, found := m.Path(from, goal, func(t Tile) uint16{ - if isImpassable(t[0]) { +path, distance, found := m.Path(from, goal, func(v tile.Value) uint16{ + if isImpassable(v) { return 0 } return 1 @@ -108,26 +117,27 @@ The `Around()` method provides you with the ability to do a breadth-first search ```go point := At(50, 50) radius := 5 -m.Around(point, radius, func(t Tile) uint16{ - if isImpassable(t[0]) { +m.Around(point, radius, func(v tile.Value) uint16{ + if isImpassable(v) { return 0 } return 1 -}, func(p Point, t Tile) { +}, 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. +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 `NewView()` method which creates an `Observer` 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 order to use these observers, you need to first call the `NewView()` function 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. Note that `NewView[S, T]` takes two type parameters, the first one is the type of the state object and the second one is the type of the tile value. The state object is used to store additional information about the view itself, such as the name of the view or a pointer to a socket that is used to send updates to the client. In the example below we create a new 20x20 view on the grid and iterate through all of the tiles in the view. ```go -view := grid.View(NewRect(0, 0, 20, 20), func(p Point, tile Tile){ +view := tile.NewView[string, string](grid, "My View #1") +view.Resize(tile.NewRect(0, 0, 20, 20), func(p tile.Point, t tile.Tile){ // Optional, all of the tiles that are in the view now }) @@ -141,25 +151,25 @@ for { 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). ```go -view.MoveBy(0, 5, func(p Point, tile Tile){ - // Every tile which entered our view +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. ```go -view.MoveAt(At(10, 10), func(p Point, tile Tile){ - // Every tile which entered our view +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. ```go -viewRect := NewRect(10, 10, 30, 30) -view.Resize(viewRect, func(p Point, tile Tile){ - // Every tile which entered our view +viewRect := tile.NewRect(10, 10, 30, 30) +view.Resize(viewRect, func(p tile.Point, t tile.Tile){ + // Every tile which entered our view }) ``` @@ -172,7 +182,7 @@ 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](https://github.com/klauspost/compress) 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 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](https://github.com/klauspost/compress) 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. @@ -209,29 +219,33 @@ if err != nil{ 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. ``` -enchmarkGrid/each-8 514 2309290 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/neighbors-8 14809420 81.0 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/within-8 18488 64583 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/at-8 59917014 19.4 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/write-8 59944251 19.3 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/merge-8 49933837 24.0 ns/op 0 B/op 0 allocs/op -BenchmarkPath/9x9-8 206911 5361 ns/op 16468 B/op 3 allocs/op -BenchmarkPath/300x300-8 460 2558757 ns/op 7801175 B/op 4 allocs/op -BenchmarkPath/381x381-8 454 2689466 ns/op 62394354 B/op 4 allocs/op -BenchmarkPath/384x384-8 152 7809399 ns/op 62396320 B/op 5 allocs/op -BenchmarkPath/6144x6144-8 141 7461047 ns/op 62395595 B/op 3 allocs/op -BenchmarkPath/6147x6147-8 160 7462501 ns/op 62395357 B/op 3 allocs/op -BenchmarkAround/3r-8 333166 3485 ns/op 385 B/op 1 allocs/op -BenchmarkAround/5r-8 153844 7833 ns/op 931 B/op 2 allocs/op -BenchmarkAround/10r-8 59702 20083 ns/op 3489 B/op 2 allocs/op -BenchmarkHeap-8 97560 12229 ns/op 3968 B/op 5 allocs/op -BenchmarkPoint/within-8 1000000000 0.218 ns/op 0 B/op 0 allocs/op -BenchmarkPoint/within-rect-8 1000000000 0.218 ns/op 0 B/op 0 allocs/op -BenchmarkPoint/interleave-8 1000000000 0.652 ns/op 0 B/op 0 allocs/op -BenchmarkStore/save-8 7045 173594 ns/op 8 B/op 1 allocs/op -BenchmarkStore/read-8 2666 453553 ns/op 651594 B/op 8 allocs/op -BenchmarkView/write-8 10619553 111 ns/op 16 B/op 1 allocs/op -BenchmarkView/move-8 7500 160667 ns/op 0 B/op 0 allocs/op +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 @@ -240,4 +254,4 @@ We are open to contributions, feel free to submit a pull request and we'll revie ## License -Tile is licensed under the [MIT License](LICENSE.md). \ No newline at end of file +Tile is licensed under the [MIT License](LICENSE.md). diff --git a/fixtures/logo.png b/fixtures/logo.png deleted file mode 100644 index 22429ff..0000000 Binary files a/fixtures/logo.png and /dev/null differ diff --git a/go.mod b/go.mod index 9813b81..8090015 100644 --- a/go.mod +++ b/go.mod @@ -1,10 +1,11 @@ module github.com/kelindar/tile -go 1.19 +go 1.24 require ( - github.com/kelindar/iostream v1.3.0 - github.com/stretchr/testify v1.8.1 + github.com/kelindar/intmap v1.5.0 + github.com/kelindar/iostream v1.4.0 + github.com/stretchr/testify v1.9.0 ) require ( diff --git a/go.sum b/go.sum index 040afb3..f924de3 100644 --- a/go.sum +++ b/go.sum @@ -1,19 +1,14 @@ -github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38= github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c= github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38= -github.com/kelindar/iostream v1.3.0 h1:Bz2qQabipZlF1XCk64bnxsGLete+iHtayGPeWVpbwbo= -github.com/kelindar/iostream v1.3.0/go.mod h1:MkjMuVb6zGdPQVdwLnFRO0xOTOdDvBWTztFmjRDQkXk= +github.com/kelindar/intmap v1.5.0 h1:VY+AdO4Wx1sF1vGiTkS8n2lxhmFgOQwCIFuePQP4Iqw= +github.com/kelindar/intmap v1.5.0/go.mod h1:NkypxhfaklmDTJqwano3Q1BWk6je77qgQwszDwu8Kc8= +github.com/kelindar/iostream v1.4.0 h1:ELKlinnM/K3GbRp9pYhWuZOyBxMMlYAfsOP+gauvZaY= +github.com/kelindar/iostream v1.4.0/go.mod h1:MkjMuVb6zGdPQVdwLnFRO0xOTOdDvBWTztFmjRDQkXk= github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM= github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4= -github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME= -github.com/stretchr/objx v0.4.0/go.mod h1:YvHI0jy2hoMjB+UWwv71VJQ9isScKT/TqJzVSSt89Yw= -github.com/stretchr/objx v0.5.0/go.mod h1:Yh+to48EsGEfYuaHDzXPcE3xhTkx73EhmCGUpEOglKo= -github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg= -github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU= -github.com/stretchr/testify v1.8.1 h1:w7B6lhMri9wdJUVmEZPGGhZzrYTPvgJArz7wNPgYKsk= -github.com/stretchr/testify v1.8.1/go.mod h1:w2LPCIKwWwSfY2zedu0+kehJoqGctiVI29o6fzry7u4= +github.com/stretchr/testify v1.9.0 h1:HtqpIVDClZ4nwg75+f6Lvsy/wHu+3BoSGCbBAcpTsTg= +github.com/stretchr/testify v1.9.0/go.mod h1:r2ic/lqez/lEtzL7wO/rwa5dbSLXVDPFyf8C91i36aY= gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM= gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0= -gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM= gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA= gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM= diff --git a/grid.go b/grid.go index 881eadc..63cdef5 100644 --- a/grid.go +++ b/grid.go @@ -4,55 +4,48 @@ package tile import ( - "reflect" - "runtime" + "sync" "sync/atomic" - "unsafe" ) -// Iterator represents an iterator function. -type Iterator = func(Point, Tile) -type pageFn = func(*page) -type indexFn = func(x, y int16) int -type pointFn = func(i int) Point - // Grid represents a 2D tile map. Internally, a map is composed of 3x3 pages. -type Grid struct { - pages []page // The pages of the map - pageWidth int16 // The max page width - pageHeight int16 // The max page height - observers pubsub // The map of observers - Size Point // The map size - indexOf indexFn // The page index function +type Grid[T comparable] struct { + pages []page[T] // The pages of the map + pageWidth int16 // The max page width + pageHeight int16 // The max page height + observers pubsub[T] // The map of observers + Size Point // The map size } // NewGrid returns a new map of the specified size. The width and height must be both // multiples of 3. -func NewGrid(width, height int16) *Grid { +func NewGrid(width, height int16) *Grid[string] { + return NewGridOf[string](width, height) +} + +// NewGridOf returns a new map of the specified size. The width and height must be both +// multiples of 3. +func NewGridOf[T comparable](width, height int16) *Grid[T] { width, height = width/3, height/3 max := int32(width) * int32(height) - pages := make([]page, max) - m := &Grid{ + pages := make([]page[T], max) + m := &Grid[T]{ pages: pages, pageWidth: width, pageHeight: height, - observers: pubsub{}, Size: At(width*3, height*3), + observers: pubsub[T]{ + tmp: sync.Pool{ + New: func() any { return make(map[Observer[T]]struct{}, 4) }, + }, + }, } // Function to calculate a point based on the index var pointAt func(i int) Point = func(i int) Point { return At(int16(i%int(width)), int16(i/int(width))) } - m.indexOf = m.pointToFlat - - // If the map is square and page count is a power of 2, use z-curve filling instead - // as this will speed up data access under certain conditions. - if width == height && (width&(width-1)) == 0 { - pointAt = deinterleavePoint - m.indexOf = m.pointToZ - } for i := 0; i < int(max); i++ { pages[i].point = pointAt(i).MultiplyScalar(3) @@ -60,29 +53,21 @@ func NewGrid(width, height int16) *Grid { return m } -func (m *Grid) pointToFlat(x, y int16) int { - return int(x) + int(m.pageWidth)*int(y) -} - -func (m *Grid) pointToZ(x, y int16) int { - return int(At(x, y).Interleave()) -} - // Each iterates over all of the tiles in the map. -func (m *Grid) Each(fn Iterator) { +func (m *Grid[T]) Each(fn func(Point, Tile[T])) { until := int(m.pageHeight) * int(m.pageWidth) for i := 0; i < until; i++ { - m.pages[i].Each(fn) + m.pages[i].Each(m, fn) } } // Within selects the tiles within a specifid bounding box which is specified by // north-west and south-east coordinates. -func (m *Grid) Within(nw, se Point, fn Iterator) { - m.pagesWithin(nw, se, func(page *page) { - page.Each(func(p Point, tile Tile) { +func (m *Grid[T]) Within(nw, se Point, fn func(Point, Tile[T])) { + m.pagesWithin(nw, se, func(page *page[T]) { + page.Each(m, func(p Point, v Tile[T]) { if p.Within(nw, se) { - fn(p, tile) + fn(p, v) } }) }) @@ -90,56 +75,51 @@ func (m *Grid) Within(nw, se Point, fn Iterator) { // pagesWithin selects the pages within a specifid bounding box which is specified // by north-west and south-east coordinates. -func (m *Grid) pagesWithin(nw, se Point, fn pageFn) { +func (m *Grid[T]) pagesWithin(nw, se Point, fn func(*page[T])) { if !se.WithinSize(m.Size) { se = At(m.Size.X-1, m.Size.Y-1) } for x := nw.X / 3; x <= se.X/3; x++ { for y := nw.Y / 3; y <= se.Y/3; y++ { - fn(&m.pages[m.indexOf(x, y)]) + fn(m.pageAt(x, y)) } } } // At returns the tile at a specified position -func (m *Grid) At(x, y int16) (Tile, bool) { +func (m *Grid[T]) At(x, y int16) (Tile[T], bool) { if x >= 0 && y >= 0 && x < m.Size.X && y < m.Size.Y { - return m.pages[m.indexOf(x/3, y/3)].Get(x, y), true + return m.pageAt(x/3, y/3).At(m, x, y), true } - return Tile{}, false + return Tile[T]{}, false } // WriteAt updates the entire tile value at a specific coordinate -func (m *Grid) WriteAt(x, y int16, tile Tile) { +func (m *Grid[T]) WriteAt(x, y int16, tile Value) { if x >= 0 && y >= 0 && x < m.Size.X && y < m.Size.Y { - if m.pages[m.indexOf(x/3, y/3)].SetTile(x, y, tile) { - m.observers.Notify(At(x/3*3, y/3*3), At(x, y), tile) - } + m.pageAt(x/3, y/3).writeTile(m, uint8((y%3)*3+(x%3)), tile) } } -// 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 (m *Grid) MergeAt(x, y int16, tile, mask Tile) { - if x >= 0 && y >= 0 && x < m.Size.X && y < m.Size.Y { - if v, ok := m.pages[m.indexOf(x/3, y/3)].SetBits(x, y, tile, mask); ok { - m.observers.Notify(At(x/3*3, y/3*3), At(x, y), v) - } - } +// 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 (m *Grid[T]) MaskAt(x, y int16, tile, mask Value) { + m.MergeAt(x, y, func(value Value) Value { + return (value &^ mask) | (tile & mask) + }) } -// NotifyAt triggers the notification event for all of the observers at a given tile. -func (m *Grid) NotifyAt(x, y int16) { +// Merge atomically merges the tile by applying a merging function at a specific coordinate. +func (m *Grid[T]) MergeAt(x, y int16, merge func(Value) Value) { if x >= 0 && y >= 0 && x < m.Size.X && y < m.Size.Y { - tile := m.pages[m.indexOf(x/3, y/3)].Get(x, y) - m.observers.Notify(At(x/3*3, y/3*3), At(x, y), tile) + m.pageAt(x/3, y/3).mergeTile(m, uint8((y%3)*3+(x%3)), merge) } } // Neighbors iterates over the direct neighbouring tiles -func (m *Grid) Neighbors(x, y int16, fn Iterator) { +func (m *Grid[T]) Neighbors(x, y int16, fn func(Point, Tile[T])) { // First we need to figure out which pages contain the neighboring tiles and // then load them. In the best-case we need to load only a single page. In @@ -151,161 +131,364 @@ func (m *Grid) Neighbors(x, y int16, fn Iterator) { // Get the North if y > 0 { - fn(At(x, y-1), m.pages[m.indexOf(nX, nY)].Get(x, y-1)) + fn(At(x, y-1), m.pageAt(nX, nY).At(m, x, y-1)) } // Get the East if eX < m.pageWidth { - fn(At(x+1, y), m.pages[m.indexOf(eX, eY)].Get(x+1, y)) + fn(At(x+1, y), m.pageAt(eX, eY).At(m, x+1, y)) } // Get the South if sY < m.pageHeight { - fn(At(x, y+1), m.pages[m.indexOf(sX, sY)].Get(x, y+1)) + fn(At(x, y+1), m.pageAt(sX, sY).At(m, x, y+1)) } // Get the West if x > 0 { - fn(At(x-1, y), m.pages[m.indexOf(wX, wY)].Get(x-1, y)) + fn(At(x-1, y), m.pageAt(wX, wY).At(m, x-1, y)) } } -// View creates a new view of the map. -func (m *Grid) View(rect Rect, fn Iterator) *View { - view := &View{ - Grid: m, - Inbox: make(chan Update, 16), - rect: NewRect(-1, -1, -1, -1), +// pageAt loads a page at a given page location +func (m *Grid[T]) pageAt(x, y int16) *page[T] { + index := int(x) + int(m.pageWidth)*int(y) + + // Eliminate bounds checks + if index >= 0 && index < len(m.pages) { + return &m.pages[index] } - // Call the resize method - view.Resize(rect, fn) - return view + return nil } -// ----------------------------------------------------------------------------- +// ---------------------------------- Tile ---------------------------------- -// Tile represents a packed tile information, it must fit on 6 bytes. -type Tile [6]byte +// Value represents a packed tile information, it must fit on 4 bytes. +type Value = uint32 -// ----------------------------------------------------------------------------- +// ---------------------------------- Page ---------------------------------- // page represents a 3x3 tile page each page should neatly fit on a cache // line and speed things up. -type page struct { - lock int32 // Page spin-lock, 4 bytes - flags uint16 // Page flags, 2 bytes - point Point // Page X, Y coordinate, 4 bytes - tiles [9]Tile // Page tiles, 54 bytes +type page[T comparable] struct { + mu sync.Mutex // State lock, 8 bytes + state map[T]uint8 // State data, 8 bytes + flags uint32 // Page flags, 4 bytes + point Point // Page X, Y coordinate, 4 bytes + tiles [9]Value // Page tiles, 36 bytes +} + +// tileAt reads a tile at a page index +func (p *page[T]) tileAt(idx uint8) Value { + return Value(atomic.LoadUint32((*uint32)(&p.tiles[idx]))) +} + +// IsObserved returns whether the tile is observed or not +func (p *page[T]) IsObserved() bool { + return (atomic.LoadUint32(&p.flags))&1 != 0 } // Bounds returns the bounding box for the tile page. -func (p *page) Bounds() Rect { +func (p *page[T]) Bounds() Rect { return Rect{p.point, At(p.point.X+3, p.point.Y+3)} } -// SetTile updates the tile at a specific coordinate -func (p *page) SetTile(x, y int16, tile Tile) bool { - i := (y%3)*3 + (x % 3) +// At returns a cursor at a specific coordinate +func (p *page[T]) At(grid *Grid[T], x, y int16) Tile[T] { + return Tile[T]{grid: grid, data: p, idx: uint8((y%3)*3 + (x % 3))} +} - // Synchronize the update from this point on - p.Lock() - p.tiles[i] = tile - notify := p.flags&1 != 0 - p.Unlock() +// Each iterates over all of the tiles in the page. +func (p *page[T]) Each(grid *Grid[T], fn func(Point, Tile[T])) { + x, y := p.point.X, p.point.Y + fn(Point{x, y}, Tile[T]{grid: grid, data: p, idx: 0}) // NW + fn(Point{x + 1, y}, Tile[T]{grid: grid, data: p, idx: 1}) // N + fn(Point{x + 2, y}, Tile[T]{grid: grid, data: p, idx: 2}) // NE + fn(Point{x, y + 1}, Tile[T]{grid: grid, data: p, idx: 3}) // W + fn(Point{x + 1, y + 1}, Tile[T]{grid: grid, data: p, idx: 4}) // C + fn(Point{x + 2, y + 1}, Tile[T]{grid: grid, data: p, idx: 5}) // E + fn(Point{x, y + 2}, Tile[T]{grid: grid, data: p, idx: 6}) // SW + fn(Point{x + 1, y + 2}, Tile[T]{grid: grid, data: p, idx: 7}) // S + fn(Point{x + 2, y + 2}, Tile[T]{grid: grid, data: p, idx: 8}) // SE +} + +// SetObserved sets the observed flag on the page +func (p *page[T]) SetObserved(observed bool) { + const flagObserved = 0x1 + for { + value := atomic.LoadUint32(&p.flags) + merge := value + if observed { + merge = value | flagObserved + } else { + merge = value &^ flagObserved + } - // Return whether tile is observed or not - return notify + if atomic.CompareAndSwapUint32(&p.flags, value, merge) { + break + } + } } -// SetBits updates certain tile bits at a specific coordinate -func (p *page) SetBits(x, y int16, tile, mask Tile) (Tile, bool) { - t := uint64(tile[0]) | uint64(tile[1])<<8 | uint64(tile[2])<<16 | - uint64(tile[3])<<24 | uint64(tile[4])<<32 | uint64(tile[5])<<40 - m := uint64(mask[0]) | uint64(mask[1])<<8 | uint64(mask[2])<<16 | - uint64(mask[3])<<24 | uint64(mask[4])<<32 | uint64(mask[5])<<40 - i := (y%3)*3 + (x % 3) +// Lock locks the state. Note: this needs to be named Lock() so go vet will +// complain if the page is copied around. +func (p *page[T]) Lock() { + p.mu.Lock() +} - // Get the tile and do the binary merge - p.Lock() - b := &p.tiles[i] - v := uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | - uint64(b[3])<<24 | uint64(b[4])<<32 | uint64(b[5])<<40 - v = (v &^ m) | (t & m) - - // Write the merged result back - b[0] = byte(v) - b[1] = byte(v >> 8) - b[2] = byte(v >> 16) - b[3] = byte(v >> 24) - b[4] = byte(v >> 32) - b[5] = byte(v >> 40) - merged, notify := *b, p.flags&1 != 0 - p.Unlock() +// Unlock unlocks the state. Note: this needs to be named Unlock() so go vet will +// complain if the page is copied around. +func (p *page[T]) Unlock() { + p.mu.Unlock() +} + +// ---------------------------------- Mutations ---------------------------------- + +// writeTile stores the tile and return whether tile is observed or not +func (p *page[T]) writeTile(grid *Grid[T], idx uint8, after Value) { + before := p.tileAt(idx) + for !atomic.CompareAndSwapUint32(&p.tiles[idx], uint32(before), uint32(after)) { + before = p.tileAt(idx) + } - // Return the merged tile data and whether tile is observed or not - return merged, notify + // If observed, notify the observers of the tile + if p.IsObserved() { + at := pointOf(p.point, idx) + grid.observers.Notify1(&Update[T]{ + Old: ValueAt{ + Point: at, + Value: before, + }, + New: ValueAt{ + Point: at, + Value: after, + }, + }, p.point) + } } -// Get gets a tile at a specific coordinate. -func (p *page) Get(x, y int16) (tile Tile) { - i := (y%3)*3 + (x % 3) +// mergeTile atomically merges the tile bits given a function +func (p *page[T]) mergeTile(grid *Grid[T], idx uint8, fn func(Value) Value) Value { + before := p.tileAt(idx) + after := fn(before) + + // Swap, if we're not able to re-merge again + for !atomic.CompareAndSwapUint32(&p.tiles[idx], uint32(before), uint32(after)) { + before = p.tileAt(idx) + after = fn(before) + } + + // If observed, notify the observers of the tile + if p.IsObserved() { + at := pointOf(p.point, idx) + grid.observers.Notify1(&Update[T]{ + Old: ValueAt{ + Point: at, + Value: before, + }, + New: ValueAt{ + Point: at, + Value: after, + }, + }, p.point) + } + + // Return the merged tile data + return after +} +// addObject adds object to the set +func (p *page[T]) addObject(idx uint8, object T) (value uint32) { p.Lock() - tile = p.tiles[i] + + // Lazily initialize the map, as most pages might not have anything stored + // in them (e.g. water or empty tile) + if p.state == nil { + p.state = make(map[T]uint8) + } + + p.state[object] = uint8(idx) + value = p.tileAt(idx) p.Unlock() return } -// Each iterates over all of the tiles in the page. -func (p *page) Each(fn Iterator) { +// delObject removes the object from the set +func (p *page[T]) delObject(idx uint8, object T) (value uint32) { p.Lock() - tiles := p.tiles + if p.state != nil { + delete(p.state, object) + } + value = p.tileAt(idx) p.Unlock() + return +} - x, y := p.point.X, p.point.Y - fn(Point{x, y}, tiles[0]) // NW - fn(Point{x + 1, y}, tiles[1]) // N - fn(Point{x + 2, y}, tiles[2]) // NE - fn(Point{x, y + 1}, tiles[3]) // W - fn(Point{x + 1, y + 1}, tiles[4]) // C - fn(Point{x + 2, y + 1}, tiles[5]) // E - fn(Point{x, y + 2}, tiles[6]) // SW - fn(Point{x + 1, y + 2}, tiles[7]) // S - fn(Point{x + 2, y + 2}, tiles[8]) // SE +// ---------------------------------- Tile Cursor ---------------------------------- + +// Tile represents an iterator over all state objects at a particular location. +type Tile[T comparable] struct { + grid *Grid[T] // grid pointer + data *page[T] // page pointer + idx uint8 // tile index } -// SetObserved sets the observed flag on the page -func (p *page) SetObserved(observed bool) { - p.Lock() - defer p.Unlock() +// Count returns number of objects at the current tile. +func (t Tile[T]) Count() (count int) { + t.data.Lock() + defer t.data.Unlock() + for _, idx := range t.data.state { + if idx == uint8(t.idx) { + count++ + } + } + return +} + +// Point returns the point of the tile +func (t Tile[T]) Point() Point { + return pointOf(t.data.point, t.idx) +} + +// Value reads the tile information +func (t Tile[T]) Value() Value { + return t.data.tileAt(t.idx) +} - if observed { - p.flags = p.flags | 1 - } else { - p.flags = p.flags &^ 1 +// Range iterates over all of the objects in the set +func (t Tile[T]) Range(fn func(T) error) error { + t.data.Lock() + defer t.data.Unlock() + for v, idx := range t.data.state { + if idx == uint8(t.idx) { + if err := fn(v); err != nil { + return err + } + } } + return nil } -// Lock locks the spin lock. Note: this needs to be named Lock() so go vet will -// complain if the page is copied around. -func (p *page) Lock() { - for !atomic.CompareAndSwapInt32(&p.lock, 0, 1) { - runtime.Gosched() +// Observers iterates over all views observing this tile +func (t Tile[T]) Observers(fn func(view Observer[T])) { + if !t.data.IsObserved() { + return } + + t.grid.observers.Each1(func(sub Observer[T]) { + if sub.Viewport().Contains(t.Point()) { + fn(sub) + } + }, t.data.point) } -// Unlock unlocks the page. Note: this needs to be named Unlock() so go vet will -// complain if the page is copied around. -func (p *page) Unlock() { - atomic.StoreInt32(&p.lock, 0) +// Add adds object to the set +func (t Tile[T]) Add(v T) { + value := t.data.addObject(t.idx, v) + + // If observed, notify the observers of the tile + if t.data.IsObserved() { + at := t.Point() + t.grid.observers.Notify1(&Update[T]{ + Old: ValueAt{ + Point: at, + Value: value, + }, + New: ValueAt{ + Point: at, + Value: value, + }, + Add: v, + }, t.data.point) + } +} + +// Del removes the object from the set +func (t Tile[T]) Del(v T) { + value := t.data.delObject(t.idx, v) + + // If observed, notify the observers of the tile + if t.data.IsObserved() { + at := t.Point() + t.grid.observers.Notify1(&Update[T]{ + Old: ValueAt{ + Point: at, + Value: value, + }, + New: ValueAt{ + Point: at, + Value: value, + }, + Del: v, + }, t.data.point) + } } -// Data returns a buffer to the tile data, without allocations. -func (p *page) Data() []byte { - var out reflect.SliceHeader - out.Data = reflect.ValueOf(&p.tiles).Pointer() - out.Len = tileDataSize - out.Cap = tileDataSize - return *(*[]byte)(unsafe.Pointer(&out)) +// Move moves an object from the current tile to the destination tile. +func (t Tile[T]) Move(v T, dst Point) bool { + d, ok := t.grid.At(dst.X, dst.Y) + if !ok { + return false + } + + // Move the object from the source to the destination + tv := t.data.delObject(d.idx, v) + dv := d.data.addObject(d.idx, v) + if !t.data.IsObserved() && !d.data.IsObserved() { + return true + } + + // Prepare the update notification + update := &Update[T]{ + Old: ValueAt{ + Point: t.Point(), + Value: tv, + }, + New: ValueAt{ + Point: d.Point(), + Value: dv, + }, + Del: v, + Add: v, + } + + switch { + case t.data == d.data || !d.data.IsObserved(): + t.grid.observers.Notify1(update, t.data.point) + case !t.data.IsObserved(): + t.grid.observers.Notify1(update, d.data.point) + default: + t.grid.observers.Notify2(update, [2]Point{ + t.data.point, + d.data.point, + }) + } + return true +} + +// Write updates the entire tile value. +func (t Tile[T]) Write(tile Value) { + t.data.writeTile(t.grid, t.idx, tile) +} + +// Merge atomically merges the tile by applying a merging function. +func (t Tile[T]) Merge(merge func(Value) Value) Value { + return t.data.mergeTile(t.grid, t.idx, merge) +} + +// 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 (t Tile[T]) Mask(tile, mask Value) Value { + return t.data.mergeTile(t.grid, t.idx, func(value Value) Value { + return (value &^ mask) | (tile & mask) + }) +} + +// pointOf returns the point given an index +func pointOf(page Point, idx uint8) Point { + return Point{ + X: page.X + int16(idx)%3, + Y: page.Y + int16(idx)/3, + } } diff --git a/grid_test.go b/grid_test.go index e67447b..0639342 100644 --- a/grid_test.go +++ b/grid_test.go @@ -4,6 +4,9 @@ package tile import ( + "fmt" + "io" + "sync" "testing" "unsafe" @@ -11,25 +14,26 @@ import ( ) /* -cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz -BenchmarkGrid/each-8 698 1694002 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/neighbors-8 19652220 66.16 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/within-8 26200 47040 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/at-8 59190276 16.96 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/write-8 100000000 15.40 ns/op 0 B/op 0 allocs/op -BenchmarkGrid/merge-8 52110926 23.06 ns/op 0 B/op 0 allocs/op +cpu: 13th Gen Intel(R) Core(TM) i7-13700K +BenchmarkGrid/each-24 1452 830268 ns/op 0 B/op 0 allocs/op +BenchmarkGrid/neighbors-24 121583491 9.861 ns/op 0 B/op 0 allocs/op +BenchmarkGrid/within-24 49360 24477 ns/op 0 B/op 0 allocs/op +BenchmarkGrid/at-24 687659378 1.741 ns/op 0 B/op 0 allocs/op +BenchmarkGrid/write-24 191272338 6.307 ns/op 0 B/op 0 allocs/op +BenchmarkGrid/merge-24 162536985 7.332 ns/op 0 B/op 0 allocs/op +BenchmarkGrid/mask-24 158258084 7.601 ns/op 0 B/op 0 allocs/op */ func BenchmarkGrid(b *testing.B) { - var d [6]byte + var d Tile[uint32] var p Point defer assert.NotNil(b, d) - m := NewGrid(768, 768) + m := NewGridOf[uint32](768, 768) b.Run("each", func(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.Each(func(point Point, tile Tile) { + m.Each(func(point Point, tile Tile[uint32]) { p = point d = tile }) @@ -40,7 +44,7 @@ func BenchmarkGrid(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.Neighbors(300, 300, func(point Point, tile Tile) { + m.Neighbors(300, 300, func(point Point, tile Tile[uint32]) { p = point d = tile }) @@ -51,7 +55,7 @@ func BenchmarkGrid(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.Within(At(100, 100), At(200, 200), func(point Point, tile Tile) { + m.Within(At(100, 100), At(200, 200), func(point Point, tile Tile[uint32]) { p = point d = tile }) @@ -71,7 +75,7 @@ func BenchmarkGrid(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.WriteAt(100, 100, Tile{}) + m.WriteAt(100, 100, Value(0)) } }) @@ -79,29 +83,85 @@ func BenchmarkGrid(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.MergeAt(100, 100, Tile{}, Tile{0, 1, 0, 0, 0}) + m.MergeAt(100, 100, func(v Value) Value { + v += 1 + return v + }) + } + }) + + b.Run("mask", func(b *testing.B) { + b.ReportAllocs() + b.ResetTimer() + for n := 0; n < b.N; n++ { + m.MaskAt(100, 100, Value(0), Value(1)) + } + }) +} + +/* +cpu: 13th Gen Intel(R) Core(TM) i7-13700K +BenchmarkState/range-24 17017800 71.14 ns/op 0 B/op 0 allocs/op +BenchmarkState/add-24 72639224 16.32 ns/op 0 B/op 0 allocs/op +BenchmarkState/del-24 82469125 13.65 ns/op 0 B/op 0 allocs/op +*/ +func BenchmarkState(b *testing.B) { + m := NewGridOf[int](768, 768) + m.Each(func(p Point, c Tile[int]) { + for i := 0; i < 10; i++ { + c.Add(i) + } + }) + + b.Run("range", func(b *testing.B) { + b.ReportAllocs() + b.ResetTimer() + for n := 0; n < b.N; n++ { + cursor, _ := m.At(100, 100) + cursor.Range(func(v int) error { + return nil + }) + } + }) + + b.Run("add", func(b *testing.B) { + b.ReportAllocs() + b.ResetTimer() + for n := 0; n < b.N; n++ { + cursor, _ := m.At(100, 100) + cursor.Add(100) + } + }) + + b.Run("del", func(b *testing.B) { + b.ReportAllocs() + b.ResetTimer() + for n := 0; n < b.N; n++ { + cursor, _ := m.At(100, 100) + cursor.Del(100) } }) } func TestPageSize(t *testing.T) { - assert.LessOrEqual(t, int(unsafe.Sizeof(page{})), 64) + assert.Equal(t, 8, int(unsafe.Sizeof(map[uintptr]Point{}))) + assert.Equal(t, 64, int(unsafe.Sizeof(page[string]{}))) + assert.Equal(t, 36, int(unsafe.Sizeof([9]Value{}))) } func TestWithin(t *testing.T) { m := NewGrid(9, 9) var path []string - m.Within(At(1, 1), At(5, 5), func(p Point, tile Tile) { + m.Within(At(1, 1), At(5, 5), func(p Point, tile Tile[string]) { path = append(path, p.String()) }) - assert.Equal(t, 25, len(path)) + assert.Equal(t, 16, len(path)) assert.ElementsMatch(t, []string{ - "1,1", "2,1", "1,2", "2,2", "3,1", - "4,1", "5,1", "3,2", "4,2", "5,2", - "1,3", "2,3", "1,4", "2,4", "1,5", - "2,5", "3,3", "4,3", "5,3", "3,4", - "4,4", "5,4", "3,5", "4,5", "5,5", + "1,1", "2,1", "1,2", "2,2", + "3,1", "4,1", "3,2", "4,2", + "1,3", "2,3", "1,4", "2,4", + "3,3", "4,3", "3,4", "4,4", }, path) } @@ -109,7 +169,7 @@ func TestWithinCorner(t *testing.T) { m := NewGrid(9, 9) var path []string - m.Within(At(7, 6), At(10, 10), func(p Point, tile Tile) { + m.Within(At(7, 6), At(10, 10), func(p Point, tile Tile[string]) { path = append(path, p.String()) }) assert.Equal(t, 6, len(path)) @@ -119,10 +179,29 @@ func TestWithinCorner(t *testing.T) { }, path) } +func TestWithinXY(t *testing.T) { + assert.False(t, At(4, 8).WithinRect(NewRect(1, 6, 4, 10))) +} + +func TestWithinOneSide(t *testing.T) { + m := NewGrid(9, 9) + + var path []string + m.Within(At(1, 6), At(4, 10), func(p Point, tile Tile[string]) { + path = append(path, p.String()) + }) + assert.Equal(t, 9, len(path)) + assert.ElementsMatch(t, []string{ + "1,6", "2,6", "3,6", + "1,7", "2,7", "3,7", + "1,8", "2,8", "3,8", + }, path) +} + func TestWithinInvalid(t *testing.T) { m := NewGrid(9, 9) count := 0 - m.Within(At(10, 10), At(20, 20), func(p Point, tile Tile) { + m.Within(At(10, 10), At(20, 20), func(p Point, tile Tile[string]) { count++ }) assert.Equal(t, 0, count) @@ -132,7 +211,7 @@ func TestEach(t *testing.T) { m := NewGrid(9, 9) var path []string - m.Each(func(p Point, tile Tile) { + m.Each(func(p Point, tile Tile[string]) { path = append(path, p.String()) }) assert.Equal(t, 81, len(path)) @@ -163,16 +242,16 @@ func TestNeighbors(t *testing.T) { // Create a 9x9 map with labeled tiles m := NewGrid(9, 9) - m.Each(func(p Point, tile Tile) { - copy(tile[:], p.String()[:3]) - m.WriteAt(p.X, p.Y, tile) + m.Each(func(p Point, tile Tile[string]) { + m.WriteAt(p.X, p.Y, Value(p.Integer())) }) // Run all the tests for _, tc := range tests { var out []string - m.Neighbors(tc.x, tc.y, func(_ Point, tile Tile) { - out = append(out, string(tile[:3])) + m.Neighbors(tc.x, tc.y, func(_ Point, tile Tile[string]) { + loc := unpackPoint(uint32(tile.Value())) + out = append(out, loc.String()) }) assert.ElementsMatch(t, tc.expect, out) } @@ -182,22 +261,21 @@ func TestAt(t *testing.T) { // Create a 9x9 map with labeled tiles m := NewGrid(9, 9) - m.Each(func(p Point, tile Tile) { - copy(tile[:], p.String()[:3]) - m.WriteAt(p.X, p.Y, tile) + m.Each(func(p Point, tile Tile[string]) { + m.WriteAt(p.X, p.Y, Value(p.Integer())) }) // Make sure our At() and the position matches - m.Each(func(p Point, tile Tile) { + m.Each(func(p Point, tile Tile[string]) { at, _ := m.At(p.X, p.Y) - assert.Equal(t, p.String(), string(at[:3])) + assert.Equal(t, p.String(), unpackPoint(uint32(at.Value())).String()) }) // Make sure that points match for y := int16(0); y < 9; y++ { for x := int16(0); x < 9; x++ { at, _ := m.At(x, y) - assert.Equal(t, At(x, y).String(), string(at[:3])) + assert.Equal(t, At(x, y).String(), unpackPoint(uint32(at.Value())).String()) } } } @@ -207,22 +285,111 @@ func TestUpdate(t *testing.T) { // Create a 9x9 map with labeled tiles m := NewGrid(9, 9) i := 0 - m.Each(func(p Point, tile Tile) { + m.Each(func(p Point, _ Tile[string]) { i++ - tile[0] = byte(i) - m.WriteAt(p.X, p.Y, tile) + m.WriteAt(p.X, p.Y, Value(i)) }) // Assert the update - tile, _ := m.At(8, 8) - assert.Equal(t, 81, int(tile[0])) + cursor, _ := m.At(8, 8) + assert.Equal(t, 81, int(cursor.Value())) // 81 = 0b01010001 - tile[0] = 0b00101110 // change last 2 bits and should ignore other bits - m.MergeAt(8, 8, tile, Tile{ - 0b00000011, 0, 0, 0, 0, 0, + delta := Value(0b00101110) // change last 2 bits and should ignore other bits + m.MaskAt(8, 8, delta, Value(0b00000011)) + + // original: 0101 0001 + // delta: 0010 1110 + // mask: 0000 0011 + // result: 0101 0010 + cursor, _ = m.At(8, 8) + assert.Equal(t, 0b01010010, int(cursor.Value())) +} + +func TestState(t *testing.T) { + m := NewGrid(9, 9) + m.Each(func(p Point, c Tile[string]) { + c.Add(p.String()) + c.Add(p.String()) // duplicate + }) + + m.Each(func(p Point, c Tile[string]) { + assert.Equal(t, 1, c.Count()) + assert.NoError(t, c.Range(func(s string) error { + assert.Equal(t, p.String(), s) + return nil + })) + + c.Del(p.String()) + assert.Equal(t, 0, c.Count()) + }) +} + +func TestStateRangeErr(t *testing.T) { + m := NewGrid(9, 9) + m.Each(func(p Point, c Tile[string]) { + c.Add(p.String()) + }) + + m.Each(func(p Point, c Tile[string]) { + assert.Error(t, c.Range(func(s string) error { + return io.EOF + })) }) +} + +func TestPointOf(t *testing.T) { + truthTable := func(x, y int16, idx uint8) (int16, int16) { + switch idx { + case 0: + return x, y + case 1: + return x + 1, y + case 2: + return x + 2, y + case 3: + return x, y + 1 + case 4: + return x + 1, y + 1 + case 5: + return x + 2, y + 1 + case 6: + return x, y + 2 + case 7: + return x + 1, y + 2 + case 8: + return x + 2, y + 2 + default: + return x, y + } + } + + for i := 0; i < 9; i++ { + at := pointOf(At(0, 0), uint8(i)) + x, y := truthTable(0, 0, uint8(i)) + assert.Equal(t, x, at.X, fmt.Sprintf("idx=%v", i)) + assert.Equal(t, y, at.Y, fmt.Sprintf("idx=%v", i)) + } +} + +func TestConcurrentMerge(t *testing.T) { + const count = 10000 + var wg sync.WaitGroup + wg.Add(count) + + m := NewGrid(9, 9) + for i := 0; i < count; i++ { + go func() { + m.MergeAt(1, 1, func(v Value) Value { + v += 1 + return v + }) + wg.Done() + }() + } - tile, _ = m.At(8, 8) - assert.Equal(t, 0b01010010, int(tile[0])) + wg.Wait() + tile, ok := m.At(1, 1) + assert.True(t, ok) + assert.Equal(t, uint32(count), tile.Value()) } diff --git a/path.go b/path.go index 9ecb431..9fb9071 100644 --- a/path.go +++ b/path.go @@ -5,10 +5,13 @@ package tile import ( "math" + "math/bits" "sync" + + "github.com/kelindar/intmap" ) -type costFn = func(Tile) uint16 +type costFn = func(Value) uint16 // Edge represents an edge of the path type edge struct { @@ -17,7 +20,7 @@ type edge struct { } // Around performs a breadth first search around a point. -func (m *Grid) Around(from Point, distance uint32, costOf costFn, fn Iterator) { +func (m *Grid[T]) Around(from Point, distance uint32, costOf costFn, fn func(Point, Tile[T])) { start, ok := m.At(from.X, from.Y) if !ok { return @@ -25,36 +28,37 @@ func (m *Grid) Around(from Point, distance uint32, costOf costFn, fn Iterator) { fn(from, start) - // Acquire a frontier heap for search - frontier := acquireHeap() - frontier.Push(from.Integer(), 0) - defer releaseHeap(frontier) - // For pre-allocating, we use πr2 since BFS will result in a approximation // of a circle, in the worst case. maxArea := int(math.Ceil(math.Pi * float64(distance*distance))) - reached := make(map[uint32]struct{}, maxArea) - reached[from.Integer()] = struct{}{} + // Acquire a frontier heap for search + state := acquire(maxArea) + frontier := state.frontier + reached := state.edges + defer release(state) + + frontier.Push(from.Integer(), 0) + reached.Store(from.Integer(), 0) for !frontier.IsEmpty() { - pCurr, _ := frontier.Pop() + pCurr := frontier.Pop() current := unpackPoint(pCurr) // Get all of the neighbors - m.Neighbors(current.X, current.Y, func(next Point, nextTile Tile) { + m.Neighbors(current.X, current.Y, func(next Point, nextTile Tile[T]) { if d := from.DistanceTo(next); d > distance { return // Too far } - if cost := costOf(nextTile); cost == 0 { + if cost := costOf(nextTile.Value()); cost == 0 { return // Blocked tile, ignore completely } // Add to the search queue pNext := next.Integer() - if _, ok := reached[pNext]; !ok { + if _, ok := reached.Load(pNext); !ok { frontier.Push(pNext, 1) - reached[pNext] = struct{}{} + reached.Store(pNext, 1) fn(next, nextTile) } }) @@ -62,191 +66,191 @@ func (m *Grid) Around(from Point, distance uint32, costOf costFn, fn Iterator) { } // Path calculates a short path and the distance between the two locations -func (m *Grid) Path(from, to Point, costOf costFn) ([]Point, int, bool) { - - // Acquire a frontier heap for search - frontier := acquireHeap() - frontier.Push(from.Integer(), 0) - defer releaseHeap(frontier) +func (m *Grid[T]) Path(from, to Point, costOf costFn) ([]Point, int, bool) { + distance := float64(from.DistanceTo(to)) + maxArea := int(math.Ceil(math.Pi * float64(distance*distance))) // For pre-allocating, we use πr2 since BFS will result in a approximation // of a circle, in the worst case. - distance := float64(from.DistanceTo(to)) - maxArea := int(math.Ceil(math.Pi * float64(distance*distance))) - edges := make(map[uint32]edge, maxArea) - edges[from.Integer()] = edge{ - Point: from, - Cost: 0, - } + state := acquire(maxArea) + edges := state.edges + frontier := state.frontier + defer release(state) + + frontier.Push(from.Integer(), 0) + edges.Store(from.Integer(), encode(0, Direction(0))) // Starting point has no direction for !frontier.IsEmpty() { - pCurr, _ := frontier.Pop() + pCurr := frontier.Pop() current := unpackPoint(pCurr) - // We have a path to the goal + // Decode the cost to reach the current point + currentEncoded, _ := edges.Load(pCurr) + currentCost, _ := decode(currentEncoded) + + // Check if we've reached the destination if current.Equal(to) { - dist := int(edges[current.Integer()].Cost) - path := make([]Point, 0, dist) - curr, _ := edges[current.Integer()] - for !curr.Point.Equal(from) { - path = append(path, curr.Point) - curr = edges[curr.Point.Integer()] + + // Reconstruct the path + path := make([]Point, 0, 64) + path = append(path, current) + for !current.Equal(from) { + currentEncoded, _ := edges.Load(current.Integer()) + _, dir := decode(currentEncoded) + current = current.Move(oppositeDirection(dir)) + path = append(path, current) + } + + // Reverse the path to get from source to destination + for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 { + path[i], path[j] = path[j], path[i] } - return path, dist, true + return path, int(currentCost), true } - // Get all of the neighbors - m.Neighbors(current.X, current.Y, func(next Point, nextTile Tile) { - cNext := costOf(nextTile) + // Explore neighbors + m.Neighbors(current.X, current.Y, func(next Point, nextTile Tile[T]) { + cNext := costOf(nextTile.Value()) if cNext == 0 { - return // Blocked tile, ignore completely + return // Blocked tile } + nextCost := currentCost + uint32(cNext) pNext := next.Integer() - newCost := edges[pCurr].Cost + uint32(cNext) // cost(current, next) - if e, ok := edges[pNext]; !ok || newCost < e.Cost { - priority := newCost + next.DistanceTo(to) // heuristic - frontier.Push(next.Integer(), priority) + existingEncoded, visited := edges.Load(pNext) + existingCost, _ := decode(existingEncoded) - edges[pNext] = edge{ - Point: current, - Cost: newCost, - } - } + // If we haven't visited this node or we found a better path + if !visited || nextCost < existingCost { + angle := angleOf(current, next) + priority := nextCost + next.DistanceTo(to) + // Store the edge and push to the frontier + edges.Store(pNext, encode(nextCost, angle)) + frontier.Push(pNext, priority) + } }) } return nil, 0, false } -// ----------------------------------------------------------------------------- - -var heapPool = sync.Pool{ - New: func() interface{} { return new(heap32) }, -} - -// Acquires a new instance of a heap -func acquireHeap() *heap32 { - h := heapPool.Get().(*heap32) - h.Reset() - return h +// encode packs the cost and direction into a uint32 +func encode(cost uint32, dir Direction) uint32 { + return (cost << 4) | uint32(dir&0xF) } -// Releases a heap instance back to the pool -func releaseHeap(h *heap32) { - heapPool.Put(h) +// decode unpacks the cost and direction from a uint32 +func decode(value uint32) (cost uint32, dir Direction) { + cost = value >> 4 + dir = Direction(value & 0xF) + return } // ----------------------------------------------------------------------------- -// heapNode represents a ranked node for the heap. -type heapNode struct { - Value uint32 // The value of the ranked node. - Rank uint32 // The rank associated with the ranked node. +type pathfinder struct { + edges *intmap.Map + frontier *frontier } -type heap32 []heapNode - -func newHeap32(capacity int) heap32 { - return make(heap32, 0, capacity) -} - -// Reset clears the heap for reuse -func (h *heap32) Reset() { - *h = (*h)[:0] -} - -// Push pushes the element x onto the heap. -// The complexity is O(log n) where n = h.Len(). -func (h *heap32) Push(v, rank uint32) { - *h = append(*h, heapNode{ - Value: v, - Rank: rank, - }) - h.up(h.Len() - 1) +var pathfinders = sync.Pool{ + New: func() any { + return &pathfinder{ + edges: intmap.NewWithFill(32, .99), + frontier: newFrontier(), + } + }, } -// Pop removes and returns the minimum element (according to Less) from the heap. -// The complexity is O(log n) where n = h.Len(). -// Pop is equivalent to Remove(h, 0). -func (h *heap32) Pop() (uint32, bool) { - n := h.Len() - 1 - if n < 0 { - return 0, false +// Acquires a new instance of a pathfinding state +func acquire(capacity int) *pathfinder { + v := pathfinders.Get().(*pathfinder) + if v.edges.Capacity() < capacity { + v.edges = intmap.NewWithFill(capacity, .99) } - h.Swap(0, n) - h.down(0, n) - return h.pop(), true + return v } -// Remove removes and returns the element at index i from the heap. -// The complexity is O(log n) where n = h.Len(). -func (h *heap32) Remove(i int) uint32 { - n := h.Len() - 1 - if n != i { - h.Swap(i, n) - if !h.down(i, n) { - h.up(i) - } - } - return h.pop() +// release releases a pathfinding state back to the pool +func release(v *pathfinder) { + v.edges.Clear() + v.frontier.Reset() + pathfinders.Put(v) } -func (h *heap32) pop() uint32 { - old := *h - n := len(old) - no := old[n-1] - *h = old[0 : n-1] - return no.Value +// ----------------------------------------------------------------------------- + +// frontier is a priority queue implementation that uses buckets to store +// elements. Original implementation by Iskander Sharipov (https://github.com/quasilyte/pathing) +type frontier struct { + buckets [64][]uint32 + mask uint64 } -func (h *heap32) up(j int) { - for { - i := (j - 1) / 2 // parent - if i == j || !h.Less(j, i) { - break - } - h.Swap(i, j) - j = i +// newFrontier creates a new frontier priority queue +func newFrontier() *frontier { + h := &frontier{} + for i := range &h.buckets { + h.buckets[i] = make([]uint32, 0, 16) } + return h } -func (h *heap32) down(i0, n int) bool { - i := i0 - for { - j1 := 2*i + 1 - if j1 >= n || j1 < 0 { // j1 < 0 after int overflow - break +func (q *frontier) Reset() { + buckets := &q.buckets + + // Reslice storage slices back. + // To avoid traversing all len(q.buckets), + // we have some offset to skip uninteresting (already empty) buckets. + // We also stop when mask is 0 meaning all remaining buckets are empty too. + // In other words, it would only touch slices between min and max non-empty priorities. + mask := q.mask + offset := uint(bits.TrailingZeros64(mask)) + mask >>= offset + i := offset + for mask != 0 { + if i < uint(len(buckets)) { + buckets[i] = buckets[i][:0] } - j := j1 // left child - if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { - j = j2 // = 2*i + 2 // right child - } - if !h.Less(j, i) { - break - } - h.Swap(i, j) - i = j + mask >>= 1 + i++ } - return i > i0 -} -func (h heap32) Len() int { - return len(h) + q.mask = 0 } -func (h heap32) IsEmpty() bool { - return len(h) == 0 +func (q *frontier) IsEmpty() bool { + return q.mask == 0 } -func (h heap32) Less(i, j int) bool { - return h[i].Rank < h[j].Rank +func (q *frontier) Push(value, priority uint32) { + // No bound checks since compiler knows that i will never exceed 64. + // We also get a cool truncation of values above 64 to store them + // in our biggest bucket. + i := priority & 0b111111 + q.buckets[i] = append(q.buckets[i], value) + q.mask |= 1 << i } -func (h *heap32) Swap(i, j int) { - (*h)[i], (*h)[j] = (*h)[j], (*h)[i] +func (q *frontier) Pop() uint32 { + buckets := &q.buckets + + // Using uints here and explicit len check to avoid the + // implicitly inserted bound check. + i := uint(bits.TrailingZeros64(q.mask)) + if i < uint(len(buckets)) { + e := buckets[i][len(buckets[i])-1] + buckets[i] = buckets[i][:len(buckets[i])-1] + if len(buckets[i]) == 0 { + q.mask &^= 1 << i + } + return e + } + + // A queue is empty + return 0 } diff --git a/path_test.go b/path_test.go index c594574..77bb6d4 100644 --- a/path_test.go +++ b/path_test.go @@ -4,6 +4,7 @@ package tile import ( + "fmt" "image" "image/color" "image/png" @@ -19,14 +20,16 @@ func TestPath(t *testing.T) { path, dist, found := m.Path(At(1, 1), At(7, 7), costOf) assert.Equal(t, ` ......... -. x . . -. x... .. -. xxx. .. -... x. . -. xx . +.x . . +.x ... .. +.xxx . .. +...x . . +. xxx . .....x... -. xx . +. xxx. .........`, plotPath(m, path)) + + fmt.Println(plotPath(m, path)) assert.Equal(t, 12, dist) assert.True(t, found) } @@ -35,12 +38,12 @@ func TestPathTiny(t *testing.T) { m := NewGrid(6, 6) path, dist, found := m.Path(At(0, 0), At(5, 5), costOf) assert.Equal(t, ` - x - x - x - x - x - xxxx `, plotPath(m, path)) +x +x +x +x +x +xxxxxx`, plotPath(m, path)) assert.Equal(t, 10, dist) assert.True(t, found) } @@ -51,12 +54,15 @@ func TestDraw(t *testing.T) { assert.NotNil(t, out) } -// BenchmarkPath/9x9-8 210472 5316 ns/op 16468 B/op 3 allocs/op -// BenchmarkPath/300x300-8 463 2546373 ns/op 7801135 B/op 4 allocs/op -// BenchmarkPath/381x381-8 373 2732657 ns/op 62394362 B/op 4 allocs/op -// BenchmarkPath/384x384-8 153 7791925 ns/op 62396304 B/op 5 allocs/op -// BenchmarkPath/6144x6144-8 158 7468206 ns/op 62395377 B/op 3 allocs/op -// BenchmarkPath/6147x6147-8 160 7468716 ns/op 62395359 B/op 3 allocs/op +/* +BenchmarkPath/9x9-24 2856020 423.0 ns/op 256 B/op 1 allocs/op +BenchmarkPath/300x300-24 1167 1006143 ns/op 3845 B/op 4 allocs/op +BenchmarkPath/381x381-24 3150 371478 ns/op 12629 B/op 5 allocs/op +BenchmarkPath/384x384-24 3178 374982 ns/op 7298 B/op 5 allocs/op +BenchmarkPath/3069x3069-24 787 1459683 ns/op 106188 B/op 7 allocs/op +BenchmarkPath/3072x3072-24 799 1552230 ns/op 104906 B/op 7 allocs/op +BenchmarkPath/6144x6144-24 3099 381935 ns/op 12716 B/op 5 allocs/op +*/ func BenchmarkPath(b *testing.B) { b.Run("9x9", func(b *testing.B) { m := mapFrom("9x9.png") @@ -122,16 +128,19 @@ func BenchmarkPath(b *testing.B) { }) } -// BenchmarkAround/3r-8 352876 3355 ns/op 385 B/op 1 allocs/op -// BenchmarkAround/5r-8 162103 7551 ns/op 931 B/op 2 allocs/op -// BenchmarkAround/10r-8 62491 19235 ns/op 3489 B/op 2 allocs/op +/* +cpu: 13th Gen Intel(R) Core(TM) i7-13700K +BenchmarkAround/3r-24 2080566 562.7 ns/op 0 B/op 0 allocs/op +BenchmarkAround/5r-24 885582 1358 ns/op 0 B/op 0 allocs/op +BenchmarkAround/10r-24 300672 3953 ns/op 0 B/op 0 allocs/op +*/ func BenchmarkAround(b *testing.B) { m := mapFrom("300x300.png") b.Run("3r", func(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.Around(At(115, 20), 3, costOf, func(_ Point, _ Tile) {}) + m.Around(At(115, 20), 3, costOf, func(_ Point, _ Tile[string]) {}) } }) @@ -139,7 +148,7 @@ func BenchmarkAround(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.Around(At(115, 20), 5, costOf, func(_ Point, _ Tile) {}) + m.Around(At(115, 20), 5, costOf, func(_ Point, _ Tile[string]) {}) } }) @@ -147,7 +156,7 @@ func BenchmarkAround(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - m.Around(At(115, 20), 10, costOf, func(_ Point, _ Tile) {}) + m.Around(At(115, 20), 10, costOf, func(_ Point, _ Tile[string]) {}) } }) } @@ -157,7 +166,7 @@ func TestAround(t *testing.T) { for i := 0; i < 3; i++ { var path []string - m.Around(At(2, 2), 3, costOf, func(p Point, tile Tile) { + m.Around(At(2, 2), 3, costOf, func(p Point, tile Tile[string]) { path = append(path, p.String()) }) assert.Equal(t, 10, len(path)) @@ -168,10 +177,20 @@ func TestAround(t *testing.T) { } } -// BenchmarkHeap-8 94454 12303 ns/op 3968 B/op 5 allocs/op +func TestAroundMiss(t *testing.T) { + m := mapFrom("9x9.png") + m.Around(At(20, 20), 3, costOf, func(p Point, tile Tile[string]) { + t.Fail() + }) +} + +/* +cpu: 13th Gen Intel(R) Core(TM) i7-13700K +BenchmarkHeap-24 240228 5076 ns/op 6016 B/op 68 allocs/op +*/ func BenchmarkHeap(b *testing.B) { for i := 0; i < b.N; i++ { - h := newHeap32(16) + h := newFrontier() for j := 0; j < 128; j++ { h.Push(rand(j), 1) } @@ -182,28 +201,6 @@ func BenchmarkHeap(b *testing.B) { } } -func TestHeap(t *testing.T) { - h := newHeap32(16) - h.Push(1, 0) - h.Pop() -} - -func TestNewHeap(t *testing.T) { - h := newHeap32(16) - for j := 0; j < 8; j++ { - h.Push(rand(j), uint32(j)) - } - - val, _ := h.Pop() - for j := 1; j < 128; j++ { - newval, ok := h.Pop() - if ok { - assert.True(t, val < newval) - val = newval - } - } -} - // very fast semi-random function func rand(i int) uint32 { i = i + 10000 @@ -215,15 +212,15 @@ func rand(i int) uint32 { // ----------------------------------------------------------------------------- // Cost estimation function -func costOf(tile Tile) uint16 { - if (tile[0])&1 != 0 { +func costOf(tile Value) uint16 { + if (tile)&1 != 0 { return 0 // Blocked } return 1 } // mapFrom creates a map from ASCII string -func mapFrom(name string) *Grid { +func mapFrom(name string) *Grid[string] { f, err := os.Open("fixtures/" + name) defer f.Close() if err != nil { @@ -244,7 +241,7 @@ func mapFrom(name string) *Grid { switch v.R { case 255: case 0: - m.WriteAt(x, y, Tile{0xff, 0, 0, 0, 0, 0}) + m.WriteAt(x, y, Value(0xff)) } } @@ -253,18 +250,18 @@ func mapFrom(name string) *Grid { } // plotPath plots the path on ASCII map -func plotPath(m *Grid, path []Point) string { +func plotPath(m *Grid[string], path []Point) string { out := make([][]byte, m.Size.Y) for i := range out { out[i] = make([]byte, m.Size.X) } - m.Each(func(l Point, tile Tile) { + m.Each(func(l Point, tile Tile[string]) { //println(l.String(), int(tile[0])) switch { case pointInPath(l, path): out[l.Y][l.X] = 'x' - case tile[0]&1 != 0: + case tile.Value()&1 != 0: out[l.Y][l.X] = '.' default: out[l.Y][l.X] = ' ' @@ -290,16 +287,16 @@ func pointInPath(point Point, path []Point) bool { } // draw converts the map to a black and white image for debugging purposes. -func drawGrid(m *Grid, rect Rect) image.Image { +func drawGrid(m *Grid[string], rect Rect) image.Image { if rect.Max.X == 0 || rect.Max.Y == 0 { rect = NewRect(0, 0, m.Size.X, m.Size.Y) } size := rect.Size() output := image.NewRGBA(image.Rect(0, 0, int(size.X), int(size.Y))) - m.Within(rect.Min, rect.Max, func(p Point, tile Tile) { + m.Within(rect.Min, rect.Max, func(p Point, tile Tile[string]) { a := uint8(255) - if tile[0] == 1 { + if tile.Value() == 1 { a = 0 } diff --git a/point.go b/point.go index 2803de4..eb34f1e 100644 --- a/point.go +++ b/point.go @@ -9,96 +9,6 @@ import ( const invalid = int16(-1 << 15) -var interleaveLookup = [256]int32{ - 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, - 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, - 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, - 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, - 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, - 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, - 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, - 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, - - 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, - 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, - 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, - 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, - 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, - 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, - 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, - 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, - - 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, - 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, - 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, - 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, - 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, - 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, - 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, - 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, - - 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, - 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, - 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, - 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, - 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, - 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, - 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, - 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555, -} - -var deinterleaveLookup = [256]int16{ - 0x0, 0x1, 0x1, 0x1, 0x2, 0x3, 0x3, 0x3, - 0x2, 0x3, 0x3, 0x3, 0x2, 0x3, 0x3, 0x3, - 0x4, 0x5, 0x5, 0x5, 0x6, 0x7, 0x7, 0x7, - 0x6, 0x7, 0x7, 0x7, 0x6, 0x7, 0x7, 0x7, - 0x4, 0x5, 0x5, 0x5, 0x6, 0x7, 0x7, 0x7, - 0x6, 0x7, 0x7, 0x7, 0x6, 0x7, 0x7, 0x7, - 0x4, 0x5, 0x5, 0x5, 0x6, 0x7, 0x7, 0x7, - 0x6, 0x7, 0x7, 0x7, 0x6, 0x7, 0x7, 0x7, - - 0x8, 0x9, 0x9, 0x9, 0xa, 0xb, 0xb, 0xb, - 0xa, 0xb, 0xb, 0xb, 0xa, 0xb, 0xb, 0xb, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - - 0x8, 0x9, 0x9, 0x9, 0xa, 0xb, 0xb, 0xb, - 0xa, 0xb, 0xb, 0xb, 0xa, 0xb, 0xb, 0xb, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - - 0x8, 0x9, 0x9, 0x9, 0xa, 0xb, 0xb, 0xb, - 0xa, 0xb, 0xb, 0xb, 0xa, 0xb, 0xb, 0xb, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, - 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, - 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, -} - -// deinterleavePoint decodes the interleaved values. -func deinterleavePoint(code int) (p Point) { - p.X = (deinterleaveLookup[code&0x55]) | - (deinterleaveLookup[(code>>8)&0x55] << 4) | - (deinterleaveLookup[(code>>16)&0x55] << 8) | - (deinterleaveLookup[(code>>24)&0x55] << 12) - - p.Y = (deinterleaveLookup[code&0xaa]) | - (deinterleaveLookup[(code>>8)&0xaa] << 4) | - (deinterleaveLookup[(code>>16)&0xaa] << 8) | - (deinterleaveLookup[(code>>24)&0xaa] << 12) - return -} - // ----------------------------------------------------------------------------- // Point represents a 2D coordinate. @@ -126,17 +36,6 @@ func (p Point) Integer() uint32 { return (uint32(p.X) << 16) | (uint32(p.Y) & 0xffff) } -// Interleave bits of x and y, so that all of thebits of x are in the even -// positions and y in the odd (Morton Number). -func (p Point) Interleave() int32 { - // see: https://graphics.stanford.edu/~seander/bithacks.html - // and: https://github.com/golang/geo/blob/master/s2/interleave.go - return (interleaveLookup[p.X&0xff]) | - (interleaveLookup[(p.X>>8)&0xff] << 16) | - (interleaveLookup[p.Y&0xff] << 1) | - (interleaveLookup[(p.Y>>8)&0xff] << 17) -} - // Equal compares two points and returns true if they are equal. func (p Point) Equal(other Point) bool { return p.X == other.X && p.Y == other.Y @@ -174,12 +73,12 @@ func (p Point) DivideScalar(s int16) Point { // Within checks if the point is within the specified bounding box. func (p Point) Within(nw, se Point) bool { - return p.X >= nw.X && p.Y >= nw.Y && p.X <= se.X && p.Y <= se.Y + return Rect{Min: nw, Max: se}.Contains(p) } // WithinRect checks if the point is within the specified bounding box. func (p Point) WithinRect(box Rect) bool { - return p.X >= box.Min.X && p.Y >= box.Min.Y && p.X <= box.Max.X && p.Y <= box.Max.Y + return box.Contains(p) } // WithinSize checks if the point is within the specified bounding box @@ -244,20 +143,84 @@ func NewRect(left, top, right, bottom int16) Rect { } // Contains returns whether a point is within the rectangle or not. -func (r *Rect) Contains(p Point) bool { - return p.X >= r.Min.X && p.Y >= r.Min.Y && p.X <= r.Max.X && p.Y <= r.Max.Y +func (a Rect) Contains(p Point) bool { + return a.Min.X <= p.X && p.X < a.Max.X && a.Min.Y <= p.Y && p.Y < a.Max.Y } // Intersects returns whether a rectangle intersects with another rectangle or not. -func (r *Rect) Intersects(box Rect) bool { - return !(box.Max.X < r.Min.X || box.Min.X > r.Max.X || box.Max.Y < r.Min.Y || box.Min.Y > r.Max.Y) +func (a Rect) Intersects(b Rect) bool { + return b.Min.X < a.Max.X && a.Min.X < b.Max.X && b.Min.Y < a.Max.Y && a.Min.Y < b.Max.Y } // Size returns the size of the rectangle -func (r *Rect) Size() Point { +func (a *Rect) Size() Point { return Point{ - X: r.Max.X - r.Min.X, - Y: r.Max.Y - r.Min.Y, + X: a.Max.X - a.Min.X, + Y: a.Max.Y - a.Min.Y, + } +} + +// IsZero returns true if the rectangle is zero-value +func (a Rect) IsZero() bool { + return a.Min.X == a.Max.X && a.Min.Y == a.Max.Y +} + +// Difference calculates up to four non-overlapping regions in a that are not covered by b. +// If there are fewer than four distinct regions, the remaining Rects will be zero-value. +func (a Rect) Difference(b Rect) (result [4]Rect) { + if b.Contains(a.Min) && b.Contains(a.Max) { + return // Fully covered, return zero-value result + } + + // Check for non-overlapping cases + if !a.Intersects(b) { + result[0] = a // No overlap, return A as is + return + } + + left := min(a.Min.X, b.Min.X) + right := max(a.Max.X, b.Max.X) + top := min(a.Min.Y, b.Min.Y) + bottom := max(a.Max.Y, b.Max.Y) + + result[0].Min = Point{X: left, Y: top} + result[0].Max = Point{X: right, Y: max(a.Min.Y, b.Min.Y)} + + result[1].Min = Point{X: left, Y: min(a.Max.Y, b.Max.Y)} + result[1].Max = Point{X: right, Y: bottom} + + result[2].Min = Point{X: left, Y: top} + result[2].Max = Point{X: max(a.Min.X, b.Min.X), Y: bottom} + + result[3].Min = Point{X: min(a.Max.X, b.Max.X), Y: top} + result[3].Max = Point{X: right, Y: bottom} + + if result[0].Size().X == 0 || result[0].Size().Y == 0 { + result[0] = Rect{} + } + if result[1].Size().X == 0 || result[1].Size().Y == 0 { + result[1] = Rect{} + } + if result[2].Size().X == 0 || result[2].Size().Y == 0 { + result[2] = Rect{} + } + if result[3].Size().X == 0 || result[3].Size().Y == 0 { + result[3] = Rect{} + } + + return +} + +// Pack returns a packed representation of a rectangle +func (a Rect) pack() uint64 { + return uint64(a.Min.Integer())<<32 | uint64(a.Max.Integer()) +} + +// Unpack returns a rectangle from a packed representation +func unpackRect(v uint64) Rect { + return Rect{ + Min: unpackPoint(uint32(v >> 32)), + Max: unpackPoint(uint32(v)), } } @@ -301,3 +264,40 @@ func (v Direction) String() string { return "" } } + +// Vector returns a direction vector with a given scale +func (v Direction) Vector(scale int16) Point { + return Point{}.MoveBy(v, scale) +} + +// angleOf returns the direction from one point to another +func angleOf(from, to Point) Direction { + dx := to.X - from.X + dy := to.Y - from.Y + + switch { + case dx == 0 && dy == -1: + return North + case dx == 1 && dy == -1: + return NorthEast + case dx == 1 && dy == 0: + return East + case dx == 1 && dy == 1: + return SouthEast + case dx == 0 && dy == 1: + return South + case dx == -1 && dy == 1: + return SouthWest + case dx == -1 && dy == 0: + return West + case dx == -1 && dy == -1: + return NorthWest + default: + return Direction(0) // Invalid direction + } +} + +// oppositeDirection returns the opposite of the given direction +func oppositeDirection(dir Direction) Direction { + return Direction((dir + 4) % 8) +} diff --git a/point_test.go b/point_test.go index aaebbfe..e2e7bbb 100644 --- a/point_test.go +++ b/point_test.go @@ -10,10 +10,9 @@ import ( ) /* -cpu: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz -BenchmarkPoint/within-8 1000000000 0.2697 ns/op 0 B/op 0 allocs/op -BenchmarkPoint/within-rect-8 1000000000 0.2928 ns/op 0 B/op 0 allocs/op -BenchmarkPoint/interleave-8 1000000000 0.8242 ns/op 0 B/op 0 allocs/op +cpu: 13th Gen Intel(R) Core(TM) i7-13700K +BenchmarkPoint/within-24 1000000000 0.09854 ns/op 0 B/op 0 allocs/op +BenchmarkPoint/within-rect-24 1000000000 0.09966 ns/op 0 B/op 0 allocs/op */ func BenchmarkPoint(b *testing.B) { p := At(10, 20) @@ -32,17 +31,6 @@ func BenchmarkPoint(b *testing.B) { p.WithinRect(NewRect(0, 0, 100, 100)) } }) - - b.Run("interleave", func(b *testing.B) { - out := int32(0) - p := At(8191, 8191) - b.ReportAllocs() - b.ResetTimer() - for n := 0; n < b.N; n++ { - out = p.Interleave() - } - assert.NotZero(b, out) - }) } func TestPoint(t *testing.T) { @@ -61,16 +49,16 @@ func TestPoint(t *testing.T) { assert.Equal(t, "8,18", p.Subtract(p2).String()) assert.Equal(t, "20,40", p.Multiply(p2).String()) assert.Equal(t, "5,10", p.Divide(p2).String()) - assert.True(t, p.Within(At(1, 1), At(10, 20))) - assert.True(t, p.WithinRect(NewRect(1, 1, 10, 20))) + assert.True(t, p.Within(At(1, 1), At(20, 30))) + assert.True(t, p.WithinRect(NewRect(1, 1, 20, 30))) assert.False(t, p.WithinSize(At(10, 20))) assert.True(t, p.WithinSize(At(20, 30))) } -func TestMorton(t *testing.T) { - p := At(8191, 8191) - assert.Equal(t, 67108863, int(p.Interleave())) - assert.Equal(t, p, deinterleavePoint(67108863)) +func TestIntersects(t *testing.T) { + assert.True(t, NewRect(0, 0, 2, 2).Intersects(NewRect(1, 0, 3, 2))) + assert.False(t, NewRect(0, 0, 2, 2).Intersects(NewRect(2, 0, 4, 2))) + assert.False(t, NewRect(10, 10, 12, 12).Intersects(NewRect(9, 12, 11, 14))) } func TestDirection(t *testing.T) { @@ -105,3 +93,57 @@ func TestMove(t *testing.T) { assert.Equal(t, tc.out, Point{}.Move(tc.dir), tc.dir.String()) } } + +func TestContains(t *testing.T) { + tests := map[Point]bool{ + {X: 0, Y: 0}: true, + {X: 1, Y: 0}: true, + {X: 0, Y: 1}: true, + {X: 1, Y: 1}: true, + {X: 2, Y: 2}: false, + {X: 3, Y: 3}: false, + {X: 1, Y: 2}: false, + {X: 2, Y: 1}: false, + } + + for point, expect := range tests { + r := NewRect(0, 0, 2, 2) + assert.Equal(t, expect, r.Contains(point), point.String()) + } +} + +func TestDiff_Right(t *testing.T) { + a := Rect{At(0, 0), At(2, 2)} + b := Rect{At(1, 0), At(3, 2)} + + diff := a.Difference(b) + assert.Equal(t, Rect{At(0, 0), At(1, 2)}, diff[2]) + assert.Equal(t, Rect{At(2, 0), At(3, 2)}, diff[3]) +} + +func TestDiff_Left(t *testing.T) { + a := Rect{At(0, 0), At(2, 2)} + b := Rect{At(-1, 0), At(1, 2)} + + diff := a.Difference(b) + assert.Equal(t, Rect{At(-1, 0), At(0, 2)}, diff[2]) + assert.Equal(t, Rect{At(1, 0), At(2, 2)}, diff[3]) +} + +func TestDiff_Up(t *testing.T) { + a := Rect{At(0, 0), At(2, 2)} + b := Rect{At(0, -1), At(2, 1)} + + diff := a.Difference(b) + assert.Equal(t, Rect{At(0, -1), At(2, 0)}, diff[0]) + assert.Equal(t, Rect{At(0, 1), At(2, 2)}, diff[1]) +} + +func TestDiff_Down(t *testing.T) { + a := Rect{At(0, 0), At(2, 2)} + b := Rect{At(0, 1), At(2, 3)} + + diff := a.Difference(b) + assert.Equal(t, Rect{At(0, 0), At(2, 1)}, diff[0]) + assert.Equal(t, Rect{At(0, 2), At(2, 3)}, diff[1]) +} diff --git a/store.go b/store.go index cc97be1..bcbb56a 100644 --- a/store.go +++ b/store.go @@ -8,16 +8,17 @@ import ( "encoding/binary" "io" "os" + "unsafe" "github.com/kelindar/iostream" ) -const tileDataSize = 54 +const tileDataSize = int(unsafe.Sizeof([9]Value{})) // ---------------------------------- Stream ---------------------------------- // WriteTo writes the grid to a specific writer. -func (m *Grid) WriteTo(dst io.Writer) (n int64, err error) { +func (m *Grid[T]) WriteTo(dst io.Writer) (n int64, err error) { p1 := At(0, 0) p2 := At(m.Size.X-1, m.Size.Y-1) @@ -33,8 +34,9 @@ func (m *Grid) WriteTo(dst io.Writer) (n int64, err error) { } // Write the grid data - m.pagesWithin(p1, p2, func(page *page) { - if _, err := w.Write(page.Data()); err != nil { + m.pagesWithin(p1, p2, func(page *page[T]) { + buffer := (*[tileDataSize]byte)(unsafe.Pointer(&page.tiles))[:] + if _, err := w.Write(buffer); err != nil { return } }) @@ -42,7 +44,7 @@ func (m *Grid) WriteTo(dst io.Writer) (n int64, err error) { } // ReadFrom reads the grid from the reader. -func ReadFrom(src io.Reader) (grid *Grid, err error) { +func ReadFrom[T comparable](src io.Reader) (grid *Grid[T], err error) { r := iostream.NewReader(src) header := make([]byte, 8) if _, err := io.ReadFull(r, header); err != nil { @@ -57,14 +59,14 @@ func ReadFrom(src io.Reader) (grid *Grid, err error) { view.Max.Y = int16(binary.BigEndian.Uint16(header[6:8])) // Allocate a new grid - grid = NewGrid(view.Max.X+1, view.Max.Y+1) + grid = NewGridOf[T](view.Max.X+1, view.Max.Y+1) buf := make([]byte, tileDataSize) - grid.pagesWithin(view.Min, view.Max, func(page *page) { - if _, err := io.ReadFull(r, buf); err != nil { + grid.pagesWithin(view.Min, view.Max, func(page *page[T]) { + if _, err = io.ReadFull(r, buf); err != nil { return } - copy(page.Data(), buf) + copy((*[tileDataSize]byte)(unsafe.Pointer(&page.tiles))[:], buf) }) return } @@ -72,7 +74,7 @@ func ReadFrom(src io.Reader) (grid *Grid, err error) { // ---------------------------------- File ---------------------------------- // WriteFile writes the grid into a flate-compressed binary file. -func (m *Grid) WriteFile(filename string) error { +func (m *Grid[T]) WriteFile(filename string) error { file, err := os.Create(filename) if err != nil { return err @@ -92,7 +94,7 @@ func (m *Grid) WriteFile(filename string) error { // Restore restores the grid from the specified file. The grid must // be written using the corresponding WriteFile() method. -func ReadFile(filename string) (grid *Grid, err error) { +func ReadFile[T comparable](filename string) (grid *Grid[T], err error) { if _, err := os.Stat(filename); os.IsNotExist(err) { return nil, os.ErrNotExist } @@ -104,5 +106,5 @@ func ReadFile(filename string) (grid *Grid, err error) { } defer file.Close() - return ReadFrom(flate.NewReader(file)) + return ReadFrom[T](flate.NewReader(file)) } diff --git a/store_test.go b/store_test.go index 05cd105..80fcef7 100644 --- a/store_test.go +++ b/store_test.go @@ -14,8 +14,8 @@ import ( /* cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz -BenchmarkStore/save-8 9068 129974 ns/op 8 B/op 1 allocs/op -BenchmarkStore/read-8 2967 379663 ns/op 647465 B/op 8 allocs/op +BenchmarkStore/save-8 14455 81883 ns/op 8 B/op 1 allocs/op +BenchmarkStore/read-8 2787 399699 ns/op 647421 B/op 7 allocs/op */ func BenchmarkStore(b *testing.B) { m := mapFrom("300x300.png") @@ -38,7 +38,7 @@ func BenchmarkStore(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - ReadFrom(bytes.NewBuffer(enc.Bytes())) + ReadFrom[string](bytes.NewBuffer(enc.Bytes())) } }) @@ -51,10 +51,10 @@ func TestSaveLoad(t *testing.T) { enc := new(bytes.Buffer) n, err := m.WriteTo(enc) assert.NoError(t, err) - assert.Equal(t, int64(540008), n) + assert.Equal(t, int64(360008), n) // Load the map back - out, err := ReadFrom(enc) + out, err := ReadFrom[string](enc) assert.NoError(t, err) assert.Equal(t, m.pages, out.pages) } @@ -70,12 +70,12 @@ func TestSaveLoadFlate(t *testing.T) { n, err := m.WriteTo(writer) assert.NoError(t, writer.Close()) assert.NoError(t, err) - assert.Equal(t, int64(540008), n) - assert.Equal(t, int(18299), output.Len()) + assert.Equal(t, int64(360008), n) + assert.Equal(t, int(16533), output.Len()) // Load the map back reader := flate.NewReader(output) - out, err := ReadFrom(reader) + out, err := ReadFrom[string](reader) assert.NoError(t, err) assert.Equal(t, m.pages, out.pages) } @@ -85,13 +85,15 @@ func TestSaveLoadFile(t *testing.T) { assert.NoError(t, err) defer os.Remove(temp.Name()) - println(temp.Name()) // Write a test map into temp file m := mapFrom("300x300.png") assert.NoError(t, m.WriteFile(temp.Name())) + fi, _ := temp.Stat() + assert.Equal(t, int64(16533), fi.Size()) + // Read the map back - out, err := ReadFile(temp.Name()) + out, err := ReadFile[string](temp.Name()) assert.NoError(t, err) assert.Equal(t, m.pages, out.pages) } diff --git a/view.go b/view.go index d01b68b..8c2cda4 100644 --- a/view.go +++ b/view.go @@ -5,68 +5,120 @@ package tile import ( "sync" + "sync/atomic" ) +// Observer represents a tile update Observer. +type Observer[T comparable] interface { + Viewport() Rect + Resize(Rect, func(Point, Tile[T])) + onUpdate(*Update[T]) +} + +// ValueAt represents a tile and its value. +type ValueAt struct { + Point // The point of the tile + Value // The value of the tile +} + // Update represents a tile update notification. -type Update struct { - Point // The tile location - Tile // The tile data +type Update[T comparable] struct { + Old ValueAt // Old tile + value + New ValueAt // New tile + value + Add T // An object was added to the tile + Del T // An object was removed from the tile } -// View represents a view which can monitor a collection of tiles. -type View struct { - Grid *Grid // The associated map - Inbox chan Update // The update inbox for the view - rect Rect // The view box +var _ Observer[string] = (*View[string, string])(nil) + +// View represents a view which can monitor a collection of tiles. Type parameters +// S and T are the state and tile types respectively. +type View[S any, T comparable] struct { + Grid *Grid[T] // The associated map + Inbox chan Update[T] // The update inbox for the view + State S // The state of the view + rect atomic.Uint64 // The view box +} + +// NewView creates a new view for a map with a given state. State can be anything +// that is passed to the view and can be used to store additional information. +func NewView[S any, T comparable](m *Grid[T], state S) *View[S, T] { + v := &View[S, T]{ + Grid: m, + Inbox: make(chan Update[T], 32), + State: state, + } + v.rect.Store(NewRect(-1, -1, -1, -1).pack()) + return v } -// Resize resizes the viewport. -func (v *View) Resize(box Rect, fn Iterator) { - owner := v.Grid // The parent map - prev := v.rect // Previous bounding box - v.rect = box // New bounding box +// Viewport returns the current viewport of the view. +func (v *View[S, T]) Viewport() Rect { + return unpackRect(v.rect.Load()) +} + +// Resize resizes the viewport and notifies the observers of the changes. +func (v *View[S, T]) Resize(view Rect, fn func(Point, Tile[T])) { + grid := v.Grid + prev := unpackRect(v.rect.Swap(view.pack())) + + for _, diff := range view.Difference(prev) { + if diff.IsZero() { + continue // Skip zero-value rectangles + } + + grid.pagesWithin(diff.Min, diff.Max, func(page *page[T]) { + r := page.Bounds() + switch { + + // Page is now in view + case view.Intersects(r) && !prev.Intersects(r): + if grid.observers.Subscribe(page.point, v) { + page.SetObserved(true) // Mark the page as being observed + } - // Unsubscribe from the pages which are not required anymore - if prev.Min.X >= 0 || prev.Min.Y >= 0 || prev.Max.X >= 0 || prev.Max.Y >= 0 { - owner.pagesWithin(prev.Min, prev.Max, func(page *page) { - if bounds := page.Bounds(); !bounds.Intersects(box) { - if owner.observers.Unsubscribe(page.point, v) { + // Page is no longer in view + case !view.Intersects(r) && prev.Intersects(r): + if grid.observers.Unsubscribe(page.point, v) { page.SetObserved(false) // Mark the page as not being observed } } - }) - } - // Subscribe to every page which we have not previously subscribed - owner.pagesWithin(box.Min, box.Max, func(page *page) { - if bounds := page.Bounds(); !bounds.Intersects(prev) { - if owner.observers.Subscribe(page.point, v) { - page.SetObserved(true) // Mark the page as being observed + // Callback for each new tile in the view + if fn != nil { + page.Each(v.Grid, func(p Point, tile Tile[T]) { + if view.Contains(p) && !prev.Contains(p) { + fn(p, tile) + } + }) } - } + }) + } +} - // Callback for each new tile in the view - if fn != nil { - page.Each(func(p Point, tile Tile) { - if !prev.Contains(p) && box.Contains(p) { - fn(p, tile) - } - }) - } - }) +// MoveTo moves the viewport towards a particular direction. +func (v *View[S, T]) MoveTo(angle Direction, distance int16, fn func(Point, Tile[T])) { + p := angle.Vector(distance) + r := v.Viewport() + v.Resize(Rect{ + Min: r.Min.Add(p), + Max: r.Max.Add(p), + }, fn) } // MoveBy moves the viewport towards a particular direction. -func (v *View) MoveBy(x, y int16, fn Iterator) { +func (v *View[S, T]) MoveBy(x, y int16, fn func(Point, Tile[T])) { + r := v.Viewport() v.Resize(Rect{ - Min: v.rect.Min.Add(At(x, y)), - Max: v.rect.Max.Add(At(x, y)), + Min: r.Min.Add(At(x, y)), + Max: r.Max.Add(At(x, y)), }, fn) } // MoveAt moves the viewport to a specific coordinate. -func (v *View) MoveAt(nw Point, fn Iterator) { - size := v.rect.Max.Subtract(v.rect.Min) +func (v *View[S, T]) MoveAt(nw Point, fn func(Point, Tile[T])) { + r := v.Viewport() + size := r.Max.Subtract(r.Min) v.Resize(Rect{ Min: nw, Max: nw.Add(size), @@ -74,29 +126,31 @@ func (v *View) MoveAt(nw Point, fn Iterator) { } // Each iterates over all of the tiles in the view. -func (v *View) Each(fn Iterator) { - v.Grid.Within(v.rect.Min, v.rect.Max, fn) +func (v *View[S, T]) Each(fn func(Point, Tile[T])) { + r := v.Viewport() + v.Grid.Within(r.Min, r.Max, fn) } // At returns the tile at a specified position. -func (v *View) At(x, y int16) (Tile, bool) { +func (v *View[S, T]) At(x, y int16) (Tile[T], bool) { return v.Grid.At(x, y) } // WriteAt updates the entire tile at a specific coordinate. -func (v *View) WriteAt(x, y int16, tile Tile) { +func (v *View[S, T]) WriteAt(x, y int16, tile Value) { v.Grid.WriteAt(x, y, tile) } // 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 (v *View) MergeAt(x, y int16, tile, mask Tile) { - v.Grid.MergeAt(x, y, tile, mask) +func (v *View[S, T]) MergeAt(x, y int16, tile, mask Value) { + v.Grid.MaskAt(x, y, tile, mask) } // Close closes the view and unsubscribes from everything. -func (v *View) Close() error { - v.Grid.pagesWithin(v.rect.Min, v.rect.Max, func(page *page) { +func (v *View[S, T]) Close() error { + r := v.Viewport() + v.Grid.pagesWithin(r.Min, r.Max, func(page *page[T]) { if v.Grid.observers.Unsubscribe(page.point, v) { page.SetObserved(false) // Mark the page as not being observed } @@ -105,87 +159,118 @@ func (v *View) Close() error { } // onUpdate occurs when a tile has updated. -func (v *View) onUpdate(ev *Update) { - if v.rect.Contains(ev.Point) { - v.Inbox <- *ev // (copy) - } +func (v *View[S, T]) onUpdate(ev *Update[T]) { + v.Inbox <- *ev // (copy) } // ----------------------------------------------------------------------------- -// observer represents a tile update observer. -type observer interface { - onUpdate(*Update) +// Pubsub represents a publish/subscribe layer for observers. +type pubsub[T comparable] struct { + m sync.Map // Concurrent map of observers + tmp sync.Pool // Temporary observer sets for notifications } -// Pubsub represents a publish/subscribe layer for observers. -type pubsub struct { - m sync.Map +// Subscribe registers an event listener on a system +func (p *pubsub[T]) Subscribe(page Point, sub Observer[T]) bool { + if v, ok := p.m.Load(page.Integer()); ok { + return v.(*observers[T]).Subscribe(sub) + } + + // Slow path + v, _ := p.m.LoadOrStore(page.Integer(), newObservers[T]()) + return v.(*observers[T]).Subscribe(sub) +} + +// Unsubscribe deregisters an event listener from a system +func (p *pubsub[T]) Unsubscribe(page Point, sub Observer[T]) bool { + if v, ok := p.m.Load(page.Integer()); ok { + return v.(*observers[T]).Unsubscribe(sub) + } + return false +} + +// Notify notifies listeners of an update that happened. +func (p *pubsub[T]) Notify1(ev *Update[T], page Point) { + p.Each1(func(sub Observer[T]) { + viewport := sub.Viewport() + if viewport.Contains(ev.New.Point) || viewport.Contains(ev.Old.Point) { + sub.onUpdate(ev) + } + }, page) } // Notify notifies listeners of an update that happened. -func (p *pubsub) Notify(page, point Point, tile Tile) { +func (p *pubsub[T]) Notify2(ev *Update[T], pages [2]Point) { + p.Each2(func(sub Observer[T]) { + viewport := sub.Viewport() + if viewport.Contains(ev.New.Point) || viewport.Contains(ev.Old.Point) { + sub.onUpdate(ev) + } + }, pages) +} + +// Each iterates over each observer in a page +func (p *pubsub[T]) Each1(fn func(sub Observer[T]), page Point) { if v, ok := p.m.Load(page.Integer()); ok { - v.(*observers).Notify(&Update{ - Point: point, - Tile: tile, + v.(*observers[T]).Each(func(sub Observer[T]) { + fn(sub) }) } } -// Subscribe registers an event listener on a system -func (p *pubsub) Subscribe(at Point, sub observer) bool { - if v, ok := p.m.Load(at.Integer()); ok { - return v.(*observers).Subscribe(sub) +// Each2 iterates over each observer in a page +func (p *pubsub[T]) Each2(fn func(sub Observer[T]), pages [2]Point) { + targets := p.tmp.Get().(map[Observer[T]]struct{}) + clear(targets) + defer p.tmp.Put(targets) + + // Collect all observers from all pages + for _, page := range pages { + if v, ok := p.m.Load(page.Integer()); ok { + v.(*observers[T]).Each(func(sub Observer[T]) { + targets[sub] = struct{}{} + }) + } } - // Slow path - v, _ := p.m.LoadOrStore(at.Integer(), newObservers()) - return v.(*observers).Subscribe(sub) -} - -// Unsubscribe deregisters an event listener from a system -func (p *pubsub) Unsubscribe(at Point, sub observer) bool { - if v, ok := p.m.Load(at.Integer()); ok { - return v.(*observers).Unsubscribe(sub) + // Invoke the callback for each observer, once + for sub := range targets { + fn(sub) } - return false } // ----------------------------------------------------------------------------- // Observers represents a change notifier which notifies the subscribers when // a specific tile is updated. -type observers struct { +type observers[T comparable] struct { sync.Mutex - subs []observer + subs []Observer[T] } // newObservers creates a new instance of an change observer. -func newObservers() *observers { - return &observers{ - subs: make([]observer, 0, 8), +func newObservers[T comparable]() *observers[T] { + return &observers[T]{ + subs: make([]Observer[T], 0, 8), } } -// Notify notifies listeners of an update that happened. -func (s *observers) Notify(ev *Update) { +// Each iterates over each observer +func (s *observers[T]) Each(fn func(sub Observer[T])) { if s == nil { return } s.Lock() - subs := s.subs - s.Unlock() - - // Update every subscriber - for _, sub := range subs { - sub.onUpdate(ev) + defer s.Unlock() + for _, sub := range s.subs { + fn(sub) } } // Subscribe registers an event listener on a system -func (s *observers) Subscribe(sub observer) bool { +func (s *observers[T]) Subscribe(sub Observer[T]) bool { s.Lock() defer s.Unlock() s.subs = append(s.subs, sub) @@ -193,7 +278,7 @@ func (s *observers) Subscribe(sub observer) bool { } // Unsubscribe deregisters an event listener from a system -func (s *observers) Unsubscribe(sub observer) bool { +func (s *observers[T]) Unsubscribe(sub Observer[T]) bool { s.Lock() defer s.Unlock() diff --git a/view_test.go b/view_test.go index e01ccb5..08ffb25 100644 --- a/view_test.go +++ b/view_test.go @@ -5,20 +5,21 @@ package tile import ( "testing" - "time" + "unsafe" "github.com/stretchr/testify/assert" ) /* -cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz -BenchmarkView/write-8 5910660 191.7 ns/op 16 B/op 1 allocs/op -BenchmarkView/move-8 8253 138149 ns/op 0 B/op 0 allocs/op -BenchmarkView/notify-8 6024670 197.5 ns/op 16 B/op 1 allocs/op +cpu: 13th Gen Intel(R) Core(TM) i7-13700K +BenchmarkView/write-24 9540012 125.0 ns/op 48 B/op 1 allocs/op +BenchmarkView/move-24 16141 74408 ns/op 0 B/op 0 allocs/op */ func BenchmarkView(b *testing.B) { m := mapFrom("300x300.png") - v := m.View(NewRect(100, 0, 199, 99), nil) + v := NewView(m, "view 1") + v.Resize(NewRect(100, 0, 200, 100), nil) + go func() { for range v.Inbox { } @@ -28,7 +29,7 @@ func BenchmarkView(b *testing.B) { b.ReportAllocs() b.ResetTimer() for n := 0; n < b.N; n++ { - v.WriteAt(152, 52, Tile{}) + v.WriteAt(152, 52, Value(0)) } }) @@ -44,14 +45,6 @@ func BenchmarkView(b *testing.B) { v.MoveAt(locs[n%2], nil) } }) - - b.Run("notify", func(b *testing.B) { - b.ReportAllocs() - b.ResetTimer() - for n := 0; n < b.N; n++ { - m.NotifyAt(150, 50) - } - }) } func TestView(t *testing.T) { @@ -59,24 +52,25 @@ func TestView(t *testing.T) { // Create a new view c := counter(0) - v := m.View(NewRect(100, 0, 199, 99), c.count) + v := NewView[string, string](m, "view 1") + v.Resize(NewRect(100, 0, 200, 100), c.count) assert.NotNil(t, v) assert.Equal(t, 10000, int(c)) // Resize to 10x10 c = counter(0) - v.Resize(NewRect(0, 0, 9, 9), c.count) + v.Resize(NewRect(0, 0, 10, 10), c.count) assert.Equal(t, 100, int(c)) // Move down-right c = counter(0) v.MoveBy(2, 2, c.count) - assert.Equal(t, 36, int(c)) + assert.Equal(t, 48, int(c)) // Move at location c = counter(0) v.MoveAt(At(4, 4), c.count) - assert.Equal(t, 36, int(c)) + assert.Equal(t, 48, int(c)) // Each c = counter(0) @@ -84,87 +78,289 @@ func TestView(t *testing.T) { assert.Equal(t, 100, int(c)) // Update a tile in view - tile, _ := v.At(5, 5) - tile[0] = 55 - v.WriteAt(5, 5, tile) + cursor, _ := v.At(5, 5) + before := cursor.Value() + v.WriteAt(5, 5, Value(55)) update := <-v.Inbox - assert.Equal(t, At(5, 5), update.Point) - assert.Equal(t, tile, update.Tile) + assert.Equal(t, At(5, 5), update.New.Point) + assert.NotEqual(t, before, update.New) // Merge a tile in view, but with zero mask (won't do anything) - tile, _ = v.At(5, 5) - tile[0] = 66 - v.MergeAt(5, 5, tile, Tile{}) // zero mask + cursor, _ = v.At(5, 5) + before = cursor.Value() + v.MergeAt(5, 5, Value(66), Value(0)) // zero mask update = <-v.Inbox - assert.Equal(t, At(5, 5), update.Point) - assert.NotEqual(t, tile, update.Tile) + assert.Equal(t, At(5, 5), update.New.Point) + assert.Equal(t, before, update.New.Value) // Close the view assert.NoError(t, v.Close()) - v.WriteAt(5, 5, tile) + v.WriteAt(5, 5, Value(66)) assert.Equal(t, 0, len(v.Inbox)) } -type counter int +func TestUpdates_Simple(t *testing.T) { + m := mapFrom("300x300.png") + c := counter(0) + v := NewView(m, "view 1") + v.Resize(NewRect(0, 0, 10, 10), c.count) -func (c *counter) count(p Point, tile Tile) { - *c++ + assert.NotNil(t, v) + assert.Equal(t, 100, int(c)) + + // Update a tile in view + cursor, _ := v.At(5, 5) + cursor.Write(Value(0xF0)) + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(5, 5), + }, + New: ValueAt{ + Point: At(5, 5), + Value: Value(0xF0), + }, + }, <-v.Inbox) + + // Add an object to an observed tile + cursor.Add("A") + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(5, 5), + Value: Value(0xF0), + }, + New: ValueAt{ + Point: At(5, 5), + Value: Value(0xF0), + }, + Add: "A", + }, <-v.Inbox) + + // Delete an object from an observed tile + cursor.Del("A") + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(5, 5), + Value: Value(0xF0), + }, + New: ValueAt{ + Point: At(5, 5), + Value: Value(0xF0), + }, + Del: "A", + }, <-v.Inbox) + + // Mask a tile in view + cursor.Mask(0xFF, 0x0F) + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(5, 5), + Value: Value(0xF0), + }, + New: ValueAt{ + Point: At(5, 5), + Value: Value(0xFF), + }, + }, <-v.Inbox) + + // Merge a tile in view + cursor.Merge(func(v Value) Value { + return 0xAA + }) + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(5, 5), + Value: Value(0xFF), + }, + New: ValueAt{ + Point: At(5, 5), + Value: Value(0xAA), + }, + }, <-v.Inbox) } -func TestObservers(t *testing.T) { - ev := newObservers() - assert.NotNil(t, ev) +func TestMove_Within(t *testing.T) { + m := mapFrom("300x300.png") + c := counter(0) + v := NewView(m, "view 1") + v.Resize(NewRect(0, 0, 10, 10), c.count) + + // Add an object to an observed tile. This should only fire once since + // both the old and new states are the observed by the view. + cursor, _ := v.At(5, 5) + cursor.Move("A", At(6, 6)) + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(5, 5), + }, + New: ValueAt{ + Point: At(6, 6), + }, + Del: "A", + Add: "A", + }, <-v.Inbox) +} + +func TestMove_Incoming(t *testing.T) { + m := mapFrom("300x300.png") + c := counter(0) + v := NewView(m, "view 1") + v.Resize(NewRect(0, 0, 10, 10), c.count) + + // Add an object to an observed tile from outside the view. + cursor, _ := v.At(20, 20) + cursor.Move("A", At(5, 5)) + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(20, 20), + }, + New: ValueAt{ + Point: At(5, 5), + }, + Del: "A", + Add: "A", + }, <-v.Inbox) +} + +func TestMove_Outgoing(t *testing.T) { + m := mapFrom("300x300.png") + c := counter(0) + v := NewView(m, "view 1") + v.Resize(NewRect(0, 0, 10, 10), c.count) + + // Move an object from an observed tile outside of the view. + cursor, _ := v.At(5, 5) + cursor.Move("A", At(20, 20)) + assert.Equal(t, Update[string]{ + Old: ValueAt{ + Point: At(5, 5), + }, + New: ValueAt{ + Point: At(20, 20), + }, + Del: "A", + Add: "A", + }, <-v.Inbox) +} + +func TestView_MoveTo(t *testing.T) { + m := mapFrom("300x300.png") - // Subscriber which does nothing - var sub1 fakeView = func(e *Update) {} - ev.Subscribe(&sub1) + // Create a new view + c := counter(0) + v := NewView(m, "view 1") + v.Resize(NewRect(10, 10, 12, 12), c.count) - // Counting subscriber - var count int - var sub2 fakeView = func(e *Update) { - count += int(e.X) + assert.NotNil(t, v) + assert.Equal(t, 4, int(c)) + assert.Equal(t, 9, countObservers(m)) + + const distance = 10 + + assert.Equal(t, 1, countObserversAt(m, 10, 10)) + for i := 0; i < distance; i++ { + v.MoveTo(East, 1, c.count) + } + + assert.Equal(t, 0, countObserversAt(m, 10, 10)) + for i := 0; i < distance; i++ { + v.MoveTo(South, 1, c.count) + } + + assert.Equal(t, 0, countObserversAt(m, 10, 10)) + for i := 0; i < distance; i++ { + v.MoveTo(West, 1, c.count) + } + + assert.Equal(t, 0, countObserversAt(m, 10, 10)) + for i := 0; i < distance; i++ { + v.MoveTo(North, 1, c.count) } - ev.Subscribe(&sub2) - ev.Notify(&Update{Point: At(1, 0)}) - ev.Notify(&Update{Point: At(2, 0)}) - ev.Notify(&Update{Point: At(3, 0)}) + // Start should have the observer attached + assert.Equal(t, 1, countObserversAt(m, 10, 10)) + assert.Equal(t, 0, countObserversAt(m, 100, 100)) - for count < 6 { - time.Sleep(1 * time.Millisecond) + // Count the number of observers, should be the same as before + assert.Equal(t, 9, countObservers(m)) + assert.NoError(t, v.Close()) +} + +func TestView_Updates(t *testing.T) { + m := mapFrom("300x300.png") + v := NewView(m, "view 1") + v.Resize(NewRect(10, 10, 15, 15), nil) + + move := func(x1, y1, x2, y2 int16) { + at, _ := m.At(x1, y1) + at.Move("A", At(x2, y2)) + + assert.Equal(t, Update[string]{ + Old: ValueAt{Point: At(x1, y1)}, + New: ValueAt{Point: At(x2, y2)}, + Del: "A", Add: "A", + }, <-v.Inbox) } - assert.Equal(t, 6, count) - ev.Unsubscribe(&sub2) + move(9, 12, 10, 12) // Enter from left edge + move(10, 12, 9, 12) // Exit to left edge + move(15, 12, 14, 12) // Enter from right edge + move(14, 12, 15, 12) // Exit to right edge + move(12, 9, 12, 10) // Enter from top edge + move(12, 10, 12, 9) // Exit to top edge + move(12, 15, 12, 14) // Enter from bottom edge + move(12, 14, 12, 15) // Exit to bottom edge + move(9, 9, 10, 10) // Enter from top-left diagonal + move(10, 10, 9, 9) // Exit to top-left diagonal + move(15, 9, 14, 10) // Enter from top-right diagonal + move(14, 10, 15, 9) // Exit to top-right diagonal + move(9, 15, 10, 14) // Enter from bottom-left diagonal + move(10, 14, 9, 15) // Exit to bottom-left diagonal + move(15, 15, 14, 14) // Enter from bottom-right diagonal + move(14, 14, 15, 15) // Exit to bottom-right diagonal - ev.Notify(&Update{Point: At(2, 0)}) - assert.Equal(t, 6, count) + assert.NoError(t, v.Close()) +} + +func TestSizeUpdate(t *testing.T) { + assert.Equal(t, 24, int(unsafe.Sizeof(Update[uint32]{}))) } -func TestObserversNil(t *testing.T) { - assert.NotPanics(t, func() { - var ev *observers - ev.Notify(&Update{Point: At(1, 0)}) +// ---------------------------------- Mocks ---------------------------------- + +func countObserversAt(m *Grid[string], x, y int16) (count int) { + start, _ := m.At(x, y) + start.Observers(func(view Observer[string]) { + count++ }) + return count } -func TestNotifyAt(t *testing.T) { - m := mapFrom("300x300.png") +func countObservers(m *Grid[string]) int { + var observers int + m.Each(func(p Point, t Tile[string]) { + if t.data.IsObserved() { + observers++ + } + }) + return observers +} - // Create a new view - c := counter(0) - v := m.View(NewRect(0, 0, 99, 99), c.count) - assert.NotNil(t, v) - assert.Equal(t, 10000, int(c)) +type fakeView[T comparable] func(*Update[T]) - m.NotifyAt(1, 1) - update := <-v.Inbox - assert.Equal(t, int16(1), update.X) - assert.Equal(t, int16(1), update.Y) +func (f fakeView[T]) Viewport() Rect { + return Rect{} } -type fakeView func(*Update) +func (f fakeView[T]) Resize(r Rect, fn func(Point, Tile[T])) { + // Do nothing +} -func (f fakeView) onUpdate(e *Update) { +func (f fakeView[T]) onUpdate(e *Update[T]) { f(e) } + +type counter int + +func (c *counter) count(p Point, tile Tile[string]) { + *c++ +}