Структура данных в задаче “Волчий остров”

#c #структуры_данных

Как бы Вы организовали данные в такой задаче? Программирую я на C, если это вдруг важно.
Волчий остров размером 20х20 заселен дикими кроликами, волками и волчицами. Имеется
по нескольку представителей каждого вида. Кролики довольно глупы: в каждый момент времени
они с одинаковой вероятностью 1/9 передвигаются в один из восьми соседних квадратов
(за исключением участков, ограниченных береговой линией) или просто сидят неподвижно.
Каждый кролик с вероятностью 0,2 превращается в двух кроликов. Каждая волчица передвигается
случайным образом, пока в одном из соседних восьми квадратов не окажется кролик, за
которым она охотится. Если волчица и кролик оказываются в одном квадрате, волчица съедает
кролика и получает одно очко. В противном случае она теряет 0,1 очка. Волки и волчицы
с нулевым количеством очков умирают.
В начальный момент времени все волки и волчицы имеют 1 очко. Волк ведет себя подобно
волчице до тех пор, пока в соседних квадратах не исчезнут все кролики; тогда, если
волчица находится в одном из восьми близлежащих квадратов, волк гонится за ней. Если
волк и волчица окажутся в одном квадрате и там нет кролика, которого нужно съесть,
они производят потомство случайного пола.
Запрограммировать предполагаемую экологическую модель и понаблюдать за изменением
популяции в течение некоторого периода времени.
Я рассматривал несколько вариантов: список зверей, при этом элемент "зверь" хранит
собственные координаты. Но тогда поиск "соседей" осложняется. Можно сделать массив
списков. В каждом таком списке только те звери, которые "живут" в соответствующем месте
карты. Уже лучше. Была даже мысль организовать данные так: в каждой ячейке массива
структура (одна, не список), а внутри число (количество зайцев) и два массива из 10
элементов каждый. В каждой ячейке массива - количество волков/волчиц, имеющих соответствующее
здоровье (0.1 очка, 0.2 очка и т.д.) Это идеальный вариант, но он предполагает, что
больше 1 очка у волка не может быть, а в условии задачи об этом прямо не говорится.
Хотя это логично, ведь нельзя же съесть тонну еды, чтобы потом не есть год.    

Ответы

Ответ 1

С точки зрения ООП (Java) в этой игре есть 5 классов:

Игровая карта класс Environment - класс или статический или в виде Singleton
Животное - абстрактный класс Animal
Волк - класс Wolf extends Animal
Волчица - класс Wolfess extends Wolf
Кролик - класс Rabbit extends Animal

При этом класс Animal содержит текущие координаты и имеет 3 абстрактных метода: 

doStep() - шаг, логика которого отличается у волков и кроликов
doBirth() - рождение, пустой у волков, непустой у волчиц и кроликов
doEat() - поедание - непустой у волков и волчиц и пустой у кроликов

Класс Environment кроме игрового поля содержит в себе список животных - типа List,
который добавляется/убавляется при отработке методов doBirth() и doEat()
Собсно игровой ход: получаем объект Environment берем список животных и по каждому
из них делаем doStep()
Как то так.


Ответ 2

Я писал на С++, но общий принцип следующий.

Объект Region - содержит в себе перечень животных.
Объект Map - содержит в себе перечень регионов и их координаты.
Объект MapControl - по-сути, объект, управляющий игрой. Имеет набор методов, каждый
из которых на вход ждет ссылку на карту. Методы: вывести состояние карты и животных
на экран, вывести статистику (в моем случае по мутациям и по количеству живых на карте),
задать стартовое состояние карты (случайная расстановка зайцев и волков), MoveAll (это
сдвиг всех монстров на карте) и ActAll (это выполнение всех действий всех монстров
на карте).
Объект Action с одним абстрактным методом Do, принимающим на вход координаты, животное
и карту. Объект, который имеет право изменять состояние животных и карты.
Объекты, наследники от Action, это 3 варианта движения для волков (с разной логикой),
питание для волков, размножение для зайцев, размножение для волков, смерть для волков.
Иерархия классов животных, как у Barmaley: Animal с двумя абстрактными методами,
один возвозвращает Action движения животного, другой возвращает массив указателей на
все Action's животного, которые должны быть выполнены на этапе ActAll.
Объект Rabbit : public Animal с реализацией методов, возвращающих относящиеся к нему
Actions, и аналогично два объекта Wolf и Wolfess.

Поскольку я ввел понятие инициативы, и выполнение Move происходит в очередности ее
роста (чем меньше инициатива, тем раньше сдвиг), при этом при размножении заяц имеет
инициативу родителя +/-2, волк = (инициативу папы * 3 + инициативу мамы * 1)/4 +/-
4, волчица просто (инициативу папы * 3 + инициативу мамы * 1)/4. Таким образом, волчицы
не мутируют, но наследуют мутацию отца.
Кроме того, выживаемость волков сильно возросла, когда я добавил условие, что если
волк сыт более чем на 6, то сначала он ищет волчицу, а потом еду.
При стартовых 170ти зайцах и 20-20 волков, есть несколько этапов развития:

популяция зайцев медленно растет к 600-700, популяция волков до 150-200 каждого пола.
популяция зайцев начинает резко падать до 20-40, волки тоже переходят свой максимум
и их в районе 100-150 каждого пола.
популяция зайцев начинает потихоньку расти, до 70-80, волки к этому моменту вымирают.

Так вот, ожидаемо, что инициатива зайцев будет все время увеличиваться. И к третьему
этапу вместо стартовых средних 5,5, зайцы имеют ~9,5 в среднем. Но что удивительно
- инициатива волков падает. И когда их остается несколько десятков, их средняя инициатива
колеблется в районе 3-4.
Я предполагаю, что высокая инициатива, хоть и хорошо сказывается на охоте, плохо
сказывается на спаривании (инициатива самок должна быть маленькой), поэтому в итоге
инициатива лучшего волка бывает ниже инициативы худшего зайца. 
Кроме того, тот, кто последним пришел в регион (с более высокой инициативой), оказывается
в конце списка животных, и если там уже несколько волков, ему может не хватить зайцев.
Такие вот интересные результаты :)