2025, Nov 01 08:16
Устранение направленного перекоса потока воды на клеточной сетке
Почему симметричные правила дают перекос потока на клеточной сетке и как этого избежать. Разбираем ошибки порядка проверок, буферизацию и честный алгоритм выбора.
Устранение направленного перекоса в потоках воды на клеточной сетке
При моделировании течения воды по сетке клеток незаметные особенности порядка проверок в условной логике способны исказить результат. Частый симптом — вода постепенно «уползает» в одну горизонтальную сторону, хотя правила задумывались симметричными. Ниже — реальный шаблон, который провоцирует такой перекос, и вариант его переработки, чтобы выбор оставался честным и поддерживаемым.
Проблемное дерево решений
Суть проста: на каждом кадре клетка пытается передать небольшую порцию воды в одну соседнюю клетку по правилам пригодности. Соседство задано структурой из двух элементов на направление: по индексу 0 — объект соседней клетки, по индексу 1 — признак «слишком высокая» (если True, в неё сливать нельзя). Ниже пример сильно вложенного дерева решений: сначала явно предпочитается Юг, затем с дополнительными развилками сравниваются Запад и Восток, и в конце проверяется Север.
import random
def disperse_liquid_step(self):
# self.<dir>_ref[0] = объект соседней клетки
# self.<dir>_ref[1] = признак «выше допустимого»
target_cell = self
if self.water > FLOW:
# Юг существует
if self.south_ref != None:
# Юг не выше допустимого
if self.south_ref[1] != True:
# Юг не заполнен
if self.south_ref[0].water < (100-FLOW):
target_cell = self.south_ref[0]
# Юг заполнен
else:
# Юг заполнен, Запад существует
if self.west_ref != None:
# Запад не выше допустимого
if self.west_ref[1] != True:
# Запад не заполнен
if self.west_ref[0].water < (100 - FLOW):
# Проверяем Восток
# Восток существует
if self.east_ref != None:
# Восток выше допустимого
if self.east_ref[1] == True:
target_cell = self.west_ref[0]
# Восток не выше допустимого
else:
# Восток не заполнен
if self.east_ref[0].water <= (100 - FLOW):
# На Востоке воды меньше, чем у текущей клетки
if self.east_ref[0].water < self.water:
# На Западе воды меньше, чем у текущей клетки
if self.west_ref[0].water < self.water:
if self.east_ref[0].water > self.west_ref[0].water:
target_cell = self.west_ref[0]
elif self.east_ref[0].water < self.west_ref[0].water:
target_cell = self.east_ref[0]
else:
target_cell = random.choice([self.east_ref[0], self.west_ref[0]])
# На Западе столько же или больше, чем у текущей клетки
else:
target_cell = self.east_ref[0]
# На Востоке столько же или больше, чем у текущей клетки
else:
target_cell = self.west_ref[0]
# Востока нет
else:
target_cell = self.west_ref[0]
# Запад заполнен
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Запад выше допустимого
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Юг заполнен, Запада нет
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Юг выше допустимого
else:
# Запад существует
if self.west_ref != None:
# Запад не выше допустимого
if self.west_ref[1] != True:
# Запад не заполнен
if self.west_ref[0].water < (100 - FLOW):
# Проверяем Восток
# Восток существует
if self.east_ref != None:
# Восток выше допустимого
if self.east_ref[1] == True:
target_cell = self.west_ref[0]
# Восток не выше допустимого
else:
# Восток не заполнен
if self.east_ref[0].water < (100 - FLOW):
# На Востоке воды меньше, чем у текущей клетки
if self.east_ref[0].water < self.water:
# На Западе воды меньше, чем у текущей клетки
if self.west_ref[0].water < self.water:
if self.east_ref[0].water > self.west_ref[0].water:
target_cell = self.west_ref[0]
elif self.east_ref[0].water < self.west_ref[0].water:
target_cell = self.east_ref[0]
else:
target_cell = random.choice([self.east_ref[0], self.west_ref[0]])
# На Западе столько же или больше, чем у текущей клетки
else:
target_cell = self.east_ref[0]
# На Востоке столько же или больше, чем у текущей клетки
else:
target_cell = self.west_ref[0]
# Востока нет
else:
target_cell = self.west_ref[0]
# Запад заполнен
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Запад выше допустимого
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Запада нет
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Юга нет
else:
# Запад существует
if self.west_ref != None:
# Запад не выше допустимого
if self.west_ref[1] != True:
# Запад не заполнен
if self.west_ref[0].water < (100 - FLOW):
# Проверяем Восток
# Восток существует
if self.east_ref != None:
# Восток выше допустимого
if self.east_ref[1] == True:
target_cell = self.west_ref[0]
# Восток не выше допустимого
else:
# Восток не заполнен
if self.east_ref[0].water < (100 - FLOW):
# На Востоке воды меньше, чем у текущей клетки
if self.east_ref[0].water < self.water:
# На Западе воды меньше, чем у текущей клетки
if self.west_ref[0].water < self.water:
if self.east_ref[0].water > self.west_ref[0].water:
target_cell = self.west_ref[0]
elif self.east_ref[0].water < self.west_ref[0].water:
target_cell = self.east_ref[0]
else:
target_cell = random.choice([self.east_ref[0], self.west_ref[0]])
# На Западе столько же или больше, чем у текущей клетки
else:
target_cell = self.east_ref[0]
# На Востоке столько же или больше, чем у текущей клетки
else:
target_cell = self.west_ref[0]
# Востока нет
else:
target_cell = self.west_ref[0]
# Запад заполнен
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Запад выше допустимого
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Запада нет
else:
# Восток существует
if self.east_ref != None:
# Восток не выше допустимого
if self.east_ref[1] != True:
# Восток не заполнен
if self.east_ref[0].water < (100-FLOW):
target_cell = self.east_ref
# Восток заполнен
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Восток выше допустимого
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
# Востока нет
else:
# Север существует
if self.north_ref != None:
# Север не выше допустимого
if self.north_ref[1] != True:
# Север не заполнен
if self.north_ref[0].water < (100 - FLOW):
target_cell = self.north_ref
Что происходит на самом деле
Форма дерева решений имеет значение. Если одну горизонтальную сторону проверять раньше другой, она «побеждает» всякий раз, когда обе подходят, а ранние проверки обрывают оставшиеся ветки. Иначе говоря, порядок сравнений и ветвлений может создать предпочтение, даже если вы хотели «честного» выбора. Поэтому вложенное дерево вроде приведённого чаще выбирает Восток: его условия подтверждаются раньше Запада в нескольких ветках, а Запад берётся только после того, как Восток не проходит через ряд проверок. Этого одного эффекта порядка уже достаточно, чтобы перекосить симуляцию.
Есть и практический аспект. Если вы проходите клетки по порядку и сразу изменяете объём воды, ранние клетки меняют состояние так, что решения для поздних клеток смещаются. Буферизуйте результат на кадр: сначала вычислите, куда вода должна пойти из каждой клетки, и только потом применяйте переносы. Так порядок итерации не будет влиять на исход.
Более простой и проверяемый алгоритм потока
Надёжный способ избежать скрытого перекоса — отделить проверки по направлениям, собрать все подходящие варианты и выбрать среди них в одном месте. Такой подход сохраняет симметрию правил, уменьшает ветвление и позволяет легко вводить критерии равенства без неявного приоритета одной стороны. Ниже — компактная реализация этой идеи. Соглашение о соседях прежнее: для направления в индексе 0 объект соседней клетки, в индексе 1 — признак «высокая».
import random
FLOW = 10 # минимально переносимое количество
class Cell:
def __init__(self, level=0, raised=False):
self.level = level
self.raised = raised
self.north_ref = None
self.south_ref = None
self.east_ref = None
self.west_ref = None
def can_drain_into(self, ref):
return ref and not ref[1] and ref[0].level < (100 - FLOW)
def decide_flow(self):
target = self
if self.level <= FLOW:
return target
# Немедленный приоритет Югу, если он подходит
if self.can_drain_into(self.south_ref):
return self.south_ref[0]
# Симметрично собираем боковые варианты
lateral = []
if self.can_drain_into(self.west_ref):
lateral.append(self.west_ref[0])
if self.can_drain_into(self.east_ref):
lateral.append(self.east_ref[0])
# Разрешение ничьей между Западом и Востоком, когда оба валидны
if self.west_ref and self.east_ref:
west_ok = self.west_ref[0] in lateral
east_ok = self.east_ref[0] in lateral
if west_ok and east_ok:
w_amt = self.west_ref[0].level
e_amt = self.east_ref[0].level
if w_amt < self.level or e_amt < self.level:
if w_amt < e_amt:
return self.west_ref[0]
elif e_amt < w_amt:
return self.east_ref[0]
else:
return random.choice([self.east_ref[0], self.west_ref[0]])
else:
return self.west_ref[0] # ветка по умолчанию, как в исходной логике
# Если доступен только один боковой вариант, используем его
if lateral:
return random.choice(lateral)
# И, наконец, рассматриваем Север
if self.can_drain_into(self.north_ref):
return self.north_ref[0]
return target
Почему это работает
Разделение проверок направлений на небольшие предикаты и выбор из собранного набора кандидатов устраняет неявный приоритет, возникающий из-за порядка ветвлений. Когда и Запад, и Восток допустимы, код последовательно сравнивает уровни воды и, в случае равенства, честно выбирает случайно. Поскольку у Юга и Севера своя роль в наборе правил, их можно обрабатывать явно, не возвращая скрытую асимметрию. Такой подход проще понимать и тестировать: каждое условие выражено один раз, а финальный выбор централизован.
Практические выводы
Отделяйте проверки пригодности от выбора — так вы сможете рассуждать о них изолированно и не привносить неумышленные предпочтения порядком if/else. Если вы обновляете воду «на месте» во время обхода сетки, сначала буферизуйте решения для всех клеток и только затем применяйте изменения; это исключит влияние порядка итерации на направление потока. Переработка в сторону небольших вспомогательных функций не только уменьшает глубину ветвлений, но и делает правила потока расширяемыми и удобными для отладки.
Заключение
Направленный перекос в сеточных симуляциях часто возникает из структуры дерева решений, а не из самих правил. Превращая проверки по направлениям в маленькие помощники, собирая все валидные цели и выбирая между ними с понятными критериями равенства или случайностью, вы сохраняете симуляцию честной, симметричной и проще в сопровождении. А если цикл немедленно обновляет клетки, добавьте покадровый буфер, чтобы отделить вычисление от применения — поток станет заметно естественнее.