The game of God, or as I "Wolf Island" wrote

    Once upon a time, when I was still at university, I heard that programmers were asked an interesting task at the faculty of mathematics at our university: to model the so-called “wolf island”. Its essence is approximately as follows.



    What's in the picture
    Stop / Start - Start the world
    Turn - Stop the world
    Restart - Re-create the world
    Green cells - Cells with grass. The greener the more grass.
    Little hares and wolves - puppies.
    Big hares and wolves - adults.
    Red and blue stripes on the pictogram of animals - current satiety. Reds are males, blue are females.
    The number in the lower left corner of each cell is the number of creatures on the given cell.
    Below is the total number of hares and wolves, as well as the time taken to process the last move

    A wolf island of size N * N is inhabited by wild hares and wolves. There are several representatives of each species. Hares at each moment of time with equal probability 1/9 move to one of eight neighboring squares (with the exception of areas bounded by the coastline) or sit motionless. Each hare with probability p (br) turns into two birds with one stone. Each wolf with probability p (bw) turns into two wolves. Each wolf moves randomly (like a hare), until in one of the neighboring eight squares there is a hare for which he hunts. If the wolf and the hare are in the same square, the wolf eats the hare and gets h "points". Otherwise, it loses d"Points". Wolves with zero points die. At the initial time, all wolves have H0 points. The parameters of the problem could vary slightly, often there were modifications: for example, “honest” sexual reproduction of at least wolves, but the essence remained the same.

    This model was extremely interesting to me, and I wanted to try to implement it in at least some form. But it so happened that the hands reached only recently. However, now I could do it much more interesting, including “fantasizing” on the behavior of both wolves and hares. In this article, I would like to talk about a thorny, but extremely interesting way to balance a complex ecosystem.

    Selection of initial parameters


    Firstly, I did not want to be limited to a square field, and I took a rectangular one as a basis. There was, of course, the idea of ​​making a hexagonal one, but I wanted to bring something alive to the screen as quickly as possible, so the classic rectangular grid and 4 possible directions seemed the best choice.

    Next, it was necessary to decide, due to which the population of both hares and wolves would be supported. As in the animal kingdom, the reproduction of organisms takes on this role. In the initial version, the choice fell on the asexual reproduction of hares and sexual reproduction for wolves. In the first case, with some probability, each turn of the hare generates its own copy (as was originally described in the task), but the second case is much more interesting in implementation. The wolves were supposed to be of two sexes - female and male, and there would be no other differences at all. The algorithm was extremely simple: if two wolves of opposite sexes met on the same cell, then a new random wolf was simply generated.

    Now you need to decide how to prevent uncontrolled reproduction of creatures. It was assumed that the population of hares will be controlled by a population of wolves, for which, in turn, in the original problem, a hunger model is proposed. According to this model, wolves would lose certain satiety “points” every move, replenish them by eating hares on the same cage, and die when their satiety became equal to zero.

    It remains only to establish a model of behavior for creatures. The easiest way was to take the initial behavior: let the hares randomly move around in space pieces of meat, and the wolves aimlessly wandering predators until they notice a hare, which they immediately begin to hunt.

    Java 8 was chosen as the implementation language simply because the most familiar technology, and the object-oriented language, was perfectly suitable for such models. For the conclusion, I used the graphical primitives of standard Java tools - after all, the model itself interested me much more than its presentation.

    First pancake


    Yes, he was lumpy. Initially, the ecosystem seemed to work the first time, but no. The first problem I encountered was the poor survival of wolves: wolves did not always have time to breed. Yes, they hunted hares, but interest in the opposite sex was not laid in them. Only occasionally did two wolves collide on a neighboring cage, spawn a third and continue to wander aimlessly through the forest. So I decided to add some wolves to the map. The very first launch of a large flock of wolves into the forest showed how unstable the ecosystem is. Let's reason like a wolf (for definiteness - a male): we wander through the forest, if we meet a hare, then we eat. If we meet a female, then spawn our own small copy. And on the next move, another small copy, because the female, most likely, did not have time to escape anywhere. Moreover, the rules did not introduce any exclusive access to the partner, and in fact, the same wolf or wolf could be used to generate the third wolf more than once per turn. The worst thing is that newborn wolves immediately began to act on the same algorithm. Under such conditions, the growth of the wolf population took place in an avalanche-like manner - they didn’t even have to eat rabbits: new wolves were born completely full, and for their satiety they managed to breed many more wolves than one.

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

    This alignment is hardly a success, so immediately attempts were made to modify the system. The following restrictions have been added:

    1. only a she-wolf generated a small wolf of a random sex when meeting with a male (at least two new wolves had previously appeared);
    2. the concepts of “age” and “adulthood” were introduced: wolves could reproduce only from a certain age. Both wolves and hares became mortal. This restriction was introduced to prevent an explosion of the population too much;
    3. the concept of “visibility” was introduced: a wolf could analyze only objects within a certain radius (so far on its cage), but did not know anything about objects outside it;
    4. hares began to give more “saturation points” to compensate for the reduced breeding efficiency as a means of maintaining the population.

    I will not intrigue - this was not enough. The probability of the birth of hares allowed the species not to disappear, age at a certain value (depending on the probability of generating a hare) made it possible to limit them from above. But the wolves either began to die out, because there were too few hares, then they began to live right on the hares, because there were too many of them. The system was unstable and depended very much on the initial parameters. Modifications were definitely needed to model the real ecosystem.

    Balancing


    It was decided to add “pregnancy” for wolves. The mechanics consisted in the fact that the new wolf did not appear immediately, but after a certain number of moves. During the “pregnancy”, the she-wolf could not conceive again, which was supposed to eliminate the effect of a population explosion.

    But still, the survival rate of a wolf (like any other living creature) strongly depends on the model of behavior. Therefore, the simplest implementation of the behavior of wolves was added. For this, “visibility” turned out to be very useful - when we will transfer some of the objects of the world for analysis to a specific creature.

    Wolves begin to protect the grass from hares

    Brown squares - asexual hares
    Blue circles - wolves
    Yellow circles - wolves

    The creature’s move becomes more complex - it required some refactoring. Now the phases of the creature’s move were clearly distinguished:

    • update — update the creature’s natural counters: hunger (health), pregnancy, and age;
    • move - the function of choosing the direction of movement from the state of the creature and a list of objects inside the radius of visibility. Hares move randomly, and wolves chase hares in the field of visibility and individuals of the opposite sex;
    • feed - a wolf eats a hare located on the same cage, while the hares feed on solar energy;
    • multiply - a hare with a certain probability generates its copy, the case of wolves is described above.

    The behavior of the wolf "reasonable"


    The behavior of a creature in a given system is a set of functions responsible for all the basic actions in which it is necessary to make a choice. At that time, the choice of a wolf is determined only by the direction of movement (move).

    It seemed like a good idea to separate the animal’s basic functions (update), which do not affect its choice and should occur automatically (rules), from behavioral functions, which ideally should be replaced with more advanced versions in the process of developing algorithms. Thus, the first version of the "intelligent" wolf appears. For further discussion, we introduce the concept of "object of interest" - a creature in the field of visibility, which can be potentially eaten or with which reproduction is possible. The “intelligent” wolf acted as follows:

    1. all possible directions of movement are subtracted;
    2. it is determined whether the wolf wants to eat (if health is below half);
    3. if the wolf wants to eat, then among the visible objects the nearest object of interest is selected, which can be eaten (if there are several, then the first one);
    4. if the wolf does not want to eat, then among the visible objects the nearest object of interest is selected, with which you can breed;
    5. returns the direction of movement to the selected object of interest;
    6. if there are no objects of interest, then a random direction of movement is returned from the possible ones.

    This scheme allowed the wolves to catch all the nearest birds with one stone rather quickly to maintain their own satiety, and also to go astray while allowing hunger for quick access to the opposite sex. However, such a world degenerated: the wolves remained in packs, occasionally eating rabbits running past, and slowly died, while rabbits multiplied with impunity on the other side of the world, which they subsequently captured. It became clear that it was necessary to introduce complicating rules for rabbits to prevent their uncontrolled reproduction.

    And the result of such breeding


    The behavior of the hare "reasonable"


    In the next version, hares have a desire to eat and a desire to live, and, like wolves, sex. First, it was decided to try adding “desire to eat.”
    Now for the existence of a hare, it is necessary to maintain its own health scale. The hare will feed on grass, which slowly but surely grows underfoot (feeding on solar energy). Initially, the idea was that the number of food units in the area should limit the population of hares from above. Thus, using the parameters of grass growth and reducing satiety of hares, one could get a fairly accurate value of their maximum number on the island.

    To realize the “desire to eat”, we add a simple algorithm for calculating the direction from the nearest predator. However, under these rules, the wolf will never catch up with a single hare; therefore, the concept of “speed” was introduced — the number of complete life cycles of “move” and “eat”. Thus, a fairly hungry wolf with a speed of 2 almost always catches up with a hare at a speed of 1 if it appears in its area of ​​visibility. To prevent the wolves from interfering with each other, a slight unwillingness to move toward the wolf of the same sex was added to their target calculation algorithm, because he is a competitor and can eat a hare earlier.

    And here, in the process of stabilizing the current model, it took me the head to add a smell (in order to further shatter the already fragile ecological balance). The smell is left by hares on the cage where they are located (initial valueS ), each move this value is reduced by a certain dS to zero. Such a mechanism allowed theoretically increasing the visibility of the wolf, because if it was on a cell with the smell of N , it meant that somewhere within$ (S - N) \ over dS $cells is the hare that left him.

    The first ten launches made it clear that nothing changes in general: the reproduction of hares overlaps the need to eat, because it’s easier to breed your copy than there is grass. This means that it is necessary to complicate the reproduction of hares in a different way, and this will be the same reproduction as wolves, but with slightly different parameters: an increased likelihood of more than one offspring and a reduced gestational age of rabbits. Such a change will require greater “rationality” for the hares, since now they need to eat, escape from predators and breed. A similar algorithm has already been used for wolves, you just need to redefine the weight for food, predator, partner and competitor.

    But negative weights do not want to work as expected along with positive ones. So, you need to distribute the weight of each cell to its neighbors in decreasing order. Now, the central points are placed on the creature’s area of ​​visibility, spreading a decreasing effect with distance (in the current implementation 1 for each step). The result is a map of scales, according to which the creature "rolls" into positive holes in order to achieve the desired.

    // Алгоритм перемещения зайца
    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 move(Visibility visibility) {
        // Карта весов для юнитов
        Map> positionValues
            = updateWithUnits(visibility.units());
        // Карта весов для клеток
        HashMap positionValueMap
            = positionValues.entrySet().stream()
            .collect(Collectors.toMap(
                Map.Entry::getKey,
                e -> e.getValue().stream()
                    .mapToInt(VALUE_MAP::get).sum(),
                Integer::sum,
                HashMap::new));
        // Карта весов для хищника
        Map predatorValueMap
            = updateProliferatingValues(visibility, PREDATOR, positionValues);
        // Карта весов для сородича того же пола
        Map competitorValueMap
            = updateProliferatingValues(visibility, COMPETITOR, positionValues);
        // Карта весов для еды (травы)
        Integer foodCellValue = VALUE_MAP.get(FOOD);
        Map cellValues
            = visibility.cells()
                .collect(Collectors.toMap(
                        Cell::getPosition,
                        c -> 
                            c.getGrass().getFoodCurrent() >= c.getGrass().getFoodValue()
                            ? foodCellValue
                            : 0));
        Map totalValueMap
            = CollectionUtils.mergeMaps(
                Integer::sum,
                predatorValueMap,
                competitorValueMap,
                positionValueMap,
                cellValues);
        return totalValueMap.entrySet().stream()
                .max(Comparator.comparingInt(Map.Entry::getValue))
                .map(max -> {
                    List 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 updateProliferatingValues(
        Visibility visibility,
        RegularRabbitTargetAttitude key,
        Map> positionValues
    ) {
        List 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) 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> updateWithUnits(
        Stream units
    ) {
        Map> positionValues
            = new HashMap<>();
        Map> 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;
    }
    

    And this was the very point at which the system finally stabilized: the population of hares no longer grew uncontrollably, the wolves did not die out because of their “stupidity”. A balance has come in the world, and I set about optimizing and implementing additional amenities for the observer.

    You can see the story "in the context", as well as run and play on github .

    Update Already assembled version with a simple config on github

    Also popular now: