PROTO.md (10404B)
1 Catan 2 ------------------------------------------------------------------------------- 3 4 This protocol is based on the [Catan 5th ed. base game rules](catan-5ed-rules). 5 6 A rough description of the game, taken from the above rules, is as follows: 7 8 - Catan plays on a hexagonal grid, with each hex (tile) having an associated 9 resource and counter. The board's tiles and counter values are generated 10 randomly, and players get assigned 2 placed settlements and 2 placed roads, 11 and a set of resource cards as their starting hand. In addition to resources, 12 there are one or more desert tiles (on one of which the robber is initially 13 placed) which produce nothing. At the edge of the board are "coasts", and 14 at coast-tile intersections are placed harbours. 15 16 - On each player's turn, two dice are first rolled and each tile with the 17 matching counter value produces its associated resource for all players with 18 a settlement or city on one of the vertices of said tile. The current player 19 then enters their combined build/trade phase. 20 21 - Should a 7 be rolled, all players with more than 7 cards in hand discard 22 half of their hand (rounded down), and the current player moves the robber 23 to a new tile. After moving the robber, the current player chooses a target 24 player to steal from (from the set of players with settlements or cities 25 on the robber tile's vertices), and moves one random resource card from the 26 target player's hand into their own. 27 28 - During a player's turn, they may spend resources to build structures (roads 29 or settlements), upgrade a settlement into a city, buy a development card, 30 play a development card bought at least 1 turn ago, or offer a trade to the 31 bank or another player. 32 33 - Trades allow for a player to trade `n` of one resource for `m` of a different 34 type of resource, either in a `4:1` ratio (in the case a default bank trade), 35 a `3:1` ratio (in the case of a default harbour trade), a `2:1` ratio (in the 36 case of a specialty harbour trade), or an `n:m` ratio (in the case of a 37 player trade). 38 39 Catan: Protocol 40 =============================================================================== 41 42 This protocol is intended for use over a network, and is assumed to use a 43 byte-oriented stream transport protocol (such as TCP). The protocol message 44 description below is written in a C-like language, with the caveat that 45 anonymous unions describe conditional parts of a message (with the condition 46 noted by a comment), and that the `<stdint.h>` header for fixed-size types is 47 assumed to be included. 48 49 ```c 50 // NOTE: https://www.redblobgames.com/grids/hexagons/#coordinates-axial 51 struct tilepos { 52 int8_t q, r; 53 }; 54 55 // NOTE: https://www.redblobgames.com/grids/parts/#hexagon-relationships 56 enum edge : uint8_t { 57 W = 0, 58 NW = 1, 59 NE = 2, 60 }; 61 62 struct edgepos { 63 int8_t q, r; 64 enum edge e; 65 }; 66 67 // NOTE: https://www.redblobgames.com/grids/parts/#hexagon-relationships 68 enum vert : uint8_t { 69 N = 0, 70 S = 1, 71 }; 72 73 struct vertpos { 74 int8_t q, r; 75 enum vert v; 76 }; 77 78 enum resource : uint8_t { 79 ANY = 0, 80 BRICK = 1, 81 GRAIN = 2, 82 LUMBER = 3, 83 ORE = 4, 84 WOOL = 5, 85 }; 86 87 struct trade_offer { 88 enum resource resource; 89 uint8_t count; 90 }; 91 92 enum tile_type : uint8_t { 93 TILE_EMPTY = 0, 94 TILE_HILLS = BRICK, 95 TILE_FIELDS = GRAIN, 96 TILE_FOREST = LUMBER, 97 TILE_MOUNTAINS = ORE, 98 TILE_PASTURE = WOOL, 99 TILE_DESERT = 6, 100 }; 101 102 struct tile { 103 enum tile_type type; 104 uint8_t counter; 105 }; 106 107 enum buildable : uint8_t { 108 ROAD = 0, 109 SETTLEMENT = 1, 110 CITY = 2, 111 DEVELOPMENT_CARD = 3, 112 }; 113 114 enum devcard : uint8_t { 115 KNIGHT = 0, 116 ROAD_BUILDING = 1, 117 YEAR_OF_PLENTY = 2, 118 MONOPOLY = 3, 119 VICTORY_POINT = 4, 120 }; 121 122 enum msg_type : uint8_t { 123 MSG_BEGIN = 0, // gives game setup info 124 MSG_SETUP = 1, // sends initial board and agent states 125 MSG_KICK = 2, // removes a misbehaving agent from the game 126 MSG_END = 3, // gives the winner of the game 127 128 MSG_TURN = 10, // marks beginning of given agent's turn 129 MSG_ROLL = 11, // request a roll 130 MSG_ROLL_RESULT = 12, // public result of rolling a dice 131 MSG_PLAY = 13, // plays a development card 132 MSG_BUILD = 14, // builds a structure or development card 133 MSG_BUILD_RESULT = 15, // private result of building a structure or devcard 134 MSG_TRADE = 16, // requests a trade with a given agent 135 MSG_TRADE_ACCEPT = 17, // accepts a pending trade offer 136 MSG_TRADE_REJECT = 18, // rejects a pending trade offer 137 MSG_PASS = 19, // marks end of agent's turn 138 139 MSG_ROB = 20, // moves the robber to a new tile, and robs an agent 140 MSG_ROB_RESULT = 21, // public result of robbing a given agent 141 }; 142 143 struct msg_begin_tag { 144 uint32_t timeout_secs; 145 uint32_t thread_limit; 146 uint32_t memory_limit; // in MiB 147 uint8_t board_radius; // excluding central tile 148 uint8_t player_id; 149 150 uint32_t cell_count; 151 uint32_t harbour_count; 152 uint32_t player_count; 153 }; 154 155 struct msg_setup_tag { 156 struct { 157 struct tilepos pos; 158 struct tile tile; 159 } cells[begin.cell_count]; 160 161 struct { 162 struct vertpos vert1; 163 struct vertpos vert2; 164 enum resource resource; 165 uint8_t cost; 166 } harbours[begin.harbour_count]; 167 168 struct { 169 uint8_t id; 170 struct vertpos house1; 171 struct edgepos road1; 172 struct vertpos house2; 173 struct edgepos road2; 174 enum resource starting_hand[3]; 175 } players[begin.player_count]; 176 }; 177 178 struct msg_kick_tag { 179 uint8_t kick_id; 180 }; 181 182 struct msg_end_tag { 183 uint8_t winner_id; 184 }; 185 186 struct msg_turn_tag { 187 uint8_t player_id; 188 }; 189 190 struct msg_roll_tag {}; 191 192 struct msg_roll_result { 193 uint8_t roll; 194 }; 195 196 struct msg_play_tag { 197 uint8_t player_id; 198 enum devcard card; 199 }; 200 201 struct msg_build_tag { 202 uint8_t player_id; 203 enum buildable type; 204 union { 205 struct edgepos edgepos; // if type == ROAD 206 struct vertpos vertpos; // if type == SETTLEMENT || type == CITY 207 }; 208 }; 209 210 struct msg_build_result_tag { 211 enum buildable type; 212 union { 213 enum devcard card; // if type == DEVELOPMENT_CARD 214 }; 215 }; 216 217 struct msg_trade_tag { 218 uint8_t player_id; 219 uint8_t target_id; 220 struct trade_offer offer; 221 struct trade_offer ask; 222 }; 223 224 struct msg_trade_accept_tag { 225 uint8_t player_id; 226 uint8_t target_id; 227 }; 228 229 struct msg_trade_reject_tag { 230 uint8_t player_id; 231 uint8_t target_id; 232 }; 233 234 struct msg_pass_tag {}; 235 236 struct msg_rob_tag { 237 struct tilepos tilepos; 238 uint8_t target_id; 239 }; 240 241 struct msg_rob_result_tag { 242 uint8_t player_id; 243 uint8_t target_id; 244 enum resource card; 245 }; 246 247 union msg_tag { 248 struct msg_begin_tag begin; 249 struct msg_setup_tag setup; 250 struct msg_kick_tag kick; 251 struct msg_end_tag end; 252 253 struct msg_turn_tag turn; 254 struct msg_roll_tag roll; 255 struct msg_roll_result_tag roll_result; 256 struct msg_play_tag play; 257 struct msg_build_tag build; 258 struct msg_build_result_tag build_result; 259 struct msg_trade_tag trade; 260 struct msg_trade_accept_tag trade_accept; 261 struct msg_trade_reject_tag trade_reject; 262 struct msg_pass_tag pass; 263 264 struct msg_rob_tag rob; 265 struct msg_rob_result_tag rob_result; 266 }; 267 268 struct msg { 269 enum msg_type type; 270 union msg_tag tag; 271 }; 272 ``` 273 274 Catan: Protocol: Server Flow 275 =============================================================================== 276 277 The server finite state machine is roughly described below in pseudocode: 278 279 ```text 280 INIT: 281 generate board and agent state 282 GOTO ACCEPT 283 284 ACCEPT: 285 start all agent processes 286 accept all agent connections 287 GOTO BEGIN 288 289 BEGIN: 290 send `MSG_BEGIN` to all agents, assigning player ids from 0 to N 291 set `player_id` to id of last agent in agent turn order 292 GOTO TURN 293 294 TURN: 295 set `player_id` to next agent in agent turn order 296 send `MSG_TURN` to all agents 297 298 mark `agents[player_id]` as not having played a development card this turn 299 mark `agents[player_id]` as not having rolled this turn 300 while `agents[player_id]` has not timed out 301 if `agents[player_id]` has not rolled this turn 302 set `expected_messages` to { MSG_ROLL, MSG_PLAY } 303 else 304 set `expected_messages` to { MSG_PASS, MSG_PLAY, MSG_BUILD, MSG_TRADE } 305 306 receive a message `msg` from `agents[player_id]` 307 if `msg.type` not in `expected_messages` 308 set `kick_id` to `player_id` 309 GOTO KICK 310 311 if `msg.type == MSG_PASS` 312 GOTO PASS 313 else if `msg.type == MSG_ROLL` 314 mark `agents[player_id]` as having rolled this turn 315 generate a random dice roll between 2 and 12 316 update hand state for all agents 317 send `MSG_ROLL_RESULT` to all agents 318 if dice rolled a 7 319 receive a message `msg` from `agents[player_id]` 320 if `msg.type != MSG_ROB` 321 set `kick_id` to `player_id` 322 GOTO KICK 323 else 324 send `msg` to all other agents 325 move the robber to the tile at `msg.tilepos` 326 select a random resource from the hand of `agents[msg.target_id]` 327 send `MSG_ROB_RESULT` to `agents[player_id]` and `agents[msg.target_id]` 328 else if `msg.type == MSG_PLAY` 329 if `agents[player_id]` has already played a development card this turn 330 set `kick_id` to `player_id` 331 GOTO KICK 332 else 333 mark `agents[player_id]` as having played a development card this turn 334 play `msg.devcard` 335 send `msg` to all other agents 336 else if `msg.type == MSG_BUILD` 337 build structure or buy development card 338 send `msg` to all other agents 339 send `MSG_BUILD_RESULT` to `agents[player_id]` 340 else if `msg.type == MSG_TRADE` 341 send `msg` to all other agents 342 receive a message `response` from `agents[msg.target_id]` 343 if `response.type` not in { MSG_TRADE_ACCEPT, MSG_TRADE_REJECT } 344 set `kick_id` to `msg.target_id` 345 GOTO KICK 346 else 347 send `response` to all other agents 348 update hands of `agents[msg.player_id]` and `agents[msg.target_id]` 349 350 PASS: 351 if `agents[player_id]` has reached 10 victory points 352 GOTO END 353 else 354 GOTO TURN 355 356 KICK: 357 send `MSG_KICK` for `agents[kick_id]` to all other agents 358 close `agents[kick_id]` connection 359 GOTO TURN 360 361 END: 362 send `MSG_END` to all agents 363 GOTO DEINIT 364 365 DEINIT: 366 close all agent connections 367 ``` 368 369 Catan: References 370 =============================================================================== 371 [catan-5ed-rules]: https://www.catan.com/sites/default/files/2021-06/catan_base_rules_2020_200707.pdf