Câu hỏi về Game of Life khác (lưới vô hạn)?

Question

Tôi đã chơi đùa với Trò chơi của Conway và gần đây đã khám phá ra một số triển khai nhanh chóng đáng kinh ngạc như Hashlife và Golly. (tải xuống Golly tại đây - http://golly.sourceforge.net/)

Một điều mà tôi không thể hiểu được là làm thế nào để các nhà lập trình thực hiện lưới vô hạn? Chúng tôi không thể giữ một mảng vô hạn của bất cứ điều gì, nếu bạn chạy golly và nhận được một vài tàu lượn bay qua các cạnh, chờ một vài phút và phóng to ngay, bạn sẽ thấy những chiếc tàu lượn vẫn còn trong không gian chạy đi, Vì vậy, làm thế nào trong tên thần là khái niệm này của vô cùng xử lý với lập trình? Có một mô hình tài liệu hay gì không?

Rất cám ơn

Answer 1

Wikipedia explains it. Ý tưởng cơ bản là Trò chơi cuộc sống của Conway trưng bày địa phương, vì thông tin di chuyển với tốc độ chậm so với kích thước mẫu và mật độ tối đa của các ô được lấp đầy khoảng 1/2 ô ở bất kỳ vùng nào. (Thêm sẽ giết chết các tế bào do tình trạng quá tải.)

Vì có địa phương, bạn có thể tách riêng trường trong các phần khác nhau và mô phỏng từng phần một cách độc lập. Nếu bạn chọn địa phương của bạn tốt, bạn sẽ thường thấy các mẫu giống nhau. Bạn có thể mô phỏng cách những người phát triển và lưu trữ các kết quả trong bảng tra cứu, để các trường hợp khác của cùng một mẫu không cần phải được mô phỏng nhiều lần. Kết hợp các mẫu liền kề vào các 'metapatterns' lớn hơn cũng cho phép bạn tính toán trước các giá trị đó, v.v.

Answer 2

Có thể biểu thị các nút sống với một số loại ma trận thưa thớt trong tình huống này. Ví dụ: nếu chúng tôi lưu trữ danh sách các cặp (LivingNode, Coordinate) thay vì một mảng là Nodes trong đó mỗi mạng sống hoặc chết, chúng tôi chỉ đơn giản là thay đổi Coordinates thay vì tăng kích thước của mảng. Do đó, không gian cần thiết cho điều này là tỷ lệ thuận với số lượng LivingNodes.

Giải pháp này không hoạt động đối với các tiểu bang nơi số lượng nút sống liên tục tăng, nhưng nó hoạt động rất tốt cho tàu lượn.

CHỈNH SỬA: Vì vậy, điều đó đã nằm ngoài đỉnh đầu của tôi. Biến ra Wikipedia has an article hiển thị giải pháp tốt hơn nhiều. Oh well! :) Thưởng thức.