Игра в жизнь: как заставить «сущности» развиваться параллельно? - PullRequest
7 голосов
/ 15 сентября 2010

Хорошо, название не понятно, вот что я имею в виду.

Я программирую какую-то игру (например, игру жизни). Например, есть животных (каждое животное является экземпляром класса Java).

Все эти животные на карте, и весь этот " мир " развивается каждый "ход".

Эти животные могут совершать действия в каждый ход . Пример: волк убивает овцу .

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

Пример:

  • Первый волк : волк убивает овец (тогда овца мертва, поэтому никаких действий)
  • Сначала овцы : овца ест немного травы и ТО (поворот волка) волк убивает овцу

Как я могу решить эту проблему?

Многопоточность? (но у меня будет много животных, таких как 1000 и даже больше ...). Есть ли алгоритм, «способ» сделать это?

Спасибо

Ответы [ 9 ]

10 голосов
/ 15 сентября 2010

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

  1. На текущем шаге овца ест немного травы, а волк убивает ее.
  2. В следующем состоянии мира есть волк и нет овец (или тушу овцы - в зависимости от вашей модели).

Таким образом, порядок оценки не влияет на результат, что открывает возможность, например, распараллелить выполнение, предпочтительно используя FutureTask с и ThreadPoolExecutor.

4 голосов
/ 15 сентября 2010

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

3 голосов
/ 15 сентября 2010

О, вы не хотите заниматься многопоточностью, все станет еще более запутанным.

В этом случае переберите всех животных и позвольте им выбрать свое действие. ТО обновите карту.

1 голос
/ 15 сентября 2010

Я думаю, что сущности могут развиваться параллельно только в очень простых сценариях (например, в жизни Конвея) - для вашего мира "волки-овцы-травы" все сложнее, чем больше вы думаете об этом:

  • Рассмотрим ситуацию с двумя волками и одной овцой.Волк Один решает съесть овец;Волк Два решает съесть овец - как бы вы решили, кто из них получает овец (предположим, что еда - это атомарная операция - волки не могут делиться едой).Таким образом, вам все равно нужно будет определиться с тем или иным порядком, скажем, у Wolf One есть овца, а у Wolf Two ничего нет (что совершенно неожиданно для Wolf 2 - там была овца секунду назад, она открывает рот и - БАМ! -нет ничего)

  • Есть два волка и две овцы;«привлекательность» обеих овец одинакова для обоих волков, поэтому они выбирают свою добычу случайным образом.К сожалению, они выбирают одну и ту же овцу: Волк Один ест Овцу Один, Волк Два тоже пытается съесть Овцу Один, но она волшебным образом исчезает прямо под его носом.Конец хода.В следующем ходу Овца Два убегает, Волк Два голодает - что совершенно нелогично.

Поэтому я думаю, что просто перебираю список Животных и вызываю метод для каждого животного, которое выполняетатомное действие приводит к более логичной вселенной.Если вы обеспокоены тем, что животные, появившиеся ранее, имеют несправедливое преимущество перед теми, которые появились позже, вы можете просто рандомизировать список животных перед каждым ходом - таким образом, в вашем примере, либо Овца съедает немного травы, а затем получает ее от Волкаили Волк съест его, прежде чем у него будет шанс съесть любую траву.C'est la vie.

1 голос
/ 15 сентября 2010

Звучит так, будто вы хотите, чтобы мир развивался одинаково каждый раз, как жизнь Конвея. В Life вы смотрите на каждую ячейку и рассчитываете, какой будет результат для нее на основе предыдущего состояния. Если у ячейки есть два соседа, она будет жить следующему поколению, независимо от того, не будут ли эти соседи в следующем поколении. Исходное состояние должно быть доступно только для чтения, а правила должны работать независимо от того, что.

Например, что если у вас есть два волка рядом с овцой, они оба ее съедят или только один? Если только один, то вам нужно правило, по которому можно есть овец, а другому нужно это знать. Вы могли бы пойти противоположным путем, то есть посмотреть на овец, найти животное, которое бы его съело. Допустим, вы хотите, чтобы только один волк съел овец, и вы говорите, что волк с наименьшей координатой «Y» получает овцу или наименьшую координату «X», если есть два волка с одинаковым «Y». Если вы обрабатываете волка, вам нужно убедиться, что нет другого волка, который сначала съел бы овцу. Это может стать еще более запутанным, потому что, возможно, рядом с ним будет другая овца, которую она будет есть, поэтому она не будет есть первую ...

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

