summary refs log tree commit diff stats
diff options
context:
space:
mode:
-rw-r--r--gamestate.cpp325
-rw-r--r--util.cpp18
-rw-r--r--util.h2
3 files changed, 260 insertions, 85 deletions
diff --git a/gamestate.cpp b/gamestate.cpp index 18e41c2..8c2df9c 100644 --- a/gamestate.cpp +++ b/gamestate.cpp
@@ -14,6 +14,9 @@
14#include <deque> 14#include <deque>
15#include <iostream> 15#include <iostream>
16#include <sstream> 16#include <sstream>
17#include <list>
18#include <unordered_map>
19#include <unordered_set>
17 20
18class GameBoard { 21class GameBoard {
19 public: 22 public:
@@ -23,13 +26,32 @@ class GameBoard {
23 bool isObstructed(int x, int y) const; 26 bool isObstructed(int x, int y) const;
24 bool operator<(const GameBoard& other) const; 27 bool operator<(const GameBoard& other) const;
25 28
29 using coord = std::tuple<int, int>;
30
26 private: 31 private:
27 void initialize(int level); 32 void initialize(int level);
28 int solve(int playerx, int playery) const; 33 bool solve(int playerx, int playery) const;
29 std::string dump() const; 34 std::string dump() const;
30 35
31 std::bitset<WIDTH*HEIGHT> blocks; 36 using board_type = std::bitset<WIDTH*HEIGHT>;
32 std::bitset<WIDTH*HEIGHT> updateable; 37
38 void incrementIfNeighbor(
39 int x,
40 int y,
41 const board_type& temp,
42 int playerx,
43 int playery,
44 int& tick) const;
45
46 bool applyNeighbors(
47 int x,
48 int y,
49 const board_type& temp,
50 int playerx,
51 int playery) const;
52
53 board_type blocks;
54 board_type updateable;
33 int oldx; 55 int oldx;
34 int oldy; 56 int oldy;
35}; 57};
@@ -80,18 +102,24 @@ void setRendererDeadColor(SDL_Renderer* renderer, int level)
80 } 102 }
81} 103}
82 104
83void incrementIfNeighbor(int x, int y, std::bitset<WIDTH*HEIGHT>& temp, int* tick, int playerx, int playery) 105void GameBoard::incrementIfNeighbor(
106 int x,
107 int y,
108 const board_type& temp,
109 int playerx,
110 int playery,
111 int& tick) const
84{ 112{
85 int nx = x; 113 int nx = x;
86 int ny = y; 114 int ny = y;
87 115
88 wrap(&x, &y); 116 wrap(x, y);
89 117
90 if (!((nx!=x)&&(ny!=y))) 118 if (!((nx!=x)&&(ny!=y)))
91 { 119 {
92 if ((temp[x+y*WIDTH])||((playerx==x)&&(playery==y))||((x==15)&&(y==15))) 120 if ((temp[x+y*WIDTH])||((playerx==x)&&(playery==y))||((x==15)&&(y==15)))
93 { 121 {
94 ++*tick; 122 ++tick;
95 } 123 }
96 } 124 }
97} 125}
@@ -285,7 +313,7 @@ State* PlayGameState::operator() (SDL_Window* window, SDL_Renderer* renderer)
285 313
286bool PlayGameState::move(int x, int y) 314bool PlayGameState::move(int x, int y)
287{ 315{
288 wrap(&x, &y); 316 wrap(x, y);
289 317
290 // Are we at the event? 318 // Are we at the event?
291 if ((x==15)&&(y==15)) 319 if ((x==15)&&(y==15))
@@ -317,8 +345,7 @@ GameBoard::GameBoard(int level, int playerx, int playery)
317 tick(playerx, playery); 345 tick(playerx, playery);
318 } 346 }
319 347
320 int states = solve(playerx, playery); 348 if (solve(playerx, playery))
321 if (states != 0)
322 { 349 {
323 break; 350 break;
324 } else { 351 } else {
@@ -329,8 +356,8 @@ GameBoard::GameBoard(int level, int playerx, int playery)
329 356
330void GameBoard::tick(int playerx, int playery) 357void GameBoard::tick(int playerx, int playery)
331{ 358{
332 std::bitset<WIDTH*HEIGHT> temp {blocks}; 359 board_type temp {blocks};
333 std::bitset<WIDTH*HEIGHT> tempdateable {updateable}; 360 board_type tempdateable {updateable};
334 if ((playerx != oldx) || (playery != oldy)) 361 if ((playerx != oldx) || (playery != oldy))
335 { 362 {
336 for (int dy = -1; dy <= 1; dy++) 363 for (int dy = -1; dy <= 1; dy++)
@@ -339,12 +366,12 @@ void GameBoard::tick(int playerx, int playery)
339 { 366 {
340 int tdx = oldx+dx; 367 int tdx = oldx+dx;
341 int tdy = oldy+dy; 368 int tdy = oldy+dy;
342 wrap(&tdx, &tdy); 369 wrap(tdx, tdy);
343 tempdateable.set(tdx+tdy*WIDTH); 370 tempdateable.set(tdx+tdy*WIDTH);
344 371
345 tdx = playerx+dx; 372 tdx = playerx+dx;
346 tdy = playery+dy; 373 tdy = playery+dy;
347 wrap(&tdx, &tdy); 374 wrap(tdx, tdy);
348 tempdateable.set(tdx+tdy*WIDTH); 375 tempdateable.set(tdx+tdy*WIDTH);
349 } 376 }
350 } 377 }
@@ -364,23 +391,7 @@ void GameBoard::tick(int playerx, int playery)
364 continue; 391 continue;
365 } 392 }
366 393
367 int neighbors = 0; 394 blocks[x+y*WIDTH] = applyNeighbors(x, y, temp, playerx, playery);
368
369 incrementIfNeighbor(x-1, y-1, temp, &neighbors, playerx, playery);
370 incrementIfNeighbor(x-1, y , temp, &neighbors, playerx, playery);
371 incrementIfNeighbor(x-1, y+1, temp, &neighbors, playerx, playery);
372 incrementIfNeighbor(x , y-1, temp, &neighbors, playerx, playery);
373 incrementIfNeighbor(x , y+1, temp, &neighbors, playerx, playery);
374 incrementIfNeighbor(x+1, y-1, temp, &neighbors, playerx, playery);
375 incrementIfNeighbor(x+1, y , temp, &neighbors, playerx, playery);
376 incrementIfNeighbor(x+1, y+1, temp, &neighbors, playerx, playery);
377
378 if (temp[x+y*WIDTH])
379 {
380 blocks[x+y*WIDTH] = ((neighbors >= 1) && (neighbors <= 4));
381 } else {
382 blocks[x+y*WIDTH] = (neighbors == 3);
383 }
384 395
385 if (temp[x+y*WIDTH] != blocks[x+y*WIDTH]) 396 if (temp[x+y*WIDTH] != blocks[x+y*WIDTH])
386 { 397 {
@@ -390,7 +401,7 @@ void GameBoard::tick(int playerx, int playery)
390 { 401 {
391 int tdx = x+dx; 402 int tdx = x+dx;
392 int tdy = y+dy; 403 int tdy = y+dy;
393 wrap(&tdx, &tdy); 404 wrap(tdx, tdy);
394 updateable.set(tdx+tdy*WIDTH); 405 updateable.set(tdx+tdy*WIDTH);
395 } 406 }
396 } 407 }
@@ -399,6 +410,32 @@ void GameBoard::tick(int playerx, int playery)
399 } 410 }
400} 411}
401 412
413bool GameBoard::applyNeighbors(
414 int x,
415 int y,
416 const board_type& temp,
417 int playerx,
418 int playery) const
419{
420 int neighbors = 0;
421
422 incrementIfNeighbor(x-1, y-1, temp, playerx, playery, neighbors);
423 incrementIfNeighbor(x-1, y , temp, playerx, playery, neighbors);
424 incrementIfNeighbor(x-1, y+1, temp, playerx, playery, neighbors);
425 incrementIfNeighbor(x , y-1, temp, playerx, playery, neighbors);
426 incrementIfNeighbor(x , y+1, temp, playerx, playery, neighbors);
427 incrementIfNeighbor(x+1, y-1, temp, playerx, playery, neighbors);
428 incrementIfNeighbor(x+1, y , temp, playerx, playery, neighbors);
429 incrementIfNeighbor(x+1, y+1, temp, playerx, playery, neighbors);
430
431 if (temp[x+y*WIDTH])
432 {
433 return ((neighbors >= 1) && (neighbors <= 4));
434 } else {
435 return (neighbors == 3);
436 }
437}
438
402void GameBoard::render(SDL_Renderer* renderer, int level) const 439void GameBoard::render(SDL_Renderer* renderer, int level) const
403{ 440{
404 SDL_Rect block; 441 SDL_Rect block;
@@ -426,7 +463,7 @@ void GameBoard::render(SDL_Renderer* renderer, int level) const
426 463
427bool GameBoard::isObstructed(int x, int y) const 464bool GameBoard::isObstructed(int x, int y) const
428{ 465{
429 return blocks[x+y*WIDTH]; 466 return blocks[x+y*WIDTH] || (x == 15 && y == 15);
430} 467}
431 468
432void GameBoard::initialize(int level) 469void GameBoard::initialize(int level)
@@ -481,82 +518,220 @@ bool GameBoard::operator<(const GameBoard& other) const
481 return false; 518 return false;
482} 519}
483 520
484int GameBoard::solve(int playerx, int playery) const 521bool GameBoard::solve(int playerx, int playery) const
485{ 522{
486 std::deque<std::tuple<int, int, GameBoard, int>> search; 523 std::deque<std::tuple<GameBoard, coord, int>> search;
487 std::set<std::tuple<int, int, GameBoard>> done; 524 std::unordered_map<board_type, board_type> done;
488 search.push_front(std::make_tuple(playerx, playery, *this, 0)); 525
526 // Assume that the player will not move while the board is changing, so tick
527 // the board until it either stops changing, or it reaches a state that it has
528 // already been in (in the case of alternating systems).
529 {
530 GameBoard original = *this;
531
532 std::unordered_set<board_type> pastStates;
533 pastStates.insert(original.blocks);
534
535 while (original.updateable.any())
536 {
537 original.tick(playerx, playery);
489 538
539 if (pastStates.count(original.blocks))
540 {
541 break;
542 }
543
544 pastStates.insert(original.blocks);
545 }
546
547 search.emplace_front(std::move(original), coord{playerx, playery}, 0);
548 }
549
550 // Use breadth first search to find a solution.
490 bool exists = false; 551 bool exists = false;
491 while (!search.empty()) 552 while (!search.empty())
492 { 553 {
493 auto cur = search.front(); 554 auto cur = std::move(search.front());
494 search.pop_front(); 555 search.pop_front();
495 556
496 int cpx = std::get<0>(cur); 557 GameBoard& cbr = std::get<0>(cur);
497 int cpy = std::get<1>(cur); 558 coord& cpl = std::get<1>(cur);
498 GameBoard& cbr = std::get<2>(cur); 559 int cns = std::get<2>(cur);
499 int cns = std::get<3>(cur);
500
501 auto cdn = std::make_tuple(cpx, cpy, cbr);
502 done.insert(cdn);
503 560
504 if (((cpx == 15) && ((cpy == 14) || (cpy == 16))) || ((cpy == 15) && ((cpx == 14) || (cpx == 16)))) 561 // If it has been over 100 generations, give up.
562 if (cns > 100)
505 { 563 {
506 exists = true; 564 continue;
507 break;
508 } 565 }
509 566
510 if (cns >= 100) 567 int cplx = std::get<0>(cpl);
568 int cply = std::get<1>(cpl);
569
570 // If this section of this board state has already been checked, skip it.
571 if (done.count(cbr.blocks) && done.at(cbr.blocks)[cplx+cply*WIDTH])
511 { 572 {
512 continue; 573 continue;
513 } 574 }
514 575
515 GameBoard immnext {cbr}; 576 // Use a flood fill to find a set of positions accessible to the player
516 immnext.tick(cpx, cpy); 577 // without modifying the board state, as well as a set of positions adjacent
517 if (immnext.blocks != cbr.blocks) 578 // to the flood that /will/ modify the board state.
579 board_type flood;
580 std::deque<coord> front;
581 front.push_front(cpl);
582 flood[cplx+cply*WIDTH] = true;
583
584 std::set<coord> edges;
585
586 while (!front.empty())
518 { 587 {
519 if (done.count(std::make_tuple(cpx, cpy, immnext)) == 0) 588 coord frontLoc = std::move(front.front());
589 front.pop_front();
590
591 // Iterate over the positions 4-adjacent to the current one.
592 for (coord& fc : std::list<coord>{
593 {std::get<0>(frontLoc) - 1, std::get<1>(frontLoc) },
594 {std::get<0>(frontLoc) + 1, std::get<1>(frontLoc) },
595 {std::get<0>(frontLoc) , std::get<1>(frontLoc) - 1},
596 {std::get<0>(frontLoc) , std::get<1>(frontLoc) + 1},
597 })
520 { 598 {
521 search.push_front(std::make_tuple(cpx, cpy, immnext, cns)); 599 wrap(std::get<0>(fc), std::get<1>(fc));
600 int fcx = std::get<0>(fc);
601 int fcy = std::get<1>(fc);
602
603 // If this position is already in the flood, skip it.
604 if (flood[fcx+fcy*WIDTH])
605 {
606 continue;
607 }
522 608
523 continue; 609 // If the player could not move into this position, skip it.
610 if (cbr.isObstructed(fcx, fcy))
611 {
612 continue;
613 }
614
615 // If this position is adjacent to the event, then the board is
616 // solvable.
617 if (((fcx == 15) && ((fcy == 14) || (fcy == 16))) ||
618 ((fcy == 15) && ((fcx == 14) || (fcx == 16))))
619 {
620 exists = true;
621 break;
622 }
623
624 // Check if the player moving would cause any positions 8-adjacent to
625 // the start or end positions to change. This is more efficient than
626 // copying the board state and then running tick.
627 bool changed = false;
628 for (int dy = -1; dy <= 1; dy++)
629 {
630 for (int dx = -1; dx <=1; dx++)
631 {
632 if (dx == 0 && dy == 0)
633 {
634 continue;
635 }
636
637 int cpldx = cplx + dx;
638 int cpldy = cply + dy;
639 wrap(cpldx, cpldy);
640
641 if (cbr.isObstructed(cpldx, cpldy) !=
642 applyNeighbors(
643 cpldx,
644 cpldy,
645 cbr.blocks,
646 fcx,
647 fcy))
648 {
649 changed = true;
650 break;
651 }
652
653 int fcxdx = fcx + dx;
654 int fcydy = fcy + dy;
655 wrap(fcxdx, fcydy);
656
657 if (cbr.isObstructed(fcxdx, fcydy) !=
658 applyNeighbors(
659 fcxdx,
660 fcydy,
661 cbr.blocks,
662 fcx,
663 fcy))
664 {
665 changed = true;
666 break;
667 }
668 }
669
670 if (changed)
671 {
672 break;
673 }
674 }
675
676 // If moving to this position would change the board state, add it to
677 // the set of edges; otherwise, add it to the flood and the flood front.
678 if (changed)
679 {
680 edges.insert(fc);
681 } else {
682 flood[fcx+fcy*WIDTH] = true;
683 front.push_back(fc);
684 }
685 }
686
687 if (exists)
688 {
689 break;
524 } 690 }
525 } 691 }
526 692
527 std::vector<std::pair<int, int>> dirchanges {{cpx-1,cpy}, {cpx,cpy-1}, {cpx+1,cpy}, {cpx,cpy+1}}; 693 if (exists)
528 std::sort(std::begin(dirchanges), std::end(dirchanges), [] (const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) { 694 {
529 int lhd = sqrt(pow(15 - lhs.first, 2.0) + pow(15 - lhs.second, 2.0)); 695 break;
530 int rhd = sqrt(pow(15 - rhs.first, 2.0) + pow(15 - rhs.second, 2.0)); 696 }
531 697
532 return lhd > rhd; 698 // Add the flood to the set of checked positions for this board state.
533 }); 699 done[cbr.blocks] |= flood;
534 700
535 for (auto& dirchange : dirchanges) 701 // Add the edges to the search queue.
702 for (const coord& newLoc : edges)
536 { 703 {
537 GameBoard next {cbr}; 704 GameBoard nextState1 = cbr;
538 int npx = cpx + dirchange.first; 705 nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));
539 int npy = cpy + dirchange.second;
540 wrap(&npx, &npy);
541 706
542 if (!next.isObstructed(npx, npy)) 707 // Assume that the player will not move while the board is changing, so
708 // tick the board until it either stops changing, or it reaches a state
709 // that it has already been in (in the case of alternating systems).
710 std::unordered_set<board_type> pastStates;
711 pastStates.insert(nextState1.blocks);
712
713 while (nextState1.updateable.any())
543 { 714 {
544 next.tick(npx, npy); 715 nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));
545 716
546 if (done.count(std::make_tuple(npx, npy, next)) == 0) 717 if (pastStates.count(nextState1.blocks))
547 { 718 {
548 search.push_front(std::make_tuple(npx, npy, next, cns+1)); 719 break;
549 } 720 }
721
722 pastStates.insert(nextState1.blocks);
723 }
724
725 if (!done.count(nextState1.blocks) ||
726 !done.at(nextState1.blocks)
727 [std::get<0>(newLoc) + std::get<1>(newLoc)*WIDTH])
728 {
729 search.emplace_back(std::move(nextState1), newLoc, cns+1);
550 } 730 }
551 } 731 }
552 } 732 }
553 733
554 if (exists) 734 return exists;
555 {
556 return done.size();
557 } else {
558 return 0;
559 }
560} 735}
561 736
562std::string GameBoard::dump() const 737std::string GameBoard::dump() const
diff --git a/util.cpp b/util.cpp index 5ccfe51..9fcdbbd 100644 --- a/util.cpp +++ b/util.cpp
@@ -2,22 +2,22 @@
2#include "mazeoflife.h" 2#include "mazeoflife.h"
3#include <iostream> 3#include <iostream>
4 4
5void wrap(int* x, int* y) 5void wrap(int& x, int& y)
6{ 6{
7 if (*x < 0) 7 if (x < 0)
8 { 8 {
9 *x = WIDTH-(0-*x); 9 x = WIDTH+x;
10 } else if (*x >= WIDTH) 10 } else if (x >= WIDTH)
11 { 11 {
12 *x = *x-WIDTH; 12 x = x-WIDTH;
13 } 13 }
14 14
15 if (*y < 0) 15 if (y < 0)
16 { 16 {
17 *y = HEIGHT-(0-*y); 17 y = HEIGHT+y;
18 } else if (*y >= HEIGHT) 18 } else if (y >= HEIGHT)
19 { 19 {
20 *y = *y-HEIGHT; 20 y = y-HEIGHT;
21 } 21 }
22} 22}
23 23
diff --git a/util.h b/util.h index 365a759..0e1fa2e 100644 --- a/util.h +++ b/util.h
@@ -5,7 +5,7 @@
5#ifndef UTIL_H 5#ifndef UTIL_H
6#define UTIL_H 6#define UTIL_H
7 7
8void wrap(int* x, int* y); 8void wrap(int& x, int& y);
9TTF_Font* loadFont(int size); 9TTF_Font* loadFont(int size);
10const char* getDataFile(); 10const char* getDataFile();
11SDL_Texture* loadImage(SDL_Renderer* renderer, std::string file); 11SDL_Texture* loadImage(SDL_Renderer* renderer, std::string file);