Messages

1

Off Topic / Re: Thrive project

« on: April 14, 2014, 12:05:16 AM »

A quick look at the wiki and I had difficulty telling the difference between the high level descriptions of Thrive and Spore. I remember some early footage of the Spore development and it seemed to have so much promise. One of the most intriguing ideas was "verb creation" where your creature could learn a small set of skills and combine them in ways not explicitly defined by its genetic structure. A specific example was bite + move = drag; you would bite an object or dead enemy and move to drag it behind you perhaps to your nest.

As the game moved closer to release, it lost any of this complexity and instead focused more on the aesthetic unit and building creators. When you say that Thrive is trying to create a game that Spore would have been, I'd love to know what exactly it's adding/removing/changing to improve on the concept of Spore. Obviously being open source is a plus but I doubt that's the extent of it.

Maybe there's some information that I skipped over in my browsing.

2

Darwinbots Program Source Code / Re: Need fastest possible code to compare dna

« on: February 07, 2014, 08:00:08 PM »

Oh gosh. I forgot that you were developing in the "ancient" VB6. Of course that makes more sense with the values in DB having a range of -32,768 to 32,767.

Luckily, "<< 16" can be replicated by multiplying by 2^16 (Using 16 instead of 32 because VB6 Integers are half the size of VB.NET Integers).

Code: [Select]

Dim nucleic As Long
nucleic = tipo * 2^16          ' Edit: You will still probably need to cast tipo as a long for this to work
nucleic = nucleic Or value

And just so that I'm clear, combining the tipo and value isn't required for the algorithm to work. You can also compare them individually and if either are different, increase the local edit distance.

I also remembered about the Damerau?Levenshtein distance which can handle transposition of adjacent elements. I don't think you'd want this in your particular case, but I thought I'd throw it out there.

3

Darwinbots Program Source Code / Re: Need fastest possible code to compare dna

« on: February 07, 2014, 05:34:50 PM »

<< is not supported in vb

This MSDN page told me that it is present in all versions of VB dating back to VS2005. I guess you can't always trust what you read on the internet. 

4

Darwinbots Program Source Code / Re: Need fastest possible code to compare dna

« on: February 07, 2014, 05:24:59 PM »

I highlighted the final edit distance in the picture. To convert to a percent difference, I think the most intuitive way would be to run through the algorithm and then do: percentage = edit_distance/size_of_longest_array * 100 percentage = (1 - edit_distance/size_of_longest_array) * 100

So in the kitten:sitting example you'd get:

Code: [Select]

percentage = (1 - 3/7)*100 = ~58%
And in the Saturday:Sunday example you'd get:

Code: [Select]

percentage = (1 - 3/8)*100 = ~63%
Edit: Fixed the example to correspond to your request. Percentage now represents similarity rather than difference.

5

Darwinbots Program Source Code / Re: Need fastest possible code to compare dna

« on: February 07, 2014, 05:01:13 PM »

A couple of points about the edit distance produced by the Levenshtein algorithm:

• It will find the distance to transform a string not only with substitutions, but also insertions and deletions. The edit distance between ACG and ATCG is 1 because one insertion is required for the first sequence. I don't know if that is the desired functionality for you.
• The final result of the computation is a matrix that contains all of the edit distances for each of the substrings. This allows you at the end to find the exact path that generated the complete shortest distance. The final edit distance will be found at I_MAX, J_MAX where those are the lengths of the arrays. You may not need this extra functionality, which means there are optimizations for the space complexity of the algorithm.

I looked up and there is a double-wide integral type for Visual Basic (LONG and ULONG), so my suggestion to simplify the algorithm (with at least a small hit to performance) stands as an alternative. Each block could become a single value for comparison (I have virtually no experience with Visual Basic so I apologize if the code below is gibberish):

Code: [Select]

Dim nucleic As Long
nucleic = tipo << 32          ' Edit: You will probably need to cast tipo as a long for this to work, based on a cursory glance at the MSDN pages
nucleic = nucleic Or value


