An attempt to implement 2D terrain destruction (Vietnamese)

Thỉnh thoảng tôi tìm những bài toán trong lập trình mà có thể mô tả trong 1 câu, vừa fun khi giải quyết, vừa dễ dàng kiểm tra kết quả, để giải quyết cho vui.

Một trong những lý do tôi làm vậy là tôi nhớ đến 1 câu nói trong bài viết nào đó tôi từng đọc. Câu nói có đại ý là phần lớn vấn đề trong lập trình (cụ thể là backend) là xử lý chuỗi ký tự. Tất nhiên câu này không hề đúng, vấn đề ở chỗ phải "xử lý chuỗi" như thế nào và số lượng của chúng có lớn hay không nữa. Cơ mà từ đó tôi hay tìm những bài toán không phải xoay quanh xử lý chuỗi, và đủ nhỏ để giải quyết cho vui trong thời gian ngắn.

Gần đây tôi được rủ chơi lại Gunny, một game mà 8x, 9x đều quen thuộc. Nói là chơi lại cũng không đúng vì tôi chưa từng chơi game này, vì tôi không thích đồ họa của nó lắm. Theo tôi tìm hiểu thì Gunny được phát triển ban đầu bởi một cty Trung Quốc từ 2008-2009. Và game này không phải là game đầu tiên có lối chơi kiểu phá hủy địa hình như này (game đầu tiên là series Worms từ 1999 mà trước đây tôi từng chơi 1 tựa game trong series đấy).

Điều làm tôi thấy thú vị là nhà phát triển của Gunny cũng như Worms hiện thực cơ chế phá hủy địa hình 2 chiều (2D terrain destruction) như thế nào. Có thể cách đơn giản nhất là lưu từng điểm ảnh (pixel) của cả bản đồ và mỗi khi muốn phá hủy chỗ nào thì chỉ cần xóa những pixels đấy đi. Cách này giống như những phần mềm đồ họa như Microsoft Paint làm. Nếu họ làm cách này, họ có thể áp dụng những tối ưu như không cần lưu từng pixel của những vùng hình chữ nhật lớn mà chưa bị phá hủy (thay vì lưu từng pixel với số lượng hàng triệu (bản đồ 1000x1000 pixels) thì họ dùng một cấu trúc dữ liệu như quad-tree để lưu ít hơn rất nhiều, chỉ cần lưu 1 node trong cái tree đấy cho mỗi vùng chữ nhật lớn).

Hoặc một cách khác là xem cả bản đồ và mọi viên đạn là những đa giác đơn giản (simple polygon, một simple polygon không được phép có cạnh nào cắt chính nó). Khi đấy việc phá hủy địa hình là việc lấy một đa giác trừ đi một đa giác khác. Mỗi đa giác (đơn giản) bất kỳ đều có thể phân tách thành nhiều tam giác. Khi này bài toán trừ 2 đa giác có thể quy về trừ 2 tam giác. Ngoài ra cách này còn có thể mở rộng lên 3 chiều, khi ấy đa giác trở thành hình khối (meshes) và tam giác sẽ trở thành tứ diện (tetrahedron). Tôi quyết định giải quyết bài toán này cho vui. Bài toán có thể được phát biểu đơn giản là phép trừ 2 đa giác. Và tôi có thể dễ dàng kiểm tra kết quả bằng cách vẽ lên màn hình và nhìn bằng mắt thường.

Ok giờ tôi chỉ cần hiện thực 2 thao tác chính: biến đa giác thành nhiều tam giác (triangulation) và trừ 2 tam giác (triangle subtraction/clipping). Bài toán triangulation có một thuật toán rất là tường minh gọi là ear-clipping và có thể phát biểu như sau: lần lượt tìm từng tam giác ở rìa đa giác (ears) rồi xóa nó khỏi đa giác, lặp lại cho đến khi đa giác trở nên trống rỗng. Những tam giác rìa (ears) bị xóa đi chính là kết quả.

Bài toán tam giác A trừ tam giác B có thể giải quyết như sau: tìm mọi điểm giao của A và B, sau đó tạo ra những tam giác từ những điểm đấy cộng với 3 điểm của A, sau đó loại bỏ những tam giác nằm trong B. Những tam giác còn lại chính là kết quả của tam giác A trừ tam giác B.

