# Technical Tricks, Aug 2022

Today we’ll be talking about a few technical tricks that we used to speed up deploying multiple contracts for our first fully on-chain strategy game. You can try the game here.

### Map initialization

In our game, each tile is denoted by its position and terrain type number (water, coast, …). After the map is generated using a combination of Perlin noise and custom algorithms, the map, which is represented as a 2D array of numbers, must be set in Solidity.

A typical map that houses 100 players for 1 hour requires roughly a 200×200 grid map. That’s 40,000 tiles to be initialized, and to initialize each, we need to set the terrain field in each of the 40,000 tile structs on-chain.

How can we initialize this large game map within a reasonable amount of time?

### Naive solution

We first wrote a setMapChunk function, which allows the world creator to initialize a chunk of the map by passing in a 2D array of numbers, each number representing the terrain-base combination of one tile. We’ll refer to this combination as a tile type in the rest of article. In this instance 3 represents a water tile, and 5 represents a land tile with a city

``````
function setMapChunk(Position memory _startPos, uint256[][] memory _chunk) external onlyAdmin {
for (uint256 _dx = 0; _dx < _chunk.length; _dx++) {
for (uint256 _dy = 0; _dy < _chunk.length; _dy++) {
Position memory _pos = Position({x: _startPos.x + _dx, y: _startPos.y + _dy});
uint256 _terrainId = _chunk[_dx][_dy];

if (_terrainId >= 3) {
// Note: temporary way to set base
BASE_NAME _baseName = _terrainId == 3 ? BASE_NAME.PORT : BASE_NAME.CITY;
_terrainId -= 3;
}

gs().map[_pos.x][_pos.y].terrain = TERRAIN(_terrainId);
}
}
}``````

The initialization is broken into 10×10 map chunks; otherwise, its gas consumption would exceed the gas limit. Using Hardhat on localhost, setting just a 100×100 map with a few dozen bases takes roughly 142 seconds. The problem becomes serious when players themselves deploy maps to play with others — we can’t expect them to wait 2 minutes for a custom game to be created.

### Bit of clever math

We decided to use arithmetic encoding. The largest uint256 is 2^256–1, a number much larger than the number of tile types (which is 6 at the moment) we have. This means that every uint256 we use to store a tile type has a lot of “unused” space.

Now, here’s the intuition: Suppose we have only 2 tile types. We can then have each digit in a uint256 represent a tile, and therefore each integer representing 256 tiles. What if we use 6-arithmetic for 6 tile types? After some calculation, it turns out that the largest power of 6 smaller than 2^256 is 99, which means we can store up to 98 tiles in a single uint256 without overflowing. To be extra safe, we use 50.

Let’s run through a simple example by encoding the type numbers of 50 tiles in one uint256. The first tile would be encoded as TILE_TYPE_0×6⁰, the second tile as TILE_TYPE_1×6¹, etc. The resulting encoded uint256, C, would be the sum of individual encoded tile types.

Such encoding has an important property: The input tuple of tile types, denoted M = [TILE_TYPE_0, TILE_TYPE_1, … , TILE_TYPE_49], is uniquely decodable from the resulting uint256, C, from the operation. More rigorously, the operation is injective.

The decoding goes as follows: To fetch the tile type of the i-th tile, we first take the remainder of C divided by 6^(i+1). Since the types of all tiles with index greater than i are divisible by 6^(i+1), and only they are, the remainder should only contain the sum of all encrypted tile numbers whose index is at most i. Then, floor divide the remainder by 6^i. Since all tiles with index lower than i are smaller than this divider and thus yield 0 in the floor division, we get back exactly TILE_TYPE_i, the tile type of the i-th tile.

## Corresponding code

In this new solution, we encode a 2D map of integer tile types into batches of encoded columns. Note that this step happens in TypeScript before the result is passed on-chain, so the duration is negligible.

