lunaix-os/usr/maze.c

   1 #include <errno.h>
   2 #include <fcntl.h>
   3 #include <sys/lunaix.h>
   4 #include <stdio.h>
   5 #include <string.h>
   6 #include <unistd.h>
   7 #include <termios.h>
   8
   9 #define check(statement)                                                       \
  10     ({                                                                         \
  11         int err = 0;                                                           \
  12         if ((err = (statement)) < 0) {                                         \
  13             syslog(2, #statement " failed: %d", err);                          \
  14             _exit(1);                                                          \
  15         }                                                                      \
  16         err;                                                                   \
  17     })
  18
  19
  20 #define TTY_WIDTH 80
  21 #define TTY_HEIGHT 25
  22
  23 #define MAZE_WIDTH TTY_WIDTH-1
  24 #define MAZE_HEIGHT TTY_HEIGHT
  25
  26 #define BUFFER_SIZE 1024
  27
  28 #define WALL '#'
  29 #define ROAD ' '
  30 #define PLAYER 'P'
  31 #define FLAG 'F'
  32 #define CUE '.'
  33
  34 #define VISITED 1
  35
  36 #define UP 0
  37 #define RIGHT 1
  38 #define DOWN 2
  39 #define LEFT 3
  40
  41 int rand_fd;
  42 int fd;
  43
  44 void get_rand(unsigned int *r, unsigned int max) {
  45     if (max==0)
  46     {
  47         *r = 0;
  48         return;
  49     }
  50     read(rand_fd, r, 4);
  51     *r = (*r)%max;
  52 }
  53
  54 typedef struct player_t {
  55     int x;
  56     int y;
  57 }player_t;
  58
  59 typedef struct write_cmd {
  60     int x;
  61     int y;
  62     char data[MAZE_WIDTH+1];
  63 }write_cmd;
  64
  65 typedef struct node_t {
  66     int x;
  67     int y;
  68 }node_t;
  69
  70 typedef struct stack_t {
  71     node_t node[1000];
  72     unsigned int length;
  73 }road_list_t, cue_list_t;
  74
  75 road_list_t road_list;
  76 cue_list_t cue_list;
  77
  78 void init_list() {
  79     for (size_t i = 0; i < 1000; i++)
  80     {
  81         road_list.node[i].x = 0;
  82         road_list.node[i].y = 0;
  83     }
  84     road_list.length = 0;
  85
  86     for (size_t i = 0; i < 1000; i++)
  87     {
  88         cue_list.node[i].x = 0;
  89         cue_list.node[i].y = 0;
  90     }
  91     cue_list.length = 0;
  92 }
  93
  94 int insert_road_list(node_t n) {
  95     if (road_list.length>=1000)
  96     {
  97         return 0;
  98     }
  99
 100     unsigned int r = 0;
 101     get_rand(&r, road_list.length);
 102     for (size_t i = road_list.length; i > r; i--)
 103     {
 104         road_list.node[i] = road_list.node[i-1];
 105     }
 106     road_list.node[r] = n;
 107     road_list.length+=1;
 108     return 1;
 109 }
 110
 111 int push_road_list(node_t node) {
 112     if (road_list.length>=1000)
 113     {
 114         return 0;
 115     }
 116     road_list.node[road_list.length] = node;
 117     road_list.length+=1;
 118     return 1;
 119 }
 120
 121 node_t pop_road_list() {
 122     node_t n={.x = 0, .y = 0};
 123     if (road_list.length==0)
 124     {
 125         return n;
 126     }
 127     n = road_list.node[road_list.length-1];
 128     road_list.node[road_list.length-1].x = 0;
 129     road_list.node[road_list.length-1].y = 0;
 130     road_list.length-=1;
 131     return n;
 132 }
 133
 134 int push_cue_list(node_t node) {
 135     if (cue_list.length>=1000)
 136     {
 137         return 0;
 138     }
 139     cue_list.node[cue_list.length] = node;
 140     cue_list.length+=1;
 141     return 1;
 142 }
 143
 144 node_t pop_cue_list() {
 145     node_t n={.x = 0, .y = 0};
 146     if (cue_list.length==0)
 147     {
 148         return n;
 149     }
 150     n = cue_list.node[cue_list.length-1];
 151     cue_list.node[cue_list.length-1].x = 0;
 152     cue_list.node[cue_list.length-1].y = 0;
 153     cue_list.length-=1;
 154     return n;
 155 }
 156
 157 int iswall(node_t n) {
 158     if (n.x<0 || n.y<0)
 159     {
 160         return 0;
 161     }
 162
 163     return n.x%2==0 || n.y%2==0;
 164 }
 165
 166 // is road position
 167 // no matter it is marked as '-'
 168 int isroad(node_t n) {
 169     if (n.x<=0 || n.y<=0 || n.x>=MAZE_WIDTH-1 || n.y>=MAZE_HEIGHT-1)
 170     {
 171         return 0;
 172     }
 173
 174     return !iswall(n);
 175 }
 176
 177
 178 void generate_rand_road_node(node_t *n)
 179 {
 180     get_rand((unsigned int *)&n->x, MAZE_WIDTH);
 181     get_rand((unsigned int *)&n->y, MAZE_HEIGHT);
 182     if (isroad(*n))
 183     {
 184         return;
 185     }
 186
 187     if (n->x%2==0)
 188     {
 189         if (n->x<=(MAZE_WIDTH/2))
 190         {
 191             n->x+=1;
 192         }
 193         else
 194         {
 195             n->x-=1;
 196         }
 197     }
 198
 199     if (n->y%2==0)
 200     {
 201         if (n->y<=(MAZE_HEIGHT/2))
 202         {
 203             n->y+=1;
 204         }
 205         else
 206         {
 207             n->y-=1;
 208         }
 209     }
 210 }
 211
 212 char maze[MAZE_HEIGHT][MAZE_WIDTH];
 213 char visited[MAZE_HEIGHT][MAZE_WIDTH];
 214
 215 void pick_near_road_to_list(node_t current_node) {
 216     node_t picked_node;
 217
 218     //UP
 219     picked_node.x = current_node.x;
 220     picked_node.y = current_node.y-2;
 221     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
 222     {
 223         insert_road_list(picked_node);
 224     }
 225
 226     //RIGHT
 227     picked_node.x = current_node.x+2;
 228     picked_node.y = current_node.y;
 229     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
 230     {
 231         insert_road_list(picked_node);
 232     }
 233
 234     //DOWN
 235     picked_node.x = current_node.x;
 236     picked_node.y = current_node.y+2;
 237     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
 238     {
 239         insert_road_list(picked_node);
 240     }
 241
 242     //LEFT
 243     picked_node.x = current_node.x-2;
 244     picked_node.y = current_node.y;
 245     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
 246     {
 247         insert_road_list(picked_node);
 248     }
 249 }
 250
 251 node_t pick_near_road(node_t current_node) {
 252     node_t picked_node;
 253
 254     //UP
 255     picked_node.x = current_node.x;
 256     picked_node.y = current_node.y-2;
 257     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
 258     {
 259         return picked_node;
 260     }
 261
 262     //LEFT
 263     picked_node.x = current_node.x-2;
 264     picked_node.y = current_node.y;
 265     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
 266     {
 267         return picked_node;
 268     }
 269
 270     //DOWN
 271     picked_node.x = current_node.x;
 272     picked_node.y = current_node.y+2;
 273     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
 274     {
 275         return picked_node;
 276     }
 277
 278     //RIGHT
 279     picked_node.x = current_node.x+2;
 280     picked_node.y = current_node.y;
 281     if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
 282     {
 283         return picked_node;
 284     }
 285
 286     return picked_node;
 287 }
 288
 289
 290 void break_wall(node_t n1, node_t n2)
 291 {
 292     if (n1.x==n2.x)
 293     {
 294         maze[(n1.y+n2.y+1)/2][n1.x]=ROAD;
 295     }
 296     else if(n1.y==n2.y)
 297     {
 298         maze[n1.y][(n1.x+n2.x+1)/2]=ROAD;
 299     }
 300 }
 301
 302 void print_maze(){
 303     write_cmd wcmd;
 304     wcmd.x = 0;
 305     wcmd.data[MAZE_WIDTH] = '\0';
 306
 307     for (size_t j = 0; j < MAZE_HEIGHT; j++)
 308     {
 309         for (size_t i = 0; i < MAZE_WIDTH; i++)
 310         {
 311             wcmd.data[i] = maze[j][i];
 312         }
 313         wcmd.y = j;
 314         write(fd, &wcmd, sizeof(write_cmd));
 315     }
 316 }
 317
 318 void refresh_line(int y){
 319     write_cmd wcmd;
 320     wcmd.x = 0;
 321     wcmd.y = y;
 322     wcmd.data[MAZE_WIDTH] = '\0';
 323
 324     for (size_t i = 0; i < MAZE_WIDTH; i++)
 325     {
 326         wcmd.data[i] = maze[y][i];
 327     }
 328
 329     write(fd, &wcmd, sizeof(write_cmd));
 330 }
 331
 332 // Prim algorithm
 333 void generate_maze()
 334 {
 335     node_t start_node;
 336
 337     for (size_t i = 0; i < MAZE_HEIGHT; i++)
 338     {
 339         for (size_t j = 0; j < MAZE_WIDTH; j++)
 340         {
 341             maze[i][j] = WALL;
 342         }
 343     }
 344
 345     rand_fd = open("/dev/rand", O_RDONLY);
 346
 347     generate_rand_road_node(&start_node);
 348
 349     maze[start_node.y][start_node.x] = ROAD;
 350
 351     pick_near_road_to_list(start_node);
 352
 353     while (road_list.length>0)
 354     {
 355         node_t n = pop_road_list();
 356         maze[n.y][n.x] = ROAD;
 357         node_t n2 = pick_near_road(n);
 358         maze[n2.y][n2.x] = ROAD;
 359         break_wall(n, n2);
 360         pick_near_road_to_list(n);
 361         print_maze();
 362     }
 363
 364     maze[1][1] = PLAYER;
 365     maze[MAZE_HEIGHT-2][MAZE_WIDTH-2] = FLAG;
 366     refresh_line(1);
 367     refresh_line(MAZE_HEIGHT-2);
 368 }
 369
 370
 371 int
 372 set_termios(int fd) {
 373     struct termios term;
 374
 375     check(tcgetattr(fd, &term));
 376
 377     term.c_lflag = IEXTEN | ISIG | ECHO | ECHOE | ECHONL;
 378     term.c_cc[VERASE] = 0x7f;
 379
 380     check(tcsetattr(fd, 0, &term));
 381
 382     return 0;
 383 }
 384
 385 int
 386 set_termios_end(int fd) {
 387     struct termios term;
 388
 389     check(tcgetattr(fd, &term));
 390
 391     term.c_lflag = ICANON | IEXTEN | ISIG | ECHO | ECHOE | ECHONL;
 392     term.c_cc[VERASE] = 0x7f;
 393
 394     check(tcsetattr(fd, 0, &term));
 395
 396     return 0;
 397 }
 398
 399 node_t player;
 400
 401 void up(){
 402     if (maze[player.y-1][player.x]!='#')
 403     {
 404         player.y-=1;
 405         maze[player.y][player.x] = 'P';
 406         maze[player.y+1][player.x] = ' ';
 407     }
 408     refresh_line(player.y);
 409     refresh_line(player.y+1);
 410 }
 411
 412 void right(){
 413     if (maze[player.y][player.x+1]!='#')
 414     {
 415         player.x+=1;
 416         maze[player.y][player.x] = 'P';
 417         maze[player.y][player.x-1] = ' ';
 418     }
 419     refresh_line(player.y);
 420 }
 421
 422 void down(){
 423     if (maze[player.y+1][player.x]!='#')
 424     {
 425         player.y+=1;
 426         maze[player.y][player.x] = 'P';
 427         maze[player.y-1][player.x] = ' ';
 428     }
 429     refresh_line(player.y);
 430     refresh_line(player.y-1);
 431 }
 432
 433 void left(){
 434     if (maze[player.y][player.x-1]!='#')
 435     {
 436         player.x-=1;
 437         maze[player.y][player.x] = 'P';
 438         maze[player.y][player.x+1] = ' ';
 439     }
 440     refresh_line(player.y);
 441 }
 442
 443 void visit_node(node_t current_node){
 444     node_t picked_node;
 445
 446     //UP
 447     picked_node.x = current_node.x;
 448     picked_node.y = current_node.y-1;
 449     if (maze[picked_node.y][picked_node.x]!=PLAYER && maze[picked_node.y][picked_node.x]!=WALL && visited[picked_node.y][picked_node.x]!=VISITED)
 450     {
 451         push_road_list(picked_node);
 452     }
 453
 454     //RIGHT
 455     picked_node.x = current_node.x+1;
 456     picked_node.y = current_node.y;
 457     if (maze[picked_node.y][picked_node.x]!=PLAYER && maze[picked_node.y][picked_node.x]!=WALL && visited[picked_node.y][picked_node.x]!=VISITED)
 458     {
 459         push_road_list(picked_node);
 460     }
 461
 462     //DOWN
 463     picked_node.x = current_node.x;
 464     picked_node.y = current_node.y+1;
 465     if (maze[picked_node.y][picked_node.x]!=PLAYER && maze[picked_node.y][picked_node.x]!=WALL && visited[picked_node.y][picked_node.x]!=VISITED)
 466     {
 467         push_road_list(picked_node);
 468     }
 469
 470     //LEFT
 471     picked_node.x = current_node.x-1;
 472     picked_node.y = current_node.y;
 473     if (maze[picked_node.y][picked_node.x]!=PLAYER && maze[picked_node.y][picked_node.x]!=WALL && visited[picked_node.y][picked_node.x]!=VISITED)
 474     {
 475         push_road_list(picked_node);
 476     }
 477 }
 478
 479 int is_near_node(node_t n1, node_t n2){
 480     if (n1.x==n2.x && (n1.y-n2.y==1 || n1.y-n2.y==-1))
 481     {
 482         return 1;
 483     }
 484     else if (n1.y==n2.y && (n1.x-n2.x==1 || n1.x-n2.x==-1))
 485     {
 486         return 1;
 487     }
 488     else if (n1.x==n2.x && n1.y==n2.y)
 489     {
 490         return 1;
 491     }
 492     else
 493     {
 494         return 0;
 495     }
 496 }
 497
 498 void dfs(){
 499     for (size_t i = 0; i < MAZE_HEIGHT; i++)
 500     {
 501         for (size_t j = 0; j < MAZE_WIDTH; j++)
 502         {
 503             visited[i][j] = 0;
 504         }
 505     }
 506
 507     node_t node = player;
 508     node_t cue_node = player;
 509     push_road_list(node);
 510     push_cue_list(cue_node);
 511     while (road_list.length>0 && maze[node.y][node.x]!=FLAG)
 512     {
 513         node = pop_road_list();
 514         cue_node = pop_cue_list();
 515         while (!is_near_node(node, cue_node) && cue_node.x!=0)
 516         {
 517             if (maze[cue_node.y][cue_node.x] != PLAYER)
 518             {
 519                 maze[cue_node.y][cue_node.x] = ROAD;
 520             }
 521             refresh_line(cue_node.y);
 522             cue_node = pop_cue_list();
 523         }
 524         if (cue_node.x!=0)
 525         {
 526             push_cue_list(cue_node);
 527         }
 528
 529         if (maze[node.y][node.x]!=FLAG && visited[node.y][node.x]!=VISITED)
 530         {
 531             if (maze[node.y][node.x]!=PLAYER)
 532             {
 533                 maze[node.y][node.x] = CUE;
 534             }
 535             push_cue_list(node);
 536             visited[node.y][node.x] = VISITED;
 537             visit_node(node);
 538         }
 539
 540         refresh_line(node.y);
 541     }
 542 }
 543
 544 int
 545 main(int argc, char* argv[])
 546 {
 547     fd = open("/dev/ttyG0", FO_RDWR);
 548     check(set_termios(fd));
 549     init_list();
 550     generate_maze();
 551
 552     char action = '\0';
 553     player.x=1;
 554     player.y=1;
 555     while (action!='Q')
 556     {
 557         read(fd, &action, 1);
 558         switch (action)
 559         {
 560         case 'W':
 561             up();
 562             break;
 563         case 'D':
 564             right();
 565             break;
 566         case 'S':
 567             down();
 568             break;
 569         case 'A':
 570             left();
 571             break;
 572         case 'H':
 573             dfs();
 574             break;
 575         case 'N':
 576             generate_maze();
 577             break;
 578         default:
 579             break;
 580         }
 581     }
 582
 583     check(set_termios_end(fd));
 584     return 0;
 585 }