public class Cell {
    public int CellType = 0; // 0 == empty, 1 == grass, 2 == sheep, 3 == wolf
    public int Feedings = 0;
}

public class World {
public Cell [] Cells = new Cell[100];
public int Rows = 10, Cols = 10;

public Cell GetCell(x, y) {
    if (x < 0 || x >= Cols || y < 0 || y >= Rows) return null;
    if (Cells[y * Cols + x] == null) {
        Cells[y * Cols + x] = new Cell();
    }
    return Cells[y * Cols + x];
}

public World Evolve() {
    World w = new World();
    for (int y = 0; y < Rows; y++) {
        for (int x = 0; x < Cols; x++) {
            HandleCell(w, x, y);
        }
    }
    return w;
}

public void HandleCell(World newWorld, int x, int y) {
    Cell result = newWorld.GetCell(x, y);

    Cell c = GetCell(x, y);
    if (c.CellType == 2) { // sheep
        bool foundWolf = false;
        bool foundGrass = false;

        // code here to find if a wolf or grass are around the sheep

        if (foundWolf) {
            // default cell type is empty, so leave it be (wolf ate me)
        } else {
            result.cellType = 2; // still a sheep here
            if (foundGrass) {
                result.Feedings = c.Feedings + 1; // and he ate!
            } else {
                result.Feedings = c.Feedings; // or not...
            }
        }
    }

    if (c.CellType == 3) { // wolf
        bool foundSheep = false;

        // code here to find if a sheep is around the wolf

        result.CellType = 3;
        if (foundSheep) {
            result.Feedings = c.Feedings + 1; // ate the sheep!
        } else {
            result.Feedings = c.Feedings;
        }
    }
}
1 голос
/ 15 сентября 2010

Если у вас есть центральный менеджер, который может получать и отправлять уведомления, вы можете использовать Наблюдатель шаблон . Каждый раз, когда разворачивается ход, животные уведомляют, где они находятся. Менеджер уведомляет, кто там, и они выполняют свой метод eat() в соответствии с контекстом. Когда они поели, они notify() менеджер, который в свою очередь говорит им, что делать (например, sheep.die())

0 голосов
/ 15 сентября 2010

Может быть, вы могли бы сделать это совершенно случайно.

Первый случайный пример: овца ест траву, а затем волк ест овцу (овца -> волк)

Второй случайный пример: волк ест овец, потому что бедняга слишком медленно шел к траве (волк -> /)

Является ли реальный мир детерминированным? :)

0 голосов
/ 15 сентября 2010

Один из способов сделать это:

  1. Пусть овцы сделают свои действия и запишут их на следующем шаге.
  2. Обновить доску для действий овец
  3. Выполните каждое действие волка и запишите их на следующем шаге.
  4. Обновить доску для действий волка.

Два способа два многопоточности это:

  • Разделите доску на разные регионы и назначьте каждую ветку для региона. У вас будут проблемы с выяснением, как переместить его из одного региона в другой.

  • Другим способом может быть разрыв цикла между существами в разные потоки. например,

    for(w=THREAD_NUM; w<NUM_OF_WOLVES; w+=NUM_OF_THREADS) { w.doAction(); }

0 голосов
/ 15 сентября 2010

Вне моей головы, вы можете сделать что-то вроде этого:

Имейте единственный объект Мира, который управляет списком объектов Игрока. У игрока есть следующие методы:

Игрок

  • public void takeTurn (Мир мира)
  • public boolean isDead ()
  • public void kill ()

Когда экземпляр World попадает к каждому игроку, он спрашивает его, мертв ли ​​он. Если нет, он вызывает метод takeTurn. Или takeTurn может вызвать isDead () внутри и просто вернуть, если это так. Если вы убиваете другого игрока (или себя), вы просто вызываете метод kill игрока.

Передача в мир takeTurn на всякий случай, если вам нужно сделать обратный вызов, чтобы обновить состояние мира .

...