We are two young devs that are starting to explore this amazing world. As a starting project we wanted to make a funny, but real, project on Ethereum.

The project is inspired by DecentraLand (LAND) and is pretty simple:

We have a 1000x1000 area (representing a map) and we want to let the users to claim an arbitrary piece of this map, communicating a Starting XY and an Ending XY coordinates.

This will generate an unique token (ERC-271) that will represent this area of the map.

Our main problem is the algorithm that will check if an area is already claimed or not.

The more users will claim a piece of map the more we will have to iterate to know if a new order should fail or not, raising the gas fee to the roof.

The smart contract will be like:

  • Take the new order containing the start and the ending coordinates
  • Iterates for every previous area bought while checking if there is an overlap
  • Revert or Confirm the transaction

And this will get so much expensive in terms of gas when you have to check a lot of previuosly claimed areas.

Any suggestion? Thank you a lot!

  • Why not iterate on the client and send the processed information to the contract, instead of processing and iterating on the contract? – Juanu Mar 15 at 18:50
  • Because the contract will need to know if a land is free or claimed to approve the transaction or to make it fail, so we need an algorithm to check this even if we will put it client side. – Univers3 Mar 15 at 23:27

I would store a two-dimension array of booleans of static 1000x1000 size. Whenever someone reserves some size of land, the algorithm marks each 1x1 spot as reserved. If any of those is already reserved (boolean: true) it reverts.

This includes iterating, and you have to figure out whether the transaction may exceed gas limits due to this iterating, but at least the iterations are limited and the maximum amount of iterations is known.

  • 2
    I agree, this is the most obvious way to do it. The buyer pays for the cost of the reservations. Large reservations may require multiple transactions owing to the cost of iterating over large, nested loops and the block gas limit. – Rob Hitchens Mar 15 at 17:39
  • Yes, this is what we achieve to write too. But even only a 100x100 (1% of the map) iteration on a boolean matrix is crazy expensive in gas. – Univers3 Mar 15 at 23:25
  • You don't need to iterate over all of it. You just need to 1) determine the 1x1 squares the reservation requires 2) check those in the array like require(!reservations[53][13], "reserved"); – Lauri Peltonen Mar 16 at 5:55

In case you're looking for a non-obvious solution that could support much larger sets, you could use a counterfactual approach.

Buyer stakes funds at risk over his coordinates claim and the contract holds a list of historic claims. A bounty function lets anyone seize the buyer's stake and revokes their claim if they can prove that 1 of the pixels within the claimed region was previously claimed by someone else.

The bounty-hunters would provide the exact records to use to evaluate the proof, which means the contract doesn't need to iterate. It simply needs to confirm that the disputed pixel is between top-left and bottom-right that are claimed in the identified previous historic record.

function claimBounty(bytes32 claimId, bytes32 previousClaimId, uint pixelX, uint pixelY) external ... {
  // Is pixelX/pixelY inside both rectangles?
  // slashes claimId, revokes claimsId, sends money

More generally, reframe the process as an economic problem rather than a mechanical problem.

Hope it helps.

  • Actually it's pretty smart this solution, you are externalizing the effort to check overlap to the users. The only problem is that this solution doesn't suit our user experience. Thank you! – Univers3 Mar 15 at 23:22

I propose another solution where the gas consumption is more related to the number of users rather than the size of the lands.

Let's assume we have the following data structures:

struct Coordinates {
   uint startX,
   uint startY,
   uint endX,
   uint endY 
mapping(address => Coordinates) public coordinates;
address [] public users;

This way, you could have an array of users with their geographical area. Whenever a user claims a new arbitrary piece of the map (new coordinate), you should go through the users' array and check whether the new area (mapping) is not included in any of the existing ones.

Perhaps the complexity with this approach is to calculate whether an area falls inside another area. Something that would ease this process would be to define a rule such as: "the starting coordinate must be the lowest-left point, and the ending coordinate the highest-right point".

It's just thinking loud, but it may work...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.