summary refs log tree commit diff stats
path: root/gamestate.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gamestate.cpp')
-rw-r--r--gamestate.cpp323
1 files changed, 245 insertions, 78 deletions
diff --git a/gamestate.cpp b/gamestate.cpp index f0de67a..3ff08c4 100644 --- a/gamestate.cpp +++ b/gamestate.cpp
@@ -6,17 +6,32 @@
6#include "titlestate.h" 6#include "titlestate.h"
7#include <fstream> 7#include <fstream>
8#include "hslist.h" 8#include "hslist.h"
9#include <set>
10#include <bitset>
11#include <tuple>
12#include <algorithm>
13#include <vector>
14#include <deque>
15#include <iostream>
16#include <sstream>
9 17
10class GameBoard { 18class GameBoard {
11 public: 19 public:
12 GameBoard(int level); 20 GameBoard(int level, int playerx, int playery);
13 void tick(int playerx, int playery); 21 void tick(int playerx, int playery);
14 void render(SDL_Renderer* renderer); 22 void render(SDL_Renderer* renderer, int level) const;
15 bool isObstructed(int x, int y); 23 bool isObstructed(int x, int y) const;
24 bool operator<(const GameBoard& other) const;
16 25
17 private: 26 private:
18 int level; 27 void initialize(int level);
19 bool blocks[WIDTH][HEIGHT]; 28 int solve(int playerx, int playery) const;
29 std::string dump() const;
30
31 std::bitset<WIDTH*HEIGHT> blocks;
32 std::bitset<WIDTH*HEIGHT> updateable;
33 int oldx;
34 int oldy;
20}; 35};
21 36
22class LoadGameState : public State { 37class LoadGameState : public State {
@@ -65,7 +80,7 @@ void setRendererDeadColor(SDL_Renderer* renderer, int level)
65 } 80 }
66} 81}
67 82
68void incrementIfNeighbor(int x, int y, bool temp[WIDTH][HEIGHT], int* tick, int playerx, int playery) 83void incrementIfNeighbor(int x, int y, std::bitset<WIDTH*HEIGHT>& temp, int* tick, int playerx, int playery)
69{ 84{
70 int nx = x; 85 int nx = x;
71 int ny = y; 86 int ny = y;
@@ -74,7 +89,7 @@ void incrementIfNeighbor(int x, int y, bool temp[WIDTH][HEIGHT], int* tick, int
74 89
75 if (!((nx!=x)&&(ny!=y))) 90 if (!((nx!=x)&&(ny!=y)))
76 { 91 {
77 if ((temp[x][y])||((playerx==x)&&(playery==y))||((x==15)&&(y==15))) 92 if ((temp[x+y*WIDTH])||((playerx==x)&&(playery==y))||((x==15)&&(y==15)))
78 { 93 {
79 ++*tick; 94 ++*tick;
80 } 95 }
@@ -128,11 +143,7 @@ State* LoadGameState::operator() (SDL_Window* window, SDL_Renderer* renderer)
128 SDL_RenderPresent(renderer); 143 SDL_RenderPresent(renderer);
129 144
130 // Do 50 gens of Conway 145 // Do 50 gens of Conway
131 GameBoard* board = new GameBoard(level); 146 GameBoard* board = new GameBoard(level, playerx, playery);
132 for (int i=0; i<50; i++)
133 {
134 board->tick(playerx, playery);
135 }
136 147
137 // Wait a bit 148 // Wait a bit
138 SDL_Delay(500); 149 SDL_Delay(500);
@@ -159,7 +170,7 @@ State* PlayGameState::operator() (SDL_Window* window, SDL_Renderer* renderer)
159 board->tick(playerx, playery); 170 board->tick(playerx, playery);
160 171
161 // Paint board 172 // Paint board
162 board->render(renderer); 173 board->render(renderer, level);
163 174
164 // Paint event 175 // Paint event
165 SDL_Rect block; 176 SDL_Rect block;
@@ -292,90 +303,103 @@ bool PlayGameState::move(int x, int y)
292 return false; 303 return false;
293} 304}
294 305
295GameBoard::GameBoard(int m_level) 306GameBoard::GameBoard(int level, int playerx, int playery)
296{ 307{
297 level = m_level; 308 for (;;)
298 309 {
299 for (int y=0; y<HEIGHT; y++) 310 initialize(level);
300 { 311 updateable.set();
301 for (int x=0; x<WIDTH; x++) 312 oldx = playerx;
302 { 313 oldy = playery;
303 blocks[x][y] = false; 314
304 315 for (int i=0; i<50; i++)
305 switch (level/10+1) 316 {
306 { 317 tick(playerx, playery);
307 case 1: 318 }
308 if ((x>13)&&(x<17)&&(y>13)&&(y<17)) 319
309 { 320 int states = solve(playerx, playery);
310 blocks[x][y] = rand() % 2; 321 if (states != 0)
311 } 322 {
312 break; 323 break;
313 case 2: 324 } else {
314 case 3: 325 std::cout << "Impossible board: " << playerx << "," << playery << "," << dump() << std::endl;
315 if ((x>12)&&(x<18)&&(y>12)&&(y<18)) 326 }
316 { 327 }
317 blocks[x][y] = rand() % 2;
318 }
319 break;
320 case 4:
321 case 5:
322 if ((x>11)&&(x<19)&&(y>11)&&(y<19))
323 {
324 blocks[x][y] = rand() % 2;
325 }
326 break;
327 default:
328 blocks[x][y] = rand() % 2;
329 }
330 }
331 }
332
333 blocks[15][15] = false;
334} 328}
335 329
336void GameBoard::tick(int playerx, int playery) 330void GameBoard::tick(int playerx, int playery)
337{ 331{
338 bool temp[WIDTH][HEIGHT]; 332 std::bitset<WIDTH*HEIGHT> temp {blocks};
339 int x,y; 333 std::bitset<WIDTH*HEIGHT> tempdateable {updateable};
340 for (x=0;x<WIDTH;x++) 334 if ((playerx != oldx) || (playery != oldy))
341 { 335 {
342 for (y=0;y<HEIGHT;y++) 336 for (int dy = -1; dy <= 1; dy++)
343 { 337 {
344 temp[x][y] = blocks[x][y]; 338 for (int dx = -1; dx <=1; dx++)
345 } 339 {
346 } 340 int tdx = oldx+dx;
341 int tdy = oldy+dy;
342 wrap(&tdx, &tdy);
343 tempdateable.set(tdx+tdy*WIDTH);
344
345 tdx = playerx+dx;
346 tdy = playery+dy;
347 wrap(&tdx, &tdy);
348 tempdateable.set(tdx+tdy*WIDTH);
349 }
350 }
351 }
352
353 oldx = playerx;
354 oldy = playery;
355
356 updateable.reset();
347 357
348 for (x=0;x<WIDTH;x++) 358 for (int y=0;y<HEIGHT;y++)
349 { 359 {
350 for (y=0;y<HEIGHT;y++) 360 for (int x=0;x<WIDTH;x++)
351 { 361 {
352 if ((x==15)&&(y==15)) 362 if (((x==15)&&(y==15)) || (!tempdateable[x+y*WIDTH]))
353 { 363 {
354 continue; 364 continue;
355 } 365 }
356 366
357 int neighbors = 0; 367 int neighbors = 0;
358 368
359 incrementIfNeighbor(x-1,y-1,temp,&neighbors, playerx, playery); 369 incrementIfNeighbor(x-1, y-1, temp, &neighbors, playerx, playery);
360 incrementIfNeighbor(x-1,y,temp,&neighbors, playerx, playery); 370 incrementIfNeighbor(x-1, y , temp, &neighbors, playerx, playery);
361 incrementIfNeighbor(x-1,y+1,temp,&neighbors, playerx, playery); 371 incrementIfNeighbor(x-1, y+1, temp, &neighbors, playerx, playery);
362 incrementIfNeighbor(x,y-1,temp,&neighbors, playerx, playery); 372 incrementIfNeighbor(x , y-1, temp, &neighbors, playerx, playery);
363 incrementIfNeighbor(x,y+1,temp,&neighbors, playerx, playery); 373 incrementIfNeighbor(x , y+1, temp, &neighbors, playerx, playery);
364 incrementIfNeighbor(x+1,y-1,temp,&neighbors, playerx, playery); 374 incrementIfNeighbor(x+1, y-1, temp, &neighbors, playerx, playery);
365 incrementIfNeighbor(x+1,y,temp,&neighbors, playerx, playery); 375 incrementIfNeighbor(x+1, y , temp, &neighbors, playerx, playery);
366 incrementIfNeighbor(x+1,y+1,temp,&neighbors, playerx, playery); 376 incrementIfNeighbor(x+1, y+1, temp, &neighbors, playerx, playery);
367 377
368 if (temp[x][y]) 378 if (temp[x+y*WIDTH])
369 { 379 {
370 blocks[x][y] = ((neighbors >= 1) && (neighbors <= 4)); 380 blocks[x+y*WIDTH] = ((neighbors >= 1) && (neighbors <= 4));
371 } else { 381 } else {
372 blocks[x][y] = (neighbors == 3); 382 blocks[x+y*WIDTH] = (neighbors == 3);
373 } 383 }
384
385 if (temp[x+y*WIDTH] != blocks[x+y*WIDTH])
386 {
387 for (int dy = -1; dy <= 1; dy++)
388 {
389 for (int dx = -1; dx <=1; dx++)
390 {
391 int tdx = x+dx;
392 int tdy = y+dy;
393 wrap(&tdx, &tdy);
394 updateable.set(tdx+tdy*WIDTH);
395 }
396 }
397 }
374 } 398 }
375 } 399 }
376} 400}
377 401
378void GameBoard::render(SDL_Renderer* renderer) 402void GameBoard::render(SDL_Renderer* renderer, int level) const
379{ 403{
380 SDL_Rect block; 404 SDL_Rect block;
381 block.w = 16; 405 block.w = 16;
@@ -388,7 +412,7 @@ void GameBoard::render(SDL_Renderer* renderer)
388 block.x = x*16; 412 block.x = x*16;
389 block.y = y*16; 413 block.y = y*16;
390 414
391 if (blocks[x][y]) 415 if (blocks[x+y*WIDTH])
392 { 416 {
393 setRendererAliveColor(renderer, level); 417 setRendererAliveColor(renderer, level);
394 } else { 418 } else {
@@ -400,7 +424,150 @@ void GameBoard::render(SDL_Renderer* renderer)
400 } 424 }
401} 425}
402 426
403bool GameBoard::isObstructed(int x, int y) 427bool GameBoard::isObstructed(int x, int y) const
428{
429 return blocks[x+y*WIDTH];
430}
431
432void GameBoard::initialize(int level)
433{
434 for (int y=0; y<HEIGHT; y++)
435 {
436 for (int x=0; x<WIDTH; x++)
437 {
438 blocks[x+y*WIDTH] = false;
439
440 switch (level/10+1)
441 {
442 case 1:
443 if ((x>13)&&(x<17)&&(y>13)&&(y<17))
444 {
445 blocks[x+y*WIDTH] = rand() % 2;
446 }
447 break;
448 case 2:
449 case 3:
450 if ((x>12)&&(x<18)&&(y>12)&&(y<18))
451 {
452 blocks[x+y*WIDTH] = rand() % 2;
453 }
454 break;
455 case 4:
456 case 5:
457 if ((x>11)&&(x<19)&&(y>11)&&(y<19))
458 {
459 blocks[x+y*WIDTH] = rand() % 2;
460 }
461 break;
462 default:
463 blocks[x+y*WIDTH] = rand() % 2;
464 }
465 }
466 }
467
468 blocks[15+15*WIDTH] = false;
469}
470
471bool GameBoard::operator<(const GameBoard& other) const
472{
473 for (int i = WIDTH*HEIGHT-1; i >= 0; i--)
474 {
475 if (blocks[i] ^ other.blocks[i])
476 {
477 return other.blocks[i];
478 }
479 }
480
481 return false;
482}
483
484int GameBoard::solve(int playerx, int playery) const
485{
486 std::deque<std::tuple<int, int, GameBoard, int>> search;
487 std::set<std::tuple<int, int, GameBoard>> done;
488 search.push_front(std::make_tuple(playerx, playery, *this, 0));
489
490 bool exists = false;
491 while (!search.empty())
492 {
493 auto cur = search.front();
494 search.pop_front();
495
496 int cpx = std::get<0>(cur);
497 int cpy = std::get<1>(cur);
498 GameBoard& cbr = 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
504 if (((cpx == 15) && ((cpy == 14) || (cpy == 16))) || ((cpy == 15) && ((cpx == 14) || (cpx == 16))))
505 {
506 exists = true;
507 break;
508 }
509
510 if (cns >= 100)
511 {
512 continue;
513 }
514
515 GameBoard immnext {cbr};
516 immnext.tick(cpx, cpy);
517 if (immnext.blocks != cbr.blocks)
518 {
519 if (done.count(std::make_tuple(cpx, cpy, immnext)) == 0)
520 {
521 search.push_front(std::make_tuple(cpx, cpy, immnext, cns));
522
523 continue;
524 }
525 }
526
527 std::vector<std::pair<int, int>> dirchanges {{cpx-1,cpy}, {cpx,cpy-1}, {cpx+1,cpy}, {cpx,cpy+1}};
528 std::sort(std::begin(dirchanges), std::end(dirchanges), [] (const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
529 int lhd = sqrt(pow(15 - lhs.first, 2.0) + pow(15 - lhs.second, 2.0));
530 int rhd = sqrt(pow(15 - rhs.first, 2.0) + pow(15 - rhs.second, 2.0));
531
532 return lhd > rhd;
533 });
534
535 for (auto& dirchange : dirchanges)
536 {
537 GameBoard next {cbr};
538 int npx = cpx + dirchange.first;
539 int npy = cpy + dirchange.second;
540 wrap(&npx, &npy);
541
542 if (!next.isObstructed(npx, npy))
543 {
544 next.tick(npx, npy);
545
546 if (done.count(std::make_tuple(npx, npy, next)) == 0)
547 {
548 search.push_front(std::make_tuple(npx, npy, next, cns+1));
549 }
550 }
551 }
552 }
553
554 if (exists)
555 {
556 return done.size();
557 } else {
558 return 0;
559 }
560}
561
562std::string GameBoard::dump() const
404{ 563{
405 return blocks[x][y]; 564 std::stringstream output;
565 output << std::hex;
566 for (int i=0; i<WIDTH*HEIGHT/4; i++)
567 {
568 int chunk = (8 * blocks[i*4]) + (4 * blocks[i*4+1]) + (2 * blocks[i*4+2]) + blocks[i*4+3];
569 output << chunk;
570 }
571
572 return output.str();
406} 573}