Close

Local environment map: how to optimise the perception/movement steps?

A project log for Evol'artist

Evolv'artist is an open source computer game project on evolution.

emma-barmeEmma Barme 09/08/2017 at 08:110 Comments

In the simulation, each creature first perceives its local environment then move according to this local perception. Different creatures might not be able to "see" the same information from the map (temperature, presence of plants or other creatures, type of ground, ...) and their movements depends on their perceived value of each grid spot.

The naive implementation approach to this problem is to maintain one matrix of the real world grid plus one "perceived" copy per creature. However, this requires to generate as many world grid matrices as there are creatures. In this configuration, a lot of space is used for little information, as each creature only has information on a small sub-matrix of the grid. In addition to this, the time complexity of the move function is also sub-optimal, as for each and every creature the entire world grid must be looked at to determine the target for the move.

The best alternative I have found for now is to add in the definition of the creatures the maximum range of the perception. That is, the maximum value of the various perception capacities, vision, smell, thermosensing... Let's call it maxPercep. During the perception step, a matrix of size (2 * maxPercep + 1)^2 will be generated. It will be centered on the current position of the creature. There would be no border issues as the world grid is wrapping on itself. The perceived value of the grid spots outside of this local matrix is null. Depending on the size of the grid world and the maximum range of perception, this could save an enormous amount of space and quite a bit of time during the move step. The only downside is that it requires more careful implementation, but hey, I wouldn't be working on that project if I didn't like programming challenges!

Discussions