I visit Dragon Cave, a virtual pets website where you breed and hatch virtual dragons. A large part of the main interest is in creating impressive dragon lineages, whether attractive looking or long. Many users, including myself do not want to accidentally breed two related dragons together and create an inborn dragon. Finding out whether two dragons are related is rather hard to do on the site. To solve this problem, I wrote a program in Python with Beautiful Soup that can calculate the Coefficient of Inbreeding and Coefficient of Relationship of two given dragons.
The two main hurdles in this project were (1) finding and implementing the calculation of the coefficients and (2) minimizing the number of HTTP requests sent by the program.
Finding and Implementing the Calculation of the Coefficients
These coefficients are used by professional breeders in real life. They are especially used by dog and horse breeders who want to breed for certain traits while avoiding inbreeding too much. To implement the calculation of these coefficients required research into exactly how they are calculated. This was more difficult than I expected because many examples are much too simplistic to be of any use. I eventually found a site explaining in enough detail a general algorithm that I could use.
My implementation builds a tree of the dragon’s entire lineage and finds any common ancestors of the mother and father. It then builds a path from the dragon to the common ancestor and uses the length of that path in the calculation. The method is then recursively called on the common ancestor. This is repeated for every common ancestor.
The coefficients can be calculated to within one percent of accuracy if the lineage is known to 10 generations, but since unlike real animals, these dragons have their complete lineages recorded online, I decided to get the most precise calculation I could, instead of stopping the calculation at 10 generations.
Minimizing the Number of HTTP requests sent by the program
To increase the speed of the program and to decrease the load on the Dragon Cave website, I aimed to minimize the number of HTTP requests sent by the program.
In my first implementation I used a dragon’s main info page which has links to its mother and father. This required an HTTP request for every single dragon in the lineage.
Then I designed an algorithm to read in the HTML table on a dragon’s lineage page into a tree data structure. The HTML for these tables is very unintuitive, especially on unbalanced lineages. Once that was implemented it only needs to load the first lineage page and a couple more if there are more ancestors than would fit on the first page.
This exponentially decreased the number of HTTP requests needed and sped up the program tenfold.