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.
- Update player states: Update each player states based on their moves. There's no inter-dependency in state updates across players.
- 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)
- 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.
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 ). 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