我正在开发一款需要随机生成地图的游戏。实际上，地图将是一个巨大的网格，其中大部分是空的，物体分散在各处，按区域分组。其想法是，我首先生成这些区域，然后每个区域类型的单独类处理区域内地图的生成。
我目前正在尝试在网格上随机生成这些区域。区域将始终是矩形或正方形，并且具有任何大小，并且网格本身也可以具有任何大小（再次，矩形或正方形）。
为了简化这一切，我试图在任意大小的网格上生成随机比例的矩形。记录在案，当我说任意时，我的意思是非常大——我们可能会看到高达100000 x 100000的尺寸。区域可能最大为100x100，但同样，脚本应该能够应付任何大小。
只是为了增加一些限制，这些区域不能重叠。最终，区域和每个区域内生成的对象都将被放入MySQL数据库中。
我最初认为，使用二维数组来表示整个网格，并简单地标记其中的空间是可以的，这是在小型网格的初始测试中。我发现对于非常大的网格，Php抱怨超过了内存限制，并且不会执行脚本。
我想过但没有尝试过的另一种方法是在创建区域时将其插入数据库，然后在数据库上运行查询，查看每次需要区域时区域是否为空。我相信我可以做到这一点，但数据库查询的数量将是巨大的。我可以通过消除某些正方形来减少所需的测试数量，我可以通过纯粹的数学方法确定这些正方形是不可用的，但对于大型网格，我们仍然在谈论大量的查询。这会让剧本非常非常耗时，我忍不住觉得没有必要。如果可能的话，我更喜欢用另一种方式做事。
我想到的最后一种方法是纯粹的数学方法，如果我能让它发挥作用，那就太完美了。我只使用了两个变量——最大x和最大y来存储每个轴上的最高值。当测试创建一个区域时，我只检查了新区域的左上角坐标是否低于最大值x和y——如果是，则不能使用该空间。如果其中任何一个更高，就没有问题，区域就创建了。我想，你们中的一些人可能会发现这里的问题，但长话短说，在某些情况下，这个系统会判断一个空空间不可用，所以当我运行脚本时，会出现大量随机的空块。
所以，我被卡住了。我忍不住觉得有一个很好的数学解决方案，它使用了固定数量的变量，但我看不出来。如果不能做到这一点，有人知道另一种方法来实现我想要的吗？
仔细阅读一下，也许会有所帮助。我还没有测试过，但我已经评论了我的意图，所以你应该能够根据它想出一些东西。
//create some globals we will need
$region_id = 1;
$current_x = 0;
$current_y = 0;
$squares = array();
//Create the base grid
$grid = array(GRID_WIDTH);
foreach($grid as $a)
{
$a = array(GRID_HEIGHT);
$a = array_fill(0, count($a), 0);
}
//$grid[0][0] will be the top left square
//Iterates over the grid until it is full
while($current_x != (-1) && $current_y != (-1))
{
//We just need to set these counters back to their minimums
$max_x = $current_x;
$max_y = $current_y;
//Lets see how many spaces we have between current x and end of the row
//$max_x will be the maxiumum newX2
for($x = $current_x; $x<GRID_WIDTH; $x++)
{
if($grid[$x][$current_y]==0)
{
$max_x = $x;
}
}
//Lets create a width between 1 and the max left in the row
$newX1 = $current_x;
$newX2 = rand($current_x, $max_x)
//Now lets see how tall we can make it by going down the y until we hit a square or the end.. do for each x
for($x = $newX1; $x<newX2;$x++)
{
for($y = $current_y; $y<GRID_HEIGHT; $y++)
{
if($grid[$x][$y]==0)
{
//We just need the maxiumum y we can have based on our already determined width
//Since this distance has to be smallest possible distance
//We only let max_y get larger on the first iteration of x
if($y>$max_y && $x==$newX1)
{
$max_y = $y;
}
}
}
}
//lets create a height bettwen 1 and the max
$newY1 = $current_y;
$newY2 = rand($current_y, $max_y);
//create a spacewith these values
occupySpace($newX1, $newX2, $newY1, $newY2, $grid, $region_id);
$squares[] = array($newX1, $newX2, $newY1, $newY2);
//Iterate over the grid looking for an empty space
//First lets set current_x and current_y to -1. We will use this to evalute done
$current_x = -1;
$current_y = -1;
for($x = 0; $x<GRID_WIDTH; $x++)
{
for($y = 0; $y<GRID_HEIGHT; $y++)
{
//Looking for any space that hasn't been occupied, if one is found break both for loops
if($grid[$x][$y]==0)
{
$current_x = $x;
$current_y = $y;
break 2;
}
}
}
}
//fills all spaces in the region with the current region id and increments region id
function occupySpace($x1, $x2, $y1, $y2, &$grid, &$region_id)
{
for($x=$x1; $x<$x2; $x++)
{
for($y=$y1; $y<$y2; $y++)
{
$grid[$x][$y] = $region_id;
}
}
$region_id += 1;
}
?>
更新：此解决方案最初没有跟踪创建的"区域"。现在它们存在于数组$square中。
PS-如果这将是你的脚本/业务的重要组成部分，我会考虑为Grid和region编写一些类，
-
没有必要将每一位信息都保存到数据库中。对于每个矩形，您只需要顶部/左侧坐标+宽度/高度。
-
那么你应该能够通过一个查询获得给定坐标的最大可用空间（例如，获得比你的x大的最小值-x，也位于所需的y空间内）
更新：
对于最大宽度，您可以使用：
选择`x`-：x AS`maxWidth`FROM`test`其中`x`>:xAND（`y`>:y或`y`+`h`>：y）按`y`，`y`+`h排序`限制1
最大高度：
选择`y`-：y AS`maxHeight`FROM`test`其中`y`>:yAND（`x`>:x或`x`+`w`>:x）订单依据`x`，`x`+`w`限制1