hiệu quả tìm kiếm quảng trường xung quanh lớn nhất trong lưới 2D

Question

Trong một trò chơi với một bản đồ lưới 2D Tôi đang phải đối mặt với tình huống sau đây:

tôi cần phải tìm ra lớn nhất bounding vuông bao quanh vị trí của người chơi (dấu chấm màu đỏ). Hoặc ít nhất một hình vuông có kích thước tối đa là, vì có thể có nhiều hơn. Lưu ý: hình vuông, không phải hình chữ nhật.

Trong trường hợp này, nó khá dễ dàng để xem quảng trường lớn nhất là 8x8:

Nếu tôi thêm một trở ngại trong bản đồ, khả năng lớn nhất hiện nay là 5x5:

Tôi đang tìm kiếm cách nhanh chóng và hiệu quả cách tìm (hoặc hình vuông tối đa) chứa vị trí trình phát.

gì tôi đang làm là loại brute force:

• Một hình vuông 1x1 luôn là có thể (vị trí người chơi chính nó).
• Sau đó, tôi thử tất cả 2 * 2 ô vuông có chứa trình phát, đó là 4 ô vuông khác nhau, và mỗi ô tôi thực hiện vòng lặp 2 * 2, kiểm tra xem tất cả các ô lưới có rõ ràng không (tường hoặc chướng ngại vật).
• Nếu có thể có 2 * 2 ô vuông, thì tôi thử tất cả 3 ô vuông có thể có 3 * 3 xung quanh người chơi (9 ô vuông khác nhau) và mỗi vòng lặp 3 * 3 để kiểm tra xem không có thu nhỏ.
• Et cetera, cho đến khi kích thước N * N không có hình vuông là có thể.

Nó hoạt động, nó rất đơn giản, nhưng nó cảm thấy rất không hiệu quả. Rõ ràng tôi đang làm rất nhiều kiểm tra dư thừa ở đây, và tôi tự hỏi nếu có một cách thông minh hơn/nhanh hơn để làm điều này. Có ai biết một thuật toán để làm điều này một cách hiệu quả?

(sửa) Bổ sung quan trọng: bên cạnh trình phát di chuyển xung quanh, chướng ngại vật hoặc tường được tự động thêm hoặc di chuyển, vì vậy việc tối ưu hóa bộ nhớ đệm hoặc precalc khó thực hiện ở đây.

Answer 1

Tôi nghĩ rằng bạn có thể cải thiện thuật toán của mình bằng cách, ở mỗi giai đoạn, chỉ cần kiểm tra ranh giới hợp lệ của 'hình vuông lớn nhất hiện có' của bạn. Nó có lẽ dễ dàng hơn để giải thích sơ đồ này ... nhưng về cơ bản. Tất cả những gì bạn cần làm là

**Growth Algorithm** 
repeat 
    search the bounding sub-squares on the valid sides of the largest valid square found so far 
    increase size of square on 'valid' sides and mark newly blocked sides as invalid 
until all sides invalid 

then check if largest valid square can be translated 1 unit diagonally in any of 4 directions 
if so repeat the growth algorithm on each new square until none get bigger 

Bằng cách này, bạn chỉ cần kiểm tra từng ô vuông của hình vuông hợp lệ cuối cùng một lần duy nhất. Vì vậy, một quá trình n^2 nếu hình vuông là n trên mặt của nó. IO don '; t nghĩ rằng bạn có thể làm tốt hơn khi bạn cần phải kiểm tra từng tiểu vuông cho hiệu lực.

Answer 2

Sử dụng biến thể về điều này: Maximum size square sub-matrix with all 1s.

Thuật toán:

