避免战舰游戏随机放置算法中的死局。

Question

我需要一些关于如何构建一个算法来放置多艘船只的建议，根据规则，船只不能重叠或接触（甚至是对角线）。在选择随机位置后，我如何确保还有足够的空间放置其余的船只呢？

例如，我想在一个6x6的二维数组上放置5艘船只，它们的大小分别为：5、4、3、1、1。有多种方法可以安排它们，其中一种如下所示：

 -------------
| 1 1 1 1 1 . |
| . . . . . . |
| 2 2 2 2 . 4 |
| . . . . . . |
| 3 3 3 . . 5 |
| . . . . . . |
 -------------

随机算法看起来像这样：

1. Get next ship
2. Get random cell and orientation
3. Try to fit ship (find any conflicts)
    3a. If ship cannot fit, try different 
        cell and orientation, untill all cells 
        have been tried (function fails)
    3b. If ship fits, get another ship (goto 1) 

但是如果我使用它，我可能会像这样结束（编辑：更改以反映在步骤0中按大小排序的船只）：

 -------------
| . 3 3 3 . 4 |   5
| . . . . . . |
| . 2 2 2 2 . |
| . . . . . . |
| 1 1 1 1 1 . |
| . . . . . . |
 ------------- 

意味着没有足够的空间放置大小为1个小方格的船只。我该如何避免这个问题？我应该如何实现在3b中放置函数 verifyRestShipsWillFit()？

- JockX

Answer 1

使用一些启发式方法，例如先放置最大的船只来对船只进行排序。然后通过从一个空棋盘和完整的船只列表开始使放置递归化。这本质上是一次树形搜索：

请记住，如果您有不可变类，则始终更容易使用递归。在棋盘上放置一艘船会创建一个新的棋盘，而不会改变原棋盘。

Board GetRandomBoard()
{
   List<Ship> ships = { .. }   // List of all ships.
   Board = Board.Empty();
   Board result = PlaceShips(ships, board);
   return result; // You could have a retry here as well if it fails.
}

private Board PlaceShips(IEnumerable<Ship> shipsRemaining, Board board)
{    
   Ship shipToPlace = shipsRemaining.FirstOrDefault();

   // If all ships were placed, we are done.
   if (shipToPlace == null)
      return board;

   int attempts = 0;       
   while (attempts++ < MaxAttempts)
   {
       // Get a position for the new ship that is OK with the current board.
       ShipPosition pos = GetRandomShipPosition(board, shipToPlace); 

       // If it isn't possible to find such a position, this branch is bad.
       if (pos == null)
          return null;

       // Create a new board, including the new ship.
       Board newBoard = new board.WithShip(shipToplace, pos);

       // Recurse by placing remaining ships on the new board.
       board nextBoard = PlaceShips(shipsRemaining.Skip(1).ToList(), newBoard);
       if (nextBoard != null)
          return nextBoard;
   }
   return null;
}

- Anders Forsgren

Answer 2

对于这样的小问题，最简单的方法是这样做：

1. Get next ship
2. Get random cell and orientation
3. Try to fit ship (find any conflicts)
    3a. If ship doesn't fit there, **delete all ships and start over**
    3b. If ship fits, get another ship (goto 1) 

如果您对终止操作非常谨慎，请设置（高）迭代限制并返回到确定性配置。

- David Eisenstat

Answer 3

先放置最大的船只。我的算法与你的完全相同，但在第一步之前，我会添加另一步来按大小对它们进行排序。

编辑：可能在这个地图大小下，算法仍然会失败。在3a和3b之间再添加一步：

3a.1 - if the function fails, restart from scratch.

第二次编辑：有一个替代方案：不是插入船只，而是插入它们的命中框。命中框与船只一样大，并围绕其坐标。允许命中框重叠，只要它们的核心（船只所在的位置）不重叠，并且允许命中框泄漏到地图外（但核心不能泄漏）。

使用任何一种方法，我也会尝试使解决方案独立于地图大小。

- Geeky Guy

---

这仍然不能保证不会发生死路。 - JockX

当您无法定位对象时，我不会立即从头开始重新创建板子。对于大型棋盘，这将是低效的。使用递归搜索需要3或4行额外代码来设置，当无法放置物体时进行回溯。实际上，我至少会有一个计数器来测试已尝试的布局数量；在测试游戏时，您可能会意外指定一些无法放置的船只组合，希望有某种方法来捕获这种情况。 - Peter Webb