Changeset 329

Timestamp:

09/03/07 03:54:09 (15 months ago)

Author:

eevee

Message:

 

Location:

veekun/trunk

Files:

• lib/Vee/Controller/Dex/Utils.pm (modified) (3 diffs)
• lib/Vee/Schema/PokeMoves.pm (modified) (1 diff)
• lib/Vee/Schema/Pokemon.pm (modified) (2 diffs)
• root/dex-images/tree.png (added)
• templates/dex/page/pokemon.tt (modified) (7 diffs)
• templates/dex/utils/backtrace.tt (modified) (1 diff)

veekun/trunk/lib/Vee/Controller/Dex/Utils.pm

@@ -143 +143 @@
     
     my $gen = 'dp'; # TODO: :(
-    
-    my $pokemon = $c->model('DBIC::Pokemon')->single({ name => $c->req->captures->[0] }, { prefetch => 'breeds' });
-    my $move    = $c->model('DBIC::Moves')  ->single({ name => $c->req->args    ->[0] });  # assumed to be an egg move
+
+    my $pokemon_name = $c->req->captures->[0];
+    my $move_name    = $c->req->args    ->[0];
+
+    # For some reason, Catalyst::DispatchType::Chained doesn't url-decode either
+    # args or captures, so do it here; this is safe to do since valid move and
+    # Pokemon names will never ever contain percent signs..  I hope.
+    $pokemon_name =~ s/%([0-9A-Fa-f]{2})/chr(hex($1))/eg;
+    $move_name    =~ s/%([0-9A-Fa-f]{2})/chr(hex($1))/eg;
+    
+    my $pokemon = $c->model('DBIC::Pokemon')->single({ name => $pokemon_name }, { prefetch => 'breeds' });
+    my $move    = $c->model('DBIC::Moves')  ->single({ name => $move_name    });
+
+    $c->vee_stop('No such Pokémon ', $pokemon_name, '.')
+        if not $pokemon;
+    $c->vee_stop('No such move ', $move_name, '.')
+        if not $move;
 
     $s->{page_title} = $pokemon->name . ' - ' . $move->name . ' parents';
@@ -152 +166 @@
         '<a href="' . $c->uri('Dex', 'pokemon_list') . '">Pok&eacute;mon</a>',
         '<a href="' . $c->uri('Dex', 'pokemon', lc $pokemon->name) . '">' . $pokemon->name . '</a>',
-        'Breeding chains for <a href="' . $c->uri('Dex', 'moves', lc $move->name) . '">' . $move->name . '</a>',
+        'Breeding chains',
+        '<a href="' . $c->uri('Dex', 'moves', lc $move->name) . '">' . $move->name . '</a>',
     ];
 
@@ -163 +178 @@
         -nest  => \ "FIND_IN_SET('$gen', version)",
     });
