Игра в Бога, или как я «Волчий остров» писал

Давным-давно, когда я еще учился в университете, я услышал что на математическом факультете в нашем вузе программистам задают интересную задачу: смоделировать так называемый «волчий остров». Суть ее примерно в следующем.

Волчий остров размером N * N заселен дикими зайцами и волками. Имеется по несколько представителей каждого вида. Зайцы в каждый момент времени с одинаковой вероятностью 1/9 передвигаются в один из восьми соседних квадратов (за исключением участков, ограниченных береговой линией) или сидят неподвижно. Каждый заяц с вероятностью p(br) превращается в двух зайцев. Каждый волк с вероятностью p(bw) превращается в двух волков. Каждый волк передвигается случайным образом (как и заяц), пока в одном из соседних восьми квадратов не окажется заяц, за которым он охотится. Если волк и заяц оказываются в одном квадрате, волк съедает кролика и получает h «очков». В противном случае он теряет d «очков». Волки с нулевым количеством очков умирают. В начальный момент времени все волки имеют H0 очков. Параметры задачи могли незначительно изменяться, часто имели место модификации: например, «честное» половое размножение хотя бы волков, но суть оставалась все той же.

Эта модель меня крайне заинтересовала, и хотелось попробовать ее реализовать хоть в каком-нибудь виде. Но так уж случилось, что руки дошли только недавно. Однако теперь я мог это сделать гораздо интереснее, в том числе и «пофантазировать» на тему поведения и волков, и зайцев. В этой статье я хотел бы рассказать о тернистом, но крайне интересном пути к балансу сложной экосистемы.

Выбор начальных параметров

Во-первых, не хотелось ограничиваться квадратным полем, и за основу я взял прямоугольное. Была, конечно, мысль сделать и гексагональное, но хотелось как можно быстрее вывести что-нибудь живое на экран, поэтому классическая прямоугольная сетка и 4 возможных направления казались самым удачным выбором.

Далее необходимо было решить, засчет чего будет поддерживаться популяция и зайцев, и волков. Как и в животном мире, эту роль берет на себя размножение организмов. В начальной версии выбор пал на бесполое размножение зайцев и половое размножение для волков. В первом случае с некоторой вероятностью каждый ход заяц порождает свою копию (как и изначально было описано в задаче), а вот второй случай гораздо интереснее в реализации. Волки должны были быть двух полов — самка и самец, причем иных отличий не было бы вовсе. Алгоритм был крайне прост: если два волка противоположных полов встречались на одной клетке, то просто порождался новый волк случайного пола.

Теперь необходимо определиться, как не допустить бесконтрольного размножения существ. Предполагалось, что популяцию зайцев будет контролировать популяция волков, для которых, в свою очередь, в оригинальной задаче предлагается модель голода. Согласно данной модели волки бы каждый ход теряли определенные «очки» сытости, пополняли их съедая зайцев на той же клетке и умирали, когда сытость становилась равной нулю.

Осталось только установить модель поведения для существ. Проще всего было взять начальное поведение: зайцы пусть будут хаотично передвигающимися в пространстве кусками мяса, а волки бесцельно блуждающими хищниками до тех пор, пока не замечают зайца, за которым сразу начинают охоту.

В качестве языка реализации была выбрана Java 8 просто потому, что самая знакомая технология, да и объектно-ориентированный язык отлично подходил для подобного рода моделей. Для вывода я воспользовался графическими примитивами стандартных средств Java — все-таки сама модель интересовала меня куда больше, нежели ее представление.

Первый блин

Да, он был комом. Изначально казалось, что экосистема заработает с первого раза, но нет. Первой проблемой, с которой я столкнулся, была слабая выживаемость волков: волки не всегда успевали размножиться. Да, они охотились на зайцев, но к противоположному полу интерес в них заложен не был. Лишь изредка два волка сталкивались на соседней клетке, порождали третьего и продолжали бесцельно бродить по лесу. Поэтому я решил добавить несколько волков на карту. Первый же запуск большой стаи волков в лес показал, насколько экосистема неустойчива. Давайте порассуждаем как волк (для определенности — самец): бродим по лесу, если встречаем зайца, то съедаем. Если встречаем самку, то порождаем свою маленькую копию. А на следующем ходу еще одну маленькую копию, ведь самка, скорее всего, никуда убежать не успела. Более того, правилами не было введено никакого монопольного доступа на партнера, и по факту, один и тот же волк или волчиха могли быть использованы для генерации третьего волка не один раз за ход. Самое страшное, что новорожденные волки сразу же начинали действовать по такому же алгоритму. В таких условиях рост популяции волков происходил лавинообразно — им даже не надо было есть зайцев: новые волки рождались полностью сытыми, и за свою сытость успевали породить много больше волков, чем одного.

