# Technical Tricks, Aug 2022

By Yijia Chen

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

*in the rest of article. In this instance 3 represents a water tile, and 5 represents a land tile with a city*

*tile type*```
function setMapChunk(Position memory _startPos, uint256[][] memory _chunk) external onlyAdmin {
for (uint256 _dx = 0; _dx < _chunk.length; _dx++) {
for (uint256 _dy = 0; _dy < _chunk[0].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;
Util._addBase(_pos, _baseName);
_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

*×6¹, etc. The resulting encoded uint256,*

*TILE_TYPE_1**, would be the sum of individual encoded tile types.*

**C**Such encoding has an important property: The input tuple of tile types, denoted **M**** **= [

*,*

*TILE_TYPE_0**, … ,*

*TILE_TYPE_1**], is*

*TILE_TYPE_49**from the resulting uint256,*

*uniquely decodable**, from the operation. More rigorously, the operation is*

**C***.*

*injective*The decoding goes as follows: To fetch the tile type of the * i-*th tile, we first take the remainder of

*divided by 6^(*

**C***+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*

*i**, the tile type of the*

*TILE_TYPE_i**-th tile.*

*i*## 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[0].length / batchSize);
const lastBatchSize = tileMap[0].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);
_addBase(_pos, _baseName);
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

**improvement compared to the naive solution.**

**23x**### 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

*, 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.*

*abi.encode*```
function getSelectors(string memory _facetName) internal returns (bytes4[] memory selectors) {
string[] memory cmd = new string[](5);
cmd[0] = "yarn";
cmd[1] = "--silent";
cmd[2] = "run";
cmd[3] = "getFuncSelectors";
cmd[4] = _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.