Просто обратите внимание, я буду использовать синтаксис ООП, чтобы упростить это, но это недопустимый код.Давайте сначала создадим интерфейс для определения желаемого поведения:
class CityBlock {
Building[] buildings // should initially contain one building taking up the whole CityBlock
double width
double height
double maxBuildingSize
double minBuildingSize
splitBuilding(horizontal/vertical, coord) // This will split a building horizontally/vertically
createRandomBuildings() // this is what we want to create!
}
class Building {
Point position // position of top-left corner
Building[] subBuildings // buildings created by subdivision
double width
double height
double size() { return width * height }
}
Теперь самое интересное!Давайте попробуем сделать метод createRandomBuildings().Подход, который я выберу, состоит в том, чтобы многократно подразделять здания, пока они не будут между 2 * minBuildingSize (меньше, чем это означает, что ни одно подразделение не может создать два действительных здания) и maxBuildingSize.
ВАЖНОЕ ПРИМЕЧАНИЕ: Этот подход гарантирует действительные здания, только если maxBuildingSize >= 2 * minBuildingSize, даже если допустимое подразделение возможно.Учитывая ваш вариант использования, я полагал, что ограничение размера не будет создавать никаких проблем, и более «случайное» решение будет лучше, чем более детерминированное.
Давайте доберемся до этого!Мы создадим рекурсивную функцию с именем subdivide для выполнения тяжелой работы.
Building[] subdivide(Building b, horizontal/vertical) {} // Subdivides b into a random number of other buildings
Способ, которым я подразделяю каждое здание, состоит в том, чтобы разбить его на случайное количество горизонтальных / вертикальных сегментов.Пример.
Из этого
К этому
ПРИМЕЧАНИЕ: Чтобы упростить дело, я собираюсь рассмотреть это, рассматривая подразделение как вертикальное, как на рисунке выше.Для горизонтального подразделения просто поменяйте местами ширину / высоту.
Конечно, мы не можем использовать любое количество подразделений.Слишком много, и все получающиеся здания будут слишком маленькими.Поэтому мы должны сначала определить максимальное количество подразделений, которое позволит нам создавать действительные здания.
minSubdivisionWidth = minSize / b.height // ensures that subdivisionWidth * b.height >= minSize
maxSubdivisions = floor(b.width / minSubdivisionWidth)
subdivisions = randomInt(2, maxSubdivisions)
Теперь, когда у нас есть действительное количество подразделений, нам нужно расположить их случайным образом, обеспечивая при этом здания.не слишком маленький.Для этого давайте разделим имеющееся у нас пространство на две части: минимум пробел и свободный пробел.Каждое подразделение должно иметь минимальное пространство, но есть также свободное (или оставшееся) пространство, равное b.size() - minBuildingSize * subdivisions.Это свободное пространство - это то, что мы хотим случайным образом распределить среди наших подразделенных прямоугольников.
Синий - это минимальное пространство, а розовый - этосвободное пространство
Давайте выделим это пространство:
widths[] // This will be the widths of our subdivided buildings
freeWidth = b.width - minSubdivisionWidth * subdivisions
weights[] // randomly assigned weight for free space
sumWeight
for i = 1 to subdivisions {
randWeight = random()
weights[i] = randWeight
sumWeight += randWeight
}
for i = 1 to subdivisions {
widths[i] = minSubdivisionWidth + (weights[i] / sumWeight) * freeWidth
}
И теперь мы можем сделать фактическое подразделение:
// transform individual widths into coordinates for building split
cumulativeWidth = 0
for i = 1 to (subdivisions - 1) {
cumulativeWidth += widths[i]
splitBuilding(vertical, cumulativeWidth)
}
Мы почтитам!Теперь нам просто нужен фрагмент, чтобы случайно не подразделить, если здание ниже максимума:
probToNotSubdivide = .3 // obviously change this to whatever
if b.size() < maxBuildingSize and randomDouble(0, 1) <= probToNotSubdivide { return }
Один, чтобы не подразделить, если здание слишком маленькое:
if b.size() < minBuildingSize * 2 { return }
Один, чтобы неподразделите, если это отрежет здание от края блока:
/*
If the building is touching a horizontal edge, vertical subdivisions
will not cut anything off. If the building is touching both
vertical edges, one subdivision can be made.
*/
if not (b.position.y == 0 or (b.position.y + b.height) == cityBlock.height) {
if b.width == cityBlock.width {
// do one subdivision and recurse
splitBuilding(vertical, randomDouble(minSubdivisionWidth, cityBlock.width - minSubdivisionWidth)
for subBuilding in b.subBuildings {
subdivide(horizontal, subBuilding)
}
return
} else { return }
}
Добавьте немного рекурсии в конце и ...
Building[] subdivide(Building b, horizontal/vertical) {
// exit conditions
if b.size() < maxBuildingSize and randomDouble(0, 1) <= probToNotSubdivide { return }
if b.size() < minBuildingSize * 2 { return }
/*
If the building is touching a horizontal edge, vertical subdivisions
will not cut anything off. If the building is touching both
vertical edges, one subdivision can be made.
*/
if not (b.position.y == 0 or (b.position.y + b.height) == cityBlock.height) {
if b.width == cityBlock.width {
// do one subdivision and recurse
splitBuilding(vertical, randomDouble(minSubdivisionWidth, cityBlock.width - minSubdivisionWidth)
for subBuilding in b.subBuildings {
subdivide(horizontal, subBuilding)
}
return
} else { return }
}
// get # subdivisions
minSubdivisionWidth = minSize / b.height // ensures that subdivisionWidth * b.height <= minSize
maxSubdivisions = floor(b.width / minSubdivisionWidth)
subdivisions = randomInt(2, maxSubdivisions)
// get subdivision widths
widths[] // This will be the widths of our subdivided buildings
freeWidth = b.width - minSubdivisionWidth * subdivisions
weights[] // randomly assigned weight for free space
sumWeight
for i = 1 to subdivisions {
randWeight = random()
weights[i] = randWeight
sumWeight += randWeight
}
for i = 1 to subdivisions {
widths[i] = minSubdivisionWidth + (weights[i] / sumWeight) * freeWidth
}
// transform individual widths into coordinates for building split
cumulativeWidth = 0
for i = 1 to (subdivisions - 1) {
cumulativeWidth += widths[i]
splitBuilding(vertical, cumulativeWidth)
}
// recurse
for subBuilding in b.subBuildings {
subdivide(horizontal, subBuilding)
}
}
И это все!Теперь у нас есть createRandomBuildings() { subdivide(vertical, initialBuilding) }, и мы разделили наш городской квартал.
PS Опять же, этот код не должен быть действительным, и это также очень длинный пост.Если что-то здесь не работает правильно, отредактируйте / прокомментируйте этот ответ.Я надеюсь, что это дает некоторое представление о подходе, который вы могли бы использовать.
РЕДАКТИРОВАТЬ: Чтобы уточнить, вы должны переключаться между горизонтальным и вертикальным подразделениями на каждом уровне рекурсии.