X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~yarrgweb/git?p=ypp-sc-tools.db-test.git;a=blobdiff_plain;f=yarrg%2Frssearch.c;h=245070e9ad6c34740f576707dee52dca95df03b1;hp=0286584dddaa5f5045ce392a2b3e2350f119b0f8;hb=d3e7c3bd4fdd22952861782197f02115da645bc6;hpb=39c06791f9cefbedf3438c2a661716142c889bee diff --git a/yarrg/rssearch.c b/yarrg/rssearch.c index 0286584..245070e 100644 --- a/yarrg/rssearch.c +++ b/yarrg/rssearch.c @@ -1,4 +1,29 @@ -/**/ +/* + * Route searcher - recursive iteration over all routes + */ +/* + * This is part of the YARRG website, a tool for assisting + * players of Yohoho Puzzle Pirates. + * + * Copyright (C) 2009 Ian Jackson + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as + * published by the Free Software Foundation, either version 3 of the + * License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see . + * + * Yohoho and Puzzle Pirates are probably trademarks of Three Rings and + * are used without permission. This program is not endorsed or + * sponsored by Three Rings. + */ #include "rscommon.h" @@ -15,6 +40,7 @@ static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */ static sqlite3_stmt *ss_neigh; static int ports[MAX_ROUTELEN]; +static int final_isle; static Neighbour *get_neighbours(int isle) { Neighbour **np= &neighbours[isle]; @@ -23,7 +49,8 @@ static Neighbour *get_neighbours(int isle) { SQL_BIND(ss_neigh, 1, isle); while (SQL_STEP(ss_neigh)) { - Neighbour *add= mmalloc(sizeof(*add)); + Neighbour *add; + NEW(add); add->islandid= sqlite3_column_int(ss_neigh, 0); add->dist= sqlite3_column_int(ss_neigh, 1); add->next= head; @@ -36,38 +63,29 @@ static Neighbour *get_neighbours(int isle) { } -static PotentialResult ***strat_base; +static Bucket ***buckets_base[GRANUS]; -static inline int isle2arch(int isle) { - int arch= islandid2arch[isle]; - assert(arch>=0); - return arch; -} - static double process_route(int nports, int totaldist, double overestimate_excepting_tail) { - int i; + int i, ap, granui; int leagues_divisor= totaldist + nports; ctr_routes_considered++; + int wrong_final= final_isle && ports[nports-1] != final_isle; + debugf("========== ROUTE"); for (i=0; i=2) { int pair[2], i; pair[1]= ports[nports-1]; - double guess_absolute= overestimate_excepting_tail; - + guess[A]= overestimate_excepting_tail; + for (i=0; iroute_tail_value= value_route(2, pair, pair[0]!=pair[1]); } - guess_absolute += ip->route_tail_value; + guess[A] += ip->route_tail_value; } - double guess_perleague= guess_absolute / leagues_divisor; + guess[P]= guess[A] / leagues_divisor; - if (guess_absolute <= strat->absolute && - guess_perleague <= strat->perleague) { - ctr_routes_eliminated++; - debugf(" ELIM %f %f\n", guess_absolute, guess_perleague); - return guess_absolute; + if (wrong_final) { + ctr_routes_wrongfinalelim++; + debugf(" WFELIM\n"); + return guess[A]; } - debugf(" COMPUTE %f %f\n", guess_absolute, guess_perleague); - } - ctr_routes_valued++; + for (granui=0; granui highscores[granui][A][0].value || + guess[P] > highscores[granui][P][0].value) + goto not_quickelim; + } + ctr_routes_quickelim++; + debugf(" QELIM %f %f\n", guess[A], guess[P]); + return guess[A]; + not_quickelim:; + } - double absolute= value_route(nports, ports, 0); - double perleague= absolute / leagues_divisor; + int finisle= ports[nports-1]; + int finarch= isle2arch(finisle); + + int midisle= ports[nports/2]; + int midarch= route2midarch(ports,nports); + + Bucket *buckets[GRANUS]; + for (granui=0; granuiabsolute && - perleague <= strat->perleague) - return absolute; + if (nports>=2) { + for (granui=0; granui buckets[granui]->prs[ap].value[ap] && + guess[ap] > highscores[granui][ap][0].value) + goto not_bucketelim; + ctr_routes_bucketelim++; + debugf(" ELIM %f %f\n", guess[A], guess[P]); + return guess[A]; + not_bucketelim: + debugf(" COMPUTE %f %f\n", guess[A], guess[P]); + } - debugf(" SOMEHOW BEST\n"); + ctr_routes_valued++; - fildebugf("final %d:%3d mid %d:%3d ",finarch,finisle,midarch,midisle); + double value[AP]; + value[A]= value_route(nports, ports, 0); + value[P]= value[A] / leagues_divisor; -#define CHK(absperl) \ - fildebugf(#absperl " %15f", absperl); \ - if (absperl < strat->absperl) { \ - debugf(" "); \ - } else { \ - strat->absperl= absperl; \ - memcpy(strat->absperl##_ports, ports, sizeof(*ports) * nports); \ - fildebugf("** "); \ + if (wrong_final) { + ctr_routes_wrongfinal++; + return value[0]; } - CHK(absolute) - CHK(perleague) + for (granui=granus-1; granui>=0; granui--) { + Bucket *bucket= buckets[granui]; + + if (value[A] <= bucket->prs[A].value[A] && + value[P] <= bucket->prs[P].value[P]) + continue; + + debugf(" SOMEHOW %d BEST\n",granui); + + fildebugf("granu %d f%d:%3d mid%d:%3d ",granui, + finarch,finisle,midarch,midisle); + + for (ap=0; apprs[ap].value[ap]) { + debugf(" "); + } else { + int pos; + ctr_newbests_granu[granui*AP+ap]++; + bucket->prs[ap].length= totaldist; + memcpy(bucket->prs[ap].value, value, sizeof(value)); + memcpy(bucket->prs[ap].ports, ports, sizeof(*ports) * nports); + if (nports < MAX_ROUTELEN-1) bucket->prs[ap].ports[nports]= -1; + fildebugf("** "); + for (pos=0; pos < nscores; pos++) + if (scores[pos].bucket == bucket) goto found; + /* not found */ + pos= -1; + found: + for (;;) { + pos++; + if (pos >= nscores) break; /* new top */ + if (scores[pos].value >= value[ap]) break; /* found spot */ + if (pos>0) + scores[pos-1]= scores[pos]; + } + pos--; + if (pos>0) { + scores[pos].value= value[ap]; + scores[pos].bucket= bucket; + if (granui < granus-1 && + highscores[granui][A][0].bucket && + highscores[granui][P][0].bucket) { + /* both absolute and perleague are full at this granularity, + * so we don't care about anything more granular */ + fildebugf("\n STOP-GRANU "); + granus= granui+1; + } + } + fildebugf("@%2d/%2d ", pos, nscores); + } /* new best */ + } /* ap */ + } /* granui */ fildebugf(" route"); @@ -121,11 +222,11 @@ static double process_route(int nports, int totaldist, fildebugf(" %d",ports[i]); fildebugf("\n"); - return absolute; + return value[0]; } static void recurse(int last_isle, - int nports, /* excluding last_isle */ + int nports /* excluding last_isle */, int totaldist /* including last_isle */, double last_estimate) { ports[nports++]= last_isle; @@ -141,18 +242,27 @@ static void recurse(int last_isle, } } -void search(int start_isle, PotentialResult ****strat_base_io) { - strat_base= ONDEMAND(*strat_base_io, narches); +void search(int start_isle, int final_isle_spec, + Bucket ****buckets_base_io[GRANUS]) { + int granui; + for (granui=0; granui