Triển khai raycaster trong Bash

 (github.com/izabera)
2 điểm bởi GN⁺ 2024-12-22 | 1 bình luận | Chia sẻ qua WhatsApp
  • Đây là một raycaster được triển khai bằng Bash, một bản demo pseudo-3D chạy trong terminal, xoay/di chuyển bằng phím mũi tên và thoát bằng q
  • Phần triển khai về cơ bản là bản port của hướng dẫn raycasting của Lode Vandevenne, và toàn bộ phép toán được xử lý bằng số nguyên với hệ số tỷ lệ 64K, không dùng số thực dấu phẩy động
  • Hạn chế lớn nhất là hiệu năng của Bash: nếu chạy lệnh cho từng pixel hoặc giữ trạng thái màn hình bằng mảng/chuỗi thì rất khó xuất kịp trong thời gian của một khung hình
  • Việc hiển thị trong terminal dùng Unicode half block cùng màu foreground/background 24-bit để gần như tăng gấp đôi độ phân giải theo chiều dọc, nhưng có ràng buộc là phải biết màu của các pixel liền kề
  • Trong lộ trình hiện tại, fluid movement, decent framerate, parallel rendering, kitty keyboard protocol, nguyên mẫu ban đầu của sound, v.v. đã hoàn thành; còn textures, sprites, enemies, particles, multiplayer, v.v. vẫn chưa hoàn tất

Raycaster terminal làm bằng Bash

  • Dự án này là một raycaster chạy trong Bash, render hình ảnh pseudo-3D bên trong terminal
  • Điều khiển bằng phím mũi tên để xoay và di chuyển, nhấn q để thoát
  • Có thêm ảnh chụp màn hình và video trong album Imgur
  • Phần triển khai chủ yếu là bản port của hướng dẫn raycasting của Lode Vandevenne

Các ràng buộc khiến việc triển khai trở nên khó khăn

  • Vấn đề lớn nhất là Bash chậm
    • Tác giả cho biết ngay cả khi chỉ cần chạy đúng một lệnh cho mỗi pixel thì cũng khó đạt được acceptable frame rate
    • Ngay cả khi lưu trạng thái màn hình trong một mảng màu, việc truy cập ngẫu nhiên vào phần tử mảng vẫn là thời gian tuyến tính nên cũng thành vấn đề
    • Ngay cả khi lưu trạng thái màn hình trong một chuỗi dài duy nhất, thì dù ở LANG=C, việc truy cập ký tự thứ n vẫn là thời gian tuyến tính, nên chỉ riêng việc đọc để dump ra màn hình cũng có thể lâu hơn cả một khung hình
  • Bash không có hỗ trợ số thực dấu phẩy động và cũng không có quyền truy cập thư viện hàm toán học
    • Mọi phép toán đều được xử lý bằng số nguyên
    • Các giá trị số nguyên được phóng đại theo hệ số 64K để tính toán
  • Nếu dùng một ký tự trong terminal như một pixel thì hình ảnh không đẹp, nên tác giả dùng Unicode half block
    • Thiết lập màu foreground và background khác nhau để gần như tăng gấp đôi độ phân giải theo chiều dọc
    • Không có cách nào để chỉ cập nhật một trong hai màu trong cùng một ô
    • Cũng không có cách truy vấn màu của ô hiện tại, và trong Bash thì ngay cả việc truy vấn như vậy cũng quá chậm
    • Vì vậy mỗi khi ghi một pixel thì phải biết màu của pixel liền kề

Vấn đề terminal và nhập/xuất

  • Với Bash là một ngôn ngữ chậm, việc cập nhật toàn bộ terminal trong một lần không hề đơn giản
  • Phần lớn terminal không được thiết kế cho video game, nên không thể kiểm tra trạng thái các phím đang được nhấn
    • Thông thường chỉ lấy được đầu vào của một phím đơn đang được giữ
    • Lặp đầu vào bị debounce chậm, và giới hạn đầu vào liên tiếp cũng thấp, nên có tình huống chỉ nhận được khoảng 5–6 ký tự mỗi giây
    • Cũng khó lấy được nhiều phím bấm đồng thời ngoài các phím modifier
    • kitty keyboard protocol được cho là giải quyết được vấn đề này
  • Tô đầy terminal bằng màu đòi hỏi rất nhiều dữ liệu
    • Với cỡ font thông thường của tác giả, I/O phát sinh vào khoảng 10MB mỗi giây
  • Bash không dùng một syscall duy nhất khi in ra chuỗi có chứa nhiều dấu xuống dòng
    • Dự án này không in \n mà di chuyển con trỏ theo cách khác

