1/* 2 This file is part of GNOME 2048. 3 4 Copyright (C) 2014-2015 Juan R. García Blanco <juanrgar@gmail.com> 5 Copyright (C) 2016-2019 Arnaud Bonatti <arnaud.bonatti@gmail.com> 6 7 GNOME 2048 is free software: you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation, either version 3 of the License, or 10 (at your option) any later version. 11 12 GNOME 2048 is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GNOME 2048. If not, see <https://www.gnu.org/licenses/>. 19*/ 20 21private class Grid : Object 22{ 23 protected uint8 [,] _grid; 24 25 [CCode (notify = false)] public uint8 rows { internal get; protected construct; } 26 [CCode (notify = false)] public uint8 cols { internal get; protected construct; } 27 28 [CCode (notify = false)] internal uint target_value { internal get; internal set; default = 0; } 29 [CCode (notify = false)] internal uint target_value_simple { internal get; private set; default = 0; } 30 [CCode (notify = false)] internal bool target_value_reached { internal get; internal set; default = false; } 31 32 construct 33 { 34 if (rows < 1 || cols < 1) 35 assert_not_reached (); 36 37 _grid = new uint8 [rows, cols]; 38 _clear (ref _grid); 39 } 40 41 internal Grid (uint8 rows, uint8 cols) 42 { 43 Object (rows: rows, cols: cols); 44 } 45 46 /*\ 47 * * adding new tile 48 \*/ 49 50 internal void new_tile (out Tile tile) 51 { 52 if (_grid_is_full (ref _grid)) 53 assert_not_reached (); 54 55 GridPosition pos = { 0, 0 }; // TODO report bug: garbage init needed 56 do { _generate_random_position (rows, cols, out pos); } 57 while (_grid [pos.row, pos.col] != 0); 58 59 _grid [pos.row, pos.col] = 1; 60 tile = { pos, /* tile value */ 1 }; 61 } 62 63 private static inline void _generate_random_position (uint8 rows, uint8 cols, out GridPosition pos) 64 { 65 pos = { (int8) Random.int_range (0, (int32) rows), 66 (int8) Random.int_range (0, (int32) cols) }; 67 } 68 69 /*\ 70 * * moving 71 \*/ 72 73 internal inline void move (MoveRequest request, 74 ref Gee.LinkedList<TileMovement?> to_move, 75 ref Gee.LinkedList<TileMovement?> to_hide, 76 ref Gee.LinkedList<Tile?> to_show) 77 { 78 to_move.clear (); 79 to_hide.clear (); 80 to_show.clear (); 81 82 uint8 max_changed = 0; 83 switch (request) 84 { 85 case MoveRequest.DOWN: 86 _move_down ((int8) _cols, (int8) _rows, ref max_changed, ref _grid, ref to_move, ref to_hide, ref to_show); break; 87 case MoveRequest.UP: 88 _move_up ((int8) _cols, (int8) _rows, ref max_changed, ref _grid, ref to_move, ref to_hide, ref to_show); break; 89 case MoveRequest.LEFT: 90 _move_left ((int8) _cols, (int8) _rows, ref max_changed, ref _grid, ref to_move, ref to_hide, ref to_show); break; 91 case MoveRequest.RIGHT: 92 _move_right ((int8) _cols, (int8) _rows, ref max_changed, ref _grid, ref to_move, ref to_hide, ref to_show); break; 93 } 94 if (Math.pow (2, max_changed) >= target_value) 95 { 96 target_value_simple = max_changed; 97 target_value_reached = true; 98 } 99 } 100 101 private static void _move_down (int8 cols, 102 int8 rows, 103 ref uint8 max_changed, 104 ref uint8 [,] grid, 105 ref Gee.LinkedList<TileMovement?> to_move, 106 ref Gee.LinkedList<TileMovement?> to_hide, 107 ref Gee.LinkedList<Tile?> to_show) 108 { 109 for (int8 i = 0; i < cols; i++) 110 { 111 GridPosition free = { rows, i }; 112 113 for (int8 j = 0; j < rows; j++) 114 { 115 int8 row = rows - j - 1; 116 GridPosition cur = { row, i }; 117 uint8 val = grid [cur.row, cur.col]; 118 119 if (val == 0) 120 { 121 if (free.row == rows) 122 free.row = row; 123 continue; 124 } 125 126 // search for matches 127 GridPosition match = { 0, 0 }; 128 bool has_match = false; 129 for (int8 k = row - 1; k >= 0; k--) 130 { 131 uint8 k_val = grid [k, cur.col]; 132 133 if (k_val != 0) 134 { 135 if (k_val == val) 136 { 137 has_match = true; 138 match = { k, cur.col }; 139 } 140 break; 141 } 142 } 143 144 if (has_match) 145 { 146 if (free.row == rows) 147 free.row = row; // temporarily 148 149 _move_to_match (ref to_hide, ref to_show, ref cur, ref free, ref match, ref grid, ref val, ref max_changed); 150 free.row--; 151 } 152 else if (free.row != rows) 153 { 154 _move_to_end (ref to_move, ref cur, ref free, ref grid, ref val); 155 free.row--; 156 } 157 } 158 } 159 } 160 161 private static void _move_up (int8 cols, 162 int8 rows, 163 ref uint8 max_changed, 164 ref uint8 [,] grid, 165 ref Gee.LinkedList<TileMovement?> to_move, 166 ref Gee.LinkedList<TileMovement?> to_hide, 167 ref Gee.LinkedList<Tile?> to_show) 168 { 169 for (int8 i = 0; i < cols; i++) 170 { 171 GridPosition free = { -1, i }; 172 173 for (int8 j = 0; j < rows; j++) 174 { 175 int8 row = j; 176 GridPosition cur = { row, i }; 177 uint8 val = grid [cur.row, cur.col]; 178 179 if (val == 0) 180 { 181 if (free.row == -1) 182 free.row = row; 183 continue; 184 } 185 186 // search for matches 187 GridPosition match = { 0, 0 }; 188 bool has_match = false; 189 for (int8 k = row + 1; k < rows; k++) 190 { 191 uint8 k_val = grid [k, cur.col]; 192 193 if (k_val != 0) 194 { 195 if (k_val == val) 196 { 197 has_match = true; 198 match = { k, cur.col }; 199 } 200 break; 201 } 202 } 203 204 if (has_match) 205 { 206 if (free.row == -1) 207 free.row = row; // temporarily 208 209 _move_to_match (ref to_hide, ref to_show, ref cur, ref free, ref match, ref grid, ref val, ref max_changed); 210 free.row++; 211 } 212 else if (free.row != -1) 213 { 214 _move_to_end (ref to_move, ref cur, ref free, ref grid, ref val); 215 free.row++; 216 } 217 } 218 } 219 } 220 221 private static void _move_left (int8 cols, 222 int8 rows, 223 ref uint8 max_changed, 224 ref uint8 [,] grid, 225 ref Gee.LinkedList<TileMovement?> to_move, 226 ref Gee.LinkedList<TileMovement?> to_hide, 227 ref Gee.LinkedList<Tile?> to_show) 228 { 229 for (int8 i = 0; i < rows; i++) 230 { 231 GridPosition free = { i, -1 }; 232 233 for (int8 j = 0; j < cols; j++) 234 { 235 int8 col = j; 236 GridPosition cur = { i, col }; 237 uint8 val = grid [cur.row, cur.col]; 238 239 if (val == 0) 240 { 241 if (free.col == -1) 242 free.col = col; 243 continue; 244 } 245 246 // search for matches 247 GridPosition match = { 0, 0 }; 248 bool has_match = false; 249 for (int8 k = col + 1; k < cols; k++) 250 { 251 uint8 k_val = grid [cur.row, k]; 252 253 if (k_val != 0) 254 { 255 if (k_val == val) 256 { 257 has_match = true; 258 match = { cur.row, k }; 259 } 260 break; 261 } 262 } 263 264 if (has_match) 265 { 266 if (free.col == -1) 267 free.col = col; // temporarily 268 269 _move_to_match (ref to_hide, ref to_show, ref cur, ref free, ref match, ref grid, ref val, ref max_changed); 270 free.col++; 271 } 272 else if (free.col != -1) 273 { 274 _move_to_end (ref to_move, ref cur, ref free, ref grid, ref val); 275 free.col++; 276 } 277 } 278 } 279 } 280 281 private static void _move_right (int8 cols, 282 int8 rows, 283 ref uint8 max_changed, 284 ref uint8 [,] grid, 285 ref Gee.LinkedList<TileMovement?> to_move, 286 ref Gee.LinkedList<TileMovement?> to_hide, 287 ref Gee.LinkedList<Tile?> to_show) 288 { 289 for (int8 i = 0; i < rows; i++) 290 { 291 GridPosition free = { i, cols }; 292 293 for (int8 j = 0; j < cols; j++) 294 { 295 int8 col = cols - j - 1; 296 GridPosition cur = { i, col }; 297 uint8 val = grid [cur.row, cur.col]; 298 299 if (val == 0) 300 { 301 if (free.col == cols) 302 free.col = col; 303 continue; 304 } 305 306 // search for matches 307 GridPosition match = { 0, 0 }; 308 bool has_match = false; 309 for (int8 k = col - 1; k >= 0; k--) 310 { 311 uint8 k_val = grid [cur.row, k]; 312 313 if (k_val != 0) 314 { 315 if (k_val == val) 316 { 317 has_match = true; 318 match = { cur.row, k }; 319 } 320 break; 321 } 322 } 323 324 if (has_match) 325 { 326 if (free.col == cols) 327 free.col = col; // temporarily 328 329 _move_to_match (ref to_hide, ref to_show, ref cur, ref free, ref match, ref grid, ref val, ref max_changed); 330 free.col--; 331 } 332 else if (free.col != cols) 333 { 334 _move_to_end (ref to_move, ref cur, ref free, ref grid, ref val); 335 free.col--; 336 } 337 } 338 } 339 } 340 341 /*\ 342 * * move utilities 343 \*/ 344 345 private static void _move_to_match (ref Gee.LinkedList<TileMovement?> to_hide, 346 ref Gee.LinkedList<Tile?> to_show, 347 ref GridPosition cur, 348 ref GridPosition free, 349 ref GridPosition match, 350 ref uint8 [,] grid, 351 ref uint8 val, 352 ref uint8 max_changed) 353 { 354 debug (@"matching tile found at $match"); 355 356 TileMovement mov = { cur, free }; 357 to_hide.add (mov); 358 mov = { match, free }; 359 to_hide.add (mov); 360 361 val++; 362 Tile tile = { free, val }; 363 to_show.add (tile); 364 365 grid [cur.row, cur.col] = 0; 366 grid [match.row, match.col] = 0; 367 grid [free.row, free.col] = val; 368 if (max_changed < val) 369 max_changed = val; 370 } 371 372 private static void _move_to_end (ref Gee.LinkedList<TileMovement?> to_move, 373 ref GridPosition cur, 374 ref GridPosition free, 375 ref uint8 [,] grid, 376 ref uint8 val) 377 { 378 debug (@"moving $cur to $free"); 379 380 TileMovement mov = { cur, free }; 381 to_move.add (mov); 382 383 grid [cur.row, cur.col] = 0; 384 grid [free.row, free.col] = val; 385 } 386 387 /*\ 388 * * work on all the grid 389 \*/ 390 391 internal bool is_finished () 392 { 393 if (!_grid_is_full (ref _grid)) 394 return false; 395 396 for (uint8 i = 0; i < _rows; i++) 397 { 398 for (uint8 j = 0; j < _cols; j++) 399 { 400 uint8 val = _grid [i, j]; 401 402 if (i < (_rows - 1) && val == _grid [i + 1, j]) 403 return false; 404 405 if (j < (_cols - 1) && val == _grid [i, j + 1]) 406 return false; 407 } 408 } 409 410 return true; 411 } 412 413 protected static bool _grid_is_full (ref uint8 [,] grid) // is protected for tests 414 { 415 uint rows = grid.length [0]; 416 uint cols = grid.length [1]; 417 418 for (uint i = 0; i < rows; i++) 419 for (uint j = 0; j < cols; j++) 420 if (grid [i, j] == 0) 421 return false; 422 return true; 423 } 424 425 internal void clear () 426 { 427 _clear (ref _grid); 428 } 429 private static void _clear (ref uint8 [,] grid) 430 { 431 uint rows = grid.length [0]; 432 uint cols = grid.length [1]; 433 434 for (uint i = 0; i < rows; i++) 435 for (uint j = 0; j < cols; j++) 436 grid [i, j] = 0; 437 } 438 439 internal long get_score () 440 { 441 return _get_score (ref _grid); 442 } 443 private static long _get_score (ref uint8 [,] grid) 444 { 445 long score = 0; 446 447 uint rows = grid.length [0]; 448 uint cols = grid.length [1]; 449 450 for (uint i = 0; i < rows; i++) 451 for (uint j = 0; j < cols; j++) 452 score += _calculate_score_value (grid [i, j]); 453 return score; 454 } 455 private static inline long _calculate_score_value (uint8 tile_value) 456 { 457 if (tile_value < 2) 458 return 0; 459 return (long) (Math.pow (2, tile_value) * (tile_value - 1)); 460 } 461 462 /*\ 463 * * getting values 464 \*/ 465 466 internal Grid clone () 467 { 468 Grid grid = new Grid (_rows, _cols); 469 grid._grid = _grid; 470 grid._target_value = _target_value; 471 grid._target_value_reached = _target_value_reached; 472 473 return grid; 474 } 475 476 internal new uint8 get (uint8 row, uint8 col) // allows calling "uint8 val = _grid [i, j];" in game.vala 477 { 478 if ((row >= _rows) || (col >= _cols)) 479 return 0; 480 481 return _grid [row, col]; 482 } 483 484 internal static bool is_disallowed_grid_size (ref uint8 rows, ref uint8 cols) 485 requires (rows >= 1) 486 requires (rows <= 9) 487 requires (cols >= 1) 488 requires (cols <= 9) 489 { 490 return (rows == 1 && cols == 1) || (rows == 1 && cols == 2) || (rows == 2 && cols == 1); 491 } 492 493 /*\ 494 * * saving 495 \*/ 496 497 internal string save () // internal for tests 498 { 499 string ret_string = @"$_rows $_cols\n"; 500 _convert_to_string (ref _grid, ref ret_string); 501 ret_string += _get_score (ref _grid).to_string (); // historical, not 502 ret_string += "\n"; // used when loading 503 return ret_string; 504 } 505 506 internal string to_string () // for debug, in @"$_grid" strings 507 { 508 string ret_string = "\n"; 509 _convert_to_string (ref _grid, ref ret_string); 510 return ret_string; 511 } 512 513 private static void _convert_to_string (ref uint8 [,] grid, ref string ret_string) 514 { 515 uint rows = grid.length [0]; 516 uint cols = grid.length [1]; 517 518 for (uint i = 0; i < rows; i++) 519 { 520 for (uint j = 0; j < cols; j++) 521 { 522 uint64 val; 523 if (grid [i, j] == 0) 524 val = 0; 525 else 526 val = (uint64) Math.pow (2, grid [i, j]); 527 ret_string += "%llu%s".printf (val, (j == (cols - 1)) ? "\n" : " "); 528 } 529 } 530 } 531 532 /*\ 533 * * restoring 534 \*/ 535 536 internal bool load (ref string content) // TODO transform into a constructor // internal for tests 537 { 538 uint8 [,] grid = {{}}; // garbage 539 if (!_load_from_string (ref content, ref grid)) 540 return false; 541 542 _rows = (uint8) grid.length [0]; 543 _cols = (uint8) grid.length [1]; 544 _grid = grid; 545 return true; 546 } 547 548 private static bool _load_from_string (ref string content, 549 ref uint8 [,] grid) 550 { 551 string [] lines = content.split ("\n"); 552 553 // check that at least it contains 3 rows: size, content, score 554 if (lines.length < 4) 555 return false; 556 557 string [] tokens = lines [0].split (" "); 558 if (tokens.length != 2) 559 return false; 560 561 uint64 number_64; 562 // rows 563 if (!uint64.try_parse (tokens [0], out number_64)) 564 return false; 565 if ((number_64 == 0) || (number_64 > 9)) 566 return false; 567 uint8 rows = (uint8) number_64; 568 // cols 569 if (!uint64.try_parse (tokens [1], out number_64)) 570 return false; 571 if ((number_64 == 0) || (number_64 > 9)) 572 return false; 573 uint8 cols = (uint8) number_64; 574 575 if (is_disallowed_grid_size (ref rows, ref cols)) 576 return false; 577 // number of rows + 1 for size + 1 for score; maybe an empty line at end 578 if (lines.length < rows + 2) 579 return false; 580 581 grid = new uint8 [rows, cols]; 582 583 for (uint8 i = 0; i < rows; i++) 584 { 585 _parse_line (lines [i + 1], out tokens); 586 // we do need to be strict here 587 if (tokens.length != cols) 588 return false; 589 590 for (uint8 j = 0; j < cols; j++) 591 { 592 if (!uint64.try_parse (tokens [j], out number_64)) 593 return false; 594 uint8 number; 595 if (!_convert_tile_number (ref number_64, out number)) 596 return false; 597 grid [i, j] = number; 598 } 599 } 600 601 return true; 602 } 603 604 private static inline void _parse_line (string line, out string [] tokens) 605 { 606 tokens = line.split (" "); 607 string [] _tokens = {}; 608 foreach (string token in tokens) 609 if (token != "") 610 _tokens += token; 611 tokens = _tokens; 612 } 613 614 private static inline bool _convert_tile_number (ref uint64 number_64, 615 out uint8 number) 616 { 617 if (number_64 == 0) 618 { 619 number = 0; 620 return true; 621 } 622 for (number = 1; number <= 81; number++) 623 if (number_64 == (uint64) Math.pow (2, number)) 624 return true; 625 626 return false; 627 } 628 629 /*\ 630 * * saving and restoring from file 631 \*/ 632 633 internal void save_game (string path) 634 { 635 string contents = save (); 636 try 637 { 638 DirUtils.create_with_parents (Path.get_dirname (path), 0775); 639 FileUtils.set_contents (path, contents); 640 debug ("game saved successfully"); 641 } 642 catch (FileError e) { 643 warning ("Failed to save game: %s", e.message); 644 } 645 } 646 647 internal bool restore_game (string path) 648 { 649 string content; 650 651 try { FileUtils.get_contents (path, out content); } 652 catch (FileError e) { return false; } 653 654 if (load (ref content)) 655 return true; 656 657 warning ("Failed to restore game from saved file"); 658 return false; 659 } 660} 661 662private struct GridPosition 663{ 664 public int8 row; 665 public int8 col; 666 667 internal string to_string () 668 { 669 return @"($row,$col)"; 670 } 671} 672 673private struct TileMovement 674{ 675 public GridPosition from; 676 public GridPosition to; 677} 678 679private struct Tile 680{ 681 public GridPosition pos; 682 public uint8 val; 683} 684 685private enum MoveRequest { 686 UP, 687 RIGHT, 688 DOWN, 689 LEFT; 690 691 internal static string debug_string (MoveRequest request) 692 { 693 switch (request) 694 { 695 case UP: return "move up"; 696 case RIGHT: return "move right"; 697 case DOWN: return "move down"; 698 case LEFT: return "move left"; 699 default: assert_not_reached (); 700 } 701 } 702} 703