3

我需要一些关于根据船舶不能重叠或接触（甚至对角线）的规则构建一种算法以将许多船舶放置在板上的建议。在随机选择一个位置后，我怎样才能确保我仍然有足够的空间容纳其他船只？

例如，我想在 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 格大小的船没有地方。我怎样才能避免这样的问题？我将如何实现一个verifyRestShipsWillFit()放置在 3b 中的功能？

4

3 回答 3

2

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

请记住，如果您有不可变的类，使用递归总是更容易。将一艘船放在棋盘上会创建一个新棋盘，而无需更改棋盘。

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;
}
于 2013-05-02T12:10:02.257 回答
1

对于像这样的小问题，这是最容易做到的

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)

如果您对终止有偏执，请设置（高）迭代限制并回退到确定性配置。

于 2013-05-02T12:01:01.407 回答
0

首先放置最大的船只。我的算法和你的完全一样，但是在第 1 步之前，我会添加另一个步骤来按大小对它们进行排序。

编辑：在这种地图大小的情况下，alghotirm 可能仍然会失败。在 3a 和 3b 之间添加另一个步骤：

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

第二次编辑：还有另一种选择：不是插入船只，而是插入它们的碰撞箱。一个碰撞箱与一艘船及其周围的坐标一样大。允许 hitboxes 重叠，只要它们的核心（船所在的位置）不重叠，并且还允许 hitboxes 泄漏到地图之外（但同样，核心不能泄漏）。

无论使用哪种方法，我都会尝试使解决方案独立于地图大小。

于 2013-05-02T11:57:53.330 回答