Game of Life

Game of Life của Conway là một trò mô phỏng khá là nổi tiếng. Thoạt nhìn trông rất dễ để implement, nhưng xét ở một mức độ nào đó, ví dụ trên một ô lưới có kích thước cực kì lớn, thì nó rất phức tạp để đạt được kết quả tối ưu.

Trò chơi gồm một ô lưới $n \times m$ không giới hạn, mỗi ô (cell) có hai trạng thái alive hoặc dead.

Ở mỗi một thời điểm, toàn bộ ô lưới này được gọi là một thế hệ (generation), và máy tính sẽ tự động biến đổi từ thế hệ này sang thế hệ tiếp theo bằng cách thay đổi các cell trên lưới, theo quy tắc:

Ô sống nào có đúng 2 hoặc 3 ô sống lân cận thì sẽ tiếp tục sống đến thế hệ tiếp theo. Ngược lại thì sẽ thành ô chết.
Ô chết nào có đúng 3 ô sống lân cận thì sẽ trở thành ô sống ở thế hệ tiếp theo.

Nguồn: http://natureofcode.com/book/chapter-7-cellular-automata/

Một trong những cách dễ nhất để implement trò chơi này đó là dùng một mảng 2 chiều $n \times m$, với mỗi phần tử đại diện cho một ô.

Ở mỗi generation thì ta chạy 2 vòng for lồng nhau, đếm tổng số ô "hàng xóm" lân cận, và thực hiện việc biến đổi theo tập luật. Ví dụ hình sau, con số trên mỗi ô biểu diễn số ô sống lân cận của ô đó, biến đổi qua 2 thế hệ liên tiếp nhau:

Nguồn: http://www.paleotechnologist.net/?p=451

Input: Mảng hai chiều A kích thước $n \times m$

1: For i từ $0 \rightarrow n$:
2: For j từ $0 \rightarrow m$:
3: Đếm số ô sống lân cận của ô $A[i, j]$
4: Biến đổi trạng thái ô $A[i, j]$ dựa vào số ô sống đã đếm ở trên
5: Trả về mảng $A$

Output: Mảng hai chiều mới A kích thước $n \times m$

Thuật toán trên có độ phức tạp $O(n m)$ và hoàn toàn không phải là giải pháp tối ưu. Đối với kích thước $n \times m$ càng lớn, thì việc sinh ra generation tiếp theo sẽ càng chậm.

Có một điểm cần lưu ý đối với thuật toán trên đó là việc đếm số ô lân cận cần phải được thực hiện trên mảng đại diện cho generation cũ, chứ không phải trên generation đang được tạo ra (khúc này nếu bạn không hiểu thì không sao, cứ thử implement đi là bị liền nếu không bị thì tốt ).

Có rất nhiều giải pháp để tối ưu thuật toán sinh generation của Game of Life, đa số phục vụ cho mục đích xử lý được trò chơi với kích thước lớn nhất có thể.

Một giải pháp được đề cập đến nhiều nhất đó là thuật toán Hashlife, thể hiện ô lưới của trò chơi bằng Quadtree và sử dụng phương pháp memoize để tăng tốc độ tính toán.

Nguồn: Dr. Dobb's - An Algorithm for Compressing Space and Time

Tiếp đến là các phương pháp sử dụng các phép tính trên bit như ở link tham khảo số 9, 10 và 11.

Sau cùng là các giải pháp sử dụng GPU như giải pháp dùng texture để tính toán với WebGL, hoặc là sử dụng CUDA.

Có thể thấy, việc implement Game of Life là một chủ đề khá là thú vị, vì tùy theo khả năng, nếu ta muốn nó dễ (kích thước giới hạn, cho biết sẵn) thì nó cực kì dễ, nhưng nếu ta muốn nó khó hơn (không giới hạn kích thước), thì nó cũng trở nên cực kì phức tạp.

Đọc thêm:

[1] Conway's Game of Life, Wikipedia
[2] Cellular Automaton, Wikipedia
[3] A discussion of The Game of Life, Stanford University
[4] Cool math: Conways' Game of Life, The Paleotechnologis Blog
[5] The Nature Of Code: Cellular Automata, The Nature Of Code
[6] The Game Of Life, Michael Abrash's Graphics Programming Black Book
[7] An Algorithm for Compressing Space and Time, Dr. Doobs
[8] The Game of Life, part 2: HashLife, The Lowly Programmer
[9] Bitboard Methods for Games, Cameron Browne
[10] Game of Life bit-parallel algorithm, Yann Guidon
[11] What about a Game of Life?, Yann Guidon
[12] A GPU Approach to Conway's Game of Life, Crhis Wellons
[13] Conway's Game of Life on GPU using CUDA, Marek Fišer
[14] An implementation of Conway's Game of LIfe