我的战舰实现的网格数据结构和布局算法？

Question

我正在尝试制作自己的游戏《战舰》（德语：Schife versenken）。

我将游戏板制作为dataframe（10x10）。船只的坐标是随机创建的。我有4种不同的船只（从5到2的长度开始）。这些船中的每一个都是一个清单。列表中的元素由随机创建的起始坐标（ship_row，ship_col）组成，并且取决于船舶是水平还是垂直，其他元素是ship_row+n或ship_col+n。

问题：船的长度可能超过了船长dataframe。我如何为这些发货清单设置边界，并且如果第一个发货清单超出边界，如何创建新的发货清单以创建循环？

这是我的示例船舶Schlachtschiff的代码：

board=[]

for n in range (10):
    board.append(['O']*10)

board = pd.DataFrame(board)

g= rd.randint(1,2)
random_row(board)
random_col(board)
ship_row = random_row(board)
ship_col = random_col(board)


for Schlachtschiff in board:
    if g==1:
            Schlachtschiff = [(ship_row, ship_col),(ship_row, ship_col+1),(ship_row, ship_col+2),(ship_row, ship_col+3),(ship_row, ship_col+4)]
    else:
            Schlachtschiff= [(ship_row, ship_col),(ship_row+1, ship_col),(ship_row+2, ship_col),(ship_row+3, ship_col),(ship_row+4, ship_col)]

我试图通过查看已创建列表的最后一个元素，使用while循环来解决该问题，但这不会停止：

while Schlachtschiff[-1] not in board:
    if g==1:
            Schlachtschiff = [(ship_row, ship_col),(ship_row, ship_col+1),(ship_row, ship_col+2),(ship_row, ship_col+3),(ship_row, ship_col+4)]
    else:
            Schlachtschiff= [(ship_row, ship_col),(ship_row+1, ship_col),(ship_row+2, ship_col),(ship_row+3, ship_col),(ship_row+4, ship_col)]

    if Schlachtschiff[-1] in board:
        break

为了防止飞船重叠，我编写了以下代码（请注意：“克罗伊泽尔是第二种飞船，与上面的创建方式相同）：

for i in Schlachtschiff:

    for j in Kreuzer:
        if i == j:
            random_row(board)
            random_col(board)
            ship_row_1 = random_row(board)
            ship_col_1 = random_col(board)
            g= rd.randint(1,2)

            if g==1:
                Kreuzer = [(ship_row, ship_col),(ship_row, ship_col+1),(ship_row, ship_col+2)]

            else:
                Kreuzer = [(ship_row, ship_col),(ship_row+1, ship_col),(ship_row+2, ship_col)]

现在，由于@smci的帮助，我不再遇到该问题。我的代码现在看起来像这样：

board = []
board = pd.DataFrame(data='?', index=range(1,10+1), columns=list('ABCDEFGHIJ'))
print(board)
def random_row(board):
    return rd.randint(0,len(board)-1)

def random_col(board):
     return rd.randint(0,len(board)-1)
def Schiff_erstellen(Schiff,Start,Stop):
    g= rd.randint(1,2)
    random_row(board)
    random_col(board)
    ship_row = random_row(board)
    ship_col = random_col(board)
    Schiff=[(ship_row, ship_col)]
    while Schiff[-1] > (ship_row_probe, ship_col_probe):
    g= rd.randint(1,2)
    random_row(board)
    random_col(board)
    ship_row = random_row(board)
    ship_col = random_col(board)
    Schiff=[(ship_row, ship_col)]
    if g == 1:
        for i in range(Start,Stop):
            Schiff.append((ship_row, ship_col+i))
    else:
        for i in range(Start,Stop):
            Schiff.append((ship_row+i, ship_col))
    if Schiff[-1] <= (ship_row_probe, ship_col_probe):
        break

return Schiff

Answer 1

首先让我们看一下放置一艘船。一艘船是一条线段，因此您需要三个随机数来表征它：布尔方向（水平或垂直）和左上角的坐标。我假设对于任何给定的船，长度是固定的。现在，如果您知道长度为L且板为Mx N，您可以像这样限制位置：

