StarkMaze is a mini recurring maze game build on StarkNet ! everyday a new labyrinth will be generated. Player have to solve the daily maze as quickly as possible. at the end of his game, an nft corresponding to the path he has traveled will be generated. The player can share his score directly on twitter.
We have 3 repository:
starkmaze-contracts -> Repo of our differents Smart Contract
starkmaze-frontend -> Repo of our final site w/maze generation on-chain
starkmaze-frontend-Gen-onChain -> Repo of a test with off-chain generation of the maze
We decided to build a fully on-chain game. It mean that our maze generation algorithm will be coding and executing on-chain. First of all, we'll use depth first search to generate a perfect maze. A perfect maze is a maze with only one path between any two cells. Since there is only one path between any two points you can represent a perfect maze as a tree. Then use both depth first search and breadth first search to solve the maze.
Depth First Search (DFS) :
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The base of the algo is to starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
Our DFS Algorithm in pseudocode :
- Start at a random cell. (For now we decided to start all the time at top left)
- Mark the current cell as visited, and get a list of its neighbors.
- For each neighbor, starting with a randomly selected neighbor
- If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.
Functions already implemented :
| Functions | Objectives |
|---|---|
generate_maze() |
Generate maze. |
_cell_neighbors() |
Return the only neighbors that don't have downed walls. |
_walls_bitwise_and() |
Check that the neighbor doesn't have any walls knocked down. |
_cell_in_bounds() |
Check that the current cell is already inside the maze. |
COMING SOON
For movements, we have in our smart contract defined 4 functions (move_up, move_down, move_left, move_right) that we call each time a user performs a movement. The next step is to group each movement and use the multicall in order to have the transactions grouped
For the management of the recurring generation of the maze, we have decided to use the Yagi Finance solution which will allow us to automate the generation of the maze every day We have started the implementation but we are waiting for the return of their team in order to be able to automate everything with them.
We will continue this project and go to the end, we have discussed a lot with many people who gave us valuable advice for the rest of the project.
Next features:
Finish on-chain generation of maze
Implement NFT with good path
Add on-chain stopwatch
Multicall function with all move
Change UI
StarkMaze is released under the MIT.