-    $c->vee_stop($pokemon->name . " can't inherit " . $move->name . ".") unless $inheritable_ct;
+    $c->vee_stop('', $pokemon->name, " can't inherit ", $move->name, '.') unless $inheritable_ct;
     
     my $gender_restriction;
     if ($pokemon->gender == 255) {
-        $gender_restriction = 255;  # must also be genderless, i.e. bred with Ditto
+        # must also be genderless, i.e. bred with Ditto
+        $gender_restriction = 255;
     } else {
-        $gender_restriction = { '!=' => [ 0, 255 ] };  # cannot be female or genderless
-    }
-    
-    my $learners_rs = $c->model('DBIC::PokeMoves')->search({
+        # cannot be single-gender or genderless
+        $gender_restriction = { -not_in => [ 0, 254, 255 ] };
+    }
+
+    ### grab the methods by which any Pokemon learn the move
+
+    my $methods_rs = $c->model('DBIC::PokeMoves')->search({
         moveid => $move->id,
+        method => [qw[ level egg machine ]],
         -nest => \ "FIND_IN_SET('$gen', version)",
         'pokemon.gender' => $gender_restriction,
     }, {
-        prefetch => { pokemon => 'breeds' },
-        order_by => 'me.pokeid ASC',
-        group_by => [ 'pokemon.evid', 'breeds.breed' ],
+        join => 'pokemon',
     });
-
-    my %learners;
+    my %learn_methods;
+    while (my $row = $methods_rs->next) {
+        my $method = ucfirst $row->method;
+        if ($row->method eq 'level') {
+            $method .= ' ' . $row->level;
+        } elsif ($row->method eq 'machine') {
+            $method = 'TM/HM';
+        }
+        warn $method;
+        push @{ $learn_methods{ $row->pokeid } }, $method;
+    }
+
+    ### do a SEPARATE query to grab all the possible Pokemon at once
+    # (DBIC seems to get confused if I prefetch { pokemon => breeds } above)
+    # XXX: is this my fault or theirs?
+
+    my $learners_rs = $c->model('DBIC::Pokemon')->search({
+        id => [ keys %learn_methods ],
+    }, {
+        prefetch => 'breeds',
+        order_by => 'me.id ASC',
+    });
+
+    my (%pokemon);
     while (my $row = $learners_rs->next) {
-        $learners{ $row->pokeid } = $row;  # TODO: arrange better?
+        warn $row->id, ': ', join ' ', $row->breeds;
+        $pokemon{ $row->id } = $row;
     }
 
     my %breeding_tree = ( $pokemon->id => {} );
 
-    my %seen = ( $pokemon->id => 0 );   # hash of ( poke_id => tree_level, ... )
+    my %seen = ( $pokemon->id => 0 );   # hash of ( poke_id => 1, ... )
     my $cur_level = 0;                  # current tree level
     my @this_level = %breeding_tree;    # array of ( poke_id, hashref, ... ) on this level
-    my @next_level;                     # array of ( poke_id, hashref, ... ) created for next level
+
+    ### build the breeding-chain tree
+    # What we need is a tree of ancestors that can learn the move and pass it
+    # down; it should look something like this:
+    # pokemon => {
+    #     a => {
+    #         b => {},
+    #         c => {},
+    #         d => {
+    #             e => {},
+    #         },
+    #     },
+    #     f => {
+    #         g => {},
+    #         d => [ref to former d],
+    #     },
+    # }
+    # The rules are basically that:
+    # 1. Every Pokemon is a key in a hash
+    # 2. Each corresponding value is a similar hash, containing a list of
+    #    Pokemon that are compatible
+    # 3. No infinite looping!
 
     do {
         $cur_level++;
+        my %branches;
+
         while (my $pokeid = shift @this_level) {
-            my $this_poke = $learners{$pokeid}->pokemon;
+            my $this_poke = $pokemon{$pokeid};
             my $hashref = shift @this_level;
 
-            my @fathers = grep {
-                # must be breeding-compatible
-                $this_poke->can_breed_with($_->pokemon) and
-
-                # must not have already been seen in a higher tree level
-                # (both for optimization and to avoid inf. looping)
-                (not exists $seen{ $_->pokeid } or
-                 $seen{ $_->pokeid } >= $cur_level)
-            } values %learners;
-
-            for my $father (@fathers) {
-                $hashref->{ $father->pokeid } = {};
-                $seen{ $father->pokeid } = $cur_level unless exists $seen{ $father->pokeid };
-                push @next_level, $father->pokeid, $hashref->{ $father->pokeid };
-            }
-        }
-        @this_level = @next_level;
-    } while ($cur_level < 10 and scalar keys %learners);
-
+            for my $pokeid (keys %pokemon) {
+                next if not $this_poke->can_breed_with( $pokemon{$pokeid} );
+
+                if (exists $seen{ $pokeid }) {
+                    # don't put anything if this Pokemon has been seen higher
+                    # in the chain; needless descending is bad
+                    $hashref->{ $pokeid } = undef
+                        unless $seen{ $pokeid } < $cur_level;
+                } else {
+                    $hashref->{ $pokeid } = ( $branches{$pokeid} ||= {} );
+                    $seen{ $pokeid } = $cur_level;
+                }
+            }
+        }
+
+        @this_level = %branches;
+    } while ($cur_level < 10 and @this_level);
+
+    ### find the optimal path
+    
+    # since there should only be a small finite number of Pokemon, we can just
+    # iterate over every possibility; flatten into arrays, and take whichever
+    # is shortest
+
+    # TODO: merge this with the actual building of the tree, and toss useless
+    # branches as we go; right now this sub MODIFIES THE TREE, pruning any
+    # branches it finds that don't end with a level; this makes the dupe
+    # removal up top a little silly!
+    my $flattener; $flattener = sub {
+        my ($branch) = @_;
+        my @subchains;
+
+        for my $key (keys %$branch) {
+            if (grep /level/i, @{ $learn_methods{$key} }) {
+                # consider this Pokemon an endpoint if it learns the move
+                # naturally; TMs don't count since they are of limited quantity
+                push @subchains, [ $key ];
+                $branch->{$key} &&= {};
+                next;
+            }
+
+            # ...otherwise, only add more chains if this branch has any valid
+            # subchains of its own
+            my @child_chains = $flattener->( $branch->{$key} );
+            if (@child_chains) {
+                push @subchains, map [ $key, @$_ ], @child_chains;
+            } else {
+                delete $branch->{$key};
+            }
+        }
+
+        return @subchains;
+    };
+
+    # only take the shortest chains; it's possible there could be several!
+    my @flat_chains  = sort { $#$a <=> $#$b } $flattener->( \%breeding_tree );
+    my @optimal_path = grep { $#$_ == $#{ $flat_chains[0] } } @flat_chains;
+    @$_ = reverse @$_ for @optimal_path;
+    
+    ### cram everything important into the stash
     $s->{breeding_tree} = \%breeding_tree;
+    $s->{pokemon}       = \%pokemon;
+    $s->{learn_methods} = \%learn_methods;
+    $s->{optimal}       = \@optimal_path;
 
     $s->{template} = 'dex/utils/backtrace.tt';

veekun/trunk/lib/Vee/Schema/PokeMoves.pm

@@ -12 +12 @@
 __PACKAGE__->add_columns("pokeid", "moveid", "level", "version", "method");
 
+__PACKAGE__->set_primary_key(qw/ pokeid moveid level version method /);
+__PACKAGE__->add_unique_constraint([qw[ pokeid moveid level version method ]], undef);
+
 __PACKAGE__->belongs_to(pokemon => 'Vee::Schema::Pokemon', 'pokeid');
 __PACKAGE__->belongs_to(move => 'Vee::Schema::Moves', 'moveid');

veekun/trunk/lib/Vee/Schema/Pokemon.pm

@@ -5 +5 @@
 use strict;
 use warnings;
-
 use base 'DBIx::Class';
 
@@ -99 +98 @@
 
     # breeds cannot appear twice due to keying, so this is guaranteed to work
-    $breeds{$_}++ for map $poke1->breeding_groups, $poke2->breeding_groups;
+    $breeds{$_}++ for $poke1->breeding_groups, $poke2->breeding_groups;
     delete $breeds{15};
 

veekun/trunk/templates/dex/page/pokemon.tt

@@ -388 +388 @@
 [% END %]
 [% END %]
+
 <!-- ####################################################################### -->
 
@@ -404 +405 @@
 [% END %]
 
-[% version_headers = FOR ver IN header_icons %]
+[% version_headers = BLOCK %]
+    <th class="level"></th>
+[%     FOR ver IN header_icons %]
 <th class="level">[% Icons.$ver %]</th>
+[%     END %]
 [% END %]
 
@@ -442 +446 @@
 [% FOREACH move IN moves.level %]
 <tr class="color[% color %]">
+ <td></td>
 [%     FOREACH ver IN move_columns %]
  <td class="level"> [% move.versions.$ver ? ( move.versions.$ver == 1 ? '--' : move.versions.$ver ) : '' %] </td>
@@ -456 +461 @@
 [%         moveid = move.moveid %]
 <tr class="color[% color %]">
+ <td><a href="[% dex_uri('pokemon', this.name) %]/backtrace/[% MoveData.$moveid.name | lower %]"><img src="/dex-images/tree.png" alt="Chains" title="Breeding chains"/></a></td>
 [%         IF generation == 0 %] <td class="level"> </td>[% IF move_columns_inv.y %] <td class="level"> </td>[% END %][% END %]
 [%         IF generation <= 1 %]
@@ -479 +485 @@
 [%         moveid = move.moveid %]
 <tr class="color[% color %]">
+ <td></td>
 [%         IF generation == 0 %] <td> </td>[% IF move_columns_inv.y %] <td> </td>[% END %][% END %]
 [%         IF generation <= 1 %]
@@ -506 +513 @@
 [%         moveid = move.moveid %]
 <tr class="color[% color %]">
+ <td></td>
  <td colspan="[% move_columns.size %]" class="level"> [% move.method %] </td>
 [%         move_cells(moveid) %]
@@ -519 +527 @@
 [%         moveid = move.moveid %]
 <tr class="color[% color %]">
+ <td>[% IF move.versions.dp %]<a href="[% dex_uri('pokemon', this.name) %]/backtrace/[% MoveData.$moveid.name | lower %]"><img src="/dex-images/tree.png" alt="Chains" title="Breeding chains"/></a>[% END %]</td>
 [%         IF generation == 0 %]
  <td colspan="[% move_columns_inv.y ? 2 : 1 %]">[% IF move.versions.rb; tm_name(MoveTMs.$moveid.0); END %]</td>

veekun/trunk/templates/dex/utils/backtrace.tt

@@ -1 +1 @@
 [% PROCESS 'dex/common.tt' %]
 
-[% BLOCK breeding_branch %][%# branch %]
-<ul>
-[%     FOREACH pokemon IN branch.keys %]
-<li>
-[% pokemon %]: [%+ PokemonNames.$pokemon %]
-[%     IF branch.$pokemon.keys.size %]
-[%         INCLUDE breeding_branch branch=branch.$pokemon %]
+<h1>Optimal Chains</h1>
+[% FOREACH chain IN optimal %]
+<p>
+[%     FOREACH pokeid IN chain %]
+<a href="[% dex_uri('pokemon', pokemon.$pokeid.name) %]" class="dex-pokelist"><img src="/dex-images/icons/[% pokeid.pad(3) %].png" alt="[% pokemon.$pokeid.name %]"/></a>
+[%         UNLESS loop.last %]
+<img src="/images/see-also.png" alt="to"/>
+[%         END %]
 [%     END %]
-</li>
-[%     END %]
-</ul>
+</p>
 [% END %]
 
-[% INCLUDE breeding_branch branch=breeding_tree %]
+<h1>Full Breeding Tree</h1>
 
+[%# bypass MACRO's implicit my-ing of any assigned var %]
+[% color_hack = [1] %]
+
+[% MACRO breeding_branch(branch, depth) BLOCK %]
+[%     FOREACH pokeid IN branch.keys %]
+<tr class="color[% color_hack.0 %]">
+[%         color_hack.0 = 3 - color_hack.0 %]
+    <td style="padding-left: [% depth * 32 %]px;"><a href="[% dex_uri('pokemon', pokemon.$pokeid.name) %]"><img src="/dex-images/icons/[% pokeid.pad(3) %].png" alt=""/> [% pokemon.$pokeid.name %]</a></td>
+    [%# TODO: lol I am being so lazy with these 8V %]
+    <td class="center">[% learn_methods.$pokeid.join('<br/>') %]</td>
+[%         pokemon_cells(pokemon.$pokeid) %]
+</tr>
+[%         IF branch.$pokeid.keys.size %]
+[%             next_depth = depth + 1 %]
+[%             breeding_branch(branch.$pokeid, next_depth) %]
+[%         END %]
+[%     END %]
+[% END %]
+
+<table class="dex-table dex-pokemon" cellspacing="0">
+<tr class="heading">
+    <th>Pok&eacute;mon</th>
+    <th>Learns by</th>
+[% pokemon_header %]
+</tr>
+[% breeding_branch(breeding_tree, 0, 1) %]
+</table>
+