7 min. read
The Combinatory video game works as a mathematics game where you swipe tiles and combine them into eachother using mathematics operations, trying to get a specific score. This article will detail how I developed the Map Search Algorithm to create randomly generated levels.
Here is the full function, according to the open-source paths.kt file in the calculatory repository:
/**
* The directions a player can make on a grid. Represent up, down, left, and right.
*/
val directions = listOf(
Pair(0, 1),
Pair(0, -1),
Pair(1, 0),
Pair(-1, 0)
)
/**
* Find all the possible values that can be obtained by moving on a grid.
*
* Worst-case time complexity is `O((4m)^k)`, where `m` is the size of [functions] and k is the number of tiles that can be visited from [sx] and [sy]. This significantly decreases, as the algorithm prunes duplicate results and utilizes
* coroutines for parallel processing.
*
* For example, various testing on the [Mock Example](https://pl.kotl.in/t60amvt1e), which includes a 11x11 grid with 15 functions and 28 empty tiles, took `1.5s` and generated `73,118` values.
* @param grid The grid to move on, represented as a 2D Double Array. Values of `0` represent an empty tile.
* @param functions The operations to apply to the values.
* @param sx The starting x coordinate.
* @param sy The starting y coordinate.
* @return A set of all the possible values that can be obtained by moving on the grid.
* @see <a href="https://pl.kotl.in/t60amvt1e">Mock Example</a>
*/
suspend fun findValues(
grid: Array<DoubleArray>,
functions: List<Operation>,
sx: Int,
sy: Int
): Set<Double> = coroutineScope {
val size = grid.size
require(grid.isNotEmpty()) { "Grid must have at least one row" }
require(grid[0].isNotEmpty()) { "Grid must have at least one column" }
require(sx in grid.indices) { "Starting X Coordinate must be within the grid" }
require(sy in grid[0].indices) { "Starting Y Coordinate must be within the grid" }
require(grid.all { row -> row.size == size }) { "Grid must be square" }
val channel = Channel<Double>()
val visited = mutableSetOf<Pair<Int, Int>>()
val values = mutableSetOf<Double>()
suspend fun exploreValue(value: Double, cx: Int, cy: Int, operations: List<Operation>) {
var hasMoved = false
directions.forEach directions@{ (dx, dy) ->
val nx = cx + dx
val ny = cy + dy
if (nx < 0.0 || nx >= size) return@directions
if (ny < 0.0 || ny >= size) return@directions
if (grid[nx][ny] == 0.0) return@directions
if ((nx to ny) in visited) return@directions
visited.add(nx to ny)
val nv = grid[nx][ny]
operations.forEach { o ->
val newValue = o(value, nv)
if (newValue in values) return@forEach
values.add(newValue)
channel.send(newValue)
val remaining = operations.toMutableList()
remaining.removeAt(remaining.indexOf(o))
exploreValue(newValue, nx, ny, remaining)
hasMoved = true
}
visited.remove(nx to ny)
}
if (!hasMoved || operations.isEmpty())
channel.send(value)
}
val sv = grid[sx][sy]
launch {
exploreValue(sv, sx, sy, functions)
channel.close()
}
for (value in channel)
values.add(value)
return@coroutineScope values
}
At its barebones, Combinatory level data can be represented as a 2D Number Array:
[
[ 0, 1, 2, 3, 4 ]
[ 0, 4, 0, 2, 1 ]
[ 0, 3, 2, 3, 2 ]
[ 0, 1, 4, 6, 2 ]
[ 2, 0, 3, 2, 0 ]
]
We can immediately notice that 0 in this instance represents tiles that are not declared. Therefore, this 5x5 grid example demonstrates that there are some holes in this map.
All Combinatory map data starts as an integer, but can shift to decimal values based on division operations present, which is why the map algorithm uses an Array<DoubleArray> as opposed to an Array<IntArray>. The function also intakes a List<Operation>, which are the operations that are present (addition, subtraction, multiplication, or division), and starting X (sx) and Y (sy) coordinates.
The function starts off requiring a few things:
First, the method uses an asynchronous channel to be able to handle multiple paths at once (more on that below), a visited set of pair coordinates to act as an asynchronous mutex to prevent two paths from moving at the sametime, and and the final values set that we will return. The difference between a List and a Set is that a Set is unordered and will reject duplicate values, meaning that we reduce performance overhead and unnecessary space when multiple paths with the same outcome are found. This also works with visited where we only have to know which places were visited.
As we continue to the actual method implementation, the method defines a local function exploreValue which makes a step in any random direction given the current value. This method is called recursively until the player runs out of directions to go to. This reflects the implementation details of the actual game, where you swipe in any direction for any kind of operation until you run out of operations to swipe with. This is demonstrated through looping through both the directions and the operations array, where the former is looped through at random into new asynchronous anlayzers and the latter has its elements removed until it runs out.
After the steps have completed, the channel is closed, and the values are collected into a Set.
The function integrates with Kotlin’s Suspend functions to reduce time complexity values and explore multiple paths at the same time. It sends the values to a Channel<Double> which then propogates those into a proper Set<Double>, or all of the possible values for every single combination in a map.
While this method is specific to Combinatory, this algorithm is a performative example for how map search can be implemented in Kotlin within a 2D Array. You can utilize this method in your own applications to analyze result data of different maps present in your program.
This was a short but informative explanation about the Map Search Algorithm in the Combinatory Video Game. Stay tuned for more in-depth analysis.