+#include <errno.h>
+#include <fcntl.h>
+#include <lunaix/lunaix.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include <termios.h>
+
+#define check(statement) \
+ ({ \
+ int err = 0; \
+ if ((err = (statement)) < 0) { \
+ syslog(2, #statement " failed: %d", err); \
+ _exit(1); \
+ } \
+ err; \
+ })
+
+
+#define TTY_WIDTH 80
+#define TTY_HEIGHT 25
+
+#define MAZE_WIDTH TTY_WIDTH-1
+#define MAZE_HEIGHT TTY_HEIGHT
+
+#define BUFFER_SIZE 1024
+
+#define WALL '#'
+#define ROAD ' '
+#define PLAYER 'P'
+#define FLAG 'F'
+#define CUE '.'
+
+#define VISITED 1
+
+#define UP 0
+#define RIGHT 1
+#define DOWN 2
+#define LEFT 3
+
+int rand_fd;
+int fd;
+
+void get_rand(unsigned int *r, unsigned int max) {
+ if (max==0)
+ {
+ *r = 0;
+ return;
+ }
+ read(rand_fd, r, 4);
+ *r = (*r)%max;
+}
+
+typedef struct player_t {
+ int x;
+ int y;
+}player_t;
+
+typedef struct write_cmd {
+ int x;
+ int y;
+ char data[MAZE_WIDTH+1];
+}write_cmd;
+
+typedef struct node_t {
+ int x;
+ int y;
+}node_t;
+
+typedef struct stack_t {
+ node_t node[1000];
+ unsigned int length;
+}road_list_t, cue_list_t;
+
+road_list_t road_list;
+cue_list_t cue_list;
+
+void init_list() {
+ for (size_t i = 0; i < 1000; i++)
+ {
+ road_list.node[i].x = 0;
+ road_list.node[i].y = 0;
+ }
+ road_list.length = 0;
+
+ for (size_t i = 0; i < 1000; i++)
+ {
+ cue_list.node[i].x = 0;
+ cue_list.node[i].y = 0;
+ }
+ cue_list.length = 0;
+}
+
+int insert_road_list(node_t n) {
+ if (road_list.length>=1000)
+ {
+ return 0;
+ }
+
+ unsigned int r = 0;
+ get_rand(&r, road_list.length);
+ for (size_t i = road_list.length; i > r; i--)
+ {
+ road_list.node[i] = road_list.node[i-1];
+ }
+ road_list.node[r] = n;
+ road_list.length+=1;
+ return 1;
+}
+
+int push_road_list(node_t node) {
+ if (road_list.length>=1000)
+ {
+ return 0;
+ }
+ road_list.node[road_list.length] = node;
+ road_list.length+=1;
+ return 1;
+}
+
+node_t pop_road_list() {
+ node_t n={.x = 0, .y = 0};
+ if (road_list.length==0)
+ {
+ return n;
+ }
+ n = road_list.node[road_list.length-1];
+ road_list.node[road_list.length-1].x = 0;
+ road_list.node[road_list.length-1].y = 0;
+ road_list.length-=1;
+ return n;
+}
+
+int push_cue_list(node_t node) {
+ if (cue_list.length>=1000)
+ {
+ return 0;
+ }
+ cue_list.node[cue_list.length] = node;
+ cue_list.length+=1;
+ return 1;
+}
+
+node_t pop_cue_list() {
+ node_t n={.x = 0, .y = 0};
+ if (cue_list.length==0)
+ {
+ return n;
+ }
+ n = cue_list.node[cue_list.length-1];
+ cue_list.node[cue_list.length-1].x = 0;
+ cue_list.node[cue_list.length-1].y = 0;
+ cue_list.length-=1;
+ return n;
+}
+
+int iswall(node_t n) {
+ if (n.x<0 || n.y<0)
+ {
+ return 0;
+ }
+
+ return n.x%2==0 || n.y%2==0;
+}
+
+// is road position
+// no matter it is marked as '-'
+int isroad(node_t n) {
+ if (n.x<=0 || n.y<=0 || n.x>=MAZE_WIDTH-1 || n.y>=MAZE_HEIGHT-1)
+ {
+ return 0;
+ }
+
+ return !iswall(n);
+}
+
+
+void generate_rand_road_node(node_t *n)
+{
+ get_rand((unsigned int *)&n->x, MAZE_WIDTH);
+ get_rand((unsigned int *)&n->y, MAZE_HEIGHT);
+ if (isroad(*n))
+ {
+ return;
+ }
+
+ if (n->x%2==0)
+ {
+ if (n->x<=(MAZE_WIDTH/2))
+ {
+ n->x+=1;
+ }
+ else
+ {
+ n->x-=1;
+ }
+ }
+
+ if (n->y%2==0)
+ {
+ if (n->y<=(MAZE_HEIGHT/2))
+ {
+ n->y+=1;
+ }
+ else
+ {
+ n->y-=1;
+ }
+ }
+}
+
+char maze[MAZE_HEIGHT][MAZE_WIDTH];
+char visited[MAZE_HEIGHT][MAZE_WIDTH];
+
+void pick_near_road_to_list(node_t current_node) {
+ node_t picked_node;
+
+ //UP
+ picked_node.x = current_node.x;
+ picked_node.y = current_node.y-2;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
+ {
+ insert_road_list(picked_node);
+ }
+
+ //RIGHT
+ picked_node.x = current_node.x+2;
+ picked_node.y = current_node.y;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
+ {
+ insert_road_list(picked_node);
+ }
+
+ //DOWN
+ picked_node.x = current_node.x;
+ picked_node.y = current_node.y+2;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
+ {
+ insert_road_list(picked_node);
+ }
+
+ //LEFT
+ picked_node.x = current_node.x-2;
+ picked_node.y = current_node.y;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]!=ROAD)
+ {
+ insert_road_list(picked_node);
+ }
+}
+
+node_t pick_near_road(node_t current_node) {
+ node_t picked_node;
+
+ //UP
+ picked_node.x = current_node.x;
+ picked_node.y = current_node.y-2;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
+ {
+ return picked_node;
+ }
+
+ //LEFT
+ picked_node.x = current_node.x-2;
+ picked_node.y = current_node.y;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
+ {
+ return picked_node;
+ }
+
+ //DOWN
+ picked_node.x = current_node.x;
+ picked_node.y = current_node.y+2;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
+ {
+ return picked_node;
+ }
+
+ //RIGHT
+ picked_node.x = current_node.x+2;
+ picked_node.y = current_node.y;
+ if (isroad(picked_node) && maze[picked_node.y][picked_node.x]==ROAD)
+ {
+ return picked_node;
+ }
+
+ return picked_node;
+}
+
+
+void break_wall(node_t n1, node_t n2)
+{
+ if (n1.x==n2.x)
+ {
+ maze[(n1.y+n2.y+1)/2][n1.x]=ROAD;
+ }
+ else if(n1.y==n2.y)
+ {
+ maze[n1.y][(n1.x+n2.x+1)/2]=ROAD;
+ }
+}
+
+void print_maze(){
+ write_cmd wcmd;
+ wcmd.x = 0;
+ wcmd.data[MAZE_WIDTH] = '\0';
+
+ for (size_t j = 0; j < MAZE_HEIGHT; j++)
+ {
+ for (size_t i = 0; i < MAZE_WIDTH; i++)
+ {
+ wcmd.data[i] = maze[j][i];
+ }
+ wcmd.y = j;
+ write(fd, &wcmd, sizeof(write_cmd));
+ }
+}
+
+void refresh_line(int y){
+ write_cmd wcmd;
+ wcmd.x = 0;
+ wcmd.y = y;
+ wcmd.data[MAZE_WIDTH] = '\0';
+
+ for (size_t i = 0; i < MAZE_WIDTH; i++)
+ {
+ wcmd.data[i] = maze[y][i];
+ }
+
+ write(fd, &wcmd, sizeof(write_cmd));
+}
+
+// Prim algorithm
+void generate_maze()
+{
+ node_t start_node;
+
+ for (size_t i = 0; i < MAZE_HEIGHT; i++)
+ {
+ for (size_t j = 0; j < MAZE_WIDTH; j++)
+ {
+ maze[i][j] = WALL;
+ }
+ }
+
+ rand_fd = open("/dev/rand", O_RDONLY);
+
+ generate_rand_road_node(&start_node);
+
+ maze[start_node.y][start_node.x] = ROAD;
+
+ pick_near_road_to_list(start_node);
+
+ while (road_list.length>0)
+ {
+ node_t n = pop_road_list();
+ maze[n.y][n.x] = ROAD;
+ node_t n2 = pick_near_road(n);
+ maze[n2.y][n2.x] = ROAD;
+ break_wall(n, n2);
+ pick_near_road_to_list(n);
+ print_maze();
+ }
+
+ maze[1][1] = PLAYER;
+ maze[MAZE_HEIGHT-2][MAZE_WIDTH-2] = FLAG;
+ refresh_line(1);
+ refresh_line(MAZE_HEIGHT-2);
+}
+
+
+int
+set_termios(int fd) {
+ struct termios term;
+
+ check(tcgetattr(fd, &term));
+
+ term.c_lflag = IEXTEN | ISIG | ECHO | ECHOE | ECHONL;
+ term.c_cc[VERASE] = 0x7f;
+
+ check(tcsetattr(fd, 0, &term));
+
+ return 0;
+}
+
+int
+set_termios_end(int fd) {
+ struct termios term;
+
+ check(tcgetattr(fd, &term));
+
+ term.c_lflag = ICANON | IEXTEN | ISIG | ECHO | ECHOE | ECHONL;
+ term.c_cc[VERASE] = 0x7f;
+
+ check(tcsetattr(fd, 0, &term));
+
+ return 0;
+}
+
+node_t player;
+
+void up(){
+ if (maze[player.y-1][player.x]!='#')
+ {
+ player.y-=1;
+ maze[player.y][player.x] = 'P';
+ maze[player.y+1][player.x] = ' ';
+ }
+ refresh_line(player.y);
+ refresh_line(player.y+1);
+}
+
+void right(){
+ if (maze[player.y][player.x+1]!='#')
+ {
+ player.x+=1;
+ maze[player.y][player.x] = 'P';
+ maze[player.y][player.x-1] = ' ';
+ }
+ refresh_line(player.y);
+}
+
+void down(){
+ if (maze[player.y+1][player.x]!='#')
+ {
+ player.y+=1;
+ maze[player.y][player.x] = 'P';
+ maze[player.y-1][player.x] = ' ';
+ }
+ refresh_line(player.y);
+ refresh_line(player.y-1);
+}
+
+void left(){
+ if (maze[player.y][player.x-1]!='#')
+ {
+ player.x-=1;
+ maze[player.y][player.x] = 'P';
+ maze[player.y][player.x+1] = ' ';
+ }
+ refresh_line(player.y);
+}
+
+void visit_node(node_t current_node){
+ node_t picked_node;
+
+ //UP
+ picked_node.x = current_node.x;
+ picked_node.y = current_node.y-1;
+ 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)
+ {
+ push_road_list(picked_node);
+ }
+
+ //RIGHT
+ picked_node.x = current_node.x+1;
+ picked_node.y = current_node.y;
+ 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)
+ {
+ push_road_list(picked_node);
+ }
+
+ //DOWN
+ picked_node.x = current_node.x;
+ picked_node.y = current_node.y+1;
+ 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)
+ {
+ push_road_list(picked_node);
+ }
+
+ //LEFT
+ picked_node.x = current_node.x-1;
+ picked_node.y = current_node.y;
+ 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)
+ {
+ push_road_list(picked_node);
+ }
+}
+
+int is_near_node(node_t n1, node_t n2){
+ if (n1.x==n2.x && (n1.y-n2.y==1 || n1.y-n2.y==-1))
+ {
+ return 1;
+ }
+ else if (n1.y==n2.y && (n1.x-n2.x==1 || n1.x-n2.x==-1))
+ {
+ return 1;
+ }
+ else if (n1.x==n2.x && n1.y==n2.y)
+ {
+ return 1;
+ }
+ else
+ {
+ return 0;
+ }
+}
+
+void dfs(){
+ for (size_t i = 0; i < MAZE_HEIGHT; i++)
+ {
+ for (size_t j = 0; j < MAZE_WIDTH; j++)
+ {
+ visited[i][j] = 0;
+ }
+ }
+
+ node_t node = player;
+ node_t cue_node = player;
+ push_road_list(node);
+ push_cue_list(cue_node);
+ while (road_list.length>0 && maze[node.y][node.x]!=FLAG)
+ {
+ node = pop_road_list();
+ cue_node = pop_cue_list();
+ while (!is_near_node(node, cue_node) && cue_node.x!=0)
+ {
+ if (maze[cue_node.y][cue_node.x] != PLAYER)
+ {
+ maze[cue_node.y][cue_node.x] = ROAD;
+ }
+ refresh_line(cue_node.y);
+ cue_node = pop_cue_list();
+ }
+ if (cue_node.x!=0)
+ {
+ push_cue_list(cue_node);
+ }
+
+ if (maze[node.y][node.x]!=FLAG && visited[node.y][node.x]!=VISITED)
+ {
+ if (maze[node.y][node.x]!=PLAYER)
+ {
+ maze[node.y][node.x] = CUE;
+ }
+ push_cue_list(node);
+ visited[node.y][node.x] = VISITED;
+ visit_node(node);
+ }
+
+ refresh_line(node.y);
+ }
+}
+
+int
+main(int argc, char* argv[])
+{
+ fd = open("/dev/ttyG0", FO_RDWR);
+ check(set_termios(fd));
+ init_list();
+ generate_maze();
+
+ char action = '\0';
+ player.x=1;
+ player.y=1;
+ while (action!='Q')
+ {
+ read(fd, &action, 1);
+ switch (action)
+ {
+ case 'W':
+ up();
+ break;
+ case 'D':
+ right();
+ break;
+ case 'S':
+ down();
+ break;
+ case 'A':
+ left();
+ break;
+ case 'H':
+ dfs();
+ break;
+ case 'N':
+ generate_maze();
+ break;
+ default:
+ break;
+ }
+ }
+
+ check(set_termios_end(fd));
+ return 0;
+}
\ No newline at end of file
git://scm.lunaixsky.com / lunaix-os.git / commitdiff