Tìm các mẫu trong trò chơi Câu đố

Question

Tôi đã tự hỏi, đó là các thuật toán được sử dụng phổ biến nhất được áp dụng cho việc tìm kiếm các mẫu trong trò chơi xếp hình phù hợp với lưới ô.

Tôi biết rằng phụ thuộc vào nhiều yếu tố, như loại mẫu Bạn muốn phát hiện hoặc các quy tắc của trò chơi ... nhưng tôi muốn biết thuật toán thường được sử dụng nhất trong loại vấn đề đó là gì ..

Ví dụ: các trò chơi như cột, bejeweled, thậm chí là Tetris. Tôi cũng muốn biết nếu phát hiện các mẫu bằng "lực lượng vũ phu" (như, quét tất cả các lưới cố gắng tìm ba tế bào liền kề cùng màu) là tồi tệ nhất đáng kể khi sử dụng các thuật toán đặc biệt trong các lưới rất nhỏ, như 4 X 4 ví dụ (và một lần nữa, tôi biết điều đó phụ thuộc vào loại trò chơi và quy tắc ...)

Cấu trúc nào thường được sử dụng trong loại trò chơi này?

Answer 1

Nó luôn phụ thuộc vào tên miền. Nhưng cũng có hai tình huống mà bạn muốn thực hiện các loại tìm kiếm này. Tình hình là sau khi di chuyển (một sự thay đổi cho lĩnh vực trò chơi được thực hiện bởi người chơi), và khác sẽ là nếu/khi toàn bộ hội đồng quản trị đã thay đổi.

Trong Tetris, bạn sẽ không cần phải quét toàn bộ bảng sau khi một mảnh bị rơi. Bạn chỉ cần phải tìm kiếm các hàng mảnh được chạm vào.

Trong trò chơi match-3 như Bejeweled, khi bạn đổi hai phần liền kề một lúc, trước tiên bạn sẽ chạy tìm kiếm được bản địa hóa theo từng hướng xung quanh mỗi ô vuông thay đổi để xem có phần nào được kích hoạt hay không. Sau đó, nếu họ có, trò chơi sẽ đổ một số mảnh ngẫu nhiên mới lên bảng. Bây giờ, bạn có thể chạy cùng một tìm kiếm được bản địa hóa quanh mỗi ô vuông được thay đổi, nhưng điều đó có thể liên quan đến rất nhiều câu lệnh if và thực sự có thể chậm hơn để quét toàn bộ bảng từ trên xuống dưới cùng bên phải. Nó phụ thuộc vào việc thực hiện của bạn và sẽ yêu cầu lược tả.

Như Adrian nói, một mảng 2D đơn giản đủ. Tuy nhiên, thông thường, bạn có thể thêm một "biên giới" của các pixel xung quanh mảng này, để đơn giản hóa khía cạnh tìm kiếm-cho-mẫu. Nếu không có đường viền, bạn phải có các câu lệnh if dọc theo hình vuông cạnh có nội dung "tốt, nếu bạn ở hàng trên cùng, đừng tìm kiếm (và rời khỏi mảng)".Với một đường viền xung quanh nó, bạn có thể an toàn chỉ tìm kiếm thông qua mọi thứ: tiết kiệm cho mình các câu lệnh if, tiết kiệm cho mình sự phân nhánh, tiết kiệm các vấn đề đường ống, tìm kiếm nhanh hơn.

Với Jon: những thứ này thực sự quan trọng trong cài đặt hiệu suất cao, ngay cả trên các máy hiện đại, nếu bạn đang thực hiện thuật toán tìm kiếm để giải quyết trò chơi. Nếu bạn đang có, bạn muốn mô phỏng cơ bản của bạn để chạy càng nhanh càng tốt để tìm kiếm càng sâu càng tốt trong các chu kỳ ít nhất.

Answer 2

Về thuật toán: Nó chắc chắn phụ thuộc vào trò chơi. Ví dụ cho tetris, bạn chỉ phải quét từng hàng nếu nó có cùng màu. Tôi thậm chí không thể nghĩ ra điều gì đó sẽ không bằng phương pháp bạo lực trong trường hợp này. Nhưng đối với hầu hết các trò chơi giản dị, sức mạnh vũ phu nên được hoàn toàn tốt đẹp. Nhận dạng mẫu sẽ không đáng kể so với đồ họa và xử lý âm thanh.

Về cấu trúc: Một 2D-Array đơn giản sẽ đủ để đại diện cho bảng.

Answer 3

Với tốc độ máy tính trung bình những ngày này, nếu đó là thời gian thực khi người dùng đang chơi trò chơi, nó có thể sẽ không thành vấn đề (EDIT: chỉ dành cho các bảng trò chơi rất nhỏ). Chắc chắn, nó sẽ phụ thuộc vào sự phức tạp của logic trò chơi, nhưng cũng nhanh như thế nào mã sẽ chạy trên máy mục tiêu (tức là, đây là một trò chơi trang web JavaScript hoặc ứng dụng Windows được viết bằng C++).

Nếu điều này là dành cho một cái gì đó như mô phỏng chiến lược trò chơi, thì hãy sử dụng thuật toán hiệu quả hơn.

Một chiến lược hiệu quả hơn có thể liên quan đến việc theo dõi các thay đổi gia tăng đối với bảng trò chơi, thay vì quét lại toàn bộ bảng mỗi lần.