Frog Game

struct Coordinate { 
    x: int,
    y: int
}

struct Monster { 
    index: int
    coordinate: Coordinate
}

struct Item {
    index: int,
    coordinate: Coordinate
}

struct PlayerState { 
    index: int,
    coordinate: Coordinate
}

// UP   : y=1, x=0
// DOWN : y=1, x=0
// LEFT : y=1, x=0
// RIGHT: y=1, x=0
struct Move { 
    x: int
    y: int
}

// Terrain boundary coordinates
terrain_bounds = [Coordinate;400]


MONSTER_COUNT = 5
monsters = [Monster; MONSTER_COUNT]

ITEM_COUNT = 10
items = [Item; ITEM_COUNT]

p0_state = PlayerState {}
p1_state = PlayerState {}
p2_state = PlayerState {}
p3_state = PlayerState {}

fn outside_terrain(coordinate: Coordinate, terrain_bounds: [Coordinate;400]) -> bool: 
    '''
    Returns True if coordiante is in the terrain bounds, otherwise returns False
    
    Note: We can improve upon naively doing an equality check per coordinate in terrain 
    boundary if there's pattern in terrain boundary coordinates. Check ##Terrain boundaries
    '''
    flag = False
    for c in terrain_bounds:
        if c == coordinate:
            false = True
    return flag

fn apply_player_move(move: Move, player_state: PlayerState): 
    valid_move = True
    
    // New coordinates after move
    new_coord.x = player_state.coordinate.x + move.x
    new_coord.y = player_state.coordinate.y + move.y
    
    // If new coordinates are outside terrain, then invalidate the move
    valid_move = valid_move & !outside_terrain(new_coord, terrain_bounds)
    
    // If player attacked monster i by the move, then monsters_attacked[i] = True. 
    monsters_attacked = [0; MONSTER_COUNT]
    for (index, m) in enumerate(monsters):
        flag = new_coord == m.coordinate:
        monsters_attacked[index] = flag
        valid_move = valid_move & !flag
    
    // If the player picked item j in the move, then items_picked[j] = True
    items_picked = [0; ITEM_COUNT]
    for (index, it) in enumerate(items):
        flag = it.coordinate == new_coord
        items_picked[index] = flag
    
    // If valid_move, return new_coord else return curr_coord
    new_coord = MUX(new_coord, curr_coord, valid_move)
    
    player_state.coordinate = new_coord
        
    return (player_state, monsters_attacked, items_picked)

fn get_coord_view(coord: Coordinate):
    '''
    Returns two bit vectors monster_present and item_present.
    
    If monster `i` is at the coordinate, monster_present[i] = True.
    If item `j` is at the coordinate, item[j] = True.
    '''
    
    // Find monsters in the coordinate
    monster_present = [False; MONSTER_COUNT]
    for (index, m) in enumerate(monsters):
        flag = coord == m.coordinate:
        monster_present[index] = flag
    
    // Find items in the coordinate
    item_present = [False; ITEM_COUNT]
    for (index, m) in enumerate(items):
        flag = coord == m.coordinate:
        item_present[index] = flag
    
    return (monsters_present, items_present)

fn neighbouring_coords(coord: Coordinate) -> [Coordinate]:
    '''
    Given player is in coordinate `coord` returns list of adjacent coordinates visible to the player
    '''
    return [Coordinate]
    
fn get_player_view(player_coord: Coordinate, other_player_coords: [Coordinate;3]):
    neigh_coords = neighbouring_coords(player_coord)
    
    // find monsters and item in visible to the player
    (player_monster_view, player_item_view, other_player_in_view) = ([], [])
    for c in neigh_coords:
        (monsters_at_coord, items_at_coord) = get_coord_view(c)
        player_monster_view.push(monsters_at_coord)
        player_item_view.push(items_at_coord)
        
        others = [False; 3]
        for (index, other_c) in other_player_coords:
            others[index] = c == other_c
        other_player_in_view.push(others)
        
    return player_monster_view, player_item_view, other_player_in_view

