Một chút về ánh sáng trong làm game.

Hôm nay đang làm một game (3d) thì tự nhiên mình nghĩ đến việc implement cái Fog of War như ở trong Doto.

Đơn giản hoá

Thì mình bắt đầu từ bài toán ở trong 2D. Trước tiên ta phải chuẩn bị một mặt phẳng, trên đó có một vài chướng ngại vật mà từ một vị trí bất kỳ thì người chơi sẽ không thể nhìn thấy những gì bị khuất bởi các chướng ngại vật đó. Như sau:

Cách đầu tiên nghĩ ngay đến, bắt nguồn từ cách mắt người hoạt động, là từ vị trí người chơi, vẽ các tia bắn ra xung quanh, các tia cách đều nhau, gặp chướng ngại vật thì dừng lại tại điểm tiếp xúc. Khi đó ta sẽ được tập hợp các điểm tiếp xúc mà ở đó tầm nhìn không thể đi xa hơn được nữa. Đối với các tia không gặp chướng ngại vật thì ta coi như điểm tiếp xúc của tia đó là ở xa vô cùng. Sau khi nối các điểm tiếp xúc đó lại với nhau thì ta sẽ được một đa giác, ta có thể dễ dàng chứng minh được mọi điểm trên các tia bắn ra từ vị trí người chơi và nằm trong đa giác trên thì đều nằm trong tầm nhìn. Do đó, khi số lượng tia xung quanh tiến đến vô cùng thì ta sẽ được một đa giác vô số cạnh biểu diễn tầm nhìn. Hình sau thể hiện giải thuật trên với 60 tia bắn đều ra xung quanh.

Như ta thấy, nếu số tia quá ít thì tầm nhìn sẽ không chuẩn, có cảm giác giật lag khi di chuyển.

Nếu số tia quá nhiều thì tầm nhìn sẽ chuẩn hơn sẽ rất ảnh hưởng đến performance, do đó sẽ không mượt hơn. Như hình sau là biểu diễn với 6.000 tia.

Ê, sao tôi chả thấy gì cả?

Ông phải click, nếu tôi cập nhật khi ông di chuột thì máy tôi sẽ lăn ra chết (thực ra là không nhưng mà nó rất chậm). Còn nếu máy ông mạnh thì click vào đây

Ok, vậy nếu ít tia thì xấu, nhiều tia thì chậm thì phải làm thế nào?

Giải quyết vấn đề

Khi gặp một vấn đề về performance thì ta có 2 cách giải quyết:

Đổi sang máy xịn hơn.
Thay đổi thuật toán có độ phức tạp thời gian tốt hơn.

Tôi thích dùng cách trước hơn nên chúng ta sẽ dùng cách 2. Như ông để ý thì ở cách trên, các đỉnh của chướng ngại vật sẽ ít khi có tia nào bắn trúng, và do đó các góc sẽ bị cắt cụt đi. Khi tăng số tia lên thì đỉnh sẽ dễ được bắn trúng hơn, do đó giảm cảm giác gãy cạnh. Do đó ta nghĩ đến cách như các phần mềm vẽ sử dụng: bắt điểm. Tia ở gần đỉnh của chướng ngại vật nhất sẽ bắt luôn vào đỉnh đó. Chúng ta có thể tìm được tia gần đỉnh nhất bằng cách tính góc giữa các tia bắn ra và tia từ vị trí người chơi đến đỉnh của chướng ngại vật 𝛼. Nếu 2𝛼 < 𝛽, với 𝛽 là góc giữa 2 tia bắn ra, thì tia đó là tia gần đỉnh nhất. Khi đó, ta thấy là các tia bắt vào đỉnh rất quan trọng, và các tia còn lại, tiếp xúc với chướng ngại vật trên cạnh thì gần như không có tác dụng gì, chỉ có tác dụng nối 2 đỉnh lại với nhau. Do đó ta có thể bỏ qua các tia tiếp xúc trên cạnh. Như vậy, thay vì tạo ra nhiều tia rồi bắt đỉnh , loại bỏ các tia thừa. Ta có thể chỉ tạo ra các tia từ vị trí người chơi đến các đỉnh, rồi xét các tia đó là được (chú ý là các tia đó sẽ cắt chướng ngại vật tại 1 điểm nhưng vẫn tiếp tục được kéo dài và xét tiếp, vì tầm nhìn sẽ có thể chỉ bị chặn ở 1 phía). Khi đó ta không cần dùng đến công thức 2𝛼 < 𝛽 nữa vì các tia chắc chắn đi qua đỉnh. Một công đôi việc.

Vì ta các tia cho từng hình mà không sắp xếp lại thì sẽ không được. Do đó, sau khi sắp xếp lại các hình thì ta sẽ được kết quả sau:

Vẫn có gì đó sai sai đúng không? Khi vị trí người chơi ở trung tâm thì ổn, nhưng khi đưa ra dìa thì lại không ổn nữa. Vì 2 tia ở ngoài cùng nối với nhau nên nó tạo nên một tam giác to tổ bố, và tam giác đó đè lên trên phần còn lại của nó. Để giải quyết vấn đề này thì ta xét thêm 1 "chướng ngại vật" nữa là hình chữ nhật khung nhìn. Works like a charm.

Những thứ cần cải thiện

Thuật toán trên chỉ làm việc khi các chướng ngại vật không đè lên nhau, và không có đa giác tự cắt. Do đó ta sẽ cải tiến nó một chút, trước khi xét các tia bắn vào đỉnh, ta xét thêm các đỉnh là giao điểm của 2 cạnh bất kỳ. Và đây là kết quả cuối cùng.

Cùng với Play Ground cho các bạn. Chuột phải để vẽ chướng ngại vật, Enter để nhấc bút. PS: Hình càng phức tạp, càng có nhiều điểm tự cắt thì thuật toán thứ hai sẽ chạy càng chậm, đến 1 lúc nào đó thì nó sẽ chậm hơn thuật toán thứ nhất (với 6000 tia). Khi đó ta sẽ có 2 cách xử lý: 1 là đổi sang thuật toán thứ nhất, 2 là cải tiến thuật toán thứ hai, 3 là tăng cấu hình yêu cầu lên RTX2080.

Đường cong thì sao, đường cong làm gì có đỉnh nào mà làm kiểu này?

Khi gặp một vấn đề về... À cái này không phải về performance. Ông có thể fallback về cách ban đầu, bắn 6.000 tia ra khắp nơi. Hoặc có thể coi đường cong là tập hợp vô số đoạn thẳng, do đó có vô số đỉnh. Nhưng đối với các đường cong đơn giản như hình tròn hay eclipse thì ta có thể chỉ cần tìm và xét 2 điểm trên đó mà tạo với vị trí người chơi một góc lớn nhất. Khi đó thuật toán trên vẫn hoạt động bình thường.

Vậy trên 3D thì làm như thế nào??

Tôi chưa làm trên 3D, vì trên đó mấy cái ánh sáng được lo hết bởi engine rồi, mình chả có việc gì để làm cả. Nhưng mà tư tưởng chắc là cũng như vậy, có thể họ dùng cách thứ nhất, vì cách đó rất chậm nếu làm trên CPU, nhưng mà sẽ rất nhanh trên GPU. Và như thế là chúng ta có Ray Tracing 🙃.