Genetic Algorithms and Scalable Skeletons?
by Axel "The Cush" Cushing · in General Discussion · 04/02/2004 (9:41 am) · 6 replies
WARNING: the folllowing is an extremely ROUGH idea, and as such is prone to lapses of judgement/knowledge/understanding. Caveat emptor.
Part I: The Idea
As part of my ongoing design process for a generational RPG (where the player controls successive generations of heroes as opposed to a single "hero builds party and saves the world" storyline), I've begun tackling the problem of genetics and characteristic inheritence from generation to generation. My initial efforts were stymied by the fact that I couldn't seem to figure out exactly HOW physical traits could be passed from one character to another without effectively cloning the character. Cosmetic changes like hair and eye color would be fairly easy (if I wanted to cheat and basically put in a randomizer of some sort), but things like body type and special abilities or disabilities remained elusive. For an example of a physical characteristic being passed from father to son, look at the chins of Kirk Douglas and Michael Douglas. I want that sort of thing in the game, if maybe not exactly that specialized, but you get the idea.
It is perhaps ironic (in some obscure cosmic sort of way) that I should come up with the following idea on April Fool's Day. I was hanging out at school, killing time before class, listening to the "Morrowind" soundtrack, working on a chart that showed possible combinations of dominant and recessive genes. By this time, I had figured out that the simplest answer for the basic idea of a character genotype (the genetic makeup of an organism) was to divide the character phenotype (the physical makeup or appearance of the organism) into basic chunks, i.e. head, torso, limbs. However, it still failed to address the problem of variation within the phenotype. Every character, whether first generation or fifty-first generation, would have exactly the same sort of body, the same proportions on the limbs, the same head shape. This struck me as not only unrealistic, but damned silly to boot. Yeah, it was easy, but it didn't seem like it was good.
For some reason, I flashed on Unreal Tournament 2004. Maybe it was that I'd had a bad day and felt the need for a little bit of the old ultraviolence. Maybe I was thinking about the tutorial level that I had been building in UnrealEd which I hadn't quite finished yet. I don't know what it was, but while I was thinking about the parts of the body, I started thinking about how those parts all fit together and I started thinking about the static meshes from UT2K4, how they could be stretched and shrunk through the scaling tool.
Epiphany.
Why couldn't you make phenotype scaling information part of your character's genetic code? During the process where a new generation of character was created, the information for the proportions of the character's body parts would be already present and able to be used. It seems like a workable idea.
Part I: The Idea
As part of my ongoing design process for a generational RPG (where the player controls successive generations of heroes as opposed to a single "hero builds party and saves the world" storyline), I've begun tackling the problem of genetics and characteristic inheritence from generation to generation. My initial efforts were stymied by the fact that I couldn't seem to figure out exactly HOW physical traits could be passed from one character to another without effectively cloning the character. Cosmetic changes like hair and eye color would be fairly easy (if I wanted to cheat and basically put in a randomizer of some sort), but things like body type and special abilities or disabilities remained elusive. For an example of a physical characteristic being passed from father to son, look at the chins of Kirk Douglas and Michael Douglas. I want that sort of thing in the game, if maybe not exactly that specialized, but you get the idea.
It is perhaps ironic (in some obscure cosmic sort of way) that I should come up with the following idea on April Fool's Day. I was hanging out at school, killing time before class, listening to the "Morrowind" soundtrack, working on a chart that showed possible combinations of dominant and recessive genes. By this time, I had figured out that the simplest answer for the basic idea of a character genotype (the genetic makeup of an organism) was to divide the character phenotype (the physical makeup or appearance of the organism) into basic chunks, i.e. head, torso, limbs. However, it still failed to address the problem of variation within the phenotype. Every character, whether first generation or fifty-first generation, would have exactly the same sort of body, the same proportions on the limbs, the same head shape. This struck me as not only unrealistic, but damned silly to boot. Yeah, it was easy, but it didn't seem like it was good.
For some reason, I flashed on Unreal Tournament 2004. Maybe it was that I'd had a bad day and felt the need for a little bit of the old ultraviolence. Maybe I was thinking about the tutorial level that I had been building in UnrealEd which I hadn't quite finished yet. I don't know what it was, but while I was thinking about the parts of the body, I started thinking about how those parts all fit together and I started thinking about the static meshes from UT2K4, how they could be stretched and shrunk through the scaling tool.
Epiphany.
Why couldn't you make phenotype scaling information part of your character's genetic code? During the process where a new generation of character was created, the information for the proportions of the character's body parts would be already present and able to be used. It seems like a workable idea.
#2
As the system currently stands, the concept of building a character's physical structure using scalable skeletal pieces and genetic algorithms seems highly probable. One potential downside is having to stitch together wildly disparate body parts together in such a way as that they seem like they are part of a whole rather than a conglomeration. The transformations necessary to accomplish that are beyond my ability to calculate. Initially, I had considered the possibility of having the genes determine just the basic skeletal structure, then have a separate gene or series of genes apply the musculature and skin as layers on top of the skeleton. If I could think of a good way to do that, I might go with it, since that would not only be more detailed and more realistic, but would go a long way towards solving the problems of trying to stitch together whole body parts.
If I was feeling bold (or particularly masochistic), I could bring the number of gene types (not to be confused with genotypes) to four, effectively duplicating the A-G-C-T pattern of DNA in real life (albeit simplified), and making the implementation of dominant and recessive genes considerably more tricky. One practical upshot to this might be a more cheat-resistent character. If the attributes, abilities, and disabilities are controlled by specific combinations of base pairs, hacking your character could very easily cause more harm than good, which might well discourage hacking just from it being so bloody obtuse that it wouldn't be worth the effort involved.
Thus endeth the idea. Comments, flames, praise, lay'em on me.
04/02/2004 (11:43 am)
Part III: Other ThoughtsAs the system currently stands, the concept of building a character's physical structure using scalable skeletal pieces and genetic algorithms seems highly probable. One potential downside is having to stitch together wildly disparate body parts together in such a way as that they seem like they are part of a whole rather than a conglomeration. The transformations necessary to accomplish that are beyond my ability to calculate. Initially, I had considered the possibility of having the genes determine just the basic skeletal structure, then have a separate gene or series of genes apply the musculature and skin as layers on top of the skeleton. If I could think of a good way to do that, I might go with it, since that would not only be more detailed and more realistic, but would go a long way towards solving the problems of trying to stitch together whole body parts.
If I was feeling bold (or particularly masochistic), I could bring the number of gene types (not to be confused with genotypes) to four, effectively duplicating the A-G-C-T pattern of DNA in real life (albeit simplified), and making the implementation of dominant and recessive genes considerably more tricky. One practical upshot to this might be a more cheat-resistent character. If the attributes, abilities, and disabilities are controlled by specific combinations of base pairs, hacking your character could very easily cause more harm than good, which might well discourage hacking just from it being so bloody obtuse that it wouldn't be worth the effort involved.
Thus endeth the idea. Comments, flames, praise, lay'em on me.
#3
It's vitally important that the player can choose people to mate (or something) with so that the player has some choice of DNA for the future generations. If there's no choice or all the choices but one are bad, this idea wouldn't have any point.
You were probably planning on doing it that way anyways. :)
04/02/2004 (6:49 pm)
It sounds good in theory, but may be hard to implement. It depends on how much time you want to put into it.It's vitally important that the player can choose people to mate (or something) with so that the player has some choice of DNA for the future generations. If there's no choice or all the choices but one are bad, this idea wouldn't have any point.
You were probably planning on doing it that way anyways. :)
#4
As far as stitching together body parts... You're going to need some kind of a 'skirt' of dynamically computed vertexes to cover the gaps that are sure to show up. There's been some work on covering up gaps between adjacent LOD sections in things like terrain - you might want to pull up some terrain papers and look at the different ways that problem's been solved, since it strikes me as a similar kind of thing.
04/02/2004 (7:58 pm)
When you present this to an audience that includes programmers, try to avoid using the term 'genetic algorithm.' There's a widely known machine learning technique called genetic algorithms and you're just asking for confusion - I know I was a little confused from the title of this post.As far as stitching together body parts... You're going to need some kind of a 'skirt' of dynamically computed vertexes to cover the gaps that are sure to show up. There's been some work on covering up gaps between adjacent LOD sections in things like terrain - you might want to pull up some terrain papers and look at the different ways that problem's been solved, since it strikes me as a similar kind of thing.
#5
--Paul
04/02/2004 (8:39 pm)
Something that may be worth checking out: the game Impossible Creatures (used to be known as Sigma). They had a system where you could splice the different parts of animals together and make your own monstrosity. I'm not sure how they did it, but it may be worth seeing if there any post mortems of the game on any websites. Not exactly the same as what you are doing, but you may be able to find a reference.--Paul
#6
@Mark - when I went searching for information about virtual genotypes and what not, I saw articles occasionally referring to the concept (and perhaps incorrectly) as "genetic algorithms," perhaps in a more literal sense than the sort of genetic algorithms which are used specifically for AI behavior. As to the terrain idea, I will have to do some digging there. Kind of goes back to the idea of one set of genes building the actual skeletal structure and another set defining the musculature and skin overlaid on top of that. Potentially more complex, but more visually appealing as the end result goes.
@Paul - Totally did not think to look at Impossible Creatures. If there's a postmortem on it that mentions how they handled the skinning and joint issues, I'm sure that'll be of tremendous help. And now that I think about it, I might also want to see if I can dig up info on Black & White, since the Creature in that game could either get buff or blobby while retaining its general skeletal structure. (Never did get that damn thing older than a cub.)
04/02/2004 (10:08 pm)
@Steve - there's going to be plenty of opportunities for characters of both genders to spread the love, as it were. The catch is that the player is going to have to infer what the abilities and disabilities of the desired mate are from the course of gameplay. After all, romance itself is a quest. :) @Mark - when I went searching for information about virtual genotypes and what not, I saw articles occasionally referring to the concept (and perhaps incorrectly) as "genetic algorithms," perhaps in a more literal sense than the sort of genetic algorithms which are used specifically for AI behavior. As to the terrain idea, I will have to do some digging there. Kind of goes back to the idea of one set of genes building the actual skeletal structure and another set defining the musculature and skin overlaid on top of that. Potentially more complex, but more visually appealing as the end result goes.
@Paul - Totally did not think to look at Impossible Creatures. If there's a postmortem on it that mentions how they handled the skinning and joint issues, I'm sure that'll be of tremendous help. And now that I think about it, I might also want to see if I can dig up info on Black & White, since the Creature in that game could either get buff or blobby while retaining its general skeletal structure. (Never did get that damn thing older than a cub.)
Axel "The Cush" Cushing
My initial genetic scheme for characters simply revolved around dominant (D) and recessive (r) genes. Some abilities and disabilities would come about through the presence of a dominant gene, some through recessive, some through a pair of dominant (DD) or recessive (rr) genes. Given a genetic pair of "Dr", the dominant ability/attribute would override the recessive ability/attribute. With the idea of building the phenotype information into the genes that control the dimensions of the character's body parts, I figured I would probably need to add a third gene type, call it "null" or "average." (n)
As an example, the genotype for an average arm might be composed of the following:
gnUpperArm gnLowerArm gnWrist gnHand gnThumb gnFingerI gnFingerM gnFingerR gnFingerPNitpickers might want to make "gnLowerArm" a child of "gnUpperArm". Minimalists might want to forget about enumerating the fingers and make gnHand the last part of the arm with all the fingers included. Either way, that's the rough idea. Now, the genotype for the arm of a tenth-generation character might look something like this:gDUpperArm grLowerArm gDWrist gnHand gDThumb grFingerI grFingerM gnFingerR gDFingerPIn the context of the game, this would be happening at the moment of the character's conception (yes, that's a part of this game as well). In a rough sort of way, it's basically flipping a coin, seeing which gene gets contributed by the father, which one gets contributed by the mother, and which of those two shows as the dominant trait. When dealing with the phenotype values for mundane things like hands and feet, each gene would carry a scalable range to give the phenotype some small amount of variation among people who carry the same genes. The rough values for our hand example are below:EXAMPLE: Let us say that Bob (a third-generation character) is conceived and the genetic makeup is determined. The first part would be whether he got the Dominant hands of his mother or the average hands of his father. The coin is flipped, looks like he's getting his father's hands. The next part is to find out what scale of hands the boy will get. A random number generator set to pick a number between .90 and 1.10 picks .95, so Bob's hands will be just slightly smaller than average. And those are just his hands. He's got a whole body left to put together.