protected void breed(Visibility visibility) {
    // Критически важная проверка
    if (this.sex != Sex.FEMALE || !adult()) {
        return;
    }
    ...
}

Такой расклад трудно назвать успехом, поэтому сразу же были предприняты попытки модификации системы. Были добавлены следующие ограничения:

1. только волчиха генерировала маленького волка случайного пола при встрече с самцом (ранее появлялось как минимум два новых волка);
2. введены понятия «возраста» и «взрослости»: волки могли размножаться только с определенного возраста. И волки, и зайцы стали смертными. Данное ограничение было введено, чтобы предотвратить слишком сильный взрыв популяции;
3. введено понятие «видимости»: волк мог анализировать только объекты, находящиеся в определенном радиусе (пока на своей клетке), но ничего не знал об объектах за его пределами;
4. зайцы стали давать больше «очков» сытости, чтобы скомпенсировать сниженную эффективность размножения как средства поддержания популяции.

Не буду интриговать — этого оказалось недостаточно. Вероятность рождения зайцев позволяла виду не исчезнуть, возраст при определенном значении (в зависимости от вероятности порождения зайца) позволял ограничить их сверху. Но волки то начинали вымирать, потому что зайцев было слишком мало, то начинали жить прямо на зайцах, потому что их было слишком много. Система была нестабильна и очень сильно зависела от начальных параметров. Определенно требовались модификации, чтобы смоделировать реальную экосистему.

Балансировка

Было решено добавить «беременность» для волков. Механика заключалась в том, что новый волк появлялся не сразу, а через некоторое количество ходов. Во время «беременности» волчиха не могла забеременнеть повторно, что должно было избавить от эффекта взрыва популяции.

Но все же выживаемость волка (как и любого другого живого существа) сильно зависит от модели поведения. Поэтому была добавлена простейшая реализация поведения волков. Для этого очень кстати оказалась «видимость» — когда мы будем передавать часть объектов мира для анализа конкретному существу.

Волки начинают охранять траву от зайцев

Коричневые квадраты — бесполые зайцы
Синие круги — волчихи
Желтые круги — волки

Ход существа становится более сложным — это потребовало определенного рефакторинга. Теперь явно выделялись фазы хода существ:

• update— обновление естественных счетчиков существа: голод (здоровье), беременность и возраст;
• move — функция выбора направления движения из состояния существа и списка объектов, находящихся внутри радиуса видимости. Зайцы двигаются хаотично, а волки гоняются за зайцами в области видимости и особями противоположного пола;
• feed — волк съедает зайца, находящегося на той же клетке, а зайцы же пока питаются солнечной энергией;
• multiply — заяц с определенной вероятностью порождает свою копию, случай волков описан выше.

Поведение волка «разумного»

Поведение существа в данной системе — совокупность функций, отвечающих за все основные действия, в которых необходимо делать выбор. На тот момент выбор волка определяется только направлением перемещения (move).

Хорошей мыслью казалось отделение базовых функций животного (update), которые не влияют на его выбор и должны происходить автоматически (правила), от функций поведения, которые в идеале должны бы заменяться на более совершенные версии в процессе развития алгоритмов. Таким образом, появляется первый вариант волка «разумного». Для дальнейшего изложения введем понятие «объект интереса» — существо в области видимости, которое может быть потенциально съедено или с которым возможно продолжение рода. Волк «разумный» действовал по следующей схеме:

