encukou/test-0 — Issue #40: Breeding chain calculator
Author: encukou
Created: 2011-11-03 18:46:09+00:00
State: open
Labels: feature, gadgets, immediate, involved

**Reported by [Eevee](http://bugs.veekun.com/users/1) on 2009/08/12 23:00:16 +0000 · Migrated from [Redmine issue 68](http://bugs.veekun.com/issues/68)**

---

This is hard and I don’t know what to do about it.

I think I may have to drop the whole Pokémon chart thing and just show the names and sprites. Maybe use encounter data to figure out how hard they are to actually obtain.

Also, try to draw a family tree of some sort?

And what about TMs…

Check old Trac for a bunch of complaints about the current system.

References:
\* [Smogon’s list of illegal movesets](http://www.smogon.com/forums/showthread.php?t=63782)
\* [Sabresite’s notes on chain breeding](http://projectpokemon.org/forums/showthread.php?668-Chain-Breeding)

Redmine metadata:
Updated on: 2011/04/28 12:17:22 +0000
Start date: 2009/08/12
Done ratio: 40%
Relations:
duplicated #687

---

**Comment by [En-Cu-Kou](http://github.com/encukou) from 2011/04/28 12:17:22 +0000**

Maybe I should go all the way and write a C extension.

---

**Comment by [En-Cu-Kou](http://github.com/encukou) from 2011/04/28 01:20:40 +0000**

Every move a pokémon can learn would be simpler: now that pre-evos are in, just add Ninjask’s moves to Shedinja, everything but Chatter and Struggle to Smeargle, and all the event & colosseum pokémon…. That should be pretty much it I guess.

And yes, it’s not elegant code at all. Unfortunately, a beautiful (er) implementation using ORM objects took 5 seconds where this takes less than one. And in this case it matters :(
Oh, and I got some people to design tests for some of the corner cases. Those don’t really simplify things :(

As for the logic itself, well, most of it is quite simple – for a thousand lines of mostly algorithmic code, anyway.
First load everything that could be of use to appropriate data structures (minimizing no. of queries), then there’s the confusing part about making the breed graph (it figures out which movesets are worthwile to pass to which egg groups, which serves to limit unnecessary breeding; run with -dd to see the output), and then there’s a standard state space search in the Node classes which figure out what can be done with the pokémon next – quite easy to follow the big picture if you look at the method names, and the details aren’t all that hard to follow either IMO.

---

**Comment by [Eevee](http://bugs.veekun.com/users/1) from 2011/04/28 00:30:34 +0000**

General moveset finding is probably the best way to go about this, yeah. I’ve said somewhere (maybe in redmine, maybe not) that I’d also like some way to see every move a Pokémon can learn and how.

But the logic, aaaaauahgh.

---

**Comment by [En-Cu-Kou](http://github.com/encukou) from 2011/04/27 23:20:17 +0000**

I made one as well, see the encukou-movesets branch. It validates a pokémon’s moveset by searching for a way to obtain it. It tries to find a reasonable one, but if the user doesn’t like the result, individual pokémon/version groups may be excluded from the search. Currently there’s only a CLI interface.
With breeding, trading, tutors, evolution, Sketch, Shedinja, evolution-inducing moves and soon events, even this largely brute-force approach is pretty complicated…
It does consume quite a lot of CPU for complicated chains, and even more for complicated illegal combinations. Don’t know if that’s suitable for the web.
With some more work it could be expanded to list all pokémon that learn a particular moveset, for use in the Awesome search and/or “list other possible parents” links next to breeding suggestions on the gadget’s result page.

---

**Comment by [Eevee](http://bugs.veekun.com/users/1) from 2010/12/03 06:41:36 +0000**

I have made *a dent*.

Done: 0% ⇨ 40%

---

**Comment by [Eevee](http://bugs.veekun.com/users/1) from 2010/10/08 08:01:00 +0000**

Assignee ⇨ —

---

**Comment by [Eevee](http://bugs.veekun.com/users/1) from 2010/10/07 02:00:02 +0000**

Target version: 2010 Q3 ⇨ —

---

**Comment by [Eevee](http://bugs.veekun.com/users/1) from 2010/04/13 19:27:36 +0000**

Target version: 14 ⇨ 16

---

**Comment by [Eevee](http://bugs.veekun.com/users/1) from 2010/04/13 19:43:29 +0000**

Target version: 16 ⇨ 2010 Q3

---

**Comment by [Eevee](http://bugs.veekun.com/users/1) from 2010/09/13 02:32:15 +0000**

Bumping this up since the old site is now dead.

category_id: None ⇨ 8
priority_id: 5 ⇨ 7