6

Darwinbots Program Source Code / Re: Need fastest possible code to compare dna

« on: February 07, 2014, 03:21:13 PM »

So that's just Spanish for type then? I'm guessing that dates all the way back to Carlo's original code.

I was trying to interpret it as some special abbreviation, and couldn't come up with anything.

7

Darwinbots Program Source Code / Re: Need fastest possible code to compare dna

« on: February 07, 2014, 03:10:42 PM »

Okay, that's what I would have guessed. Instead of Strings (which can be thought of as character arrays), you'll have the two complete DNA sequences as your strings. The only major modification you should have to make to the standard algorithm is instead of comparing a single character, you'll have to compare two Integers and only consider that block (character) equivalent if both tipo and value are the same.

Another option, if you have access to double-wide data types, would be to store both the tipo (What does this stand for?) and the value in a single Double (or whatever it might be called) and then you would only have to compare a single data point. This approach would likely be less efficient though.

I'd offer up some pseudo-code, but I don't really know Visual Basic which is the language of choice for DarwinBots if memory (and your code sample) serves. For the standard String comparison though, Rosetta Code has an example. http://rosettacode.org/wiki/Levenshtein_distance#Visual_Basic_.NET
I can't really comment on the efficiency of that implementation but it might be enough to get you started.

8

Darwinbots Program Source Code / Re: Need fastest possible code to compare dna

« on: February 07, 2014, 02:19:43 PM »

My first thought is some kind of modified two character Levenshtein distance. I can expand on this process if you tell me more about what you consider similar DNA.

1) Should the block be considered distinct if just the value is different and the tipo is the same.
2) Should the block be considered distinct if just the tipo is different and the value is the same.
3) Should the block be considered distinct if either the tipo or the value is the same edit: different.

The nice thing about the Levenshtein distance algorithm is you should be able to find a very efficient solution in almost any language.

9

Newbie / Re: Greetings and other miscellany

« on: January 30, 2014, 01:25:51 AM »

Love the quick response!

Thanks for the link to the copyright notice. I wasn't too worried about strictly violating the license seeing as I'm not reusing any existing code, but I'm no IP expert and the specifics of open source licenses have always been a fuzzy area for me. I just don't want to cause unnecessary drama by creating a feature-derivative copy when there are literally hundreds of other projects I can choose. I'm glad that it doesn't look like any of that will be an issue though.

In terms of the specifics, I will be programming my simulation in Java due to familiarity (or maybe another JVM language like Scala if I'm feeling adventurous). I haven't settled on any one representation of the universe yet as I wanted to handle the legal bits before continuing onto anything too involved. Since it was the dynamic nature of Darwinbots that first caught my eye, I'm going to attempt a physics based simulation rather than grid based (I may revisit this decision if it impacts the rest of the design).  I do know of the Java port of box2D, and thank you for reminding me of its existence.

10

Newbie / Greetings and other miscellany

« on: January 29, 2014, 11:48:54 PM »

I'd like to say hello and nice to meet you all. That feels a little strange since I've been lurking for years now (almost a decade  ) watching the project develop from the sidelines. I just have to say that I'm really impressed with the work started by Carlo and continued here in this community. I've really enjoyed the concept and execution of the program.

That said, I'm going to try and transition into a programming related job after spending time in the healthcare field. This means I've been looking for a project that I can work on for the next couple of months to show potential employers that I'm capable of developing a medium sized, multifaceted product from the ground up. I'd love to do a simplified clone of Darwinbots as my self-assigned showcase. So my most pressing question at this point, what is Darwinbots license? I don't intend to use any of the code for obvious reasons, but I would like to "borrow" much of the design as the basis for my simulator. Any guidance (legal, creative, professional) from the current developers would be greatly appreciated.

Now that I've bothered to make an account after all this time, I should be at least a little more active. Expect to see more of me in the future.