1. вычиляются все возможные направления движения;
2. опеределяется, хочет ли волк есть (если здоровье ниже половины);
3. если волк хочет есть, то среди видимых объектов выбирается ближайший объект интереса, который можно съесть (если несколько, то первый попавшийся);
4. если волк не хочет есть, то среди видимых объектов выбирается ближайший объект интереса, с которым можно размножиться;
5. возвращается направление движения к выбранному объекту интереса;
6. если объектов интереса нет, то возвращается случайное направление движения из возможных.

Такая схема позволяла волкам переловить всех ближайших зайцев довольно быстро для поддержания собственной сытости, а также сбиваться в стаи пока позволяло чувство голода для быстрого доступа к противоположному полу. Однако, и такой мир вырождался: волки оставались в стаях, изредка съедая пробегающих мимо зайцев, и медленно умирали, в то время как зайцы безнаказанно плодились на другом конце мира, который впоследствии и захватывали. Стало ясно, что необходимо ввести усложняющие правила и для зайцев, чтобы предотвратить их бесконтрольное размножение.

И результат такого размножения

Поведение зайца «разумного»

В следующей версии у зайцев появляется желание есть и желание жить и, так же, как и у волков, пол. Сначала было решено попробовать добавить «желание есть».
Теперь для существования зайцу необходимо поддерживать собственную шкалу здоровья. Питаться заяц будет травой, которая медленно, но верно растет под ногами (питаясь солнечной энергией). Изначально замысел был таков, что число единиц еды на площади должно ограничивать популяцию зайцев сверху. Таким образом, с помощью параметров роста травы и снижения сытости зайцев можно было бы получить достаточно точное значение максимального их числа на острове.

Для реализации «желания есть» добавляем простой алгоритм вычисления направления от ближайшего хищника. Однако при таких правилах волк никогда не догонит ни одного зайца, поэтому было введено понятие «скорость» —количество полных циклов жизнедеятельности «двигайся» и «ешь». Таким образом, достаточно голодный волк со скоростью 2 почти всегда нагоняет зайца со скоростью 1, если тот появится в области его видимости. Чтобы волки не мешали друг другу в их алгоритм вычисления цели было добавлено легкое нежелание двигаться в сторону волка того же пола, ибо он является конкурентом и может съесть зайца раньше.

И тут в процессе стабилизации текущей модели мне взбрело в голову добавить запах (чтобы еще сильнее расшатать и без того хрупкий экологический баланс). Запах оставляют зайцы на той клетке где находятся (изначальное значение S), каждый ход это значение понижается на определенное dS до нуля. Такой механизм позволял теоретически увеличить видимость волка, ведь если он находился на клетке с запахом N, то это означало, что где-то в пределах клеток находится заяц, который его оставил.

Первый десяток запусков четко дал понять, что ничего в целом не меняется: размножение зайцев перекрывает необходимость есть, ведь проще породить свою копию, чем есть траву. Значит, необходимо затруднять размножение зайцев иным способом, и это будет такое же размножение, как и у волков, но с несколько другими параметрами: повышенной вероятностью появления больше одного потомка и пониженным сроком беременности зайчих. Такое изменение потребует большей «разумности» у зайцев, так как теперь им нужно есть, спасаться от хищников и размножаться. Похожий алгоритм уже использовался для волков, нужно лишь переопределить вес для еды, хищника, партнера и конкурента.

Вот только отрицательные веса не хотят работать как положено вместе с положительными. Значит, нужно распространять вес каждой клетки на ее соседей с убыванием. Теперь на область видимости существа помещаются центральные точки, распространяющие убывающее с расстоянием влияние (в текущей реализации 1 на каждый шаг). В результате получается карта весов, по которой существо «скатывается» в положительные ямы, чтобы достигнуть желаемого.

// Алгоритм перемещения зайца
static {
    VALUE_MAP.put(RegularRabbitTargetAttitude.PREDATOR, -20);
    VALUE_MAP.put(RegularRabbitTargetAttitude.COMPETITOR, -5);
    VALUE_MAP.put(RegularRabbitTargetAttitude.MATE, 10);
    VALUE_MAP.put(RegularRabbitTargetAttitude.FOOD, 10);
}

