#!/usr/bin/env python3 # coding: utf-8 u"""\ breed.py - a web application for finding breeding chains for pokemon moves. You can add a parent into the list by appending ?parent=ID to the url (where ID is the national ID number of a pokemon). You can specify the Generation by adding ?gen=GEN to the url (where GEN is 1, 2, 3, or 4). The database is from Veekun, and you can get it at . HOW BREEDING WORKS When two pokemon are in the Daycare Center and both Pokemon share a breeding group and the two pokemon are of opposite gender, they may make an egg. If so, then the following rules hold: - The Species of the egg will be the Base form of the female parent. - If the mother is Nidoran♀, the baby will be Nidoran♀ or Nidoran♂ - If the mother is Illumise, the baby will be Volbeat or Illumise. - For each of the moves known by the male parent, if the baby can learn the move as an Egg Move or by TM, the baby will know that move. - If the baby can learn a move by Level Up, and *both* parents know that move, then the baby will start out knowing that move. Weirdness: - In some cases, there is an extra baby form which can only be created by giving the mother a special Incense. In these cases, the baby usually can learn some moves which the base form cannot. - Smeargle can learn *any* move via sketch + except Struggle (all Generations) + except Selfdestruct, Explosion, Metronome & Transform (Gen II) + except Chatter (Gen IV) - Male-only pokemon *can* pass on moves when they breed with ditto, but only to the base form of that species (because of ditto). The only Male-only pokemon which have any Egg Moves are Tyrogue, Nidoran♂ and Volbeat. Nidoran♂ and Volbeat don't count, because of the weirdness mentioned above. TODO list: - Add a moveset chain generator. - Sort the move chain list. First group by breeding group, then sort by name (or something. Figure out some sort of rank for figuring out best pokemon to display a group under. (This mostly matters at the parent level; there's usually not much choice deeper in the chains.) Possible factors for parent pokemon: evolution stage, level move learned at, evolution method (level is better than trade w/ item). Possible factors for non-parent pokemon: i dunno. maybe the number of groups it's in. - Add Smeargle (Sketch) - Fix babies (for real) """ import flask app = flask.Flask('breed') from flask import request import sqlalchemy as sqla import sqlalchemy.event from sqlalchemy import sql import sys import os import functools from textwrap import dedent from time import time from warnings import warn from collections import defaultdict try: from roman import toRoman except ImportError: toRoman = str ##### Helper functions def plural(n, name, extension='s', alt=None): if alt is None: alt = name + extension string = str(n) + " " if n == 1: string += name else: string += alt return string def fixyield(f): @functools.wraps(f) def fixyield(*args, **kw): return u'\n'.join(f(*args, **kw)) return fixyield ##### The main program CURRENT_GEN = 4 egg_groups = u"monster water1 bug flying ground fairy plant humanshape water3 mineral indeterminate water2 ditto dragon noeggs".split() methods = u"level egg tutor machine".split() class Pokemon(object): _cache = {} def __init__(self, id=None, **kw): self.__dict__.update(kw) self.id = id or getattr(self, 'id') if id in (175, 447): # togepi and riolu are babies self.is_baby = True if isinstance(self.method, int): self.method = methods[self.method-1] self.egg_groups = set() #if id in self._cache: # warn('%s is already in the cache' % self) # disabling the cache for now #self._cache[id] = self @classmethod def get_pokemon(cls, id): """get a Pokemon object for the pokemon of the specified national id If a Pokemon object has already been created, returns that object. Otherwise, hits the database. """ # disabling the cache for now #if id in cls._cache: # return cls._cache[id] conn = meta.bind.connect() stmt = sql.select([ pokemon_table.c.id, pokemon_table.c.name, sql.literal('forced').label('method'), pokemon_table.c.gender_rate.label('gender'), pokemon_table.c.evolution_chain_id.label('evid'), pokemon_table.c.evolution_parent_pokemon_id.label('evparent'), pokemon_table.c.is_baby, ]) stmt = stmt.where(pokemon_table.c.id == id) q = list(conn.execute(stmt)) if len(q) == 0: raise IndexError('No pokemon with id %r' % id) elif 1 < len(q): # XXX Need better error message/type raise ValueError('Too many pokemon') poke = cls(**q[0]) t = pokemon_egg_groups_table q = (sql.select([t.c.pokemon_id, t.c.egg_group_id]) .where(t.c.pokemon_id == id)) for row in q.execute(): egg_group = egg_groups[row.egg_group_id-1] poke.egg_groups.add(egg_group) # disabling the cache for now #cls._cache[id] = poke #web.debug('Retrieved pokemon %r' % poke) return poke @classmethod def from_query(cls, stmt): """return Pokemon objects for each row of an SQL query""" conn = meta.bind.connect() pokemon = [cls(**row) for row in conn.execute(stmt)] pokeinfo = dict((p.id, p) for p in pokemon) ids = (p.id for p in pokemon) eg = pokemon_egg_groups_table q = (sql.select([eg.c.pokemon_id, eg.c.egg_group_id]) .where(eg.c.pokemon_id.in_(ids)) ) for row in q.execute(): egg_group = egg_groups[row.egg_group_id-1] pokeinfo[row.pokemon_id].egg_groups.add(egg_group) return pokemon def __hash__(self): return hash((self.id, self.method)) def __eq__(self, other): if self is other: return True elif isinstance(other, Pokemon): return self.id == other.id and self.method == other.method return False def __repr__(self): return u"" % (self.id, self.name) #def merge_tree(tree_rows): # tree = [] # for # tree_rows.reverse() # base = tree_rows.pop() # base = [(i, (x, None)) for i, x in base] # def combine(b, a): # i = j = 0 # for i, (n, x) in a: # while b[j][0] == i: # if m == n: # a[i] = (n # # while tree_rows: # row, base = new, tree_rows.pop() # new = [] # i = 0, j = 0 # # while True: # n, leaf = row[j] # if n == i: # e.append(row) # if def do_lowest(pokemon): """Given a list of Pokemon, returns a new list containing only the lowest-stage pokemon from each evolution family.""" evo_groups = defaultdict(list) for p in pokemon: evo_groups[p.evid].append(p) lowest = [] for group in evo_groups.values(): # XXX shouldn't modify the list we're iterating over for p in group: if p.evparent in group: group.remove(p) lowest.append(group[0]) return lowest def build_tree(parents, bases): parents.sort(key=lambda p: (p.gender in (8, -1), sorted(p.egg_groups), p.name)) bases.sort(key=lambda p: (p.gender in (8, -1), -len(p.egg_groups), sorted(p.egg_groups), p.name)) current = [(0, x) for x in parents] tree = [] used = set() while current: tree.append(current) last = current current = [] for (i, (_, p)) in enumerate(last): if 'noeggs' in p.egg_groups: continue if p.gender in (8, -1): continue # We would like to show all parents which share an egg group # above the children, rather than showing the children after # just one parent and leaving the other possible parents hidden # after the children. if (i+1 < len(last) and last[i+1][1].gender not in (8, -1)): egg_groups = p.egg_groups - last[i+1][1].egg_groups else: egg_groups = p.egg_groups if not egg_groups: continue for p2 in bases: if p2 in used: continue if 'noeggs' in p2.egg_groups: continue if p2.gender == -1: continue if p2.gender == 0: if p2.id in (32, 313): # Nidoran-m and Volbeat pass # Male-only families can pass on moves to the baby form # when breeding with ditto. # (Tyrogue is the only Male-only species with egg moves) elif p2.evid == p.evid: pass else: continue if len(p2.egg_groups & egg_groups) == 0: continue #else: # #print >>sys.stderr, p2.name.encode('ascii', 'ignore') current.append((i, p2)) used.add(p2) return tree def get_parents(moveid, gen=CURRENT_GEN): """get all the pokemon that can learn a move by level-up, plus base forms for any baby pokemon""" stmt = sql.select([ pokemon_table.c.id, pokemon_table.c.name, pokemon_moves_table.c.pokemon_move_method_id.label('method'), pokemon_moves_table.c.level, pokemon_table.c.gender_rate.label('gender'), pokemon_table.c.evolution_chain_id.label('evid'), pokemon_table.c.evolution_parent_pokemon_id.label('evparent'), pokemon_table.c.is_baby, ]) stmt = stmt.select_from( pokemon_table .join(pokemon_moves_table, pokemon_moves_table.c.pokemon_id == pokemon_table.c.id) .join(version_group_table, version_group_table.c.id == pokemon_moves_table.c.version_group_id) ) stmt = stmt.where(sql.and_( pokemon_moves_table.c.move_id == moveid, pokemon_moves_table.c.pokemon_move_method_id == 1, # levelup )) stmt = stmt.where(pokemon_table.c.generation_id <= gen) stmt = stmt.where(version_group_table.c.generation_id == gen) stmt = stmt.group_by(pokemon_table.c.id) pokemon = Pokemon.from_query(stmt) babies = [p for p in pokemon if p.is_baby] if not babies: # no further processing needed return pokemon for p in babies: p.evos = [] # since baby pokemon are not capable of breeding (they are in the noeggs # group), we must load the parent pokemon stmt = sql.select([ pokemon_table.c.id, pokemon_table.c.name, pokemon_moves_table.c.pokemon_move_method_id.label('method'), pokemon_table.c.gender_rate.label('gender'), pokemon_table.c.evolution_chain_id.label('evid'), pokemon_table.c.evolution_parent_pokemon_id.label('evparent'), pokemon_table.c.is_baby, ]) stmt = stmt.select_from( pokemon_table .outerjoin(pokemon_moves_table, sql.and_( pokemon_moves_table.c.pokemon_id == pokemon_table.c.id, pokemon_moves_table.c.move_id == moveid, pokemon_moves_table.c.pokemon_move_method_id == 1, # levelup )) .outerjoin(version_group_table, version_group_table.c.id == pokemon_moves_table.c.version_group_id) ) stmt = stmt.where(pokemon_table.c.evolution_parent_pokemon_id.in_(p.id for p in babies)) stmt = stmt.where(sql.or_( pokemon_moves_table.c.move_id == None, version_group_table.c.generation_id == gen, )) stmt = stmt.group_by(pokemon_table.c.id) q = Pokemon.from_query(stmt) pokeinfo = dict((p.id, p) for p in pokemon) for p in q: p.evparent = pokeinfo[p.evparent] p.evparent.evos.append(p) for p in babies: if not p.evos: continue for e in p.evos: if e.method == 'level': pokemon.append(e) else: e.method = 'evolve' pokemon.append(e) pokemon.remove(p) return pokemon def get_pokemon(moveid, gen=CURRENT_GEN): """get all the pokemon that can learn a move as an egg move or via a technical machine, plus base forms for any baby pokemon""" stmt = sql.select([ pokemon_table.c.id, pokemon_table.c.name, pokemon_moves_table.c.pokemon_move_method_id.label('method'), pokemon_moves_table.c.level, pokemon_table.c.gender_rate.label('gender'), pokemon_table.c.evolution_chain_id.label('evid'), pokemon_table.c.evolution_parent_pokemon_id.label('evparent'), pokemon_table.c.is_baby, ]) stmt = stmt.select_from( pokemon_table .join(pokemon_moves_table, pokemon_moves_table.c.pokemon_id == pokemon_table.c.id) .join(version_group_table, version_group_table.c.id == pokemon_moves_table.c.version_group_id) ) stmt = stmt.where(sql.and_( pokemon_moves_table.c.move_id == moveid, pokemon_moves_table.c.pokemon_move_method_id.in_((2, 4)), # egg-move, machine pokemon_table.c.evolution_parent_pokemon_id == None, )) stmt = stmt.where(pokemon_table.c.generation_id <= gen) stmt = stmt.where(version_group_table.c.generation_id == gen) stmt = stmt.where(pokemon_table.c.forme_name == None) stmt = stmt.group_by(pokemon_table.c.id) pokemon = Pokemon.from_query(stmt) babies = [p for p in pokemon if p.is_baby] if not babies: # no further processing needed return pokemon for p in babies: p.evos = [] # since baby pokemon are not capable of breeding (they are in the noeggs # group), we must load the parent pokemon stmt = sql.select([ pokemon_table.c.id, pokemon_table.c.name, pokemon_moves_table.c.pokemon_move_method_id.label('method'), pokemon_table.c.gender_rate.label('gender'), pokemon_table.c.evolution_chain_id.label('evid'), pokemon_table.c.evolution_parent_pokemon_id.label('evparent'), pokemon_table.c.is_baby, ]) stmt = stmt.select_from( pokemon_table .outerjoin(pokemon_moves_table, sql.and_( pokemon_moves_table.c.pokemon_id == pokemon_table.c.id, pokemon_moves_table.c.move_id == moveid, pokemon_moves_table.c.pokemon_move_method_id.in_((2,4)), # egg-move, machine )) .outerjoin(version_group_table, sql.and_( version_group_table.c.id == pokemon_moves_table.c.version_group_id, version_group_table.c.generation_id == gen, )) ) stmt = stmt.where(pokemon_table.c.evolution_parent_pokemon_id.in_(p.id for p in babies)) stmt = stmt.group_by(pokemon_table.c.id) q = Pokemon.from_query(stmt) pokeinfo = dict((p.id, p) for p in pokemon) for p in q: p.evparent = pokeinfo[p.evparent] p.evparent.evos.append(p) for p in babies: if not p.evos: continue for e in p.evos: e.method = 'evolve' pokemon.append(e) pokemon.remove(p) return pokemon ##### the webpage classes meta = sqla.MetaData() @app.template_filter('roman') def roman_filter(arg): return toRoman(arg) @app.route("/") def index(): #if not web.ctx.path.endswith('/'): # raise web.redirect('/') xgen = request.args.get("gen", None) gen = int(xgen) if xgen is not None else CURRENT_GEN q = sql.select([move_table]).order_by('name') if xgen is not None: q = q.where(move_table.c.generation_id <= gen) moves = q.execute() generations = list(range(2, CURRENT_GEN+1)) template = dedent(u"""\ Pokémon Breeding Chains