Scan up, down, left and right only from the dot to generate the bounds for the 
solution matrix S, not more than 20 in each direction (that's my contribution... :) 

Copy the first row and first column (within the bounds of S) from M[][] to S[][], switching 
zeros for ones and ones for zeros. 

For the remaining entries (i=1 to length S, j=1 to length S) do: 

If M[i][j] is 0 then 
    S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 
    If S[i][j] is within distance of dot 
     Best = max(S[i][j], Best) 
Else 
    S[i][j] = 0 

Answer 3

Dưới đây là một cách tiếp cận hoàn toàn khác nhau:

Bạn giữ aa ma trận 2d kích thước [Chiều dài, 2] Chiều dài được kích thước của bản đồ của bạn (tôi giả sử chiều rộng đối xứng/chiều cao, nhưng nếu không chỉ chọn một trục). Tôi sẽ gọi cột thứ nhất (Chiều dài) (bạn có thể xoay toàn bộ thuật toán 90 độ và gọi hàng này). Mỗi cột chứa 2 giá trị - Vị trí nhỏ nhất & Vị trí tối đa của phạm vi hợp lệ trong cột.

Bạn điền vào ma trận này với các thuật toán sau đây:

Bắt đầu với dấu chấm cột, tìm & cửa hàng min & tối đa vị trí của dãy liền kề trên & dưới dấu chấm. Nếu chấm là tại x, y:

int colMin, colMax; 
for(colMin = y; colMin > 0;) { 
    if(Matrix[x, colMin - 1].IsValid) 
     colMin--; 
    else break; 
} 
for(colMax = y; colMax < maxHeight;) { 
    if(Matrix[x, colMax + 1].IsValid) 
     colMax++; 
    else break; 
} 
MinMaxValid[x, 0] = colMin; 
MinMaxValid[x, 1] = colMax; 

Bạn tiến hành theo cả hai hướng một cách độc lập với các thuật toán sau đây:

int minCol = 0, maxCol = maxWidth; // These hold the min/max range of valid columns 
for(int col = x - 1; col >= 0; col--) { 
    for(colMin = y; colMin > MinMaxValid[col + 1, 0];) { // Cell is only valid if it overlaps to the next range 
     if(Matrix[col, colMin - 1].IsValid) 
      colMin--; 
     else break; 
    } 
    for(colMax = y; colMax < MinMaxValid[col + 1, 1];) { // Cell is only valid if it overlaps to the next range 
     if(Matrix[col, colMax + 1].IsValid) 
      colMax++; 
     else break; 
    } 
    if((colMax - colMin) >= (x - col)) { // if the found range is smaller than the distance for x, it can't be a part of the square 
     MinMaxValid[col, 0] = colMin; 
     MinMaxValid[col, 1] = colMax; 
    } 
    else { 
     minCol = col + 1; 
     break; // We're done on this side 
    } 
} 

for(int col = x + 1; col < maxWidth; col++) { 
    for(colMin = y; colMin > MinMaxValid[col - 1, 0];) { // Cell is only valid if it overlaps to the previous range 
     if(Matrix[col, colMin - 1].IsValid) 
      colMin--; 
     else break; 
    } 
    for(colMax = y; colMax < MinMaxValid[col - 1, 1];) { // Cell is only valid if it overlaps to the previous range 
     if(Matrix[col, colMax + 1].IsValid) 
      colMax++; 
     else break; 
    } 
    if((colMax - colMin) >= (col - x)) { // if the found range is smaller than the distance for x, it can't be a part of the square 
     MinMaxValid[col, 0] = colMin; 
     MinMaxValid[col, 1] = colMax; 
    } 
    else { 
     maxCol = col - 1; 
     break; // We're done on this side 
    } 
} 

Bây giờ bạn đã MinMaxValid bạn điền. Phần tiếp theo là chạy qua các hàng và tìm ra vuông lớn nhất:

int maxSquareSize = 0, maxSquareCol = minCol; 
for(int col = minCol; (MinMaxValid[col, 1] - MinMaxValid[col, 0]) >= (maxCol - col); col++) { 
    for(int squareSize = MinMaxValid[col, 1] - MinMaxValid[col, 0] + 1; squareSize > maxSquareSize; squareSize--) { 
     if((Min(MinMaxValid[col, 1], MinMaxValid[col + squareSize - 1, 1]) - Max(MinMaxValid[col, 0], MinMaxValid[col + squareSize - 1, 0])) >= (squareSize) { 
     maxSquareSize = squareSize; 
     maxSquareCol = col; 
     break; 
     } 
    } 
} 

Phần cuối cùng làm việc như thế này:

Bất kỳ cột có thể tham gia vào một hình vuông chỉ lớn như đó là chiều cao. Để làm như vậy, liên kết của phạm vi cột hiện tại và phạm vi tại col + squareSize - 1 phải có kích thước tối thiểu là square.

Bây giờ đến phần tốt nhất! Bất cứ khi nào cảnh thay đổi (Hình vuông trở nên không hợp lệ, dấu chấm di chuyển, v.v.) bạn chỉ có thể làm mất hiệu lực một phạm vi nhất định của ma trận MinMaxValid và đánh giá lại khi cần thiết. Tôi không bao gồm logic này vì câu trả lời này đủ dài, nhưng đó là phần dễ dàng (Về cơ bản, bạn giảm phạm vi cột để phù hợp với kịch bản mới và quét lại cả hai hướng).

Tôi phải nói rằng tôi chưa thử cái này, nhưng ngay cả khi nó không hoạt động (Và hãy cho tôi biết để tôi có thể xóa bình luận này :-), nó phải gần với một giải pháp hợp lệ.