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.
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:
- [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