Có một thuật toán đơn giản để tạo ra những tam giác (không cắt nhau) từ tập của những điểm: tạo ra mọi đoạn thẳng nối mọi điểm, lần lượt thử thêm từng đoạn thẳng đấy vào một danh sách sao cho đoạn thẳng vừa thêm vào không cắt bất kỳ đoạn thẳng nào trong danh sách. Từ danh sách đoạn thẳng không cắt nhau đấy mình có thể tạo ra những tam giác không cắt nhau.

Mọi thứ diễn ra rất suôn sẻ cho đến khi tôi gặp vấn đề về biễu diễn số thực trong máy tính. Như các bạn đã biết máy tính không thể nào biểu diễn số thực với vô hạn số sau dấu thập phân. Cho nên kết quả tính toán số thực sẽ có sai số, dù là rất nhỏ (độ nhỏ tùy vào việc dùng float32 hay float64). Bởi vì có sai số nên phép so sánh bằng nhau có thể không hoạt động như mong muốn. Ví dụ có 2 số thực được tính toán từ 2 quá trình khác nhau, về mặt toán học thì 2 quá trình đấy tương đương nhau. Nhưng do sai số cộng dồn qua các bước tính toán (của 2 quá trình), kết quả có thể cho ra 2 số khác nhau, dù khác nhau rất nhỏ. Cho nên trong lập trình người ta thường dùng một hằng số epsilon khi so sánh 2 số thực: nếu |a - b| <= epsilon thì mình xem như a = b.

Các thao tác hình học trong máy tính đều cần một hoặc nhiều hằng số epsilon, tùy vào trường hợp. Ví dụ mình cần một epsilon cho khoảng cách: 2 điểm có khoảng cách <= epsilon này thì mình xem như chúng trùng nhau. Ngoài ra cũng có epsilon cho diện tích, nếu 1 tam giác có diện tích <= epsilon thì mình coi như nó không tồn tại, như vậy mình sẽ đỡ phải vẽ 1 cái tam giác rất nhỏ, không thấy được trên màn hình. Thường những hằng số epsilon dành cho các thao tác hình học (mà cuối cùng để vẽ lên màn hình) sẽ lớn hơn epsilon dành cho việc so sánh 2 số thực.

Cơ mà việc dùng hằng số epsilon này có thể phá hỏng những logic trong hình học. Vì dụ có 3 đường thẳng a, b, và c song song với nhau. Khoảng cách giữa a và b cũng như b và c là 0.001, b "nằm giữa" a và c. Nếu epsilon = 0.001 thì a sẽ thẳng hàng (collinear) với b, và b thẳng hàng với c. Theo logic bắt cầu thì a cũng sẽ thẳng hàng với c. Cơ mà khoảng cách giữa a và c là 0.002 lớn hơn epsilon, nên cái thao tác kiểm tra thẳng hàng của a và c sẽ trả về không thẳng hàng, ngược lại với logic bắt cầu. Cơ mà nếu chày cối muốn bảo toàn logic bắt cầu này thì giả sử trường hợp có 10000 đường thẳng song song nhau, cách đều nhau 0.001. Như vậy đường thẳng đầu tiên cách đường thẳng cuối cùng 0.001 * 10000 = 10 đơn vị. Chẳng lẽ theo logic bắt cầu thì chúng thẳng hàng với nhau? Đây là một nghịch lý mà cho dù có giảm epsilon xuống bao nhiêu thì cũng không giải quyết được.

Tôi không biết có phải do những lổ hổng logic do epsilon gây ra mà chương trình của tôi có lỗi (bugs), hay bản thân bugs (như video kèm theo) do tôi gây ra.

Nếu như mục tiêu là mô phỏng lại cơ chế phá hủy địa hình của Gunny, thì tôi sẽ chọn cách đầu tiên: quản lý từng pixel. Tôi muốn xem nếu mở rộng bài toán này ra 3 chiều thì nó sẽ vui như thế nào nên tôi mới chọn cách dùng đa giác này. Để mở rộng ra 3 chiều tôi phải sửa hết mọi cái lỗi của cái 2D implementation này đã, cơ mà phải để khi khác, tôi còn phải đi chạm cỏ nữa.