FAQ và điều kiện chạy

  • Nếu thay đổi kích thước cửa sổ làm hình bị vỡ, bị nhấp nháy nặng, hoặc trông không ổn trên một số terminal nhất định, tác giả đề nghị mở issue
  • Nếu CPU quá nóng hoặc máy tính cũ chạy chậm, tác giả hướng dẫn hạ độ phân giải hoặc đặt biến môi trường FPS nhỏ hơn 30
    • Microsoft Defender được biết là làm giảm hiệu năng đáng kể nên tác giả gợi ý tắt nó đi
  • Tác giả trả lời rằng chương trình không chạy trên Bash thấp hơn 5.2
  • Đây không phải là mã hoàn toàn thuần Bash
    • Khi khởi động, chương trình gọi stty một lần để tắt echo
    • Khi kết thúc, chương trình gọi stty một lần để bật lại echo
    • Một số thống kê sau khi thoát được thu thập bằng công cụ khác

Trạng thái lộ trình

  • Các hạng mục đã hoàn thành

    • pseudo 3d bán chính xác

      • fluid movement
      • decent framerate
      • parallel rendering
      • 24 bit colours
      • kitty keyboard protocol
      • framerate-independent speed
      • sound, nhưng mới chỉ là nguyên mẫu rất sớm
      • dynamic wall colours
      • dynamic map, hiện tại chưa có sự kiện nào thay đổi nhưng về mặt kỹ thuật thì là động
      • basic animations effects for walls
      • basic on-screen minimap
      • các hạng mục chưa hoàn thành

    • mouse support

      • textures
      • sprites
      • objects/enemies
      • particles
      • better perf
      • multiplayer

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-12-22
Các ý kiến trên Hacker News
  • Cái này thật sự hay. Tôi đã thắc mắc họ vẽ hình thế nào mà không echo một lần cho từng pixel; cách làm rất thông minh
    Vì trò chơi không phải 3D “thật”, nên chỉ cần chạy ray tracing một lần cho mỗi cột, rồi vẽ vài dòng tương ứng với bầu trời, bãi cỏ và vật thể thực tế
    Cách làm là in ra terminal một chuỗi kiểu “vẽ pixel này rồi di chuyển xuống một ô” bằng lặp chuỗi đúng số lần cần thiết
    Dù không phải cho Bash, tôi từng nghĩ đến việc thử làm một engine render voxel trong một môi trường khác có tài nguyên tính toán hạn chế; chắc chắn có thể tìm thấy thứ gì đó hữu ích ở đây
  • Nếu bạn từng thắc mắc liệu có ray caster viết bằng MS Batch không, thì cũng có cái này: https://github.com/nTh0rn/batch-raycaster
  • Thật tiếc là stty lại cần fork. Có lẽ dự án tiếp theo sẽ là gọi ioctl cần thiết bằng Bash và rowhammer để xử lý mà không cần fork
  • Tôi không ngờ Bash có thể làm được những thứ như thế này. Từng có lúc tôi nghĩ mình dùng Bash ở mức khá nâng cao, nhưng cái này thật sự đáng kinh ngạc
    Tôi không đủ giỏi toán để hiểu phần triển khai, nhưng chỉ xem thôi cũng đã vui rồi
  • Script Bash của tôi tốn 300 dòng chỉ để phân tích các tùy chọn dòng lệnh đủ kiểu, trong khi hóa ra lẽ ra tôi đã có thể cho hiện một trò chơi như thế này :-P
  • Tôi vẫn không thể hiểu nổi vì sao chúng ta vẫn bị mắc kẹt với một shell chậm đến vô lý như vậy. Đúng là điên rồ thuần túy
    Tôi hiểu rằng một số ứng dụng cần đủ loại hành vi kỳ lạ của vt100, nhưng có lẽ 90% ứng dụng chỉ ghi ra stdout và stderr
    Lẽ ra phải có cách đẩy văn bản lên màn hình nhanh hơn một chút, rồi đưa 10% còn lại vào chế độ tương thích chứ
    • Shell thì chậm, đặc biệt là Bash, nhưng tôi không chắc phần sau của lập luận nối tiếp thế nào. Shell hoàn toàn không tham gia vào việc diễn giải terminal escape sequence, và các terminal hiện đại khá nhanh
      Ngay cả trên terminal rộng 350 cột cũng có thể render animation, và xét các ràng buộc thì nó chạy rất mượt
      Hơn nữa, tiền đề của bài này chính là Bash là một ngôn ngữ không phù hợp để ray casting. Giống như viết bubble sort bằng CSS vậy
      “Đưa 10% còn lại vào chế độ tương thích” thì không có gì ngăn cản cả. Chỉ cần kiểm tra chuỗi có chứa toàn ký tự bình thường hay không rồi dùng fast path
      Vấn đề là render văn bản bằng phần mềm thực ra không có fast path. Vẫn phải xử lý những thứ như ligature
  • “bash chậm.”
    Đó là một trong những lý do tôi không dùng Bash để scripting. Dùng tương tác tôi cũng không dùng
    Một số bản phân phối Linux phổ biến cũng tránh dùng Bash làm shell scripting
  • Sẽ rất hay nếu ghép cái này với triển khai ps không fork của tác giả để tạo ra một bản triển khai psDoom gần như không fork
    Đùa vậy thôi, thật sự rất tuyệt
  • Tất nhiên cũng phải nhắc đến ray caster bằng awk từ 9 năm trước một cách trang trọng: https://github.com/TheMozg/awk-raycaster/tree/master