onlydustxyz/starkonquest

make much faster turns by maintaining ships and dusts locations in Grid

Closed this issue · 0 comments

Following issue #47 and PR #60

In the current implementation of https://github.com/onlydustxyz/starkonquest/blob/main/contracts/libraries/move.cairo , for dusts or ships, two loops are happening for each turn.

The first one over the whole grid to find the dusts/ships positions and store them in an Vector2 array.
The second one over this Vector2 positions array to move the ships/dusts from where they are.

Each turn in a battle would be much faster and have much less operations per turn if we get rid of this first loop by storing dusts/ships position and not iterating over the whole grid each time to re-build it.

A way to do it would be to add two new Vector2* fields in the Grid struct to keep track of every elements (ships or dusts) positions.

Note that in the current implementation, the first ship to move is the first one found by the Grid iterator.
With a change of this nature and nothing else, the first ship to move would be the ship #1, then the ship #2, etc.
But by maintaining the ships positions, we could also have arbitrary control on the order of ships movement,
ie : for ships 1,2,3, ...N, we could for example shuffle the numbers and make them move on a different random order at each turn, which I think would be more fair.

I propose to first only implement maintaining locations and have the ships moving the ascending order, then open a new issue about making it random.