def generate_ship(L, M, N):
    """ Returns the slices to fill in on an MxN board to get a random L-sized ship """
    # True = vertical
    direction = random.randrange(2)
    rsize = direction * (L - 1)
    csize = (not direction) * (L - 1)
    row = random.randrange(M - rsize)
    col = random.randrange(N - csize)
    return slice(row, row + 1 + rsize), slice(col, col + 1 + csize)

乘以direction和not direction可以省去使用if语句来处理不同情况的麻烦。您可以直接将此函数的结果与 一起使用df.iloc，因为它是一个切片元组：

import numpy as np
import pandas as pd
import random
from string import ascii_uppercase

M = N = 10
df = pd.DataFrame(np.tile([[' ']], [M, N]), index=np.arange(M), columns=list(ascii_uppercase[:N]))
df.iloc[generate_ship(3, M, N)] = 'O'

到目前为止一切顺利，但现在您想要生成多艘不重叠的船只。最简单的方法是蛮力：从最大的船开始，不断生成一艘新船，直到得到一艘不重叠的船：

M = N = 10
df = pd.DataFrame(np.tile([[' ']], [M, N]), index=np.arange(M), columns=list(ascii_uppercase[:N]))
for L in (5, 4, 4, 3, 3, 2, 2, 2):
    while True:
        ship = generate_ship(L, M, N)
        if (df.iloc[ship] == ' ').all():
            df.iloc[ship] = 'O'
            break

一种更具确定性的方法是维护可用坐标的网格，并在每次生成船舶时对其进行修剪。例如，您可以维护一个 2xMxN 数组，记录可以放置在给定位置的最大船舶。每次你放置一艘船时，你都会更新这个数组。要生成，您只需通过以下方式从可用位置中进行选择np.argwhere(options[direction] >= L)：

class ShipGenerator:
    def __init__(self, M, N):
        horiz = np.arange(N, 0, -1)[None, :].repeat(M, axis=0)
        vert = np.arange(M, 0, -1)[:, None].repeat(N, axis=1)
        self.options = np.stack((horiz, vert), axis=0)

    def generate_ship(self, L):
        options = np.argwhere(self.options >= L)
        n = len(options)
        if n == 0:
            raise ValueError(f'Unable to generate ship of size {L}. '
                             f'Max remaining space is {self.options.max(None)}')

        direction, row, col = options[random.randrange(len(options))]
        row_end = row + 1 + direction * (L - 1)
        col_end = col + 1 + (not direction) * (L - 1)

        self.clear_region(row, row_end, col, col_end)
        return (slice(row, row_end), slice(col, col_end))

    def clear_region(self, r_start, r_end, c_start, c_end, margin=0):
        """ Once a ship has been generated, update the map to restrict squared around it """
        r_start = max(r_start - margin, 0)
        c_start = max(c_start - margin, 0)
        r_end = min(r_end + margin, self.options.shape[1])
        c_end = min(c_end + margin, self.options.shape[2])

        # Update ship + margin
        self.options[:, r_start:r_end, c_start:c_end] = 0

        # Update horizontal restrictions
        self.options[0, r_start:r_end, :c_start] = \
            np.minimum(self.options[0, r_start:r_end, :c_start],
                       np.arange(c_start, 0, -1))

        # Update vertical restrictions
        self.options[1, :r_start, c_start:c_end] = \
            np.minimum(self.options[1, :r_start, c_start:c_end],
                       np.arange(r_start, 0, -1)[:, None])

生成板现在变得更加简单：

df = pd.DataFrame(np.tile([[' ']], [M, N]), index=np.arange(M), columns=list(ascii_uppercase[:N]))
generator = ShipGenerator(M, N)
for L in (5, 4, 4, 3, 3, 2, 2, 2):
    df.iloc[generator.generate_ship(L)] = 'O'

您可能需要维护一个板来记录敌人的攻击，还需要维护各个船只的元数据。在板上存储元数据会很浪费。相反，您可以创建一个Ship包含元数据的对象，包括generate_ship. 然后，该板将成为一组标签，这些标签是 s 列表的索引Ship。