{% for move in moves -%} {{ move.name }} {% endfor %}

{% for i in generations -%} {% if i == gen -%} Generation {{ i|roman }} {% else -%} Generation {{ i|roman }} {% endif %} {% endfor %}

""") return flask.render_template_string(template, moves=moves, generations=generations, gen=gen, xgen=xgen) @app.route("/") def findtree(moveid): time_a = time() q = sql.select([move_table.c.id, move_table.c.name]).where(move_table.c.id==moveid) q = q.execute() move = q.first() if move is None: flask.abort(404) gen = int(request.args.get("gen", CURRENT_GEN)) parents = get_parents(moveid, gen) parents = do_lowest(parents) pokemon = get_pokemon(moveid, gen) # inject a parent extra = request.args.getlist("parent") parents.extend(Pokemon.get_pokemon(x) for x in extra) tree = build_tree(parents, pokemon) #print(repr(tree)) time_b = time() all_pokemon = set(parents) | set(pokemon) done_pokemon = set() for row in tree: done_pokemon.update(p for _, p in row) orphan_pokemon = set(pokemon) - done_pokemon orphan_pokemon_groups = set(g for p in orphan_pokemon for g in p.egg_groups) all_groups = set(g for p in all_pokemon for g in p.egg_groups) done_groups = set(g for p in done_pokemon for g in p.egg_groups) orphan_groups = all_groups - done_groups orphan_groups.discard('noeggs') info = { 'move': move, 'tree': tree, 'done_pokemon': done_pokemon, 'done_groups': done_groups, 'orphan_pokemon': orphan_pokemon, 'orphan_pokemon_groups': orphan_pokemon_groups, 'orphan_groups': orphan_groups, 'time_a': time_a, 'time_b': time_b, } return u"\n".join(render_text(info)), {'content-type': 'text/plain; charset=utf-8'} def render_text(info): yield u"Move #%d - %s\n\n" % (info['move']['id'], info['move']['name']) def recursive_print(tree, level=1, i=0): if not tree: return rest = tree[1:] for j, (n, p) in enumerate(tree[0]): if n == i: prefix = "\t" * level if p.method == 'evolve': prefix += p.evparent.name + " -> " if p.method == 'level': yield u"%s%s L%d (%s)" % ( prefix, p.name, p.level, ','.join(p.egg_groups)) else: yield u"%s%s (%s)" % ( prefix, p.name, ','.join(p.egg_groups)) for x in recursive_print(rest, level=level+1, i=j): yield x for x in recursive_print(info['tree'], level=0, i=0): yield x orphan_pokemon = info['orphan_pokemon'] if orphan_pokemon: orphans = { 'genderless': [], 'male': [], 'noeggs': [], 'baby': [], 'other': [], } for p in sorted(orphan_pokemon, key=lambda p: p.name): if 'noeggs' in p.egg_groups: if p.is_baby: orphans['baby'].append(p) else: orphans['noeggs'].append(p) elif p.gender == -1: orphans['genderless'].append(p) elif p.gender == 0: orphans['male'].append(p) else: orphans['other'].append(p) @fixyield def do_orphans(title, type, groups=False): if not orphans[type]: return yield "\n" + title + ":" for p in orphans[type]: if groups: yield p.name + " (" + ','.join(p.egg_groups) + ")" else: yield p.name #yield u"\n\nOrphans:" yield " " yield do_orphans('Orphan', 'other', groups=True) yield do_orphans('Genderless', 'genderless', groups=True) yield do_orphans('Male-only', 'male', groups=True) yield do_orphans('Babies', 'baby') yield do_orphans('Legendary', 'noeggs') time_a = info['time_a'] time_b = info['time_b'] time_c = time() yield u"\n\n" yield u"%d pokemon in %s" % ( len(info['done_pokemon']), plural(len(info['done_groups']), 'egg group')) yield u"%d orphan pokemon in %s" % ( len(info['orphan_pokemon']), plural(len(info['orphan_pokemon_groups']), 'egg group')) yield u"%s (%s)" % ( plural(len(info['orphan_groups']), 'orphan egg group'), ', '.join(sorted(info['orphan_groups']))) yield u"%d queries in %f (+%f) seconds" % (flask.g.sql_query_count, time_b-time_a, time_c-time_b) @app.route("/about") def about(): return __doc__, {'content-type': 'text/plain; charset=utf-8'} @app.route("/source") def source(): me = __file__ if me.endswith('.pyc'): me = me[:-1] # we don't want to give out the .pyc file assert me.endswith('.py') return flask.send_file(me, mimetype='text/x-python') @app.route("/database") def database(): return flask.send_file("pokedex.sqlite", as_attachment=True, attachment_filename='pokedex.sqlite') ##### The main function @app.before_first_request def setup(): # connect to the db engine = sqla.create_engine("sqlite:///pokedex.sqlite") meta.bind = engine # install event listener sqla.event.listen(engine, "before_cursor_execute", count_queries) # load db tables global pokemon_table global move_table global egg_group_table global pokemon_egg_groups_table global pokemon_moves_table global version_group_table pokemon_table = sqla.Table('pokemon', meta, autoload=True) move_table = sqla.Table('moves', meta, autoload=True) egg_group_table = sqla.Table('egg_groups', meta, autoload=True) pokemon_egg_groups_table = sqla.Table('pokemon_egg_groups', meta, autoload=True) pokemon_moves_table = sqla.Table('pokemon_moves', meta, autoload=True) version_group_table = sqla.Table('version_groups', meta, autoload=True) def count_queries(conn, cursor, statement, parameters, context, executemany): flask.g.setdefault('sql_query_count', 0) flask.g.sql_query_count += 1 def main(): # Set up the environment os.chdir(os.path.dirname(__file__) or '.') app.run(debug=True, port=5002) if __name__ == '__main__': main()