``````export const encodeTileMap = (tileMap: TILE_TYPE[][], numInitTerrainTypes: number = 6, batchSize: number = 50): string[][] => {
const result: string[][] = [];
const numBatchPerCol = Math.floor(tileMap.length / batchSize);
const lastBatchSize = tileMap.length % batchSize;

let encodedCol: string[];
let tempBatch: bigint;
let k: number;

for (let x = 0; x < tileMap.length; x++) {
encodedCol = [];
for (k = 0; k < numBatchPerCol; k++) {
tempBatch = BigInt(0);
for (let y = 0; y < batchSize; y++) {
tempBatch += BigInt(tileMap[x][k * batchSize + y]) * BigInt(numInitTerrainTypes) ** BigInt(y);
if (tempBatch >= MAX_UINT256) throw new Error('Encoding exceeds uint256 max size');
}
encodedCol.push(tempBatch.toString());
}
if (lastBatchSize > 0) {
tempBatch = BigInt(0);
for (let y = 0; y < lastBatchSize; y++) {
tempBatch += BigInt(tileMap[x][k * batchSize + y]) * BigInt(numInitTerrainTypes) ** BigInt(y);
if (tempBatch >= MAX_UINT256) throw new Error('Encoding exceeds uint256 max size');
}
encodedCol.push(tempBatch.toString());
}
result.push(encodedCol);
}

return result;
};``````

At the beginning of each player action functions such as a movement from one tile to another, we then check whether the tile is initialized or not, decoding its value.

``````    function _initializeTile(Position memory _pos) public {
WorldConstants memory _worldConstants = gs().worldConstants;
uint256 _batchSize = _worldConstants.initBatchSize;
uint256 _numInitTerrainTypes = _worldConstants.numInitTerrainTypes;

uint256 _encodedCol = gs().encodedColumnBatches[_pos.x][_pos.y / _batchSize] % (_numInitTerrainTypes**((_pos.y % _batchSize) + 1));
uint256 _divFactor = _numInitTerrainTypes**(_pos.y % _batchSize);
uint256 _terrainId = _encodedCol / _divFactor;

if (_terrainId >= 3) {
BASE_NAME _baseName = BASE_NAME(_terrainId - 3);

if (BASE_NAME(_terrainId - 3) == BASE_NAME.OIL_WELL) {
_terrainId = 1;
} else {
_terrainId -= 3;
}
}

gs().map[_pos.x][_pos.y].isInitialized = true;
gs().map[_pos.x][_pos.y].terrain = TERRAIN(_terrainId);
}``````

It turns out that this approach is much more gas-efficient. We can initialize a 100 by 100 tile map in ~6.2 seconds using Hardhat on the same machine, a 23x improvement compared to the naive solution.

### Wrangling with Foundry

This version of Curio uses the Diamond architecture along with Foundry for testing. Although there are many benefits to writing tests in Solidity, Foundry doesn’t provide a clean interface for JavaScript to be used in the test process. For instance, how do we initialize the tests with an auto-generated world map? Since our map generation is written in TypeScript, does this mean we need to rewrite the algorithm in Solidity again?

Luckily we discovered the -ffi cheatcode in Foundry, which allows a call of an arbitrary command. We used this to generate the map in TypeScript, encode the map using abi.encode, run the map gen code through a bash script, and pipe that encoded map back into Foundry to then be decode in Solidity and passed on as a large 2D array map variable. The same approach was used to get a list of all solidity function selectors in used in all of the diamond’s facets for initialization.

``````function getSelectors(string memory _facetName) internal returns (bytes4[] memory selectors) {
string[] memory cmd = new string[](5);
cmd = "yarn";
cmd = "--silent";
cmd = "run";
cmd = "getFuncSelectors";
cmd = _facetName;
bytes memory res = vm.ffi(cmd);
selectors = abi.decode(res, (bytes4[]));
}``````

### What we’re up to …

The team is busy collecting feedback from our first 2 demos while writing the yellow paper for our upcoming game. Thank you to the 500+ players who tried it out!

While we remain optimistic on what on-chain games can bring, we also acknowledge Solidity at its current stage is somewhat inflexible to craft truly complex worlds. Every day we ask ourselves things like:

• How can we bring key lessons from traditional game design (networking, entity-component-system) on-chain? Which lessons are viable and which aren’t?
• Solutions to bridge on-chain and off-chain compute without compromising composability? hmm…
• What are truly crypto-native game mechanics (🤫)?
• What are the tradeoffs between different ecosystems and languages for the future of on-chain games?

If these sound exciting to you, please reach out to team@curio.gg.