12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341 |
- /*
- * bridges.c: Implementation of the Nikoli game 'Bridges'.
- *
- * Things still to do:
- *
- * - The solver's algorithmic design is not really ideal. It makes
- * use of the same data representation as gameplay uses, which
- * often looks like a tempting reuse of code but isn't always a
- * good idea. In this case, it's unpleasant that each edge of the
- * graph ends up represented as multiple squares on a grid, with
- * flags indicating when edges and non-edges cross; that's useful
- * when the result can be directly translated into positions of
- * graphics on the display, but in purely internal work it makes
- * even simple manipulations during solving more painful than they
- * should be, and complex ones have no choice but to modify the
- * data structures temporarily, test things, and put them back. I
- * envisage a complete solver rewrite along the following lines:
- * + We have a collection of vertices (islands) and edges
- * (potential bridge locations, i.e. pairs of horizontal or
- * vertical islands with no other island in between).
- * + Each edge has an associated list of edges that cross it, and
- * hence with which it is mutually exclusive.
- * + For each edge, we track the min and max number of bridges we
- * currently think possible.
- * + For each vertex, we track the number of _liberties_ it has,
- * i.e. its clue number minus the min bridge count for each edge
- * out of it.
- * + We also maintain a dsf that identifies sets of vertices which
- * are connected components of the puzzle so far, and for each
- * equivalence class we track the total number of liberties for
- * that component. (The dsf mechanism will also already track
- * the size of each component, i.e. number of islands.)
- * + So incrementing the min for an edge requires processing along
- * the lines of:
- * - set the max for all edges crossing that one to zero
- * - decrement the liberty count for the vertex at each end,
- * and also for each vertex's equivalence class (NB they may
- * be the same class)
- * - unify the two equivalence classes if they're not already,
- * and if so, set the liberty count for the new class to be
- * the sum of the previous two.
- * + Decrementing the max is much easier, however.
- * + With this data structure the really fiddly stuff in stage3()
- * becomes more or less trivial, because it's now a quick job to
- * find out whether an island would form an isolated subgraph if
- * connected to a given subset of its neighbours:
- * - identify the connected components containing the test
- * vertex and its putative new neighbours (but be careful not
- * to count a component more than once if two or more of the
- * vertices involved are already in the same one)
- * - find the sum of those components' liberty counts, and also
- * the total number of islands involved
- * - if the total liberty count of the connected components is
- * exactly equal to twice the number of edges we'd be adding
- * (of course each edge destroys two liberties, one at each
- * end) then these components would become a subgraph with
- * zero liberties if connected together.
- * - therefore, if that subgraph also contains fewer than the
- * total number of islands, it's disallowed.
- * - As mentioned in stage3(), once we've identified such a
- * disallowed pattern, we have two choices for what to do
- * with it: if the candidate set of neighbours has size 1 we
- * can reduce the max for the edge to that one neighbour,
- * whereas if its complement has size 1 we can increase the
- * min for the edge to the _omitted_ neighbour.
- *
- * - write a recursive solver?
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #include <ctype.h>
- #include <limits.h>
- #ifdef NO_TGMATH_H
- # include <math.h>
- #else
- # include <tgmath.h>
- #endif
- #include "puzzles.h"
- #undef DRAW_GRID
- /* --- structures for params, state, etc. --- */
- #define MAX_BRIDGES 4
- #define PREFERRED_TILE_SIZE 24
- #define TILE_SIZE (ds->tilesize)
- #define BORDER (TILE_SIZE / 2)
- #define COORD(x) ( (x) * TILE_SIZE + BORDER )
- #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
- #define FLASH_TIME 0.50F
- enum {
- COL_BACKGROUND,
- COL_FOREGROUND,
- COL_HIGHLIGHT, COL_LOWLIGHT,
- COL_SELECTED, COL_MARK,
- COL_HINT, COL_GRID,
- COL_WARNING,
- COL_CURSOR,
- NCOLOURS
- };
- struct game_params {
- int w, h, maxb;
- int islands, expansion; /* %age of island squares, %age chance of expansion */
- bool allowloops;
- int difficulty;
- };
- /* general flags used by all structs */
- #define G_ISLAND 0x0001
- #define G_LINEV 0x0002 /* contains a vert. line */
- #define G_LINEH 0x0004 /* contains a horiz. line (mutex with LINEV) */
- #define G_LINE (G_LINEV|G_LINEH)
- #define G_MARKV 0x0008
- #define G_MARKH 0x0010
- #define G_MARK (G_MARKV|G_MARKH)
- #define G_NOLINEV 0x0020
- #define G_NOLINEH 0x0040
- #define G_NOLINE (G_NOLINEV|G_NOLINEH)
- /* flags used by the error checker */
- #define G_WARN 0x0080
- /* flags used by the solver etc. */
- #define G_SWEEP 0x1000
- #define G_FLAGSH (G_LINEH|G_MARKH|G_NOLINEH)
- #define G_FLAGSV (G_LINEV|G_MARKV|G_NOLINEV)
- typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */
- struct solver_state {
- DSF *dsf, *tmpdsf;
- int *comptspaces, *tmpcompspaces;
- int refcount;
- };
- /* state->gridi is an optimisation; it stores the pointer to the island
- * structs indexed by (x,y). It's not strictly necessary (we could use
- * find234 instead), but Purify showed that board generation (mostly the solver)
- * was spending 60% of its time in find234. */
- struct surrounds { /* cloned from lightup.c */
- struct { int x, y, dx, dy, off; } points[4];
- int npoints, nislands;
- };
- struct island {
- game_state *state;
- int x, y, count;
- struct surrounds adj;
- };
- struct game_state {
- int w, h, maxb;
- bool completed, solved;
- bool allowloops;
- grid_type *grid;
- struct island *islands;
- int n_islands, n_islands_alloc;
- game_params params; /* used by the aux solver. */
- #define N_WH_ARRAYS 5
- char *wha, *possv, *possh, *lines, *maxv, *maxh;
- struct island **gridi;
- struct solver_state *solver; /* refcounted */
- };
- #define GRIDSZ(s) ((s)->w * (s)->h * sizeof(grid_type))
- #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
- #define DINDEX(x,y) ((y)*state->w + (x))
- #define INDEX(s,g,x,y) ((s)->g[(y)*((s)->w) + (x)])
- #define IDX(s,g,i) ((s)->g[(i)])
- #define GRID(s,x,y) INDEX(s,grid,x,y)
- #define POSSIBLES(s,dx,x,y) ((dx) ? (INDEX(s,possh,x,y)) : (INDEX(s,possv,x,y)))
- #define MAXIMUM(s,dx,x,y) ((dx) ? (INDEX(s,maxh,x,y)) : (INDEX(s,maxv,x,y)))
- #define GRIDCOUNT(s,x,y,f) ((GRID(s,x,y) & (f)) ? (INDEX(s,lines,x,y)) : 0)
- #define WITHIN2(x,min,max) ((x) >= (min) && (x) <= (max))
- #define WITHIN(x,min,max) ((min) > (max) ? \
- WITHIN2(x,max,min) : WITHIN2(x,min,max))
- /* --- island struct and tree support functions --- */
- #define ISLAND_ORTH(is,j,f,df) \
- (is->f + (is->adj.points[(j)].off*is->adj.points[(j)].df))
- #define ISLAND_ORTHX(is,j) ISLAND_ORTH(is,j,x,dx)
- #define ISLAND_ORTHY(is,j) ISLAND_ORTH(is,j,y,dy)
- static void fixup_islands_for_realloc(game_state *state)
- {
- int i;
- for (i = 0; i < state->w*state->h; i++) state->gridi[i] = NULL;
- for (i = 0; i < state->n_islands; i++) {
- struct island *is = &state->islands[i];
- is->state = state;
- INDEX(state, gridi, is->x, is->y) = is;
- }
- }
- static bool game_can_format_as_text_now(const game_params *params)
- {
- return true;
- }
- static char *game_text_format(const game_state *state)
- {
- int x, y, len, nl;
- char *ret, *p;
- struct island *is;
- grid_type grid;
- len = (state->h) * (state->w+1) + 1;
- ret = snewn(len, char);
- p = ret;
- for (y = 0; y < state->h; y++) {
- for (x = 0; x < state->w; x++) {
- grid = GRID(state,x,y);
- nl = INDEX(state,lines,x,y);
- is = INDEX(state, gridi, x, y);
- if (is) {
- *p++ = '0' + is->count;
- } else if (grid & G_LINEV) {
- *p++ = (nl > 1) ? '"' : (nl == 1) ? '|' : '!'; /* gaah, want a double-bar. */
- } else if (grid & G_LINEH) {
- *p++ = (nl > 1) ? '=' : (nl == 1) ? '-' : '~';
- } else {
- *p++ = '.';
- }
- }
- *p++ = '\n';
- }
- *p++ = '\0';
- assert(p - ret == len);
- return ret;
- }
- static void debug_state(game_state *state)
- {
- char *textversion = game_text_format(state);
- debug(("%s", textversion));
- sfree(textversion);
- }
- /*static void debug_possibles(game_state *state)
- {
- int x, y;
- debug(("possh followed by possv\n"));
- for (y = 0; y < state->h; y++) {
- for (x = 0; x < state->w; x++) {
- debug(("%d", POSSIBLES(state, 1, x, y)));
- }
- debug((" "));
- for (x = 0; x < state->w; x++) {
- debug(("%d", POSSIBLES(state, 0, x, y)));
- }
- debug(("\n"));
- }
- debug(("\n"));
- for (y = 0; y < state->h; y++) {
- for (x = 0; x < state->w; x++) {
- debug(("%d", MAXIMUM(state, 1, x, y)));
- }
- debug((" "));
- for (x = 0; x < state->w; x++) {
- debug(("%d", MAXIMUM(state, 0, x, y)));
- }
- debug(("\n"));
- }
- debug(("\n"));
- }*/
- static void island_set_surrounds(struct island *is)
- {
- assert(INGRID(is->state,is->x,is->y));
- is->adj.npoints = is->adj.nislands = 0;
- #define ADDPOINT(cond,ddx,ddy) do {\
- if (cond) { \
- is->adj.points[is->adj.npoints].x = is->x+(ddx); \
- is->adj.points[is->adj.npoints].y = is->y+(ddy); \
- is->adj.points[is->adj.npoints].dx = (ddx); \
- is->adj.points[is->adj.npoints].dy = (ddy); \
- is->adj.points[is->adj.npoints].off = 0; \
- is->adj.npoints++; \
- } } while(0)
- ADDPOINT(is->x > 0, -1, 0);
- ADDPOINT(is->x < (is->state->w-1), +1, 0);
- ADDPOINT(is->y > 0, 0, -1);
- ADDPOINT(is->y < (is->state->h-1), 0, +1);
- }
- static void island_find_orthogonal(struct island *is)
- {
- /* fills in the rest of the 'surrounds' structure, assuming
- * all other islands are now in place. */
- int i, x, y, dx, dy, off;
- is->adj.nislands = 0;
- for (i = 0; i < is->adj.npoints; i++) {
- dx = is->adj.points[i].dx;
- dy = is->adj.points[i].dy;
- x = is->x + dx;
- y = is->y + dy;
- off = 1;
- is->adj.points[i].off = 0;
- while (INGRID(is->state, x, y)) {
- if (GRID(is->state, x, y) & G_ISLAND) {
- is->adj.points[i].off = off;
- is->adj.nislands++;
- /*debug(("island (%d,%d) has orth is. %d*(%d,%d) away at (%d,%d).\n",
- is->x, is->y, off, dx, dy,
- ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i)));*/
- goto foundisland;
- }
- off++; x += dx; y += dy;
- }
- foundisland:
- ;
- }
- }
- static bool island_hasbridge(struct island *is, int direction)
- {
- int x = is->adj.points[direction].x;
- int y = is->adj.points[direction].y;
- grid_type gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
- if (GRID(is->state, x, y) & gline) return true;
- return false;
- }
- static struct island *island_find_connection(struct island *is, int adjpt)
- {
- struct island *is_r;
- assert(adjpt < is->adj.npoints);
- if (!is->adj.points[adjpt].off) return NULL;
- if (!island_hasbridge(is, adjpt)) return NULL;
- is_r = INDEX(is->state, gridi,
- ISLAND_ORTHX(is, adjpt), ISLAND_ORTHY(is, adjpt));
- assert(is_r);
- return is_r;
- }
- static struct island *island_add(game_state *state, int x, int y, int count)
- {
- struct island *is;
- bool realloced = false;
- assert(!(GRID(state,x,y) & G_ISLAND));
- GRID(state,x,y) |= G_ISLAND;
- state->n_islands++;
- if (state->n_islands > state->n_islands_alloc) {
- state->n_islands_alloc = state->n_islands * 2;
- state->islands =
- sresize(state->islands, state->n_islands_alloc, struct island);
- realloced = true;
- }
- is = &state->islands[state->n_islands-1];
- memset(is, 0, sizeof(struct island));
- is->state = state;
- is->x = x;
- is->y = y;
- is->count = count;
- island_set_surrounds(is);
- if (realloced)
- fixup_islands_for_realloc(state);
- else
- INDEX(state, gridi, x, y) = is;
- return is;
- }
- /* n = -1 means 'flip NOLINE flags [and set line to 0].' */
- static void island_join(struct island *i1, struct island *i2, int n, bool is_max)
- {
- game_state *state = i1->state;
- int s, e, x, y;
- assert(i1->state == i2->state);
- assert(n >= -1 && n <= i1->state->maxb);
- if (i1->x == i2->x) {
- x = i1->x;
- if (i1->y < i2->y) {
- s = i1->y+1; e = i2->y-1;
- } else {
- s = i2->y+1; e = i1->y-1;
- }
- for (y = s; y <= e; y++) {
- if (is_max) {
- INDEX(state,maxv,x,y) = n;
- } else {
- if (n < 0) {
- GRID(state,x,y) ^= G_NOLINEV;
- } else if (n == 0) {
- GRID(state,x,y) &= ~G_LINEV;
- } else {
- GRID(state,x,y) |= G_LINEV;
- INDEX(state,lines,x,y) = n;
- }
- }
- }
- } else if (i1->y == i2->y) {
- y = i1->y;
- if (i1->x < i2->x) {
- s = i1->x+1; e = i2->x-1;
- } else {
- s = i2->x+1; e = i1->x-1;
- }
- for (x = s; x <= e; x++) {
- if (is_max) {
- INDEX(state,maxh,x,y) = n;
- } else {
- if (n < 0) {
- GRID(state,x,y) ^= G_NOLINEH;
- } else if (n == 0) {
- GRID(state,x,y) &= ~G_LINEH;
- } else {
- GRID(state,x,y) |= G_LINEH;
- INDEX(state,lines,x,y) = n;
- }
- }
- }
- } else {
- assert(!"island_join: islands not orthogonal.");
- }
- }
- /* Counts the number of bridges currently attached to the island. */
- static int island_countbridges(struct island *is)
- {
- int i, c = 0;
- for (i = 0; i < is->adj.npoints; i++) {
- c += GRIDCOUNT(is->state,
- is->adj.points[i].x, is->adj.points[i].y,
- is->adj.points[i].dx ? G_LINEH : G_LINEV);
- }
- /*debug(("island count for (%d,%d) is %d.\n", is->x, is->y, c));*/
- return c;
- }
- static int island_adjspace(struct island *is, bool marks, int missing,
- int direction)
- {
- int x, y, poss, curr, dx;
- grid_type gline, mline;
- x = is->adj.points[direction].x;
- y = is->adj.points[direction].y;
- dx = is->adj.points[direction].dx;
- gline = dx ? G_LINEH : G_LINEV;
- if (marks) {
- mline = dx ? G_MARKH : G_MARKV;
- if (GRID(is->state,x,y) & mline) return 0;
- }
- poss = POSSIBLES(is->state, dx, x, y);
- poss = min(poss, missing);
- curr = GRIDCOUNT(is->state, x, y, gline);
- poss = min(poss, MAXIMUM(is->state, dx, x, y) - curr);
- return poss;
- }
- /* Counts the number of bridge spaces left around the island;
- * expects the possibles to be up-to-date. */
- static int island_countspaces(struct island *is, bool marks)
- {
- int i, c = 0, missing;
- missing = is->count - island_countbridges(is);
- if (missing < 0) return 0;
- for (i = 0; i < is->adj.npoints; i++) {
- c += island_adjspace(is, marks, missing, i);
- }
- return c;
- }
- /* Returns a bridge count rather than a boolean */
- static int island_isadj(struct island *is, int direction)
- {
- int x, y;
- grid_type gline, mline;
- x = is->adj.points[direction].x;
- y = is->adj.points[direction].y;
- mline = is->adj.points[direction].dx ? G_MARKH : G_MARKV;
- gline = is->adj.points[direction].dx ? G_LINEH : G_LINEV;
- if (GRID(is->state, x, y) & mline) {
- /* If we're marked (i.e. the thing to attach to is complete)
- * only count an adjacency if we're already attached. */
- return GRIDCOUNT(is->state, x, y, gline);
- } else {
- /* If we're unmarked, count possible adjacency iff it's
- * flagged as POSSIBLE. */
- return POSSIBLES(is->state, is->adj.points[direction].dx, x, y);
- }
- return 0;
- }
- /* Counts the no. of possible adjacent islands (including islands
- * we're already connected to). */
- static int island_countadj(struct island *is)
- {
- int i, nadj = 0;
- for (i = 0; i < is->adj.npoints; i++) {
- if (island_isadj(is, i)) nadj++;
- }
- return nadj;
- }
- static void island_togglemark(struct island *is)
- {
- int i, j, x, y, o;
- struct island *is_loop;
- /* mark the island... */
- GRID(is->state, is->x, is->y) ^= G_MARK;
- /* ...remove all marks on non-island squares... */
- for (x = 0; x < is->state->w; x++) {
- for (y = 0; y < is->state->h; y++) {
- if (!(GRID(is->state, x, y) & G_ISLAND))
- GRID(is->state, x, y) &= ~G_MARK;
- }
- }
- /* ...and add marks to squares around marked islands. */
- for (i = 0; i < is->state->n_islands; i++) {
- is_loop = &is->state->islands[i];
- if (!(GRID(is_loop->state, is_loop->x, is_loop->y) & G_MARK))
- continue;
- for (j = 0; j < is_loop->adj.npoints; j++) {
- /* if this direction takes us to another island, mark all
- * squares between the two islands. */
- if (!is_loop->adj.points[j].off) continue;
- assert(is_loop->adj.points[j].off > 1);
- for (o = 1; o < is_loop->adj.points[j].off; o++) {
- GRID(is_loop->state,
- is_loop->x + is_loop->adj.points[j].dx*o,
- is_loop->y + is_loop->adj.points[j].dy*o) |=
- is_loop->adj.points[j].dy ? G_MARKV : G_MARKH;
- }
- }
- }
- }
- static bool island_impossible(struct island *is, bool strict)
- {
- int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc;
- int i, poss;
- struct island *is_orth;
- if (nspc < 0) {
- debug(("island at (%d,%d) impossible because full.\n", is->x, is->y));
- return true; /* too many bridges */
- } else if ((curr + island_countspaces(is, false)) < is->count) {
- debug(("island at (%d,%d) impossible because not enough spaces.\n", is->x, is->y));
- return true; /* impossible to create enough bridges */
- } else if (strict && curr < is->count) {
- debug(("island at (%d,%d) impossible because locked.\n", is->x, is->y));
- return true; /* not enough bridges and island is locked */
- }
- /* Count spaces in surrounding islands. */
- nsurrspc = 0;
- for (i = 0; i < is->adj.npoints; i++) {
- int ifree, dx = is->adj.points[i].dx;
- if (!is->adj.points[i].off) continue;
- poss = POSSIBLES(is->state, dx,
- is->adj.points[i].x, is->adj.points[i].y);
- if (poss == 0) continue;
- is_orth = INDEX(is->state, gridi,
- ISLAND_ORTHX(is,i), ISLAND_ORTHY(is,i));
- assert(is_orth);
- ifree = is_orth->count - island_countbridges(is_orth);
- if (ifree > 0) {
- /*
- * ifree is the number of bridges unfilled in the other
- * island, which is clearly an upper bound on the number
- * of extra bridges this island may run to it.
- *
- * Another upper bound is the number of bridges unfilled
- * on the specific line between here and there. We must
- * take the minimum of both.
- */
- int bmax = MAXIMUM(is->state, dx,
- is->adj.points[i].x, is->adj.points[i].y);
- int bcurr = GRIDCOUNT(is->state,
- is->adj.points[i].x, is->adj.points[i].y,
- dx ? G_LINEH : G_LINEV);
- assert(bcurr <= bmax);
- nsurrspc += min(ifree, bmax - bcurr);
- }
- }
- if (nsurrspc < nspc) {
- debug(("island at (%d,%d) impossible: surr. islands %d spc, need %d.\n",
- is->x, is->y, nsurrspc, nspc));
- return true; /* not enough spaces around surrounding islands to fill this one. */
- }
- return false;
- }
- /* --- Game parameter functions --- */
- #define DEFAULT_PRESET 0
- static const struct game_params bridges_presets[] = {
- { 7, 7, 2, 30, 10, 1, 0 },
- { 7, 7, 2, 30, 10, 1, 1 },
- { 7, 7, 2, 30, 10, 1, 2 },
- { 10, 10, 2, 30, 10, 1, 0 },
- { 10, 10, 2, 30, 10, 1, 1 },
- { 10, 10, 2, 30, 10, 1, 2 },
- { 15, 15, 2, 30, 10, 1, 0 },
- { 15, 15, 2, 30, 10, 1, 1 },
- { 15, 15, 2, 30, 10, 1, 2 },
- };
- static game_params *default_params(void)
- {
- game_params *ret = snew(game_params);
- *ret = bridges_presets[DEFAULT_PRESET];
- return ret;
- }
- static bool game_fetch_preset(int i, char **name, game_params **params)
- {
- game_params *ret;
- char buf[80];
- if (i < 0 || i >= lenof(bridges_presets))
- return false;
- ret = default_params();
- *ret = bridges_presets[i];
- *params = ret;
- sprintf(buf, "%dx%d %s", ret->w, ret->h,
- ret->difficulty == 0 ? "easy" :
- ret->difficulty == 1 ? "medium" : "hard");
- *name = dupstr(buf);
- return true;
- }
- static void free_params(game_params *params)
- {
- sfree(params);
- }
- static game_params *dup_params(const game_params *params)
- {
- game_params *ret = snew(game_params);
- *ret = *params; /* structure copy */
- return ret;
- }
- #define EATNUM(x) do { \
- (x) = atoi(string); \
- while (*string && isdigit((unsigned char)*string)) string++; \
- } while(0)
- static void decode_params(game_params *params, char const *string)
- {
- EATNUM(params->w);
- params->h = params->w;
- if (*string == 'x') {
- string++;
- EATNUM(params->h);
- }
- if (*string == 'i') {
- string++;
- EATNUM(params->islands);
- }
- if (*string == 'e') {
- string++;
- EATNUM(params->expansion);
- }
- if (*string == 'm') {
- string++;
- EATNUM(params->maxb);
- }
- params->allowloops = true;
- if (*string == 'L') {
- string++;
- params->allowloops = false;
- }
- if (*string == 'd') {
- string++;
- EATNUM(params->difficulty);
- }
- }
- static char *encode_params(const game_params *params, bool full)
- {
- char buf[80];
- if (full) {
- sprintf(buf, "%dx%di%de%dm%d%sd%d",
- params->w, params->h, params->islands, params->expansion,
- params->maxb, params->allowloops ? "" : "L",
- params->difficulty);
- } else {
- sprintf(buf, "%dx%dm%d%s", params->w, params->h,
- params->maxb, params->allowloops ? "" : "L");
- }
- return dupstr(buf);
- }
- static config_item *game_configure(const game_params *params)
- {
- config_item *ret;
- char buf[80];
- ret = snewn(8, config_item);
- ret[0].name = "Width";
- ret[0].type = C_STRING;
- sprintf(buf, "%d", params->w);
- ret[0].u.string.sval = dupstr(buf);
- ret[1].name = "Height";
- ret[1].type = C_STRING;
- sprintf(buf, "%d", params->h);
- ret[1].u.string.sval = dupstr(buf);
- ret[2].name = "Difficulty";
- ret[2].type = C_CHOICES;
- ret[2].u.choices.choicenames = ":Easy:Medium:Hard";
- ret[2].u.choices.selected = params->difficulty;
- ret[3].name = "Allow loops";
- ret[3].type = C_BOOLEAN;
- ret[3].u.boolean.bval = params->allowloops;
- ret[4].name = "Max. bridges per direction";
- ret[4].type = C_CHOICES;
- ret[4].u.choices.choicenames = ":1:2:3:4"; /* keep up-to-date with
- * MAX_BRIDGES */
- ret[4].u.choices.selected = params->maxb - 1;
- ret[5].name = "%age of island squares";
- ret[5].type = C_CHOICES;
- ret[5].u.choices.choicenames = ":5%:10%:15%:20%:25%:30%";
- ret[5].u.choices.selected = (params->islands / 5)-1;
- ret[6].name = "Expansion factor (%age)";
- ret[6].type = C_CHOICES;
- ret[6].u.choices.choicenames = ":0%:10%:20%:30%:40%:50%:60%:70%:80%:90%:100%";
- ret[6].u.choices.selected = params->expansion / 10;
- ret[7].name = NULL;
- ret[7].type = C_END;
- return ret;
- }
- static game_params *custom_params(const config_item *cfg)
- {
- game_params *ret = snew(game_params);
- ret->w = atoi(cfg[0].u.string.sval);
- ret->h = atoi(cfg[1].u.string.sval);
- ret->difficulty = cfg[2].u.choices.selected;
- ret->allowloops = cfg[3].u.boolean.bval;
- ret->maxb = cfg[4].u.choices.selected + 1;
- ret->islands = (cfg[5].u.choices.selected + 1) * 5;
- ret->expansion = cfg[6].u.choices.selected * 10;
- return ret;
- }
- static const char *validate_params(const game_params *params, bool full)
- {
- if (params->w < 3 || params->h < 3)
- return "Width and height must be at least 3";
- if (params->w > INT_MAX / params->h)
- return "Width times height must not be unreasonably large";
- if (params->maxb < 1 || params->maxb > MAX_BRIDGES)
- return "Too many bridges.";
- if (full) {
- if (params->islands <= 0 || params->islands > 30)
- return "%age of island squares must be between 1% and 30%";
- if (params->expansion < 0 || params->expansion > 100)
- return "Expansion factor must be between 0 and 100";
- }
- return NULL;
- }
- /* --- Game encoding and differences --- */
- static char *encode_game(game_state *state)
- {
- char *ret, *p;
- int wh = state->w*state->h, run, x, y;
- struct island *is;
- ret = snewn(wh + 1, char);
- p = ret;
- run = 0;
- for (y = 0; y < state->h; y++) {
- for (x = 0; x < state->w; x++) {
- is = INDEX(state, gridi, x, y);
- if (is) {
- if (run) {
- *p++ = ('a'-1) + run;
- run = 0;
- }
- if (is->count < 10)
- *p++ = '0' + is->count;
- else
- *p++ = 'A' + (is->count - 10);
- } else {
- if (run == 26) {
- *p++ = ('a'-1) + run;
- run = 0;
- }
- run++;
- }
- }
- }
- if (run) {
- *p++ = ('a'-1) + run;
- run = 0;
- }
- *p = '\0';
- assert(p - ret <= wh);
- return ret;
- }
- static char *game_state_diff(const game_state *src, const game_state *dest)
- {
- int movesize = 256, movelen = 0;
- char *move = snewn(movesize, char), buf[80];
- int i, d, x, y, len;
- grid_type gline, nline;
- struct island *is_s, *is_d, *is_orth;
- #define APPEND do { \
- if (movelen + len >= movesize) { \
- movesize = movelen + len + 256; \
- move = sresize(move, movesize, char); \
- } \
- strcpy(move + movelen, buf); \
- movelen += len; \
- } while(0)
- move[movelen++] = 'S';
- move[movelen] = '\0';
- assert(src->n_islands == dest->n_islands);
- for (i = 0; i < src->n_islands; i++) {
- is_s = &src->islands[i];
- is_d = &dest->islands[i];
- assert(is_s->x == is_d->x);
- assert(is_s->y == is_d->y);
- assert(is_s->adj.npoints == is_d->adj.npoints); /* more paranoia */
- for (d = 0; d < is_s->adj.npoints; d++) {
- if (is_s->adj.points[d].dx == -1 ||
- is_s->adj.points[d].dy == -1) continue;
- x = is_s->adj.points[d].x;
- y = is_s->adj.points[d].y;
- gline = is_s->adj.points[d].dx ? G_LINEH : G_LINEV;
- nline = is_s->adj.points[d].dx ? G_NOLINEH : G_NOLINEV;
- is_orth = INDEX(dest, gridi,
- ISLAND_ORTHX(is_d, d), ISLAND_ORTHY(is_d, d));
- if (GRIDCOUNT(src, x, y, gline) != GRIDCOUNT(dest, x, y, gline)) {
- assert(is_orth);
- len = sprintf(buf, ";L%d,%d,%d,%d,%d",
- is_s->x, is_s->y, is_orth->x, is_orth->y,
- GRIDCOUNT(dest, x, y, gline));
- APPEND;
- }
- if ((GRID(src,x,y) & nline) != (GRID(dest, x, y) & nline)) {
- assert(is_orth);
- len = sprintf(buf, ";N%d,%d,%d,%d",
- is_s->x, is_s->y, is_orth->x, is_orth->y);
- APPEND;
- }
- }
- if ((GRID(src, is_s->x, is_s->y) & G_MARK) !=
- (GRID(dest, is_d->x, is_d->y) & G_MARK)) {
- len = sprintf(buf, ";M%d,%d", is_s->x, is_s->y);
- APPEND;
- }
- }
- return move;
- }
- /* --- Game setup and solving utilities --- */
- /* This function is optimised; a Quantify showed that lots of grid-generation time
- * (>50%) was spent in here. Hence the IDX() stuff. */
- static void map_update_possibles(game_state *state)
- {
- int x, y, s, e, i, np, maxb, w = state->w, idx;
- bool bl;
- struct island *is_s = NULL, *is_f = NULL;
- /* Run down vertical stripes [un]setting possv... */
- for (x = 0; x < state->w; x++) {
- idx = x;
- s = e = -1;
- bl = false;
- maxb = state->params.maxb; /* placate optimiser */
- /* Unset possible flags until we find an island. */
- for (y = 0; y < state->h; y++) {
- is_s = IDX(state, gridi, idx);
- if (is_s) {
- maxb = is_s->count;
- break;
- }
- IDX(state, possv, idx) = 0;
- idx += w;
- }
- for (; y < state->h; y++) {
- maxb = min(maxb, IDX(state, maxv, idx));
- is_f = IDX(state, gridi, idx);
- if (is_f) {
- assert(is_s);
- np = min(maxb, is_f->count);
- if (s != -1) {
- for (i = s; i <= e; i++) {
- INDEX(state, possv, x, i) = bl ? 0 : np;
- }
- }
- s = y+1;
- bl = false;
- is_s = is_f;
- maxb = is_s->count;
- } else {
- e = y;
- if (IDX(state,grid,idx) & (G_LINEH|G_NOLINEV)) bl = true;
- }
- idx += w;
- }
- if (s != -1) {
- for (i = s; i <= e; i++)
- INDEX(state, possv, x, i) = 0;
- }
- }
- /* ...and now do horizontal stripes [un]setting possh. */
- /* can we lose this clone'n'hack? */
- for (y = 0; y < state->h; y++) {
- idx = y*w;
- s = e = -1;
- bl = false;
- maxb = state->params.maxb; /* placate optimiser */
- for (x = 0; x < state->w; x++) {
- is_s = IDX(state, gridi, idx);
- if (is_s) {
- maxb = is_s->count;
- break;
- }
- IDX(state, possh, idx) = 0;
- idx += 1;
- }
- for (; x < state->w; x++) {
- maxb = min(maxb, IDX(state, maxh, idx));
- is_f = IDX(state, gridi, idx);
- if (is_f) {
- assert(is_s);
- np = min(maxb, is_f->count);
- if (s != -1) {
- for (i = s; i <= e; i++) {
- INDEX(state, possh, i, y) = bl ? 0 : np;
- }
- }
- s = x+1;
- bl = false;
- is_s = is_f;
- maxb = is_s->count;
- } else {
- e = x;
- if (IDX(state,grid,idx) & (G_LINEV|G_NOLINEH)) bl = true;
- }
- idx += 1;
- }
- if (s != -1) {
- for (i = s; i <= e; i++)
- INDEX(state, possh, i, y) = 0;
- }
- }
- }
- static void map_count(game_state *state)
- {
- int i, n, ax, ay;
- grid_type flag, grid;
- struct island *is;
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- is->count = 0;
- for (n = 0; n < is->adj.npoints; n++) {
- ax = is->adj.points[n].x;
- ay = is->adj.points[n].y;
- flag = (ax == is->x) ? G_LINEV : G_LINEH;
- grid = GRID(state,ax,ay);
- if (grid & flag) {
- is->count += INDEX(state,lines,ax,ay);
- }
- }
- }
- }
- static void map_find_orthogonal(game_state *state)
- {
- int i;
- for (i = 0; i < state->n_islands; i++) {
- island_find_orthogonal(&state->islands[i]);
- }
- }
- struct bridges_neighbour_ctx {
- game_state *state;
- int i, n, neighbours[4];
- };
- static int bridges_neighbour(int vertex, void *vctx)
- {
- struct bridges_neighbour_ctx *ctx = (struct bridges_neighbour_ctx *)vctx;
- if (vertex >= 0) {
- game_state *state = ctx->state;
- int w = state->w, x = vertex % w, y = vertex / w;
- grid_type grid = GRID(state, x, y), gline = grid & G_LINE;
- struct island *is;
- int x1, y1, x2, y2, i;
- ctx->i = ctx->n = 0;
- is = INDEX(state, gridi, x, y);
- if (is) {
- for (i = 0; i < is->adj.npoints; i++) {
- gline = is->adj.points[i].dx ? G_LINEH : G_LINEV;
- if (GRID(state, is->adj.points[i].x,
- is->adj.points[i].y) & gline) {
- ctx->neighbours[ctx->n++] =
- (is->adj.points[i].y * w + is->adj.points[i].x);
- }
- }
- } else if (gline) {
- if (gline & G_LINEV) {
- x1 = x2 = x;
- y1 = y-1; y2 = y+1;
- } else {
- x1 = x-1; x2 = x+1;
- y1 = y2 = y;
- }
- /* Non-island squares with edges in should never be
- * pointing off the edge of the grid. */
- assert(INGRID(state, x1, y1));
- assert(INGRID(state, x2, y2));
- if (GRID(state, x1, y1) & (gline | G_ISLAND))
- ctx->neighbours[ctx->n++] = y1 * w + x1;
- if (GRID(state, x2, y2) & (gline | G_ISLAND))
- ctx->neighbours[ctx->n++] = y2 * w + x2;
- }
- }
- if (ctx->i < ctx->n)
- return ctx->neighbours[ctx->i++];
- else
- return -1;
- }
- static bool map_hasloops(game_state *state, bool mark)
- {
- int x, y;
- struct findloopstate *fls;
- struct bridges_neighbour_ctx ctx;
- bool ret;
- fls = findloop_new_state(state->w * state->h);
- ctx.state = state;
- ret = findloop_run(fls, state->w * state->h, bridges_neighbour, &ctx);
- if (mark) {
- for (y = 0; y < state->h; y++) {
- for (x = 0; x < state->w; x++) {
- int u, v;
- u = y * state->w + x;
- for (v = bridges_neighbour(u, &ctx); v >= 0;
- v = bridges_neighbour(-1, &ctx))
- if (findloop_is_loop_edge(fls, u, v))
- GRID(state,x,y) |= G_WARN;
- }
- }
- }
- findloop_free_state(fls);
- return ret;
- }
- static void map_group(game_state *state)
- {
- int i, d1, d2;
- int x, y, x2, y2;
- DSF *dsf = state->solver->dsf;
- struct island *is, *is_join;
- /* Initialise dsf. */
- dsf_reinit(dsf);
- /* For each island, find connected islands right or down
- * and merge the dsf for the island squares as well as the
- * bridge squares. */
- for (x = 0; x < state->w; x++) {
- for (y = 0; y < state->h; y++) {
- GRID(state,x,y) &= ~(G_SWEEP|G_WARN); /* for group_full. */
- is = INDEX(state, gridi, x, y);
- if (!is) continue;
- d1 = DINDEX(x,y);
- for (i = 0; i < is->adj.npoints; i++) {
- /* only want right/down */
- if (is->adj.points[i].dx == -1 ||
- is->adj.points[i].dy == -1) continue;
- is_join = island_find_connection(is, i);
- if (!is_join) continue;
- d2 = DINDEX(is_join->x, is_join->y);
- if (dsf_equivalent(dsf, d1, d2)) {
- ; /* we have a loop. See comment in map_hasloops. */
- /* However, we still want to merge all squares joining
- * this side-that-makes-a-loop. */
- }
- /* merge all squares between island 1 and island 2. */
- for (x2 = x; x2 <= is_join->x; x2++) {
- for (y2 = y; y2 <= is_join->y; y2++) {
- d2 = DINDEX(x2,y2);
- if (d1 != d2) dsf_merge(dsf,d1,d2);
- }
- }
- }
- }
- }
- }
- static bool map_group_check(game_state *state, int canon, bool warn,
- int *nislands_r)
- {
- DSF *dsf = state->solver->dsf;
- int nislands = 0;
- int x, y, i;
- bool allfull = true;
- struct island *is;
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- if (dsf_canonify(dsf, DINDEX(is->x,is->y)) != canon) continue;
- GRID(state, is->x, is->y) |= G_SWEEP;
- nislands++;
- if (island_countbridges(is) != is->count)
- allfull = false;
- }
- if (warn && allfull && nislands != state->n_islands) {
- /* we're full and this island group isn't the whole set.
- * Mark all squares with this dsf canon as ERR. */
- for (x = 0; x < state->w; x++) {
- for (y = 0; y < state->h; y++) {
- if (dsf_canonify(dsf, DINDEX(x,y)) == canon) {
- GRID(state,x,y) |= G_WARN;
- }
- }
- }
- }
- if (nislands_r) *nislands_r = nislands;
- return allfull;
- }
- static bool map_group_full(game_state *state, int *ngroups_r)
- {
- DSF *dsf = state->solver->dsf;
- int ngroups = 0;
- int i;
- bool anyfull = false;
- struct island *is;
- /* NB this assumes map_group (or sth else) has cleared G_SWEEP. */
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- if (GRID(state,is->x,is->y) & G_SWEEP) continue;
- ngroups++;
- if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
- true, NULL))
- anyfull = true;
- }
- *ngroups_r = ngroups;
- return anyfull;
- }
- static bool map_check(game_state *state)
- {
- int ngroups;
- /* Check for loops, if necessary. */
- if (!state->allowloops) {
- if (map_hasloops(state, true))
- return false;
- }
- /* Place islands into island groups and check for early
- * satisfied-groups. */
- map_group(state); /* clears WARN and SWEEP */
- if (map_group_full(state, &ngroups)) {
- if (ngroups == 1) return true;
- }
- return false;
- }
- static void map_clear(game_state *state)
- {
- int x, y;
- for (x = 0; x < state->w; x++) {
- for (y = 0; y < state->h; y++) {
- /* clear most flags; might want to be slightly more careful here. */
- GRID(state,x,y) &= G_ISLAND;
- }
- }
- }
- static void solve_join(struct island *is, int direction, int n, bool is_max)
- {
- struct island *is_orth;
- int d1, d2;
- DSF *dsf = is->state->solver->dsf;
- game_state *state = is->state; /* for DINDEX */
- is_orth = INDEX(is->state, gridi,
- ISLAND_ORTHX(is, direction),
- ISLAND_ORTHY(is, direction));
- assert(is_orth);
- /*debug(("...joining (%d,%d) to (%d,%d) with %d bridge(s).\n",
- is->x, is->y, is_orth->x, is_orth->y, n));*/
- island_join(is, is_orth, n, is_max);
- if (n > 0 && !is_max) {
- d1 = DINDEX(is->x, is->y);
- d2 = DINDEX(is_orth->x, is_orth->y);
- if (!dsf_equivalent(dsf, d1, d2))
- dsf_merge(dsf, d1, d2);
- }
- }
- static int solve_fillone(struct island *is)
- {
- int i, nadded = 0;
- debug(("solve_fillone for island (%d,%d).\n", is->x, is->y));
- for (i = 0; i < is->adj.npoints; i++) {
- if (island_isadj(is, i)) {
- if (island_hasbridge(is, i)) {
- /* already attached; do nothing. */;
- } else {
- solve_join(is, i, 1, false);
- nadded++;
- }
- }
- }
- return nadded;
- }
- static int solve_fill(struct island *is)
- {
- /* for each unmarked adjacent, make sure we convert every possible bridge
- * to a real one, and then work out the possibles afresh. */
- int i, nnew, ncurr, nadded = 0, missing;
- debug(("solve_fill for island (%d,%d).\n", is->x, is->y));
- missing = is->count - island_countbridges(is);
- if (missing < 0) return 0;
- /* very like island_countspaces. */
- for (i = 0; i < is->adj.npoints; i++) {
- nnew = island_adjspace(is, true, missing, i);
- if (nnew) {
- ncurr = GRIDCOUNT(is->state,
- is->adj.points[i].x, is->adj.points[i].y,
- is->adj.points[i].dx ? G_LINEH : G_LINEV);
- solve_join(is, i, nnew + ncurr, false);
- nadded += nnew;
- }
- }
- return nadded;
- }
- static bool solve_island_stage1(struct island *is, bool *didsth_r)
- {
- int bridges = island_countbridges(is);
- int nspaces = island_countspaces(is, true);
- int nadj = island_countadj(is);
- bool didsth = false;
- assert(didsth_r);
- /*debug(("island at (%d,%d) filled %d/%d (%d spc) nadj %d\n",
- is->x, is->y, bridges, is->count, nspaces, nadj));*/
- if (bridges > is->count) {
- /* We only ever add bridges when we're sure they fit, or that's
- * the only place they can go. If we've added bridges such that
- * another island has become wrong, the puzzle must not have had
- * a solution. */
- debug(("...island at (%d,%d) is overpopulated!\n", is->x, is->y));
- return false;
- } else if (bridges == is->count) {
- /* This island is full. Make sure it's marked (and update
- * possibles if we did). */
- if (!(GRID(is->state, is->x, is->y) & G_MARK)) {
- debug(("...marking island (%d,%d) as full.\n", is->x, is->y));
- island_togglemark(is);
- didsth = true;
- }
- } else if (GRID(is->state, is->x, is->y) & G_MARK) {
- debug(("...island (%d,%d) is marked but unfinished!\n",
- is->x, is->y));
- return false; /* island has been marked unfinished; no solution from here. */
- } else {
- /* This is the interesting bit; we try and fill in more information
- * about this island. */
- if (is->count == bridges + nspaces) {
- if (solve_fill(is) > 0) didsth = true;
- } else if (is->count > ((nadj-1) * is->state->maxb)) {
- /* must have at least one bridge in each possible direction. */
- if (solve_fillone(is) > 0) didsth = true;
- }
- }
- if (didsth) {
- map_update_possibles(is->state);
- *didsth_r = true;
- }
- return true;
- }
- /* returns true if a new line here would cause a loop. */
- static bool solve_island_checkloop(struct island *is, int direction)
- {
- struct island *is_orth;
- DSF *dsf = is->state->solver->dsf;
- int d1, d2;
- game_state *state = is->state;
- if (is->state->allowloops)
- return false; /* don't care anyway */
- if (island_hasbridge(is, direction))
- return false; /* already has a bridge */
- if (island_isadj(is, direction) == 0)
- return false; /* no adj island */
- is_orth = INDEX(is->state, gridi,
- ISLAND_ORTHX(is,direction),
- ISLAND_ORTHY(is,direction));
- if (!is_orth) return false;
- d1 = DINDEX(is->x, is->y);
- d2 = DINDEX(is_orth->x, is_orth->y);
- if (dsf_equivalent(dsf, d1, d2)) {
- /* two islands are connected already; don't join them. */
- return true;
- }
- return false;
- }
- static bool solve_island_stage2(struct island *is, bool *didsth_r)
- {
- int navail = 0, nadj, i;
- bool added = false, removed = false;
- assert(didsth_r);
- for (i = 0; i < is->adj.npoints; i++) {
- if (solve_island_checkloop(is, i)) {
- debug(("removing possible loop at (%d,%d) direction %d.\n",
- is->x, is->y, i));
- solve_join(is, i, -1, false);
- map_update_possibles(is->state);
- removed = true;
- } else {
- navail += island_isadj(is, i);
- /*debug(("stage2: navail for (%d,%d) direction (%d,%d) is %d.\n",
- is->x, is->y,
- is->adj.points[i].dx, is->adj.points[i].dy,
- island_isadj(is, i)));*/
- }
- }
- /*debug(("island at (%d,%d) navail %d: checking...\n", is->x, is->y, navail));*/
- for (i = 0; i < is->adj.npoints; i++) {
- if (!island_hasbridge(is, i)) {
- nadj = island_isadj(is, i);
- if (nadj > 0 && (navail - nadj) < is->count) {
- /* we couldn't now complete the island without at
- * least one bridge here; put it in. */
- /*debug(("nadj %d, navail %d, is->count %d.\n",
- nadj, navail, is->count));*/
- debug(("island at (%d,%d) direction (%d,%d) must have 1 bridge\n",
- is->x, is->y,
- is->adj.points[i].dx, is->adj.points[i].dy));
- solve_join(is, i, 1, false);
- added = true;
- /*debug_state(is->state);
- debug_possibles(is->state);*/
- }
- }
- }
- if (added) map_update_possibles(is->state);
- if (added || removed) *didsth_r = true;
- return true;
- }
- static bool solve_island_subgroup(struct island *is, int direction)
- {
- struct island *is_join;
- int nislands;
- DSF *dsf = is->state->solver->dsf;
- game_state *state = is->state;
- debug(("..checking subgroups.\n"));
- /* if is isn't full, return 0. */
- if (island_countbridges(is) < is->count) {
- debug(("...orig island (%d,%d) not full.\n", is->x, is->y));
- return false;
- }
- if (direction >= 0) {
- is_join = INDEX(state, gridi,
- ISLAND_ORTHX(is, direction),
- ISLAND_ORTHY(is, direction));
- assert(is_join);
- /* if is_join isn't full, return 0. */
- if (island_countbridges(is_join) < is_join->count) {
- debug(("...dest island (%d,%d) not full.\n",
- is_join->x, is_join->y));
- return false;
- }
- }
- /* Check group membership for is->dsf; if it's full return 1. */
- if (map_group_check(state, dsf_canonify(dsf, DINDEX(is->x,is->y)),
- false, &nislands)) {
- if (nislands < state->n_islands) {
- /* we have a full subgroup that isn't the whole set.
- * This isn't allowed. */
- debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
- is->x, is->y));
- return true;
- } else {
- debug(("...has finished puzzle.\n"));
- }
- }
- return false;
- }
- static bool solve_island_impossible(game_state *state)
- {
- struct island *is;
- int i;
- /* If any islands are impossible, return 1. */
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- if (island_impossible(is, false)) {
- debug(("island at (%d,%d) has become impossible, disallowing.\n",
- is->x, is->y));
- return true;
- }
- }
- return false;
- }
- /* Bear in mind that this function is really rather inefficient. */
- static bool solve_island_stage3(struct island *is, bool *didsth_r)
- {
- int i, n, x, y, missing, spc, curr, maxb;
- bool didsth = false;
- struct solver_state *ss = is->state->solver;
- assert(didsth_r);
- missing = is->count - island_countbridges(is);
- if (missing <= 0) return true;
- for (i = 0; i < is->adj.npoints; i++) {
- x = is->adj.points[i].x;
- y = is->adj.points[i].y;
- spc = island_adjspace(is, true, missing, i);
- if (spc == 0) continue;
- curr = GRIDCOUNT(is->state, x, y,
- is->adj.points[i].dx ? G_LINEH : G_LINEV);
- debug(("island at (%d,%d) s3, trying %d - %d bridges.\n",
- is->x, is->y, curr+1, curr+spc));
- /* Now we know that this island could have more bridges,
- * to bring the total from curr+1 to curr+spc. */
- maxb = -1;
- /* We have to squirrel the dsf away and restore it afterwards;
- * it is additive only, and can't be removed from. */
- dsf_copy(ss->tmpdsf, ss->dsf);
- for (n = curr+1; n <= curr+spc; n++) {
- solve_join(is, i, n, false);
- map_update_possibles(is->state);
- if (solve_island_subgroup(is, i) ||
- solve_island_impossible(is->state)) {
- maxb = n-1;
- debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
- is->x, is->y,
- is->adj.points[i].dx, is->adj.points[i].dy,
- maxb));
- break;
- }
- }
- solve_join(is, i, curr, false); /* put back to before. */
- dsf_copy(ss->dsf, ss->tmpdsf);
- if (maxb != -1) {
- /*debug_state(is->state);*/
- if (maxb == 0) {
- debug(("...adding NOLINE.\n"));
- solve_join(is, i, -1, false); /* we can't have any bridges here. */
- } else {
- debug(("...setting maximum\n"));
- solve_join(is, i, maxb, true);
- }
- didsth = true;
- }
- map_update_possibles(is->state);
- }
- for (i = 0; i < is->adj.npoints; i++) {
- /*
- * Now check to see if any currently empty direction must have
- * at least one bridge in order to avoid forming an isolated
- * subgraph. This differs from the check above in that it
- * considers multiple target islands. For example:
- *
- * 2 2 4
- * 1 3 2
- * 3
- * 4
- *
- * The example on the left can be handled by the above loop:
- * it will observe that connecting the central 2 twice to the
- * left would form an isolated subgraph, and hence it will
- * restrict that 2 to at most one bridge in that direction.
- * But the example on the right won't be handled by that loop,
- * because the deduction requires us to imagine connecting the
- * 3 to _both_ the 1 and 2 at once to form an isolated
- * subgraph.
- *
- * This pass is necessary _as well_ as the above one, because
- * neither can do the other's job. In the left one,
- * restricting the direction which _would_ cause trouble can
- * be done even if it's not yet clear which of the remaining
- * directions has to have a compensatory bridge; whereas the
- * pass below that can handle the right-hand example does need
- * to know what direction to point the necessary bridge in.
- *
- * Neither pass can handle the most general case, in which we
- * observe that an arbitrary subset of an island's neighbours
- * would form an isolated subgraph with it if it connected
- * maximally to them, and hence that at least one bridge must
- * point to some neighbour outside that subset but we don't
- * know which neighbour. To handle that, we'd have to have a
- * richer data format for the solver, which could cope with
- * recording the idea that at least one of two edges must have
- * a bridge.
- */
- bool got = false;
- int before[4];
- int j;
- spc = island_adjspace(is, true, missing, i);
- if (spc == 0) continue;
- for (j = 0; j < is->adj.npoints; j++)
- before[j] = GRIDCOUNT(is->state,
- is->adj.points[j].x,
- is->adj.points[j].y,
- is->adj.points[j].dx ? G_LINEH : G_LINEV);
- if (before[i] != 0) continue; /* this idea is pointless otherwise */
- dsf_copy(ss->tmpdsf, ss->dsf);
- for (j = 0; j < is->adj.npoints; j++) {
- spc = island_adjspace(is, true, missing, j);
- if (spc == 0) continue;
- if (j == i) continue;
- solve_join(is, j, before[j] + spc, false);
- }
- map_update_possibles(is->state);
- if (solve_island_subgroup(is, -1))
- got = true;
- for (j = 0; j < is->adj.npoints; j++)
- solve_join(is, j, before[j], false);
- dsf_copy(ss->dsf, ss->tmpdsf);
- if (got) {
- debug(("island at (%d,%d) must connect in direction (%d,%d) to"
- " avoid full subgroup.\n",
- is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy));
- solve_join(is, i, 1, false);
- didsth = true;
- }
- map_update_possibles(is->state);
- }
- if (didsth) *didsth_r = didsth;
- return true;
- }
- #define CONTINUE_IF_FULL do { \
- if (GRID(state, is->x, is->y) & G_MARK) { \
- /* island full, don't try fixing it */ \
- continue; \
- } } while(0)
- static int solve_sub(game_state *state, int difficulty, int depth)
- {
- struct island *is;
- int i;
- while (1) {
- bool didsth = false;
- /* First island iteration: things we can work out by looking at
- * properties of the island as a whole. */
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- if (!solve_island_stage1(is, &didsth)) return 0;
- }
- if (didsth) continue;
- else if (difficulty < 1) break;
- /* Second island iteration: thing we can work out by looking at
- * properties of individual island connections. */
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- CONTINUE_IF_FULL;
- if (!solve_island_stage2(is, &didsth)) return 0;
- }
- if (didsth) continue;
- else if (difficulty < 2) break;
- /* Third island iteration: things we can only work out by looking
- * at groups of islands. */
- for (i = 0; i < state->n_islands; i++) {
- is = &state->islands[i];
- if (!solve_island_stage3(is, &didsth)) return 0;
- }
- if (didsth) continue;
- else if (difficulty < 3) break;
- /* If we can be bothered, write a recursive solver to finish here. */
- break;
- }
- if (map_check(state)) return 1; /* solved it */
- return 0;
- }
- static void solve_for_hint(game_state *state)
- {
- map_group(state);
- solve_sub(state, 10, 0);
- }
- static int solve_from_scratch(game_state *state, int difficulty)
- {
- map_clear(state);
- map_group(state);
- map_update_possibles(state);
- return solve_sub(state, difficulty, 0);
- }
- /* --- New game functions --- */
- static game_state *new_state(const game_params *params)
- {
- game_state *ret = snew(game_state);
- int wh = params->w * params->h, i;
- ret->w = params->w;
- ret->h = params->h;
- ret->allowloops = params->allowloops;
- ret->maxb = params->maxb;
- ret->params = *params;
- ret->grid = snewn(wh, grid_type);
- memset(ret->grid, 0, GRIDSZ(ret));
- ret->wha = snewn(wh*N_WH_ARRAYS, char);
- memset(ret->wha, 0, wh*N_WH_ARRAYS*sizeof(char));
- ret->possv = ret->wha;
- ret->possh = ret->wha + wh;
- ret->lines = ret->wha + wh*2;
- ret->maxv = ret->wha + wh*3;
- ret->maxh = ret->wha + wh*4;
- memset(ret->maxv, ret->maxb, wh*sizeof(char));
- memset(ret->maxh, ret->maxb, wh*sizeof(char));
- ret->islands = NULL;
- ret->n_islands = 0;
- ret->n_islands_alloc = 0;
- ret->gridi = snewn(wh, struct island *);
- for (i = 0; i < wh; i++) ret->gridi[i] = NULL;
- ret->solved = false;
- ret->completed = false;
- ret->solver = snew(struct solver_state);
- ret->solver->dsf = dsf_new(wh);
- ret->solver->tmpdsf = dsf_new(wh);
- ret->solver->refcount = 1;
- return ret;
- }
- static game_state *dup_game(const game_state *state)
- {
- game_state *ret = snew(game_state);
- int wh = state->w*state->h;
- ret->w = state->w;
- ret->h = state->h;
- ret->allowloops = state->allowloops;
- ret->maxb = state->maxb;
- ret->params = state->params;
- ret->grid = snewn(wh, grid_type);
- memcpy(ret->grid, state->grid, GRIDSZ(ret));
- ret->wha = snewn(wh*N_WH_ARRAYS, char);
- memcpy(ret->wha, state->wha, wh*N_WH_ARRAYS*sizeof(char));
- ret->possv = ret->wha;
- ret->possh = ret->wha + wh;
- ret->lines = ret->wha + wh*2;
- ret->maxv = ret->wha + wh*3;
- ret->maxh = ret->wha + wh*4;
- ret->islands = snewn(state->n_islands, struct island);
- memcpy(ret->islands, state->islands, state->n_islands * sizeof(struct island));
- ret->n_islands = ret->n_islands_alloc = state->n_islands;
- ret->gridi = snewn(wh, struct island *);
- fixup_islands_for_realloc(ret);
- ret->solved = state->solved;
- ret->completed = state->completed;
- ret->solver = state->solver;
- ret->solver->refcount++;
- return ret;
- }
- static void free_game(game_state *state)
- {
- if (--state->solver->refcount <= 0) {
- dsf_free(state->solver->dsf);
- dsf_free(state->solver->tmpdsf);
- sfree(state->solver);
- }
- sfree(state->islands);
- sfree(state->gridi);
- sfree(state->wha);
- sfree(state->grid);
- sfree(state);
- }
- #define MAX_NEWISLAND_TRIES 50
- #define MIN_SENSIBLE_ISLANDS 3
- #define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0)
- static char *new_game_desc(const game_params *params, random_state *rs,
- char **aux, bool interactive)
- {
- game_state *tobuild = NULL;
- int i, j, wh = params->w * params->h, x, y, dx, dy;
- int minx, miny, maxx, maxy, joinx, joiny, newx, newy, diffx, diffy;
- int ni_req = max((params->islands * wh) / 100, MIN_SENSIBLE_ISLANDS), ni_curr, ni_bad;
- struct island *is, *is2;
- char *ret;
- unsigned int echeck;
- /* pick a first island position randomly. */
- generate:
- if (tobuild) free_game(tobuild);
- tobuild = new_state(params);
- x = random_upto(rs, params->w);
- y = random_upto(rs, params->h);
- island_add(tobuild, x, y, 0);
- ni_curr = 1;
- ni_bad = 0;
- debug(("Created initial island at (%d,%d).\n", x, y));
- while (ni_curr < ni_req) {
- /* Pick a random island to try and extend from. */
- i = random_upto(rs, tobuild->n_islands);
- is = &tobuild->islands[i];
- /* Pick a random direction to extend in. */
- j = random_upto(rs, is->adj.npoints);
- dx = is->adj.points[j].x - is->x;
- dy = is->adj.points[j].y - is->y;
- /* Find out limits of where we could put a new island. */
- joinx = joiny = -1;
- minx = is->x + 2*dx; miny = is->y + 2*dy; /* closest is 2 units away. */
- x = is->x+dx; y = is->y+dy;
- if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
- /* already a line next to the island, continue. */
- goto bad;
- }
- while (1) {
- if (x < 0 || x >= params->w || y < 0 || y >= params->h) {
- /* got past the edge; put a possible at the island
- * and exit. */
- maxx = x-dx; maxy = y-dy;
- goto foundmax;
- }
- if (GRID(tobuild,x,y) & G_ISLAND) {
- /* could join up to an existing island... */
- joinx = x; joiny = y;
- /* ... or make a new one 2 spaces away. */
- maxx = x - 2*dx; maxy = y - 2*dy;
- goto foundmax;
- } else if (GRID(tobuild,x,y) & (G_LINEV|G_LINEH)) {
- /* could make a new one 1 space away from the line. */
- maxx = x - dx; maxy = y - dy;
- goto foundmax;
- }
- x += dx; y += dy;
- }
- foundmax:
- debug(("Island at (%d,%d) with d(%d,%d) has new positions "
- "(%d,%d) -> (%d,%d), join (%d,%d).\n",
- is->x, is->y, dx, dy, minx, miny, maxx, maxy, joinx, joiny));
- /* Now we know where we could either put a new island
- * (between min and max), or (if loops are allowed) could join on
- * to an existing island (at join). */
- if (params->allowloops && joinx != -1 && joiny != -1) {
- if (random_upto(rs, 100) < (unsigned long)params->expansion) {
- is2 = INDEX(tobuild, gridi, joinx, joiny);
- debug(("Joining island at (%d,%d) to (%d,%d).\n",
- is->x, is->y, is2->x, is2->y));
- goto join;
- }
- }
- diffx = (maxx - minx) * dx;
- diffy = (maxy - miny) * dy;
- if (diffx < 0 || diffy < 0) goto bad;
- if (random_upto(rs,100) < (unsigned long)params->expansion) {
- newx = maxx; newy = maxy;
- debug(("Creating new island at (%d,%d) (expanded).\n", newx, newy));
- } else {
- newx = minx + random_upto(rs,diffx+1)*dx;
- newy = miny + random_upto(rs,diffy+1)*dy;
- debug(("Creating new island at (%d,%d).\n", newx, newy));
- }
- /* check we're not next to island in the other orthogonal direction. */
- if ((INGRID(tobuild,newx+dy,newy+dx) && (GRID(tobuild,newx+dy,newy+dx) & G_ISLAND)) ||
- (INGRID(tobuild,newx-dy,newy-dx) && (GRID(tobuild,newx-dy,newy-dx) & G_ISLAND))) {
- debug(("New location is adjacent to island, skipping.\n"));
- goto bad;
- }
- is2 = island_add(tobuild, newx, newy, 0);
- /* Must get is again at this point; the array might have
- * been realloced by island_add... */
- is = &tobuild->islands[i]; /* ...but order will not change. */
- ni_curr++; ni_bad = 0;
- join:
- island_join(is, is2, random_upto(rs, tobuild->maxb)+1, false);
- debug_state(tobuild);
- continue;
- bad:
- ni_bad++;
- if (ni_bad > MAX_NEWISLAND_TRIES) {
- debug(("Unable to create any new islands after %d tries; "
- "created %d [%d%%] (instead of %d [%d%%] requested).\n",
- MAX_NEWISLAND_TRIES,
- ni_curr, ni_curr * 100 / wh,
- ni_req, ni_req * 100 / wh));
- goto generated;
- }
- }
- generated:
- if (ni_curr == 1) {
- debug(("Only generated one island (!), retrying.\n"));
- goto generate;
- }
- /* Check we have at least one island on each extremity of the grid. */
- echeck = 0;
- for (x = 0; x < params->w; x++) {
- if (INDEX(tobuild, gridi, x, 0)) echeck |= 1;
- if (INDEX(tobuild, gridi, x, params->h-1)) echeck |= 2;
- }
- for (y = 0; y < params->h; y++) {
- if (INDEX(tobuild, gridi, 0, y)) echeck |= 4;
- if (INDEX(tobuild, gridi, params->w-1, y)) echeck |= 8;
- }
- if (echeck != 15) {
- debug(("Generated grid doesn't fill to sides, retrying.\n"));
- goto generate;
- }
- map_count(tobuild);
- map_find_orthogonal(tobuild);
- if (params->difficulty > 0) {
- if ((ni_curr > MIN_SENSIBLE_ISLANDS) &&
- (solve_from_scratch(tobuild, params->difficulty-1) > 0)) {
- debug(("Grid is solvable at difficulty %d (too easy); retrying.\n",
- params->difficulty-1));
- goto generate;
- }
- }
- if (solve_from_scratch(tobuild, params->difficulty) == 0) {
- debug(("Grid not solvable at difficulty %d, (too hard); retrying.\n",
- params->difficulty));
- goto generate;
- }
- /* ... tobuild is now solved. We rely on this making the diff for aux. */
- debug_state(tobuild);
- ret = encode_game(tobuild);
- {
- game_state *clean = dup_game(tobuild);
- map_clear(clean);
- map_update_possibles(clean);
- *aux = game_state_diff(clean, tobuild);
- free_game(clean);
- }
- free_game(tobuild);
- return ret;
- }
- static const char *validate_desc(const game_params *params, const char *desc)
- {
- int i, j, wh = params->w * params->h, nislands = 0;
- bool *last_row = snewn(params->w, bool);
- memset(last_row, 0, params->w * sizeof(bool));
- for (i = 0; i < wh; i++) {
- if ((*desc >= '1' && *desc <= '9') || (*desc >= 'A' && *desc <= 'G')) {
- nislands++;
- /* Look for other islands to the left and above. */
- if ((i % params->w > 0 && last_row[i % params->w - 1]) ||
- last_row[i % params->w]) {
- sfree(last_row);
- return "Game description contains joined islands";
- }
- last_row[i % params->w] = true;
- } else if (*desc >= 'a' && *desc <= 'z') {
- for (j = 0; j < *desc - 'a' + 1; j++)
- last_row[(i + j) % params->w] = false;
- i += *desc - 'a'; /* plus the i++ */
- } else if (!*desc) {
- sfree(last_row);
- return "Game description shorter than expected";
- } else {
- sfree(last_row);
- return "Game description contains unexpected character";
- }
- desc++;
- }
- sfree(last_row);
- if (*desc || i > wh)
- return "Game description longer than expected";
- if (nislands < 2)
- return "Game description has too few islands";
- return NULL;
- }
- static game_state *new_game_sub(const game_params *params, const char *desc)
- {
- game_state *state = new_state(params);
- int x, y, run = 0;
- debug(("new_game[_sub]: desc = '%s'.\n", desc));
- for (y = 0; y < params->h; y++) {
- for (x = 0; x < params->w; x++) {
- char c = '\0';
- if (run == 0) {
- c = *desc++;
- assert(c != 'S');
- if (c >= 'a' && c <= 'z')
- run = c - 'a' + 1;
- }
- if (run > 0) {
- c = 'S';
- run--;
- }
- switch (c) {
- case '1': case '2': case '3': case '4':
- case '5': case '6': case '7': case '8': case '9':
- island_add(state, x, y, (c - '0'));
- break;
- case 'A': case 'B': case 'C': case 'D':
- case 'E': case 'F': case 'G':
- island_add(state, x, y, (c - 'A') + 10);
- break;
- case 'S':
- /* empty square */
- break;
- default:
- assert(!"Malformed desc.");
- break;
- }
- }
- }
- if (*desc) assert(!"Over-long desc.");
- map_find_orthogonal(state);
- map_update_possibles(state);
- return state;
- }
- static game_state *new_game(midend *me, const game_params *params,
- const char *desc)
- {
- return new_game_sub(params, desc);
- }
- struct game_ui {
- int dragx_src, dragy_src; /* source; -1 means no drag */
- int dragx_dst, dragy_dst; /* src's closest orth island. */
- grid_type todraw;
- bool dragging, drag_is_noline;
- int nlines;
- int cur_x, cur_y; /* cursor position */
- bool cur_visible;
- bool show_hints;
- };
- static char *ui_cancel_drag(game_ui *ui)
- {
- ui->dragx_src = ui->dragy_src = -1;
- ui->dragx_dst = ui->dragy_dst = -1;
- ui->dragging = false;
- return MOVE_UI_UPDATE;
- }
- static game_ui *new_ui(const game_state *state)
- {
- game_ui *ui = snew(game_ui);
- ui_cancel_drag(ui);
- if (state != NULL) {
- ui->cur_x = state->islands[0].x;
- ui->cur_y = state->islands[0].y;
- }
- ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
- ui->show_hints = false;
- return ui;
- }
- static config_item *get_prefs(game_ui *ui)
- {
- config_item *ret;
- ret = snewn(2, config_item);
- ret[0].name = "Show possible bridge locations";
- ret[0].kw = "show-hints";
- ret[0].type = C_BOOLEAN;
- ret[0].u.boolean.bval = ui->show_hints;
- ret[1].name = NULL;
- ret[1].type = C_END;
- return ret;
- }
- static void set_prefs(game_ui *ui, const config_item *cfg)
- {
- ui->show_hints = cfg[0].u.boolean.bval;
- }
- static void free_ui(game_ui *ui)
- {
- sfree(ui);
- }
- static void game_changed_state(game_ui *ui, const game_state *oldstate,
- const game_state *newstate)
- {
- }
- static const char *current_key_label(const game_ui *ui,
- const game_state *state, int button)
- {
- if (IS_CURSOR_SELECT(button)) {
- if (!ui->cur_visible)
- return ""; /* Actually shows cursor. */
- if (ui->dragging || button == CURSOR_SELECT2)
- return "Finished";
- if (GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND)
- return "Select";
- }
- return "";
- }
- struct game_drawstate {
- int tilesize;
- int w, h;
- unsigned long *grid, *newgrid;
- int *lv, *lh;
- bool started, dragging;
- };
- static void game_get_cursor_location(const game_ui *ui,
- const game_drawstate *ds,
- const game_state *state,
- const game_params *params,
- int *x, int *y, int *w, int *h)
- {
- if(ui->cur_visible) {
- *x = COORD(ui->cur_x);
- *y = COORD(ui->cur_y);
- *w = *h = TILE_SIZE;
- }
- }
- /*
- * The contents of ds->grid are complicated, because of the circular
- * islands which overlap their own grid square into neighbouring
- * squares. An island square can contain pieces of the bridges in all
- * directions, and conversely a bridge square can be intruded on by
- * islands from any direction.
- *
- * So we define one group of flags describing what's important about
- * an island, and another describing a bridge. Island squares' entries
- * in ds->grid contain one of the former and four of the latter; bridge
- * squares, four of the former and _two_ of the latter - because a
- * horizontal and vertical 'bridge' can cross, when one of them is a
- * 'no bridge here' pencil mark.
- *
- * Bridge flags need to indicate 0-4 actual bridges (3 bits), a 'no
- * bridge' row of crosses, or a grey hint line; that's 7
- * possibilities, so 3 bits suffice. But then we also need to vary the
- * colours: the bridges can turn COL_WARNING if they're part of a loop
- * in no-loops mode, COL_HIGHLIGHT during a victory flash, or
- * COL_SELECTED if they're the bridge the user is currently dragging,
- * so that's 2 more bits for foreground colour. Also bridges can be
- * backed by COL_MARK if they're locked by the user, so that's one
- * more bit, making 6 bits per bridge direction.
- *
- * Island flags omit the actual island clue (it never changes during
- * the game, so doesn't have to be stored in ds->grid to check against
- * the previous version), so they just need to include 2 bits for
- * foreground colour (an island can be normal, COL_HIGHLIGHT during
- * victory, COL_WARNING if its clue is unsatisfiable, or COL_SELECTED
- * if it's part of the user's drag) and 2 bits for background (normal,
- * COL_MARK for a locked island, COL_CURSOR for the keyboard cursor).
- * That's 4 bits per island direction. We must also indicate whether
- * no island is present at all (in the case where the island is
- * potentially intruding into the side of a line square), which we do
- * using the unused 4th value of the background field.
- *
- * So an island square needs 4 + 4*6 = 28 bits, while a bridge square
- * needs 4*4 + 2*6 = 28 bits too. Both only just fit in 32 bits, which
- * is handy, because otherwise we'd have to faff around forever with
- * little structs!
- */
- /* Flags for line data */
- #define DL_COUNTMASK 0x07
- #define DL_COUNT_CROSS 0x06
- #define DL_COUNT_HINT 0x07
- #define DL_COLMASK 0x18
- #define DL_COL_NORMAL 0x00
- #define DL_COL_WARNING 0x08
- #define DL_COL_FLASH 0x10
- #define DL_COL_SELECTED 0x18
- #define DL_LOCK 0x20
- #define DL_MASK 0x3F
- /* Flags for island data */
- #define DI_COLMASK 0x03
- #define DI_COL_NORMAL 0x00
- #define DI_COL_FLASH 0x01
- #define DI_COL_WARNING 0x02
- #define DI_COL_SELECTED 0x03
- #define DI_BGMASK 0x0C
- #define DI_BG_NO_ISLAND 0x00
- #define DI_BG_NORMAL 0x04
- #define DI_BG_MARK 0x08
- #define DI_BG_CURSOR 0x0C
- #define DI_MASK 0x0F
- /* Shift counts for the format of a 32-bit word in an island square */
- #define D_I_ISLAND_SHIFT 0
- #define D_I_LINE_SHIFT_L 4
- #define D_I_LINE_SHIFT_R 10
- #define D_I_LINE_SHIFT_U 16
- #define D_I_LINE_SHIFT_D 24
- /* Shift counts for the format of a 32-bit word in a line square */
- #define D_L_ISLAND_SHIFT_L 0
- #define D_L_ISLAND_SHIFT_R 4
- #define D_L_ISLAND_SHIFT_U 8
- #define D_L_ISLAND_SHIFT_D 12
- #define D_L_LINE_SHIFT_H 16
- #define D_L_LINE_SHIFT_V 22
- static char *update_drag_dst(const game_state *state, game_ui *ui,
- const game_drawstate *ds, int nx, int ny)
- {
- int ox, oy, dx, dy, i, currl, maxb;
- struct island *is;
- grid_type gtype, ntype, mtype, curr;
- if (ui->dragx_src == -1 || ui->dragy_src == -1) return NULL;
- ui->dragx_dst = -1;
- ui->dragy_dst = -1;
- /* work out which of the four directions we're closest to... */
- ox = COORD(ui->dragx_src) + TILE_SIZE/2;
- oy = COORD(ui->dragy_src) + TILE_SIZE/2;
- if (abs(nx-ox) < abs(ny-oy)) {
- dx = 0;
- dy = (ny-oy) < 0 ? -1 : 1;
- gtype = G_LINEV; ntype = G_NOLINEV; mtype = G_MARKV;
- maxb = INDEX(state, maxv, ui->dragx_src+dx, ui->dragy_src+dy);
- } else {
- dy = 0;
- dx = (nx-ox) < 0 ? -1 : 1;
- gtype = G_LINEH; ntype = G_NOLINEH; mtype = G_MARKH;
- maxb = INDEX(state, maxh, ui->dragx_src+dx, ui->dragy_src+dy);
- }
- if (ui->drag_is_noline) {
- ui->todraw = ntype;
- } else {
- curr = GRID(state, ui->dragx_src+dx, ui->dragy_src+dy);
- currl = INDEX(state, lines, ui->dragx_src+dx, ui->dragy_src+dy);
- if (curr & gtype) {
- if (currl == maxb) {
- ui->todraw = 0;
- ui->nlines = 0;
- } else {
- ui->todraw = gtype;
- ui->nlines = currl + 1;
- }
- } else {
- ui->todraw = gtype;
- ui->nlines = 1;
- }
- }
- /* ... and see if there's an island off in that direction. */
- is = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
- for (i = 0; i < is->adj.npoints; i++) {
- if (is->adj.points[i].off == 0) continue;
- curr = GRID(state, is->x+dx, is->y+dy);
- if (curr & mtype) continue; /* don't allow changes to marked lines. */
- if (ui->drag_is_noline) {
- if (curr & gtype) continue; /* no no-line where already a line */
- } else {
- if (POSSIBLES(state, dx, is->x+dx, is->y+dy) == 0) continue; /* no line if !possible. */
- if (curr & ntype) continue; /* can't have a bridge where there's a no-line. */
- }
- if (is->adj.points[i].dx == dx &&
- is->adj.points[i].dy == dy) {
- ui->dragx_dst = ISLAND_ORTHX(is,i);
- ui->dragy_dst = ISLAND_ORTHY(is,i);
- }
- }
- /*debug(("update_drag src (%d,%d) d(%d,%d) dst (%d,%d)\n",
- ui->dragx_src, ui->dragy_src, dx, dy,
- ui->dragx_dst, ui->dragy_dst));*/
- return MOVE_UI_UPDATE;
- }
- static char *finish_drag(const game_state *state, game_ui *ui)
- {
- char buf[80];
- if (ui->dragx_src == -1 || ui->dragy_src == -1)
- return NULL;
- if (ui->dragx_dst == -1 || ui->dragy_dst == -1)
- return ui_cancel_drag(ui);
- if (ui->drag_is_noline) {
- sprintf(buf, "N%d,%d,%d,%d",
- ui->dragx_src, ui->dragy_src,
- ui->dragx_dst, ui->dragy_dst);
- } else {
- sprintf(buf, "L%d,%d,%d,%d,%d",
- ui->dragx_src, ui->dragy_src,
- ui->dragx_dst, ui->dragy_dst, ui->nlines);
- }
- ui_cancel_drag(ui);
- return dupstr(buf);
- }
- static char *interpret_move(const game_state *state, game_ui *ui,
- const game_drawstate *ds,
- int x, int y, int button)
- {
- int gx = FROMCOORD(x), gy = FROMCOORD(y);
- char buf[80], *ret;
- grid_type ggrid = INGRID(state,gx,gy) ? GRID(state,gx,gy) : 0;
- bool shift = button & MOD_SHFT, control = button & MOD_CTRL;
- button &= ~MOD_MASK;
- if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
- if (!INGRID(state, gx, gy)) return MOVE_UNUSED;
- ui->cur_visible = false;
- if (ggrid & G_ISLAND) {
- ui->dragx_src = gx;
- ui->dragy_src = gy;
- return MOVE_UI_UPDATE;
- } else
- return ui_cancel_drag(ui);
- } else if (button == LEFT_DRAG || button == RIGHT_DRAG) {
- if (INGRID(state, ui->dragx_src, ui->dragy_src)
- && (gx != ui->dragx_src || gy != ui->dragy_src)
- && !(GRID(state,ui->dragx_src,ui->dragy_src) & G_MARK)) {
- ui->dragging = true;
- ui->drag_is_noline = (button == RIGHT_DRAG);
- return update_drag_dst(state, ui, ds, x, y);
- } else {
- /* cancel a drag when we go back to the starting point */
- ui->dragx_dst = -1;
- ui->dragy_dst = -1;
- return MOVE_UI_UPDATE;
- }
- } else if (button == LEFT_RELEASE || button == RIGHT_RELEASE) {
- if (ui->dragging) {
- return finish_drag(state, ui);
- } else {
- if (!INGRID(state, ui->dragx_src, ui->dragy_src)
- || gx != ui->dragx_src || gy != ui->dragy_src) {
- return ui_cancel_drag(ui);
- }
- ui_cancel_drag(ui);
- if (!INGRID(state, gx, gy)) return MOVE_UNUSED;
- if (!(GRID(state, gx, gy) & G_ISLAND)) return MOVE_NO_EFFECT;
- sprintf(buf, "M%d,%d", gx, gy);
- return dupstr(buf);
- }
- } else if (button == 'h' || button == 'H') {
- game_state *solved = dup_game(state);
- solve_for_hint(solved);
- ret = game_state_diff(state, solved);
- free_game(solved);
- return ret;
- } else if (IS_CURSOR_MOVE(button)) {
- ui->cur_visible = true;
- if (control || shift) {
- ui->dragx_src = ui->cur_x;
- ui->dragy_src = ui->cur_y;
- ui->dragging = true;
- ui->drag_is_noline = !control;
- }
- if (ui->dragging) {
- int nx = ui->cur_x, ny = ui->cur_y;
- move_cursor(button, &nx, &ny, state->w, state->h, false);
- if (nx == ui->cur_x && ny == ui->cur_y)
- return MOVE_NO_EFFECT;
- update_drag_dst(state, ui, ds,
- COORD(nx)+TILE_SIZE/2,
- COORD(ny)+TILE_SIZE/2);
- return finish_drag(state, ui);
- } else {
- int dx = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : 0;
- int dy = (button == CURSOR_DOWN) ? +1 : (button == CURSOR_UP) ? -1 : 0;
- int dorthx = 1 - abs(dx), dorthy = 1 - abs(dy);
- int dir, orth, nx = x, ny = y;
- /* 'orthorder' is a tweak to ensure that if you press RIGHT and
- * happen to move upwards, when you press LEFT you then tend
- * downwards (rather than upwards again). */
- int orthorder = (button == CURSOR_LEFT || button == CURSOR_UP) ? 1 : -1;
- /* This attempts to find an island in the direction you're
- * asking for, broadly speaking. If you ask to go right, for
- * example, it'll look for islands to the right and slightly
- * above or below your current horiz. position, allowing
- * further above/below the further away it searches. */
- assert(GRID(state, ui->cur_x, ui->cur_y) & G_ISLAND);
- /* currently this is depth-first (so orthogonally-adjacent
- * islands across the other side of the grid will be moved to
- * before closer islands slightly offset). Swap the order of
- * these two loops to change to breadth-first search. */
- for (orth = 0; ; orth++) {
- bool oingrid = false;
- for (dir = 1; ; dir++) {
- bool dingrid = false;
- if (orth > dir) continue; /* only search in cone outwards. */
- nx = ui->cur_x + dir*dx + orth*dorthx*orthorder;
- ny = ui->cur_y + dir*dy + orth*dorthy*orthorder;
- if (INGRID(state, nx, ny)) {
- dingrid = true;
- oingrid = true;
- if (GRID(state, nx, ny) & G_ISLAND) goto found;
- }
- nx = ui->cur_x + dir*dx - orth*dorthx*orthorder;
- ny = ui->cur_y + dir*dy - orth*dorthy*orthorder;
- if (INGRID(state, nx, ny)) {
- dingrid = true;
- oingrid = true;
- if (GRID(state, nx, ny) & G_ISLAND) goto found;
- }
- if (!dingrid) break;
- }
- if (!oingrid) return MOVE_UI_UPDATE;
- }
- /* not reached */
- found:
- ui->cur_x = nx;
- ui->cur_y = ny;
- return MOVE_UI_UPDATE;
- }
- } else if (IS_CURSOR_SELECT(button)) {
- if (!ui->cur_visible) {
- ui->cur_visible = true;
- return MOVE_UI_UPDATE;
- }
- if (ui->dragging || button == CURSOR_SELECT2) {
- ui_cancel_drag(ui);
- if (ui->dragx_dst == -1 && ui->dragy_dst == -1) {
- sprintf(buf, "M%d,%d", ui->cur_x, ui->cur_y);
- return dupstr(buf);
- } else
- return MOVE_UI_UPDATE;
- } else {
- grid_type v = GRID(state, ui->cur_x, ui->cur_y);
- if (v & G_ISLAND) {
- ui->dragging = true;
- ui->dragx_src = ui->cur_x;
- ui->dragy_src = ui->cur_y;
- ui->dragx_dst = ui->dragy_dst = -1;
- ui->drag_is_noline = (button == CURSOR_SELECT2);
- return MOVE_UI_UPDATE;
- }
- }
- } else if ((button >= '0' && button <= '9') ||
- (button >= 'a' && button <= 'f') ||
- (button >= 'A' && button <= 'F')) {
- /* jump to island with .count == number closest to cur_{x,y} */
- int best_x = -1, best_y = -1, best_sqdist = -1, number = -1, i;
- if (button >= '0' && button <= '9')
- number = (button == '0' ? 16 : button - '0');
- else if (button >= 'a' && button <= 'f')
- number = 10 + button - 'a';
- else if (button >= 'A' && button <= 'F')
- number = 10 + button - 'A';
- if (!ui->cur_visible) {
- ui->cur_visible = true;
- return MOVE_UI_UPDATE;
- }
- for (i = 0; i < state->n_islands; ++i) {
- int x = state->islands[i].x, y = state->islands[i].y;
- int dx = x - ui->cur_x, dy = y - ui->cur_y;
- int sqdist = dx*dx + dy*dy;
- if (state->islands[i].count != number)
- continue;
- if (x == ui->cur_x && y == ui->cur_y)
- continue;
- /* new_game() reads the islands in row-major order, so by
- * breaking ties in favor of `first in state->islands' we
- * also break ties by `lexicographically smallest (y, x)'.
- * Thus, there's a stable pattern to how ties are broken
- * which the user can learn and use to navigate faster. */
- if (best_sqdist == -1 || sqdist < best_sqdist) {
- best_x = x;
- best_y = y;
- best_sqdist = sqdist;
- }
- }
- if (best_x != -1 && best_y != -1) {
- ui->cur_x = best_x;
- ui->cur_y = best_y;
- return MOVE_UI_UPDATE;
- } else
- return MOVE_NO_EFFECT;
- } else if (button == 'g' || button == 'G') {
- ui->show_hints = !ui->show_hints;
- return MOVE_UI_UPDATE;
- }
- return MOVE_UNUSED;
- }
- static game_state *execute_move(const game_state *state, const char *move)
- {
- game_state *ret = dup_game(state);
- int x1, y1, x2, y2, nl, n;
- struct island *is1, *is2;
- char c;
- debug(("execute_move: %s\n", move));
- if (!*move) goto badmove;
- while (*move) {
- c = *move++;
- if (c == 'S') {
- ret->solved = true;
- n = 0;
- } else if (c == 'L') {
- if (sscanf(move, "%d,%d,%d,%d,%d%n",
- &x1, &y1, &x2, &y2, &nl, &n) != 5)
- goto badmove;
- if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
- goto badmove;
- /* Precisely one co-ordinate must differ between islands. */
- if ((x1 != x2) + (y1 != y2) != 1) goto badmove;
- is1 = INDEX(ret, gridi, x1, y1);
- is2 = INDEX(ret, gridi, x2, y2);
- if (!is1 || !is2) goto badmove;
- if (nl < 0 || nl > state->maxb) goto badmove;
- island_join(is1, is2, nl, false);
- } else if (c == 'N') {
- if (sscanf(move, "%d,%d,%d,%d%n",
- &x1, &y1, &x2, &y2, &n) != 4)
- goto badmove;
- if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
- goto badmove;
- if ((x1 != x2) + (y1 != y2) != 1) goto badmove;
- is1 = INDEX(ret, gridi, x1, y1);
- is2 = INDEX(ret, gridi, x2, y2);
- if (!is1 || !is2) goto badmove;
- island_join(is1, is2, -1, false);
- } else if (c == 'M') {
- if (sscanf(move, "%d,%d%n",
- &x1, &y1, &n) != 2)
- goto badmove;
- if (!INGRID(ret, x1, y1))
- goto badmove;
- is1 = INDEX(ret, gridi, x1, y1);
- if (!is1) goto badmove;
- island_togglemark(is1);
- } else
- goto badmove;
- move += n;
- if (*move == ';')
- move++;
- else if (*move) goto badmove;
- }
- map_update_possibles(ret);
- if (map_check(ret)) {
- debug(("Game completed.\n"));
- ret->completed = true;
- }
- return ret;
- badmove:
- debug(("%s: unrecognised move.\n", move));
- free_game(ret);
- return NULL;
- }
- static char *solve_game(const game_state *state, const game_state *currstate,
- const char *aux, const char **error)
- {
- char *ret;
- game_state *solved;
- if (aux) {
- debug(("solve_game: aux = %s\n", aux));
- solved = execute_move(state, aux);
- if (!solved) {
- *error = "Generated aux string is not a valid move (!).";
- return NULL;
- }
- } else {
- solved = dup_game(state);
- /* solve with max strength... */
- if (solve_from_scratch(solved, 10) == 0) {
- free_game(solved);
- *error = "Game does not have a (non-recursive) solution.";
- return NULL;
- }
- }
- ret = game_state_diff(currstate, solved);
- free_game(solved);
- debug(("solve_game: ret = %s\n", ret));
- return ret;
- }
- /* ----------------------------------------------------------------------
- * Drawing routines.
- */
- static void game_compute_size(const game_params *params, int tilesize,
- const game_ui *ui, int *x, int *y)
- {
- /* Ick: fake up `ds->tilesize' for macro expansion purposes */
- struct { int tilesize; } ads, *ds = &ads;
- ads.tilesize = tilesize;
- *x = TILE_SIZE * params->w + 2 * BORDER;
- *y = TILE_SIZE * params->h + 2 * BORDER;
- }
- static void game_set_size(drawing *dr, game_drawstate *ds,
- const game_params *params, int tilesize)
- {
- ds->tilesize = tilesize;
- }
- static float *game_colours(frontend *fe, int *ncolours)
- {
- float *ret = snewn(3 * NCOLOURS, float);
- int i;
- game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
- for (i = 0; i < 3; i++) {
- ret[COL_FOREGROUND * 3 + i] = 0.0F;
- ret[COL_HINT * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
- ret[COL_GRID * 3 + i] =
- (ret[COL_HINT * 3 + i] + ret[COL_BACKGROUND * 3 + i]) * 0.5F;
- ret[COL_MARK * 3 + i] = ret[COL_HIGHLIGHT * 3 + i];
- }
- ret[COL_WARNING * 3 + 0] = 1.0F;
- ret[COL_WARNING * 3 + 1] = 0.25F;
- ret[COL_WARNING * 3 + 2] = 0.25F;
- ret[COL_SELECTED * 3 + 0] = 0.25F;
- ret[COL_SELECTED * 3 + 1] = 1.00F;
- ret[COL_SELECTED * 3 + 2] = 0.25F;
- ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
- ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.8F;
- ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.8F;
- *ncolours = NCOLOURS;
- return ret;
- }
- static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
- {
- struct game_drawstate *ds = snew(struct game_drawstate);
- int wh = state->w*state->h;
- int i;
- ds->tilesize = 0;
- ds->w = state->w;
- ds->h = state->h;
- ds->started = false;
- ds->dragging = false;
- ds->grid = snewn(wh, unsigned long);
- for (i = 0; i < wh; i++)
- ds->grid[i] = ~0UL;
- ds->newgrid = snewn(wh, unsigned long);
- ds->lv = snewn(wh, int);
- ds->lh = snewn(wh, int);
- memset(ds->lv, 0, wh*sizeof(int));
- memset(ds->lh, 0, wh*sizeof(int));
- return ds;
- }
- static void game_free_drawstate(drawing *dr, game_drawstate *ds)
- {
- sfree(ds->lv);
- sfree(ds->lh);
- sfree(ds->newgrid);
- sfree(ds->grid);
- sfree(ds);
- }
- #define LINE_WIDTH (TILE_SIZE/8)
- #define TS8(x) (((x)*TILE_SIZE)/8)
- #define OFFSET(thing) ((TILE_SIZE/2) - ((thing)/2))
- static bool between_island(const game_state *state, int sx, int sy,
- int dx, int dy)
- {
- int x = sx - dx, y = sy - dy;
- while (INGRID(state, x, y)) {
- if (GRID(state, x, y) & G_ISLAND) goto found;
- x -= dx; y -= dy;
- }
- return false;
- found:
- x = sx + dx, y = sy + dy;
- while (INGRID(state, x, y)) {
- if (GRID(state, x, y) & G_ISLAND) return true;
- x += dx; y += dy;
- }
- return false;
- }
- static void lines_lvlh(const game_state *state, const game_ui *ui,
- int x, int y, grid_type v, int *lv_r, int *lh_r)
- {
- int lh = 0, lv = 0;
- if (v & G_LINEV) lv = INDEX(state,lines,x,y);
- if (v & G_LINEH) lh = INDEX(state,lines,x,y);
- if (ui->show_hints) {
- if (between_island(state, x, y, 0, 1) && !lv) lv = 1;
- if (between_island(state, x, y, 1, 0) && !lh) lh = 1;
- }
- /*debug(("lvlh: (%d,%d) v 0x%x lv %d lh %d.\n", x, y, v, lv, lh));*/
- *lv_r = lv; *lh_r = lh;
- }
- static void draw_cross(drawing *dr, game_drawstate *ds,
- int ox, int oy, int col)
- {
- int off = TS8(2);
- draw_line(dr, ox, oy, ox+off, oy+off, col);
- draw_line(dr, ox+off, oy, ox, oy+off, col);
- }
- static void draw_general_line(drawing *dr, game_drawstate *ds,
- int ox, int oy, int fx, int fy, int ax, int ay,
- int len, unsigned long ldata, int which)
- {
- /*
- * Draw one direction of lines in a square. To permit the same
- * code to handle horizontal and vertical lines, fx,fy are the
- * 'forward' direction (along the lines) and ax,ay are the
- * 'across' direction.
- *
- * We draw the white background for a locked bridge if (which &
- * 1), and draw the bridges themselves if (which & 2). This
- * permits us to get two overlapping locked bridges right without
- * one of them erasing part of the other.
- */
- int fg;
- fg = ((ldata & DL_COUNTMASK) == DL_COUNT_HINT ? COL_HINT :
- (ldata & DL_COLMASK) == DL_COL_SELECTED ? COL_SELECTED :
- (ldata & DL_COLMASK) == DL_COL_FLASH ? COL_HIGHLIGHT :
- (ldata & DL_COLMASK) == DL_COL_WARNING ? COL_WARNING :
- COL_FOREGROUND);
- if ((ldata & DL_COUNTMASK) == DL_COUNT_CROSS) {
- draw_cross(dr, ds,
- ox + TS8(1)*fx + TS8(3)*ax,
- oy + TS8(1)*fy + TS8(3)*ay, fg);
- draw_cross(dr, ds,
- ox + TS8(5)*fx + TS8(3)*ax,
- oy + TS8(5)*fy + TS8(3)*ay, fg);
- } else if ((ldata & DL_COUNTMASK) != 0) {
- int lh, lw, gw, bw, i, loff;
- lh = (ldata & DL_COUNTMASK);
- if (lh == DL_COUNT_HINT)
- lh = 1;
- lw = gw = LINE_WIDTH;
- while ((bw = lw * lh + gw * (lh+1)) > TILE_SIZE)
- gw--;
- loff = OFFSET(bw);
- if (which & 1) {
- if ((ldata & DL_LOCK) && fg != COL_HINT)
- draw_rect(dr, ox + loff*ax, oy + loff*ay,
- len*fx+bw*ax, len*fy+bw*ay, COL_MARK);
- }
- if (which & 2) {
- for (i = 0; i < lh; i++, loff += lw + gw)
- draw_rect(dr, ox + (loff+gw)*ax, oy + (loff+gw)*ay,
- len*fx+lw*ax, len*fy+lw*ay, fg);
- }
- }
- }
- static void draw_hline(drawing *dr, game_drawstate *ds,
- int ox, int oy, int w, unsigned long vdata, int which)
- {
- draw_general_line(dr, ds, ox, oy, 1, 0, 0, 1, w, vdata, which);
- }
- static void draw_vline(drawing *dr, game_drawstate *ds,
- int ox, int oy, int h, unsigned long vdata, int which)
- {
- draw_general_line(dr, ds, ox, oy, 0, 1, 1, 0, h, vdata, which);
- }
- #define ISLAND_RADIUS ((TILE_SIZE*12)/20)
- #define ISLAND_NUMSIZE(clue) \
- (((clue) < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
- static void draw_island(drawing *dr, game_drawstate *ds,
- int ox, int oy, int clue, unsigned long idata)
- {
- int half, orad, irad, fg, bg;
- if ((idata & DI_BGMASK) == DI_BG_NO_ISLAND)
- return;
- half = TILE_SIZE/2;
- orad = ISLAND_RADIUS;
- irad = orad - LINE_WIDTH;
- fg = ((idata & DI_COLMASK) == DI_COL_SELECTED ? COL_SELECTED :
- (idata & DI_COLMASK) == DI_COL_WARNING ? COL_WARNING :
- (idata & DI_COLMASK) == DI_COL_FLASH ? COL_HIGHLIGHT :
- COL_FOREGROUND);
- bg = ((idata & DI_BGMASK) == DI_BG_CURSOR ? COL_CURSOR :
- (idata & DI_BGMASK) == DI_BG_MARK ? COL_MARK :
- COL_BACKGROUND);
- /* draw a thick circle */
- draw_circle(dr, ox+half, oy+half, orad, fg, fg);
- draw_circle(dr, ox+half, oy+half, irad, bg, bg);
- if (clue > 0) {
- char str[32];
- int textcolour = (fg == COL_SELECTED ? COL_FOREGROUND : fg);
- sprintf(str, "%d", clue);
- draw_text(dr, ox+half, oy+half, FONT_VARIABLE, ISLAND_NUMSIZE(clue),
- ALIGN_VCENTRE | ALIGN_HCENTRE, textcolour, str);
- }
- }
- static void draw_island_tile(drawing *dr, game_drawstate *ds,
- int x, int y, int clue, unsigned long data)
- {
- int ox = COORD(x), oy = COORD(y);
- int which;
- clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
- draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
- /*
- * Because of the possibility of incoming bridges just about
- * meeting at one corner, we must split the line-drawing into
- * background and foreground segments.
- */
- for (which = 1; which <= 2; which <<= 1) {
- draw_hline(dr, ds, ox, oy, TILE_SIZE/2,
- (data >> D_I_LINE_SHIFT_L) & DL_MASK, which);
- draw_hline(dr, ds, ox + TILE_SIZE - TILE_SIZE/2, oy, TILE_SIZE/2,
- (data >> D_I_LINE_SHIFT_R) & DL_MASK, which);
- draw_vline(dr, ds, ox, oy, TILE_SIZE/2,
- (data >> D_I_LINE_SHIFT_U) & DL_MASK, which);
- draw_vline(dr, ds, ox, oy + TILE_SIZE - TILE_SIZE/2, TILE_SIZE/2,
- (data >> D_I_LINE_SHIFT_D) & DL_MASK, which);
- }
- draw_island(dr, ds, ox, oy, clue, (data >> D_I_ISLAND_SHIFT) & DI_MASK);
- unclip(dr);
- draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
- }
- static void draw_line_tile(drawing *dr, game_drawstate *ds,
- int x, int y, unsigned long data)
- {
- int ox = COORD(x), oy = COORD(y);
- unsigned long hdata, vdata;
- clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
- draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
- /*
- * We have to think about which of the horizontal and vertical
- * line to draw first, if both exist.
- *
- * The rule is that hint lines are drawn at the bottom, then
- * NOLINE crosses, then actual bridges. The enumeration in the
- * DL_COUNTMASK field is set up so that this drops out of a
- * straight comparison between the two.
- *
- * Since lines crossing in this type of square cannot both be
- * actual bridges, there's no need to pass a nontrivial 'which'
- * parameter to draw_[hv]line.
- */
- hdata = (data >> D_L_LINE_SHIFT_H) & DL_MASK;
- vdata = (data >> D_L_LINE_SHIFT_V) & DL_MASK;
- if ((hdata & DL_COUNTMASK) > (vdata & DL_COUNTMASK)) {
- draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3);
- draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3);
- } else {
- draw_vline(dr, ds, ox, oy, TILE_SIZE, vdata, 3);
- draw_hline(dr, ds, ox, oy, TILE_SIZE, hdata, 3);
- }
- /*
- * The islands drawn at the edges of a line tile don't need clue
- * numbers.
- */
- draw_island(dr, ds, ox - TILE_SIZE, oy, -1,
- (data >> D_L_ISLAND_SHIFT_L) & DI_MASK);
- draw_island(dr, ds, ox + TILE_SIZE, oy, -1,
- (data >> D_L_ISLAND_SHIFT_R) & DI_MASK);
- draw_island(dr, ds, ox, oy - TILE_SIZE, -1,
- (data >> D_L_ISLAND_SHIFT_U) & DI_MASK);
- draw_island(dr, ds, ox, oy + TILE_SIZE, -1,
- (data >> D_L_ISLAND_SHIFT_D) & DI_MASK);
- unclip(dr);
- draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
- }
- static void draw_edge_tile(drawing *dr, game_drawstate *ds,
- int x, int y, int dx, int dy, unsigned long data)
- {
- int ox = COORD(x), oy = COORD(y);
- int cx = ox, cy = oy, cw = TILE_SIZE, ch = TILE_SIZE;
- if (dy) {
- if (dy > 0)
- cy += TILE_SIZE/2;
- ch -= TILE_SIZE/2;
- } else {
- if (dx > 0)
- cx += TILE_SIZE/2;
- cw -= TILE_SIZE/2;
- }
- clip(dr, cx, cy, cw, ch);
- draw_rect(dr, cx, cy, cw, ch, COL_BACKGROUND);
- draw_island(dr, ds, ox + TILE_SIZE*dx, oy + TILE_SIZE*dy, -1,
- (data >> D_I_ISLAND_SHIFT) & DI_MASK);
- unclip(dr);
- draw_update(dr, cx, cy, cw, ch);
- }
- static void game_redraw(drawing *dr, game_drawstate *ds,
- const game_state *oldstate, const game_state *state,
- int dir, const game_ui *ui,
- float animtime, float flashtime)
- {
- int x, y, lv, lh;
- grid_type v;
- bool flash = false;
- struct island *is, *is_drag_src = NULL, *is_drag_dst = NULL;
- if (flashtime) {
- int f = (int)(flashtime * 5 / FLASH_TIME);
- if (f == 1 || f == 3) flash = true;
- }
- /* Clear screen, if required. */
- if (!ds->started) {
- #ifdef DRAW_GRID
- draw_rect_outline(dr,
- COORD(0)-1, COORD(0)-1,
- TILE_SIZE * ds->w + 2, TILE_SIZE * ds->h + 2,
- COL_GRID);
- #endif
- draw_update(dr, 0, 0,
- TILE_SIZE * ds->w + 2 * BORDER,
- TILE_SIZE * ds->h + 2 * BORDER);
- ds->started = true;
- }
- if (ui->dragx_src != -1 && ui->dragy_src != -1) {
- ds->dragging = true;
- is_drag_src = INDEX(state, gridi, ui->dragx_src, ui->dragy_src);
- assert(is_drag_src);
- if (ui->dragx_dst != -1 && ui->dragy_dst != -1) {
- is_drag_dst = INDEX(state, gridi, ui->dragx_dst, ui->dragy_dst);
- assert(is_drag_dst);
- }
- } else
- ds->dragging = false;
- /*
- * Set up ds->newgrid with the current grid contents.
- */
- for (x = 0; x < ds->w; x++)
- for (y = 0; y < ds->h; y++)
- INDEX(ds,newgrid,x,y) = 0;
- for (x = 0; x < ds->w; x++) {
- for (y = 0; y < ds->h; y++) {
- v = GRID(state, x, y);
- if (v & G_ISLAND) {
- /*
- * An island square. Compute the drawing data for the
- * island, and put it in this square and surrounding
- * squares.
- */
- unsigned long idata = 0;
- is = INDEX(state, gridi, x, y);
- if (flash)
- idata |= DI_COL_FLASH;
- if (is_drag_src && (is == is_drag_src ||
- (is_drag_dst && is == is_drag_dst)))
- idata |= DI_COL_SELECTED;
- else if (island_impossible(is, v & G_MARK) || (v & G_WARN))
- idata |= DI_COL_WARNING;
- else
- idata |= DI_COL_NORMAL;
- if (ui->cur_visible &&
- ui->cur_x == is->x && ui->cur_y == is->y)
- idata |= DI_BG_CURSOR;
- else if (v & G_MARK)
- idata |= DI_BG_MARK;
- else
- idata |= DI_BG_NORMAL;
- INDEX(ds,newgrid,x,y) |= idata << D_I_ISLAND_SHIFT;
- if (x > 0 && !(GRID(state,x-1,y) & G_ISLAND))
- INDEX(ds,newgrid,x-1,y) |= idata << D_L_ISLAND_SHIFT_R;
- if (x+1 < state->w && !(GRID(state,x+1,y) & G_ISLAND))
- INDEX(ds,newgrid,x+1,y) |= idata << D_L_ISLAND_SHIFT_L;
- if (y > 0 && !(GRID(state,x,y-1) & G_ISLAND))
- INDEX(ds,newgrid,x,y-1) |= idata << D_L_ISLAND_SHIFT_D;
- if (y+1 < state->h && !(GRID(state,x,y+1) & G_ISLAND))
- INDEX(ds,newgrid,x,y+1) |= idata << D_L_ISLAND_SHIFT_U;
- } else {
- unsigned long hdata, vdata;
- bool selh = false, selv = false;
- /*
- * A line (non-island) square. Compute the drawing
- * data for any horizontal and vertical lines in the
- * square, and put them in this square's entry and
- * optionally those for neighbouring islands too.
- */
- if (is_drag_dst &&
- WITHIN(x,is_drag_src->x, is_drag_dst->x) &&
- WITHIN(y,is_drag_src->y, is_drag_dst->y)) {
- if (is_drag_src->x != is_drag_dst->x)
- selh = true;
- else
- selv = true;
- }
- lines_lvlh(state, ui, x, y, v, &lv, &lh);
- hdata = (v & G_NOLINEH ? DL_COUNT_CROSS :
- v & G_LINEH ? lh :
- (ui->show_hints &&
- between_island(state,x,y,1,0)) ? DL_COUNT_HINT : 0);
- vdata = (v & G_NOLINEV ? DL_COUNT_CROSS :
- v & G_LINEV ? lv :
- (ui->show_hints &&
- between_island(state,x,y,0,1)) ? DL_COUNT_HINT : 0);
- hdata |= (flash ? DL_COL_FLASH :
- v & G_WARN ? DL_COL_WARNING :
- selh ? DL_COL_SELECTED :
- DL_COL_NORMAL);
- vdata |= (flash ? DL_COL_FLASH :
- v & G_WARN ? DL_COL_WARNING :
- selv ? DL_COL_SELECTED :
- DL_COL_NORMAL);
- if (v & G_MARKH)
- hdata |= DL_LOCK;
- if (v & G_MARKV)
- vdata |= DL_LOCK;
- INDEX(ds,newgrid,x,y) |= hdata << D_L_LINE_SHIFT_H;
- INDEX(ds,newgrid,x,y) |= vdata << D_L_LINE_SHIFT_V;
- if (x > 0 && (GRID(state,x-1,y) & G_ISLAND))
- INDEX(ds,newgrid,x-1,y) |= hdata << D_I_LINE_SHIFT_R;
- if (x+1 < state->w && (GRID(state,x+1,y) & G_ISLAND))
- INDEX(ds,newgrid,x+1,y) |= hdata << D_I_LINE_SHIFT_L;
- if (y > 0 && (GRID(state,x,y-1) & G_ISLAND))
- INDEX(ds,newgrid,x,y-1) |= vdata << D_I_LINE_SHIFT_D;
- if (y+1 < state->h && (GRID(state,x,y+1) & G_ISLAND))
- INDEX(ds,newgrid,x,y+1) |= vdata << D_I_LINE_SHIFT_U;
- }
- }
- }
- /*
- * Now go through and draw any changed grid square.
- */
- for (x = 0; x < ds->w; x++) {
- for (y = 0; y < ds->h; y++) {
- unsigned long newval = INDEX(ds,newgrid,x,y);
- if (INDEX(ds,grid,x,y) != newval) {
- v = GRID(state, x, y);
- if (v & G_ISLAND) {
- is = INDEX(state, gridi, x, y);
- draw_island_tile(dr, ds, x, y, is->count, newval);
- /*
- * If this tile is right at the edge of the grid,
- * we must also draw the part of the island that
- * goes completely out of bounds. We don't bother
- * keeping separate entries in ds->newgrid for
- * these tiles; it's easier just to redraw them
- * iff we redraw their parent island tile.
- */
- if (x == 0)
- draw_edge_tile(dr, ds, x-1, y, +1, 0, newval);
- if (y == 0)
- draw_edge_tile(dr, ds, x, y-1, 0, +1, newval);
- if (x == state->w-1)
- draw_edge_tile(dr, ds, x+1, y, -1, 0, newval);
- if (y == state->h-1)
- draw_edge_tile(dr, ds, x, y+1, 0, -1, newval);
- } else {
- draw_line_tile(dr, ds, x, y, newval);
- }
- INDEX(ds,grid,x,y) = newval;
- }
- }
- }
- }
- static float game_anim_length(const game_state *oldstate,
- const game_state *newstate, int dir, game_ui *ui)
- {
- return 0.0F;
- }
- static float game_flash_length(const game_state *oldstate,
- const game_state *newstate, int dir, game_ui *ui)
- {
- if (!oldstate->completed && newstate->completed &&
- !oldstate->solved && !newstate->solved)
- return FLASH_TIME;
- return 0.0F;
- }
- static int game_status(const game_state *state)
- {
- return state->completed ? +1 : 0;
- }
- static void game_print_size(const game_params *params, const game_ui *ui,
- float *x, float *y)
- {
- int pw, ph;
- /* 10mm squares by default. */
- game_compute_size(params, 1000, ui, &pw, &ph);
- *x = pw / 100.0F;
- *y = ph / 100.0F;
- }
- static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
- int ts)
- {
- int ink = print_mono_colour(dr, 0);
- int paper = print_mono_colour(dr, 1);
- int x, y, cx, cy, i, nl;
- int loff;
- grid_type grid;
- /* Ick: fake up `ds->tilesize' for macro expansion purposes */
- game_drawstate ads, *ds = &ads;
- ads.tilesize = ts;
- /* I don't think this wants a border. */
- /* Bridges */
- loff = ts / (8 * sqrt((state->params.maxb - 1)));
- print_line_width(dr, ts / 12);
- for (x = 0; x < state->w; x++) {
- for (y = 0; y < state->h; y++) {
- cx = COORD(x); cy = COORD(y);
- grid = GRID(state,x,y);
- nl = INDEX(state,lines,x,y);
- if (grid & G_ISLAND) continue;
- if (grid & G_LINEV) {
- for (i = 0; i < nl; i++)
- draw_line(dr, cx+ts/2+(2*i-nl+1)*loff, cy,
- cx+ts/2+(2*i-nl+1)*loff, cy+ts, ink);
- }
- if (grid & G_LINEH) {
- for (i = 0; i < nl; i++)
- draw_line(dr, cx, cy+ts/2+(2*i-nl+1)*loff,
- cx+ts, cy+ts/2+(2*i-nl+1)*loff, ink);
- }
- }
- }
- /* Islands */
- for (i = 0; i < state->n_islands; i++) {
- char str[32];
- struct island *is = &state->islands[i];
- grid = GRID(state, is->x, is->y);
- cx = COORD(is->x) + ts/2;
- cy = COORD(is->y) + ts/2;
- draw_circle(dr, cx, cy, ISLAND_RADIUS, paper, ink);
- sprintf(str, "%d", is->count);
- draw_text(dr, cx, cy, FONT_VARIABLE, ISLAND_NUMSIZE(is->count),
- ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
- }
- }
- #ifdef COMBINED
- #define thegame bridges
- #endif
- const struct game thegame = {
- "Bridges", "games.bridges", "bridges",
- default_params,
- game_fetch_preset, NULL,
- decode_params,
- encode_params,
- free_params,
- dup_params,
- true, game_configure, custom_params,
- validate_params,
- new_game_desc,
- validate_desc,
- new_game,
- dup_game,
- free_game,
- true, solve_game,
- true, game_can_format_as_text_now, game_text_format,
- get_prefs, set_prefs,
- new_ui,
- free_ui,
- NULL, /* encode_ui */
- NULL, /* decode_ui */
- NULL, /* game_request_keys */
- game_changed_state,
- current_key_label,
- interpret_move,
- execute_move,
- PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
- game_colours,
- game_new_drawstate,
- game_free_drawstate,
- game_redraw,
- game_anim_length,
- game_flash_length,
- game_get_cursor_location,
- game_status,
- true, false, game_print_size, game_print,
- false, /* wants_statusbar */
- false, NULL, /* timing_state */
- REQUIRE_RBUTTON, /* flags */
- };
- /* vim: set shiftwidth=4 tabstop=8: */
|