public Optional<Position> move(Visibility visibility) {
    // Карта весов для юнитов
    Map<Position, Set<RegularRabbitTargetAttitude>> positionValues
        = updateWithUnits(visibility.units());
    // Карта весов для клеток
    HashMap<Position, Integer> positionValueMap
        = positionValues.entrySet().stream()
        .collect(Collectors.toMap(
            Map.Entry::getKey,
            e -> e.getValue().stream()
                .mapToInt(VALUE_MAP::get).sum(),
            Integer::sum,
            HashMap::new));
    // Карта весов для хищника
    Map<Position, Integer> predatorValueMap
        = updateProliferatingValues(visibility, PREDATOR, positionValues);
    // Карта весов для сородича того же пола
    Map<Position, Integer> competitorValueMap
        = updateProliferatingValues(visibility, COMPETITOR, positionValues);
    // Карта весов для еды (травы)
    Integer foodCellValue = VALUE_MAP.get(FOOD);
    Map<Position, Integer> cellValues
        = visibility.cells()
            .collect(Collectors.toMap(
                    Cell::getPosition,
                    c -> 
                        c.getGrass().getFoodCurrent() >= c.getGrass().getFoodValue()
                        ? foodCellValue
                        : 0));

    Map<Position, Integer> totalValueMap
        = CollectionUtils.mergeMaps(
            Integer::sum,
            predatorValueMap,
            competitorValueMap,
            positionValueMap,
            cellValues);
    return totalValueMap.entrySet().stream()
            .max(Comparator.comparingInt(Map.Entry::getValue))
            .map(max -> {
                List<Direction> availableDirections
                    = Direction.shuffledValues()
                        .filter(dir ->
                            !getPosition().by(dir)
                                .adjustableIn(
                                    0,
                                    0,
                                    visibility.getWidth(),
                                    visibility.getHeight()))
                        .collect(Collectors.toList());
                return getPosition()
                    .inDirectionTo(max.getKey(), availableDirections);
            });
}

private Map<Position, Integer> updateProliferatingValues(
    Visibility visibility,
    RegularRabbitTargetAttitude key,
    Map<Position,
    Set<RegularRabbitTargetAttitude>> positionValues
) {
    List<Position> negativePositions
        = positionValues.entrySet().stream()
            .filter(e -> e.getValue().contains(key))
            .map(Map.Entry::getKey)
            .collect(Collectors.toList());

    Integer epicenterValue = VALUE_MAP.get(key);

    return negativePositions.stream()
            .map(position ->
                    (Map<Position, Integer>) visibility.cells()
                            .map(Cell::getPosition)
                            .collect(Collectors.toMap(
                                    Function.identity(),
                                    pos -> epicenterValue + position.distance(pos),
                                    Integer::sum, HashMap::new)))
            .reduce((map1, map2) ->
                CollectionUtils.mergeMaps(Integer::sum, map1, map2))
        .orElse(Collections.emptyMap());
}

private Map<Position, Set<RegularRabbitTargetAttitude>> updateWithUnits(
    Stream<LivingUnit> units
) {
    Map<Position, Set<RegularRabbitTargetAttitude>> positionValues
        = new HashMap<>();
    Map<Position, List<LivingUnit>> positionUnits
        = units.collect(Collectors.groupingBy(LivingUnit::getPosition));

    positionUnits.forEach((key, value) -> value.stream()
        .map(InterestUnit::new)
        .forEach(iu -> {
            if (iu.asPredator != null) {
                positionValues.computeIfAbsent(key,
                    (pos) -> new HashSet<>()).add(PREDATOR);
            }
            if (iu.asMate != null) {
                RegularRabbitTargetAttitude attitude
                    = goodPartner(iu.asMate) ? MATE : COMPETITOR;
                positionValues.computeIfAbsent(key,
                    (pos) -> new HashSet<>()).add(attitude);
            }
        }));

    return positionValues;
}

И это была та самая точка, в которой система, наконец, стабилизировалась: популяция зайцев более не росла бесконтрольно, волки не вымирали из-за своей «глупости». В мире наступил баланс, а я принялся за оптимизацию и реализацию дополнительных удобств для наблюдающего.

Посмотреть историю «в разрезе», а также запустить и поиграть можно на github'е.

Автор: Evlikat

Источник