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:


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:


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.

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:

Gõ xong nhấn Ctrl + Enter để gửi. Bạn không thể xóa comment sau khi gửi.
    Đừng lo. Mình không có spam gì đâu :D Và bạn có thể unsubscribe bất cứ lúc nào.
    Nếu không thích, thì các bạn có thể tự subscribe vào RSS feed của mình.