Speciation

Wow, are we really at this stage already? In chronological terms, this post takes place just after Development Video #1. Ahhh, I was so young back then in the summer of 2011… [nostalgia]

… anyway, since I’m a cynical old fart now and clearly nothing like my half-a-year younger self, I’m free to criticise past-me for being a naive twit. And naive twit he was indeed when it came to speciation. He knew… wait… I knew? Gah, pronouns. This would be so much easier with a TARDIS, but I’m not a Time Lord. Past-me was but that was before the accident. Wait… after the accident? Goddamn time travel. Oh well, at least I stopped the Dec-2012 mayan-zombie-apocalypse. Suck it you undead sods, nobody gets to destroy this planet except me.

Back on topic, past-me I knew that seperate species, and thus speciation, was not going to be an easy thing to implement. We can’t even define it properly here in the real world! “Species” as a category usually means “unable to interbreed”, but what about ring species, where there is a continuous spectrum of creatures capable of breeding between two populations that can’t?

But they're still just birds! it's not like they've evolved into flying carnivorous fungi! Therefore evolution is false.


Image Source

This provides an interesting design challenge as well as a coding one. How do I define a species? How do I detect when two species have split?

(I say “detect” above because the existing simulation already includes speciation: what I’m describing here is a passive process that analyses the population, not an active process that forces a speciation under certain conditions)

As already stated, I knew that this was not going to be a simple problem to solve, but I was quite unprepared for the sort of problem it actually was. Coding it turned out to be difficult yes, but for all the wrong reasons. And as it turned out it was the design problems that required the most attention. This wasn’t a case of making it up as I went along (my usual method of coding): I was going to have to sketch out the problem in detail to find a realistic and sensible solution.

However, the game is called Species, so I couldn’t just chicken out on this one. It needs to be able to inform the player when speciation occurs, and allow them to track the progress of new and existing species in the ecosystem.

Initial attempts at defining this were sketchy in the extreme. Here’s something I wrote on the SMRT forum back when I was trying to work this out (because I’m too lazy to repeat myself when I can just copy/paste):

The biggest problem is defining species/populations. Just to give you an insight into the internals: I’ve set up a genetic comparison function which compares two creatures and returns their “Genetic Difference”, and I’m using this to determine mating compatibility (greater than 20 and two creatures can’t mate, and are thus different species). So, in the same generation, you have creatures A, B and C. If A’s genetic value is 10, B’s is 25 and C’s is 35, you can see the problem: A can mate with B can mate with C, but A cannot mate with C. Thus A and C are seperate species: but how do we define B?

This would be fairly simple to deal with if it weren’t for speciation. In a large population of many B’s and a few A’s (we’ll call them all “Species 1”), a C is born. What do we do? Do we mark the new C and all it’s descendants “Species 2”? Do we modify the existing populations label, making the B’s a mix of 1 and 2 depending on who’s closer? Or do we change the label and call all the B’s “Species 1.5”?

Despite the difficulties it causes, though, it’s kinda cool I’m dealing with the same issues taxologists have to deal with when trying to categorise animals…

My naivety shines through a little bit in those early comments, and later designs incorporated what I learned about ring-species and subspecies from the answers to my queries above. My second design had a system of ‘sub-species’ underneath ‘species’: a subspecies would be a group of creatures all of which were genetically compatable with one another, and a species would be the larger group that contains all subspecies, linked by those creatures that were genetically compatible with more than one subspecies. It took a few attempts at defining how this would work before I realised that my concept of a series of semi-mutually-exclusive subspecies simply wasn’t possible: the group of compatible mates is different for each creature, so any algorithm to determine this would end up with almost as many subspecies as creatures.

Eventually I dropped the concept of subspecies entirely and just stuck with a solid definition of “species”: a species is a group of living creatures from which a genetically-compatible path exists from any creature to any other creature within the Species. So despite the fact that the subspecies on either end of the ring species above cannot interbreed, the game would consider them all to be part of the same species

This solution brings up several more problems to solve: how do we tell if two creatures can interbreed? How and when do we work out if speciation has occured? And how much of a performance hit is this analysis of every creature going to be?

The first problem was, luckily, one I had already solved. While I was implementing mating, creatures had to check to see if they could mate in the first place. For reasons detailed in the previous post I couldn’t use the genetic string for this, so they instead compare their associated genetic values. Differences in floating point values increase their genetic distance proportionately to the difference, while differences in discreet values provide a constant (but dramatic) increase.

The end result is a floating point number representing the genetic distance of any two creatures. If it exceeds an arbitrary constant, creatures are no longer able to mate.

