From baca54322c66983205edecd2ebb00d997878be50 Mon Sep 17 00:00:00 2001 From: FFreestanding <62629010+FFreestanding@users.noreply.github.com> Date: Wed, 31 Jul 2024 17:19:43 +0800 Subject: [PATCH] userspace fun: maze game and a new device to support it Maze Game Introduction WASD: move H: get cue Q: quit N: new maze --- lunaix-os/hal/char/LBuild | 7 +- lunaix-os/hal/char/LConfig | 7 + lunaix-os/hal/char/chargame.c | 161 ++++++++ lunaix-os/includes/lunaix/tty/tty.h | 3 + lunaix-os/usr/LBuild | 3 +- lunaix-os/usr/maze.c | 585 ++++++++++++++++++++++++++++ 6 files changed, 764 insertions(+), 2 deletions(-) create mode 100644 lunaix-os/hal/char/chargame.c create mode 100644 lunaix-os/usr/maze.c diff --git a/lunaix-os/hal/char/LBuild b/lunaix-os/hal/char/LBuild index c00a394..dbc15be 100644 --- a/lunaix-os/hal/char/LBuild +++ b/lunaix-os/hal/char/LBuild @@ -7,4 +7,9 @@ sources([ ]) if config("vga_console"): - sources("lxconsole.c") \ No newline at end of file + + sources("lxconsole.c") + +if config("chargame_console"): + + sources("chargame.c") \ No newline at end of file diff --git a/lunaix-os/hal/char/LConfig b/lunaix-os/hal/char/LConfig index 157e2d7..788bfb4 100644 --- a/lunaix-os/hal/char/LConfig +++ b/lunaix-os/hal/char/LConfig @@ -12,3 +12,10 @@ def char_device(): type(bool) default(True) + + @Term + def chargame_console(): + """ Enable VGA Charactor Game console device (text mode only) """ + + type(bool) + default(False) \ No newline at end of file diff --git a/lunaix-os/hal/char/chargame.c b/lunaix-os/hal/char/chargame.c new file mode 100644 index 0000000..67b286c --- /dev/null +++ b/lunaix-os/hal/char/chargame.c @@ -0,0 +1,161 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +struct console +{ + struct lx_timer* flush_timer; + struct fifo_buf output; + struct fifo_buf input; + size_t wnd_start; + size_t lines; +}; + +typedef struct write_cmd { + int x; + int y; + char data[1024]; +}write_cmd; + +static struct console game_console; + +static waitq_t lx_reader; + +int +__game_listener(struct input_device* dev) +{ + u32_t key = dev->current_pkt.sys_code; + u32_t type = dev->current_pkt.pkt_type; + kbd_kstate_t state = key >> 16; + u8_t ttychr = key & 0xff; + key = key & 0xffff; + + if (type == PKT_RELEASE) { + goto done; + } + + if ((state & KBD_KEY_FLCTRL_HELD)) { + char cntrl = (char)(ttychr | 0x20); + if ('a' > cntrl || cntrl > 'z') { + goto done; + } + ttychr = cntrl - 'a' + 1; + } else if ((key & 0xff00) <= KEYPAD) { + ttychr = key; + } else { + goto done; + } + + fifo_putone(&game_console.input, ttychr); + pwake_all(&lx_reader); + +done: + return INPUT_EVT_NEXT; +} + +int +__game_write(struct device* dev, void* buf, size_t offset, size_t len); + +int +__game_read(struct device* dev, void* buf, size_t offset, size_t len); + +int +__game_write_pg(struct device* dev, void* buf, size_t offset) +{ + return __game_write(dev, buf, offset, 0x1000); +} + +int +__game_read_pg(struct device* dev, void* buf, size_t offset) +{ + return __game_read(dev, buf, offset, 0x1000); +} + +int +__game_write(struct device* dev, void* buf, size_t offset, size_t len) +{ + static bool first = 1; + if (first) + { + for (int i = 0; i < TTY_HEIGHT; i++) + { + tty_clear_line(i); + } + first = 0; + tty_set_cursor(TTY_WIDTH-1, TTY_HEIGHT-1); + } + + write_cmd *cmd = (write_cmd *)buf; + if (cmd->x==0x0a0d) { + cmd->x= 0x0a; + memcpy(cmd->data, cmd->data+1, TTY_WIDTH+1); + }else if (cmd->y==0x0a0d) { + cmd->y = 0xa; + memcpy(cmd->data, cmd->data+1, TTY_WIDTH+1); + } + + tty_put_str_at((char*)&(cmd->data), cmd->x, cmd->y); + + return len; +} + +int +__game_read(struct device* dev, void* buf, size_t offset, size_t len) +{ + struct console* console = (struct console*)dev->underlay; + size_t count = fifo_read(&console->input, buf, len); + + if (count > 0) { + return count; + } + + pwait(&lx_reader); + + return count + fifo_read(&console->input, buf + count, len - count); +} + +static int +chargame_init(struct device_def* devdef) +{ + struct device* tty_dev = device_allocseq(NULL, &game_console); + tty_dev->ops.write = __game_write; + tty_dev->ops.write_page = __game_write_pg; + tty_dev->ops.read = __game_read; + tty_dev->ops.read_page = __game_read_pg; + tty_dev->ops.read_async = __game_read; + + waitq_init(&lx_reader); + input_add_listener(__game_listener); + + register_device(tty_dev, &devdef->class, "game"); + + term_create(tty_dev, "G"); + + memset(&game_console, 0, sizeof(game_console)); + fifo_init(&game_console.output, valloc(8192), 8192, 0); + fifo_init(&game_console.input, valloc(4096), 4096, 0); + + game_console.flush_timer = NULL; + + return 0; +} + +static struct device_def chargame_def = { + .name = "Character Game Console", + .class = DEVCLASS(DEVIF_NON, DEVFN_TTY, DEV_BUILTIN), + .init = chargame_init, +}; +// FIXME +EXPORT_DEVICE(chargame, &chargame_def, load_onboot); \ No newline at end of file diff --git a/lunaix-os/includes/lunaix/tty/tty.h b/lunaix-os/includes/lunaix/tty/tty.h index 96fe485..b4a847a 100644 --- a/lunaix-os/includes/lunaix/tty/tty.h +++ b/lunaix-os/includes/lunaix/tty/tty.h @@ -43,4 +43,7 @@ tty_clear_line(int line_num); void tty_put_str_at(char* str, int x, int y); +void +tty_set_cursor(u8_t x, u8_t y); + #endif /* __LUNAIX_TTY_H */ diff --git a/lunaix-os/usr/LBuild b/lunaix-os/usr/LBuild index ec56dcb..a637308 100644 --- a/lunaix-os/usr/LBuild +++ b/lunaix-os/usr/LBuild @@ -4,7 +4,8 @@ sources([ "signal_demo", "cat", "stat", - "test_pthread" + "test_pthread", + "maze" ]) compile_opts([ diff --git a/lunaix-os/usr/maze.c b/lunaix-os/usr/maze.c new file mode 100644 index 0000000..748b814 --- /dev/null +++ b/lunaix-os/usr/maze.c @@ -0,0 +1,585 @@ +#include +#include +#include +#include +#include +#include +#include + +#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 -- 2.27.0