Preface
Allow me to preface this article by stating that this is the first in a multi-part series where I describe how I chose to implement a mechanic from one of my favourite text-based Role Playing Games (RPGs) from back in the day. This article in particular will cover the implementation details, constraints, and whilst providing context, does not yet dive into the code. As a side-note, the code shown throughout this series is not intended to be observed as production-ready. However, the gas optimisations are legit, believe dat.
Motivation
Once upon a time, I had a deep appreciation for text-based RPGs. My favourite in particular is the now defunct Hobo Wars, and yes, it’s exactly what you think it is. You start off as a Level 1 hobo on a journey to make it big! Completing quests, beating up other hobos to earn money, and training your hobo to level up various stats and skills that will benefit them in the long term.
However, there was one particular aspect of the game that always had me rushing home from school. That was… can collecting! Anticlimactic? Yes, but let me break it down for you. Every 24 hours, you are given 100 moves to explore the city. The city itself is a perfect square grid where your adventure starts from your last known position of the previous explore run. You navigate the city by clicking 1 of 8 different arrows on a simple user interface, allowing you to venture either forwards, backwards, left, right and each respective diagonal position too.
Upon venturing to a new tile, you had a chance to find varying amounts of either cans or money and even spot another player that you could engage in P2P combat with! The beauty of this mechanic was that it was so simple, yet managed to bring me great joy in my younger years. The feeling of excitement that I would get from venturing to a new tile in hopes to find a substantial amount of cans that I could later exchange at the in-game recycling depot for money. This game was truly ahead of its time.
Needless to say, more than a decade has passed since then and I have now found myself in the world of Solidity looking for new and interesting things to do. So I thought to myself, why not try to implement something similar? Gas optimisation is one of my favourite facets of the language and shortly prior to coming up with this idea, I had also begun my deep dive into assembly. It seemed like a no-brainer! Do something challenging and have the opportunity to hone my assembly skills in the process. It was officially go-time.
Implementation & Constraints
1. Layer 1 Execution
Before writing any code, I decided that it was rather important to first define some constraints of the implementation first. I wanted to approach this project with the intent of keeping execution on Layer 1. The rationale for this is that while it would make more sense to do this on a Layer 2 network, it just felt like cheating. I needed there to be some underlying motivation to optimise the code and really crunch the numbers as low as humanely possible.
2. Movement Strategy
Following this, the next problem was to determine how to go about implementing directional movement. If you recall, the Hobo Wars implementation allows a player to move in 1 of 8 directions from their current tile. After crunching the numbers, I made the decision to limit movement to up, down, left and right only. Now before you haze me, let me explain my thought process as to how and why I decided to stick with this strategy.
Let’s talk bits, 1s and 0s. If we think about movement, particularly in the context of the implementation by Hobo Wars, one would need at absolute minimum 3 bits of information to denote movement in 8 different directions which are represented as follows:
With the former in mind, we would need 300 bits of information to represent 100 moves, 3 bits per move * 100 moves. Proceeding with this approach would require the use of the bytes memory data type as 300 bits exceeds the conventional Solidity data type size of 256 bits. In addition to this, working with the bytes memory data type gets very ugly very quickly as the starting and ending bits of a particular move can vary between bytes. Whilst implementing this strategy is of course doable, I personally felt that it would result in spaghetti code and wasteful gas consumption. The negatives strongly outweighed the positives.
On the contrary, the benefits of proceeding with a 4 direction movement strategy came to light almost immediately. Not only would we be able to represent each move using only 2 bits of information, we could also fit all 100 moves within just 200 bits (25 bytes) meaning our entire move set could fit within a bytes32 data type. In addition to this, we also guarantee that each movement byte contains exactly 4 moves, meaning that parsing this information becomes trivial using some bit-shifting wizardry.
Let us visualise this movement. 11100001 is a single byte of information and represents a series of 4 moves, reading from left-to-right. If we parse these moves according to the bit values previously defined above, we can see that this binary string represents up, left, down and right which would move the player in a perfect square back to their original position.
11100001 movement visualised, reading from left-to-right.3. Loot Randomisation
Another focal point of the implementation is to determine whether a user successfully finds any cans upon moving to a new tile, and if they do, how many? One important detail that I should have mentioned earlier is that you don’t always necessarily find cans upon moving to a new tile, and if you do, that number can range from anywhere between 1 and 7.
Thankfully, implementing this type of functionality is quite trivial. However, doing it in such a way that it can’t be gamed? Not so much. Due to the stakes being relatively low despite my perceived value of cans being quite high, I decided that on-chain randomness using a mixture of both global and state variables as well as execution context was sufficient. If anything, anyone who implements their own algorithm to find the maximum amount of cans per explore deserves to reap the fruits of their labour!
To Be Continued…
I hate cliffhangers and I’m sorry that I had to leave you hanging for now! However, I don’t want each article within this series to be a behemoth wall of text, that’s mentally fatiguing! I hope at this point, you have a general understanding of the implementation and how it will function. Stay tuned for the next part where we’ll look at a naive Solidity implementation to acquire our target to beat for gas consumption and begin to work backwards and start shaving off the gas. If you have enjoyed this series so far, feel free to drop an applaud and follow me on my Twitter where I often tweet about my general dev thoughts. See you in Part 2! ✌️
