A long time ago, when I was still at university, I heard that programmers in the Faculty of Mathematics at our university are assigned an interesting task: to simulate the so-called “wolf island”. Its essence is approximately as follows.




The wolf island of size N * N is inhabited by wild hares and wolves. There are several representatives of each species. Hares at each time point with the same probability 1/9 move to one of eight adjacent squares (with the exception of areas limited 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 there is a hare in one of the neighboring eight squares, which he hunts for. If the wolf and the hare are in the same square, the wolf eats the hare and gets h "points". Otherwise, he loses d points. Wolves with zero points die. At the initial time, all wolves have H0 points. The parameters of the task could slightly change, often there were modifications: for example, “honest” sexual reproduction at least of wolves, but the essence remained the same.
')
I was extremely interested in this model, and I wanted to try to implement it at least in some form. But it just so happened that the hands reached only recently. However, now I could do it much more interesting, including “fantasizing” the behavior of wolves and hares. In this article I would like to tell you about the thorny, but extremely interesting path to the balance of a complex ecosystem.

Selection of initial parameters

First, I did not want to be limited to a square field, and I took a rectangular basis. There was, of course, the idea to make 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 most successful choice.

Next, it was necessary to decide, by which the population would be supported by hares and wolves. As in the animal world, this role is assumed by the reproduction of organisms. In the initial version, the choice fell on asexual breeding of hares and sexual reproduction for wolves. In the first case, with a certain probability, each move the hare generates its own copy (as it was originally described in the problem), but the second case is much more interesting in implementation. Wolves should have been 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 cage, then a new wolf of a random sex was simply generated.

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

It remains only to establish a behavior model for creatures. The easiest thing was to take the initial behavior: let the hares be pieces of meat moving chaotically in space, and wolves aimlessly wandering predators until they notice the hare, after 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 excellent for this kind of model. For output, I used the graphical primitives of standard Java tools - after all, the model itself interested me a lot more than its presentation.

First pancake

Yes, he was a lump. Initially, it seemed that the ecosystem would work the first time, but no. The first problem I encountered was the poor survival of wolves: wolves did not always have time to multiply. Yes, they hunted hares, but there was no interest in the opposite sex. Only occasionally two wolves collided on the next cage, gave birth to the third and continued wandering aimlessly through the forest. So I decided to add a few wolves to the map. The first launch of a large pack of wolves into the forest showed how unstable the ecosystem is. Let's speculate 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 we generate 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 the newborn wolves immediately began to act on the same algorithm. In such conditions, the growth of the wolf population occurred as an avalanche — they did not even need to eat hares: new wolves were born completely fed, and for their satiety they had time to produce many more wolves than one.

protected void breed(Visibility visibility) { //    if (this.sex != Sex.FEMALE || !adult()) { return; } ... } 

Such an alignment can hardly be called a success, so immediately attempts were made to modify the system. The following restrictions have been added:

1. only the wolf generated a small wolf of random sex when it met the male (at least two new wolves appeared earlier);
2. introduced the concept of "age" and "adulthood": wolves could breed only from a certain age. Both wolves and hares became mortal. This restriction was introduced to prevent a too strong explosion of the population;
3. the concept of "visibility" was introduced: the wolf could analyze only objects that were within a certain radius (while on its cage), but did not know anything about objects beyond its limits;
   
4. hares began to give more “points” of fullness to compensate for the reduced efficiency of reproduction as a means of maintaining the population.

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

Balancing

It was decided to add a "pregnancy" for wolves. The mechanic was that the new wolf did not appear immediately, but after a certain number of moves. During the "pregnancy" wolf could not get pregnant again, which was supposed to save the effect of the explosion of the population.

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


The course of the creature becomes more complex - this required a certain refactoring. Now clearly distinguished the phases of the course of creatures:

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

The behavior of the wolf "reasonable"

The behavior of a creature in this 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 the wolf is determined only by the direction of movement (move).

It seemed a good idea to separate the basic functions of the animal (update), which do not affect its choice and should occur automatically (rules) from the behavioral functions, which ideally should be replaced with more advanced versions in the development of algorithms. Thus, the first version of the wolf "reasonable". For further presentation, we introduce the concept of "object of interest" - a creature in the field of visibility, which can be potentially eaten or with which the continuation of the species is possible. Wolf "reasonable" acted as follows:

1. all possible directions of movement are scored;
2. determines whether the wolf wants to eat (if health is less than half);
3. if the wolf wants to eat, then among the visible objects the closest object of interest is selected, which can be eaten (if there are several, then the first one that comes across);
4. if the wolf does not want to eat, then among the visible objects the closest object of interest is selected, with which it is possible to multiply;
5. returns the direction of movement to the selected object of interest;
6. if there are no objects of interest, then the random direction of motion returns from the possible ones.

Such a scheme allowed the wolves to catch all the nearest hares rather quickly to maintain their own satiety, and also to get lost in the pack while allowing the feeling of hunger for quick access to the opposite sex. However, such a world also degenerated: wolves remained in packs, occasionally eating rabbits running past, and slowly died, while hares bred with impunity at the other end of the world, which they subsequently seized. It became clear that it was necessary to introduce complicating rules for hares as well, in order to prevent their uncontrolled reproduction.

The behavior of the hare "reasonable"

In the next version, hares have a desire to have a desire to live and, just like wolves, sex. First, it was decided to try to add the "desire to eat."
Now, for the existence of a hare, you need to maintain its own health scale. Eating a hare will be grass, which slowly but surely grows under your feet (feeding on solar energy). Initially, the idea was that the number of food units in the square should limit the population of hares from above. Thus, using the parameters of grass growth and reducing the hares satiety, one could get a fairly accurate value of their maximum number on the island.

To implement the “desire to eat” we add a simple algorithm for calculating the direction from the nearest predator. However, with such rules, the wolf will never catch up with a single hare, so the concept of “speed” was introduced — the number of complete life cycles “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 he appears in his area of ​​visibility. So that the wolves did not interfere with each other, a slight unwillingness to move in the direction of a wolf of the same sex was added to their algorithm for calculating the target, because it is a competitor and can eat the hare earlier.

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

The first dozen launches made it clear that nothing changes as a whole: the reproduction of hares overrides the need to eat, because it is easier to generate your own copy than to eat grass. This means that it is necessary to hinder the reproduction of hares in a different way, and this will be the same reproduction as wolves, but with slightly different parameters: an increased probability of the appearance of more than one descendant and a reduced hare pregnancy. Such a change will require greater rationality for hares, since now they need to eat, to flee from predators, and to multiply. A similar algorithm has already been used for wolves, you just need to redefine the weight for food, predator, partner and competitor.

However, 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 descending order. Now on the creature's scope, the central points, spreading the effect decreasing with distance (in the current implementation 1 for each step) are placed. The result is a map of weights, according to which the creature “rolls” into positive pits 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<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; } 

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." There was a balance in the world, and I set about optimizing and implementing additional amenities for the observer.

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

Update. Already compiled version with a simple config on github'e