Arkanoid

Modules used

Arkanoid game is an action game utilizing recursive proofs to build leaderboard. Arkanoid game process is divided into ticks where the game state is reproduced on every tick inside the circuit. The following modules are used:

GameHub
RandomManager

Arkanoid like game verification overview

All the game process is divided into ticks that runs N times per second. During each tick user input like arrow pressing is captured. For now every tick store cart coordinate changes, and momentum for situations where ball hits the cart.

export class Tick extends Struct({
    action: Int64,
    momentum: Int64,
}) {}

Game smartcontract stores the game state: coordinates of game items, score, win information

export class GameContext extends Struct({
    bricks: Bricks,
    nearestBricks: Provable.Array(Brick, NEAREST_BRICKS_NUM),
    totalLeft: UInt64,
    ball: Ball,
    platform: Platform,
    score: UInt64,
    winable: Bool,
    alreadyWon: Bool,
    debug: Bool,
})

Game state is changed based on user input during ticks. Game objects are identified by coorinates that are changed every tick based on velocities and collisions.

All game logic written using 01js. This allows the whole game process to be deterministic and provable. Sources of the game verification can be found here – GameContext.ts
Base competitions and leaderboard system can be found here – GameHub.ts

Coordinates

ZkNoid use field with size FIELD_WIDTH * FIELD_HEIGHT. Bottom left corner is placed to the zero point //#TODO Change coordinates upside down

Game entities

Ball

Has initial velocity directed upwards. Can collide bricks, borders and cart. Supports vertical and horisontal collisions. Collisions reverse corresponding axis ball speed. Radius equals to 1. Should be hit by user controlled cart otherwise game ends. Speed of the ball can be changed during game by hitting moving cart.

export class Ball extends Struct({
    position: IntPoint,
    speed: IntPoint,
})

Brick

Static object of the scene that can be destroyed by ball’s collision. Brick considers to be destroyed, if it health go to 1. Size: BRICK_SIZE x BRICK_SIZE. All the bricks should be destroyed by player to complete the level. Initially bricks are set pseudo-randomly using seed defined in the competition.

export class Brick extends Struct({
    pos: IntPoint,
    value: UInt64,
})

Cart

Object manipulated by user. Each tick user action is processed that moves cart or makes it stay still. Prevents ball from falling down. Has max speed - DEFAULT_PLATFORM_SPEED. And acceleration - ACCELERATION. Can bring momentum to ball.

export class Platform extends Struct({
    position: Int64,
})

Border

Static objects that bound game field. Left, top and right borders collision make the ball bounce. Bottom border collision means that user lost

Board collisions

Left border collision

Happens when ball’s x coordinate is less than 0.

In that case x coordinate is reset to -x and x velocity is reversed

Processing in smartcontract:

const leftBump = this.ball.position.x.isPositive().not();
 
// If bumf - just return it and change speed
this.ball.position.x = Provable.if(
    leftBump,
    this.ball.position.x.neg(),
    this.ball.position.x
);
 
...
 
this.ball.speed.x = Provable.if(
    leftBump.or(rightBump),
    this.ball.speed.x.neg(),
    this.ball.speed.x
);

Top border collision

Happens when ball’s y coordinate is less than 0.

In that case y coordinate is set to -y and y velocity is reversed.

Processing in smartcontract:

const topBump = this.ball.position.y.isPositive().not();
...
 
this.ball.position.y = Provable.if(
    topBump,
    this.ball.position.y.neg(),
    this.ball.position.y
);
 
this.ball.speed.y = Provable.if(
    topBump.or(bottomBump),
    this.ball.speed.y.neg(),
    this.ball.speed.y
);

Right border collision

Happens when ball’s x coordinate is greater than FIELD_WIDTH.

In that case x coordinate is reset to 2 * FIELD_WIDTH - x and x velocity is reversed.

Processing in smartcontract:

const rightBump = this.ball.position.x
    .sub(FIELD_PIXEL_WIDTH)
    .isPositive();
 
...
 
this.ball.position.x = Provable.if(
    rightBump,
    Int64.from(2 * FIELD_PIXEL_WIDTH).sub(this.ball.position.x),
    this.ball.position.x
);
 
this.ball.speed.x = Provable.if(
    leftBump.or(rightBump),
    this.ball.speed.x.neg(),
    this.ball.speed.x
);

Bottom border collision

Happens when ball’s y coordinate is more than FIELD_PIXEL_HEIGHT.

In this case we calculate true collision point(where ‘y’ = ‘0’). And checks, if ball hits cart or not. If hits - consider it as normal border collision. If not - user lost.

Processing in smartcontract:

const bottomBump = this.ball.position.y.sub(FIELD_PIXEL_HEIGHT).isPositive();
let platformLeftEndExtended = Provable.if(
    movedLeft,
    this.platform.position,
    prevPlatformPosition
);
let platformRightEndExtended = Provable.if(
    movedLeft,
    prevPlatformPosition.add(PLATFORM_WIDTH),
    this.platform.position.add(PLATFORM_WIDTH)
);
 
let adc0 = a.mul(FIELD_PIXEL_HEIGHT).sub(c);
let platformLeft = b.mul(platformLeftEndExtended);
let platformRight = b.mul(platformRightEndExtended);
 
let isFail = bottomBump.and(inRange(adc0, platformLeft, platformRight).not());
 
this.winable = this.winable.and(isFail.not());

Brick collisions

Brick collision

For collision to happen, two condition should met:

Brick should lie on ball trajectory
Ball should pass one of it border

For checking trajectory pass we use this equations

/*
    Detect where collision ocured
    ////////////// vertical part of a brick //////////////////////////
    y = d
    ay = bx + c;
    c = ay1 - bx1
        a - ball.speed.x
        b - ball.speed.y
    bx = ay - c
    bx = ad - c;
 
    x \incl [ brick.pos.x, brick.pos.x + 2 * BRICK_HALF_WIDTH ]
    bx \incl [b(brics.pos.x, b(brick.pos.x + 2 * BRICK_HALF_WIDTH))]
    ad - c \incl [b(brics.pos.x), b(brick.pos.x + 2 * BRICK_HALF_WIDTH))]
 
 
 
    /////////////// horizontal part of a brick ////////////////////////////
    x = d
    ay = bx + c
    c = ay1 - bx1
        a - ball.speed.x
        b - ball.speed.y
    ay = bd + c
 
    y \incl [ brick.pos.y, brick.pos.y + 2 * BRICK_HALF_WIDTH]
    ay \incl [ a(brick.pos.y), a(brick.pos.y + 2 * BRICK_HALF_WIDTH)]
    bd + c \incl [ a(brick.pos.y), a(brick.pos.y + 2 * BRICK_HALF_WIDTH)]
*/

Processing in smartcontract(example for right brick border):

const hasRightPass = inRange(rightBorder, prevBallPos.x, this.ball.position.x);
 
...
 
let d4 = rightBorder;
let bdc2 = b.mul(d4).add(c);
let crossBrickRight = inRange(bdc2, bottomEnd, topEnd);
let hasRightBump = crossBrickRight.and(hasRightPass);

After checking all borders collision, we should check for double collision, where ball cross both borders during tick. In such situation we should found out which border have been hitted first, and leave only this border collision.

hasRightBump = Provable.if(
    moveRight,
    hasRightBump.and(hasTopBump.not()).and(hasBottomBump.not()),
    hasRightBump
);
hasLeftBump = Provable.if(
    moveRight,
    hasLeftBump,
    hasLeftBump.and(hasTopBump.not()).and(hasBottomBump.not())
);
hasTopBump = Provable.if(
    moveTop,
    hasTopBump.and(hasRightBump.not()).and(hasLeftBump.not()),
    hasTopBump
);
hasBottomBump = Provable.if(
    moveTop,
    hasBottomBump,
    hasBottomBump.and(hasRightBump.not()).and(hasLeftBump.not())
);

Brick collision occurred if any border collision happened. In such case we reduce health of brick and change speed and position of ball(the same way we do it with playground border collision).

Nearest brick logic

All game logic had been written using o1js, which means, that it is converted to curcuit. In this case we cannot conditionaly checks collision only for some bricks. But if we check collision for all bricks - the size of the curcuit become enormous.

To mitigate this in game context we store also 2 nearest bricks. And check collision only for them. When collision happens - we update hitted brick in bricks array. This hugely reduce curcuit size and brings the oportunity to place many bricks on the field.

This how function to find nearestBricks looks like