fn global_state_transition(p0_move: Move, p1_move: Move, p2_move: Move, p3_move: Move): 
    
    // Apply player moves in parallel
    // apply_player_move returns 
    // (1) px_state: player's new state after move
    // (2) px_ma: bit vector indicating the monster, if any, it attacked in the move
    // (3) px_ip: bit vector indicating the item, if any, it picked in the move
    (p0_state, p0_ma, p0_ip) = apply_player_move(p0_move, p0_state)
    (p1_state, p1_ma, p1_ip) = apply_player_move(p1_move, p1_state)
    (p2_state, p2_ma, p2_ip) = apply_player_move(p2_move, p2_state)
    (p3_state, p3_ma, p3_ip) = apply_player_move(p3_move, p3_state)
    
    // Update public health of monsters and item availiblity
    // 
    // Players retrieve all px_ma, px_ip, decrypt them, and send values to the server.
    // 
    // Server updates the global public health and items availibility. Precedence rules must apply here.
    // For example, if P0 and P1 happen to move to same sqaure to pick an item then only P0 gets to keep it.
    //
    // What happens if P0 and P1 move to same sqaure to attack a monster? 
    // I propose to count both moves as valid and decrease monsters health twice.
    
    // Once global public state has been updated, it's time for players to retrieve their private views using get_player_view().
    

Above is quick description of how I view them game. There are few points to note:

  • If we avoid homomprhically retrieving terrain type, then no operation requires checking the entire map.
  • global_state_transition is called with player moves.
    • There are 3 parts in the function.
      1. Update player states: Update each player states based on their moves. There's no inter-dependency in state updates across players.
      2. Update global public state: Reflect, after (1), if some item has been picked up or some monster is dead. Requires players to decrypt outputs from (1)
      3. Players retrieve their private states
    • I realise we can club 2 & 3.
  • In the current model two players are permitted to be on same square.
  • Moving monsters:
    • There's a chance we can make moving monsters a thing because the moves can be processed in parallel. For example, if P0 attacks monster 0. The attack and monster 0s move can be processed in parallel. If the move is deadly for monster 0, then we don't display monster 0.
    • Is it ok to allow them to move outside terrain ?
  • I'm worried about moves. Check below.

Terrain boundaries

Is it possible to find certain bit patterns in coordinates and make terrain boundries based off that. This will reduce equality check to a few bit operations.

For example, following is a 8 x 8 map.

000000 000001 000010 000011 000100 000101 000110 000111

001000 001001 001010 001011 001100 001101 001110 001111

010000 010001 010010 010011 010100 010101 010110 010111

011000 011001 011010 011011 011100 011101 011110 011111

100000 100001 100010 100011 100100 100101 100110 100111

101000 101001 101010 101011 101100 101101 101110 101111

110000 110001 110010 110011 110100 110101 110110 110111

111000 111001 111010 111011 111100 111101 111110 111111

A very trivial terrain boundary could be the bottom row (ie coordinate (7,0) to (7,7)). Checking this requires to just check whether top 3 bits are 1.

Terrain Types

  • Can the terrain type be function of the coordinate ?

Moves

If we were to represent position on the map as x,y coordinates, then a natural way to represent moves will be via +/-1, +/-1.

For example, if current position is (34,45) and player wants to move right (0, +1). To make the move server will calculate (34, 45) + (0, +1) = (34, 46). Adding 1 bit is not that hard, it will atmost require 6 bootstrappings for carry overs (assume board is

26×26). But what happens when player wants to move left?

To move left (0, -1), server will calculate (34, 45) + (0, -1). 45 + (-1) in binary arithmetic is 101101 + 111111, which require a full 6 bit adder. A 6 bit adder should have a latency of 6 bootstrapping but will require ~4x6 bootstrappings.

This makes me wonder are there any alternative ways to represent moves & coordinates?


Benchmarks

  • collision finding with 128 collisions (32x32 board)
  • move update
  • define a function that defines a map, test