👋 Welcome Back… Maybe?
In the first part of this series, we discussed the implementation of the proposed mechanic and a variety of constraints it brought along with it. In this part, we’ll review a generic and unoptimised Solidity implementation so that we can acquire a baseline estimate for how much gas our function will consume when invoked.
In addition to this, we’ll also cover the movement aspect of this mechanic in greater detail to define clearer expectations about our system and how movement within it will be constrained. For those of you who are interested, I have uploaded this code to my GitHub where you can check it out and follow along.
🏃♂ ️Let’s Talk Movement
If you’re following the code, you’ll notice the mapSize variable on Line 34 has been declared with a value of 2499. What does this value mean and why is it so specific? If you recall from Part I, the city map in Hobo Wars was a perfect square grid. Perfect in the sense that its height was equal to its width. In order to replicate a perfect square grid within our implementation, we need to work with square numbers. As a refresher, square numbers are numbers that when squared, result in an integer. Since mapSize is inclusive of the value 0, a value of 2499 represents a 50 x 50 grid with 2500 tiles.
Let’s take a moment to reference the above grid. The blue tile located in the top-left denotes tile 0 whilst the green tile located at the bottom-right denotes tile 2499. Tiles sequentially increment moving from left-to-right meaning that the purple tile found at the end of the first row denotes tile 49. Here’s where you have to pay attention! In order to keep things relatively simple, I opted to only implement boundary checks on the lower and upper limits of mapSize. This means that a player cannot surpass the city limits if the equation provided below (Figure 2) holds true. If for whatever reason, a player decides to move right from tile 49 then their movement will be wrapped around the grid to the purple tile located below tile 0, denoting tile 50.
🗺️ Exploring the City
Now that we have a better idea of how movement within our system is defined, let’s begin to look at what actually happens when a user invokes our explore function. If you’re following along with the repository, you’ll notice the code provided has been thoroughly commented to assist with any queries you may have along the way. With disregard to any logic that may be deemed as self-explanatory, let’s dive in to the core functionality of explore.
📍 Starting Position
It would be rather trivial to store the last known position of a player and have them continue their journey from this tile. Hence, let’s spice things up a little. For any given explore run, let’s position the player in a seemingly random tile that can be calculated off-chain. It’s worth mentioning that throughout this entire process, there should be an interface available to assist the player with visualising their specified move set. A somewhat relevant example of what this interface may look like can be found here by 0xBeans.
Let’s start by calculating the gameState value. Make note of how this variable is defined on Lines 77 to 79 of the code and utilises the native abi.encode function. Hashing the concatenated values and casting the result to a uint256, our result will be some relatively large integer value that we can then use to calculate the starting position.
To calculate the starting position of a player, we simply take our gameState value and modulo it by mapSize and add 1. Doing so will result in a value within the limits of 0 and 2499. It’s that simple!
💯 Parsing 100 Moves
Now that we have calculated a starting position for our player, let’s determine how to parse the provided move set. As a refresher, recall that each of the 4 movements is denoted using 2 bits of information, therefore within a single byte (8 bits) we can pack 4 movements. For simplicity sake, let’s assume that the player has lost their bearings and expends all 100 moves constantly moving in a square from their starting position. Remember that moves are read left-to-right and direction is determined as shown below.
In the provided code, we utilise both an inner and outer loop which parses each movement byte alongside each of the 4 movements within each byte respectively. Within the outer loop on Line 107 of the code, we assign the moveSet variable to the byte of moves that we are currently iterating over. Doing so will provide us with a uint8 value indicative of the 4 moves we are about to parse. Due to the defined conditions of the inner loop, we are able to utilise bit-shifting to clean the lower and upper bits of the respective move that we are parsing and determine which direction the player wishes to venture.
🔁 Position Updating
That wasn’t so hard was it? Updating the players position is also a trivial matter. If anything, you’re probably wondering what that magic value of 50 is and why it matters. Recall that we are working with a 50 x 50 grid, so if a player is currently located at tile 150 and decides to move up towards tile 0, their position should be decremented by 50. The same applies for the inverse, except movement down towards tile 2499 should result in a 50 tile increase.
💰 Determining Loot
Now we can dig into what I would consider to be the crux of the explore logic, determining if a player is fortunate enough to find cans upon venturing to a new tile, and if so, how many? Determining how to implement this functionality plagued me for many days, and ultimately, I decided that I wanted to seed for every movement that the player made. Let’s call this seed the eventId and make note of how it is both calculated and used.
Similar to the previously mentioned gameState (Figure 3) variable, eventId is calculated by hashing the concatenated value of the current block timestamp, the players position, the current movement byte index being iterated over, and the current left-shift value which is used to clean the upper bits of move. The values used to generate this seed are subjective and can ultimately be substituted with whatever the implementer deems suitable. My personal reasoning for using the following values are as follows:
- block.timestamp — Allows for the amount of cans that are found to vary depending on when the function itself was invoked.
- pos — Made sense to account for the players current position when determining whether or not any loot was found.
- i — Guaranteed to change upon each individual movement byte being parsed and will increment with each iteration.
- j — Accompanied by the i value, ensures that a player constantly moving amongst the same positions, is not seeded with a previously given value.
Now that we have the eventId value, we can use it to determine whether or not a player has encountered a loot event. To do so, we modulo the eventId by 100 and use the resulting value as our roll for this specific tile. Due to the nature of how the modulo operation works, our roll will be some value within the range of 0 to 99. If the calculated roll is within the bounds of 0 to lootChance, precious cans await us upon our arrival.
Assuming the player has successfully found loot, we can apply an equation similar to the one that was used to calculate the players starting position to determine the amount of cans that will enter their warm embrace. This is calculated via eventId modulo maxCans and add 1. That’s it! An in-depth explanation of all the core mechanics of our explore function.
⛽ Gas Consumption
Now for the part I am sure most of you have been waiting for, what’s the gas consumption? Remember, this implementation has been written in such a way that it does not excessively consume gas, but it doesn’t really utilise the majority of lesser-known gas optimisation tricks either. To calculate our final number, I popped the smart contract into Remix, enabled the optimiser for 200 runs and called the explore function 5 times with the same input. Here’s the result…
Due to the nature of the implementation, it is expected that there is some discrepancy in gas consumption amongst calls. But there we have it, our final number to beat is 130121
gas which is inclusive of the ~21,000 gas required to create a transaction on Ethereum. From here on out, expect things to get juicy as we continue our conquest to push the limits of gas optimisation with the assembly implementation.
😉 Parting Words
If you’ve made it this far, thanks for reading! In Part III, we’ll review a heavily optimised assembly port of the provided Solidity code and touch on all the unique tips and tricks that were used to reduce gas. Expect unreadable code, more bit-shifting, branchless refactoring and most importantly, cans! If you enjoyed this article, feel free to drop an applaud and follow me on Twitter where I post various other Solidity related content and my general thoughts as a developer within the Web3 space. Peace!