updateNearestBricks(): void {
    this.nearestBricks = this.bricks.bricks.slice(0, NEAREST_BRICKS_NUM);
    let firstDist = this.distPow2ToBrick(this.bricks.bricks[0]);
    let secondDist = this.distPow2ToBrick(this.bricks.bricks[1]);
 
    // Chek order
    {
        let shouldSwap = gr(firstDist, secondDist);
        [firstDist, secondDist] = [
            Provable.if(shouldSwap, secondDist, firstDist),
            Provable.if(shouldSwap, firstDist, secondDist),
        ];
        [this.nearestBricks[0], this.nearestBricks[1]] = [
            Provable.if(
                shouldSwap,
                Brick,
                this.nearestBricks[1],
                this.nearestBricks[0]
            ) as Brick,
            Provable.if(
                shouldSwap,
                Brick,
                this.nearestBricks[0],
                this.nearestBricks[1]
            ) as Brick,
        ];
    }
 
    for (let i = 2; i < MAX_BRICKS; i++) {
        let cur = this.bricks.bricks[i];
        let curDist = this.distPow2ToBrick(cur);
        let secondGreater = gr(secondDist, curDist);
        let firstGreater = gr(firstDist, curDist);
 
        this.nearestBricks[1] = Provable.if(
            firstGreater,
            Brick,
            this.nearestBricks[0],
            Provable.if(secondGreater, Brick, cur, this.nearestBricks[1])
        ) as Brick;
 
        secondDist = Provable.if(
            firstGreater,
            secondDist,
            Provable.if(secondGreater, curDist, firstDist)
        );
 
        this.nearestBricks[0] = Provable.if(
            firstGreater,
            Brick,
            cur,
            this.nearestBricks[0]
        ) as Brick;
 
        firstDist = Provable.if(firstGreater, curDist, firstDist);
    }

We using position to find the brick, which value we should update

updateBrick(pos: IntPoint, value: UInt64): void {
    for (let i = 0; i < MAX_BRICKS; i++) {
        this.bricks.bricks[i].value = Provable.if(
            pos.equals(this.bricks.bricks[i].pos),
            value,
            this.bricks.bricks[i].value
        );
    }
}

Win conditions

For wining conditions we have two varibles:

alreadyWon - if true game is won no matter what happens next. (Default: false)
winnable - if true, alreadyWon still can be set to true. (Default: true)

When user destroys all bricks alreadyWon is setted to true in case of winnable === true. If ball hits the bottom border, winnable is setted to false. There can be situations, where alreadyWon == true, but ball hits the bottom and winnable becomes equal false. But alreadyWon still be equal to true.

Winnable update:

this.winable = this.winable.and(isFail.not());

AlreadyWon update:

this.alreadyWon = Provable.if(
    this.totalLeft.equals(UInt64.from(1)).and(this.winable),
    Bool(true),
    this.alreadyWon
);

Final check:

gameProcessProof.publicOutput.currentState.alreadyWon.assertTrue();

Recursion

o1js can operate only with fixed sized array. This limits game length to be constant sized. This leads to two main problem

Game cant last long enought
If we want to make game longer, we increase game length and it indluences on circuit lenght, so we also limited and can’t make game to be any length.

Solutuin for this it recursive proofs. Insted of having big proof, of full game session, we divide game session into smaller parts, and proof them one by one, to them combine them all together into full game proof.

In processTicks(listed below) we have as inputs previos proof, and ticks. We checks, that previosProof is valid and then continue to process state with new ticks.

export function processTicks(
    prevProof: SelfProof<void, GameProcessPublicOutput>,
    inputs: GameInputs
): GameProcessPublicOutput {
    prevProof.verify();
 
    let gameContext = prevProof.publicOutput.currentState;
    for (let i = 0; i < inputs.ticks.length; i++) {
        gameContext.processTick(inputs.ticks[i]);
    }
 
    return new GameProcessPublicOutput({
        initialState: prevProof.publicOutput.initialState,
        currentState: gameContext,
    });
}

Final game verification consist of 3 parts:

Checking map generation
Checking game process proof
Checking game win conditions

export function checkGameRecord(
    mapGenerationProof: MapGenerationProof,
    gameProcessProof: GameProcessProof
): GameRecordPublicOutput {
    // Verify map generation
    mapGenerationProof.verify();
 
    // Check if map generation output equal game process initial state
    mapGenerationProof.publicOutput
        .equals(gameProcessProof.publicOutput.initialState)
        .assertTrue();
 
    // Verify game process
    gameProcessProof.verify();
 
    // Check if game is won
    gameProcessProof.publicOutput.currentState.alreadyWon.assertTrue();
 
    // Get score
    return new GameRecordPublicOutput({
        score: gameProcessProof.publicOutput.currentState.score,
    });
}

L1 Lottery Randzu game