• Simplified simulation system

    Emma Barme • 06/15/2018 at 15:23 • 0 comments

    The five-steps simulation turned out to be faaaar to computationally heavy.

    We decided to replace it with a fitness based simulation:

     - the string genome is cut into genes

     - each gene is associated with a function of environment descriptors giving its fitness

     - survival and reproduction is decided by fitness

     - at each step creatures are reproduce, die and new creatures are born into neighbouring spots.

  • Genetic information

    Emma Barme • 10/06/2017 at 12:23 • 0 comments

    DNA is the "blueprint" of most living organisms. It is at the crux of evolution as it defines -roughly speaking- the hereditary characteristics of a living being. Not familiar with DNA? Check out this video, this interactive website or this old-school lesson for info.

    In our simulation, the behaviour of the Creatures is going to be determined mostly by their DNA, with a pinch of randomness here and there.

    We have settled on a 3-bases single-strand genetic information structure. A chromosome will be represented by a string of letters. Possible letters will be A, the beginning of a gene, O, the end of a gene, and B, C and D, the bases. A gene will be any sequence of letters beginning by a A and finishing by a O, with only B's, C's and D's in between.

    For example:
    ABBCDDCBDBCO is a gene
    ABCDBBDC is not a gene
    BDCBCBDO is not a gene
    ACBDBCACO is not a gene, but its substring ACO is
    ADBABCDDBCOCBDDO is not a gene, but its substring ABCDDBCO is

    With this structure, it is not possible to have a gene which is a substring of another gene.

    For game design and performance purposes, for now we set the maximum length of a useful gene to be of 6 bases. Any gene longer than this will have not impact on its bearer.

  • Creature movements: the classical A* algorithm

    Emma Barme • 09/29/2017 at 09:40 • 0 comments

    So, the time has come to choose a first algorithm to move the Creatures in the World grid. For now, they move pretty stupidly, by alternating horizontal and vertical movements towards a target -the Spot with the highest score in their local environment-. The plan is to improve this by implementing an A* path-finding algorithm to determine where to go next.

    Why A*?

    A* is a very common pathfinding algorithm in graphs, which means it translates perfectly to pathfinding in grids. It does not require any preprocessing of the graph/grid, which is good for our part as we will never perform the pathfinding twice on the same grid.

    A* is widely documented, so I will not detail it here. For reference, Wikipedia propose history and complexity information in addition to the pseudocode. On Ray Wenderlich's website you can find a tutorial for beginners complete with step-by-step illustrations of an example and an Obj-C pseudocode. And because it always help to be able to play around with new algorithms, here is a fantastic visualisation tool for pathfinding algorithms.

    Heuristic choice

    Part of our heuristic will relay on the evaluation of the environment, which we will probably discuss in a future log. For now, we are using the feeding power and the presence/absence of other Creatures to determine the score of a Spot during the local environment perception phase. If we could always reach our target immediately, this would not be necessary, but as it is possible that the Creature will only reach an intermediary point on the way to the target, we prefer to account for the convenience of each Spot.

    We also want to account for the number of moves necessary to reach the target -in other words the Manhattan distance from the current position. This reflects the fact that we do not want to wander all over the grid before reaching our target.

    In A*, the lower the heuristic the better. However, in our case the higher the score the better, so we set our heuristic function to be h(Spot) = ManhattanDistanceToDest(Spot) + MaximumPossibleScore - Score(Spot)

    Our heuristic is admissible but not consistent/monotonous, so we will have to keep track of visited node (closed list) in our implementation.

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

    Emma Barme • 09/08/2017 at 08:11 • 0 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!

  • Structure of the evolution simulation

    Emma Barme • 08/28/2017 at 12:41 • 0 comments

    Our general scheme for our evolution simulation is as follow. We maintain a list of the living creatures in the world and we iterate a five-step simulation over this list.

    Each step is run for all creatures before the next step is computed. The order in which the creatures are considered for the computation of a step is random.

    1. Evaluation of environment: generation of a local environment matrix which is an approximation of the world matrix as perceived through the vision -or other perception abilities- of the creature
    2. Choice of destination and movement: target the visible spot with the highest fitness and move towards it as much as possible
    3. Interactions between creatures: fights, preying, reproduction*
    4. Interaction with the environment: feeding, damage from climate or natural events
    5. Aging, dying, births

    * Reproduction is happening by a mixing of DNAs. In the very basic models with are experimenting with right now, there is no DNA mechanism yet, so we'll devote another post for our plans for this part.

  • Plan for a first evolution simulation

    Emma Barme • 08/24/2017 at 10:03 • 0 comments

    For a first draft of the evolution engine, we have settled on the followed world and creature characteristics:

    • 1000*1000 world grid
    • Each case starts with a random static value representing feeding power between 0 and 100
    • At the end of each turn the feeding power of each case increases by one
    • 100 initial adult creatures placed randomly
    • Creatures have only adult stage
    • Creatures do not have varying characteristics - they are all identical- so there will be no evolution
    • Creatures can move one step each turn
    • Creatures can see three steps in every direction
    • Creatures move toward the case with the highest feeding power in the vision field
    • Creatures' heath start at 100
    • If the health of a creature falls below 0, it dies at the end of the turn
    • Creatures' hunger start at 0
    • At the end of each turn the health of a creature is decreased by its hunger
    • Creatures' hunger increases by 5 at the end of each turn
    • During each turn creatures' hunger is decreased by the feeding power of the case they are on -but cannot fall under 0
    • When two creatures are on the same case they reproduce by producing a new creature on a random neighbour case.
    • When two creatures are on the same case they share the food.

  • Breaking down the project into small bricks

    Emma Barme • 08/23/2017 at 09:43 • 0 comments

    We all know how daunting tackling a new project can be, or how frequent it is to give up in the middle because the end still feels so far away. For me, the best way to prevent that is to break down the project into small bricks from the start and to keep track of the status for each brick.

    This is a tentative list of bricks of Evol'artist. Some bricks are divided further into smaller ones, and the goal is to never have a leaf brick of the tree seem to big to tackle.

    >Game design:

    >>Story/world

    >>>Characters

    >>>Storyline

    >>>Creatures characteristics

    >>Interface

    >>>Planet modification interface

    >>>Feedback on the creatures interface

    >>>General menu interface

    >>>Display orders

    >Programming

    >>Evolution motor

    >>>Creature entities

    >>>Life simulation

    >>>>Fetching characteristics from DNA on birth

    >>>>Simulate each step in life simultaneously for all creatures

    >>>Reproduction simulation

    >>>>Meiose

    >>>>Mixing DNAs

    >>Stats on creatures

    >>>Dynamic stat display

    >>>Stats on phenotype

    >>>Stats on genotype

    >>Game play engine

    >>>General save/create/quit...

    >>>Planet modification

    >>>Order generation

    >Art

    >>Visuals

    >>Audio

    >>Name

    >>Logo