This system is an interesting one: it leads to a couple of interesting side-effects (for example, the genetic distance value is logarithmic. Immediate descendants can easily have a genetic distance as far as 10.0 units away simply by random mutation, but randomly generated creatures with no relation to one another have only 60.0-100.0 units distance). It’s also unmappable: afterall, how do you represent co-ordinates in 80-100 dimensional space? Because that’s what the genetic values usually amount to. Of course, just because something is unmappable doesn’t mean I’m not going to try…

Everyone loves graphs!

The graph is a bit misleading: the X position of a line represents the genetic-difference away from a “baseline-creature”. So if you imagine a circle, with the baseline-creature in the centre, the horisontal position of the line is the distance away from this creature. Two creatures can be on opposite sides of the circle, but appear at the same place on the graph and a species could be moving “around” the centre (instead of towards/away, as the yellow/orange-coloured species is clearly doing) and you’d never know. And since genetic difference includes a whole load of parameters, it’s less of a “circle” and more of a “50-dimensional sphere”.

Yeah, at that point it loses me too.

… [pause for thought]…

…actually, I just worked out a way to map it while I was typing that, by using the compatible connections rather than the co-ordinates and an elastic vector-web (ever played ‘world of goo’? If you have, you can probably sort-of imagine what I’m suggesting). Not only would that work, it would be absolutely fascinating to watch. Darn it, yet another thing to add to the feature creep list…

Moving on, the second problem then is “How and when do we work out if speciation has occured?”

The genetic comparison function isn’t too bad, but it does take time to run unless I can find a way to convert a Timecube into pure software (no luck so far). Back when I was only using it to help a creature determine if they could mate with another creature it’s effects were negligable, but calling it for every creature in a species, against every other creature in a species, every frame… well, you can see where that leads.

Thankfully, speciation can only happen under very specific conditions. It never happens unless the size of the species is changing, and never in response to a birth: adding a node to the web can’t create a new species (well okay, if the new creature is completely sterile it could create a species of 1, but that’s an exception to the rule).

Speciation is triggered by death: a population will speciate when the creature(s) linking it to the main population die off. So I only need to run the speciation checking routine in response to a death.

But we still need to work out how it works. I know I said working out the design for this system was the hardest thing about building it, but because I’m not an expert in searching algorithms, programming this algorithm was a close second.

The function starts by comparing the Species Average to all other creatures in the List, dumping any that are compatible into the “main population” bin. From there it compares every creature in the ‘main population’ bin to the remainder of the population, putting each compatible match into the bin before recursing to check the match against everything remaining.

By the time this function is finished, we have two bins of creatures: the main population and the remainder. 99% of the time there will be no remainder, which shows that the search function managed to find a way into every segment of the population. But if there is a remainder then it concludes that speciation has occured and splits it off into an entirely new species.

Huh… typing these posts forces my brain to rethink the processes I’m describing, and I think I’ve just stumbled on a few cases where this routine can be optimised. That’s good news: it means the game will be smoother and more efficient in the long run. Glad to see these blog posts serving a purpose beyond my own egotism!

Which isn’t to say egotism isn’t my primary incentive for writing this blog. That, the ability to tell rediculous lies in public. Oh, and also as cover for my time travel shenanigans. Nobody will ever suspect that I am really my evil time clone! Hahhahahahahah!

Now if you’ll excuse me, predestination demands I attack my past self with a toaster in a few minutes.
Qu

*Vwhooom vwhoooom vwhooommm…*
“Guys! I’m here from the future to warn you about- !”
*WHACK*
*thump*
“That’s quite enough of that.”

“Actually, predestination is a load of bull. I just told him he had to because it was hilarious the first time.”

Advertisements

, , , , , , ,

  1. #1 by Adam Benton on March 20, 2012 - 7:45 pm

    If the graph of genetic differences is too confusing would it not be possible to somehow procedurally generate a phylogenetic tree? Whilst it would need some way of keeping track of who descended from who, at that point surely you just could feed the data into a template of “place descendant species 1 in descendant node 1” etc.

  2. #2 by ququasar on March 21, 2012 - 7:21 am

    I definately agree I need to implement a proper phylogenetic tree by species: it’s actually one of the things I’m looking forward to spending time on. My previous attempts were way too complicated (I’ll talk about them in a later post). Doing it right means keeping it simple: don’t record moment-to-moment data, just record graph nodes and speciation events.

    I’m thinking it’d be cool to make it radial, too… but that might be reaching too far again. 🙂

  1. Render Targets Are Evil « Species Development Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: