Fix problems with arrow UI with non-square grid.
[sgt/puzzles] / map.c
diff --git a/map.c b/map.c
index ee3c35b..da3c4ba 100644 (file)
--- a/map.c
+++ b/map.c
@@ -7,8 +7,6 @@
  * 
  *  - clue marking
  *  - better four-colouring algorithm?
- *  - can we make the pencil marks look nicer?
- *  - ability to drag a set of pencil marks?
  */
 
 #include <stdio.h>
@@ -102,8 +100,13 @@ static game_params *default_params(void)
 {
     game_params *ret = snew(game_params);
 
+#ifdef PORTRAIT_SCREEN
+    ret->w = 16;
+    ret->h = 18;
+#else
     ret->w = 20;
     ret->h = 15;
+#endif
     ret->n = 30;
     ret->diff = DIFF_NORMAL;
 
@@ -111,12 +114,21 @@ static game_params *default_params(void)
 }
 
 static const struct game_params map_presets[] = {
+#ifdef PORTRAIT_SCREEN
+    {16, 18, 30, DIFF_EASY},
+    {16, 18, 30, DIFF_NORMAL},
+    {16, 18, 30, DIFF_HARD},
+    {16, 18, 30, DIFF_RECURSE},
+    {25, 30, 75, DIFF_NORMAL},
+    {25, 30, 75, DIFF_HARD},
+#else
     {20, 15, 30, DIFF_EASY},
     {20, 15, 30, DIFF_NORMAL},
     {20, 15, 30, DIFF_HARD},
     {20, 15, 30, DIFF_RECURSE},
     {30, 25, 75, DIFF_NORMAL},
     {30, 25, 75, DIFF_HARD},
+#endif
 };
 
 static int game_fetch_preset(int i, char **name, game_params **params)
@@ -804,14 +816,17 @@ static void fourcolour(int *graph, int n, int ngraph, int *colouring,
 
 struct solver_scratch {
     unsigned char *possible;          /* bitmap of colours for each region */
+
     int *graph;
+    int n;
+    int ngraph;
+
     int *bfsqueue;
     int *bfscolour;
 #ifdef SOLVER_DIAGNOSTICS
     int *bfsprev;
 #endif
-    int n;
-    int ngraph;
+
     int depth;
 };
 
@@ -870,15 +885,22 @@ static int place_colour(struct solver_scratch *sc,
     int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
     int j, k;
 
-    if (!(sc->possible[index] & (1 << colour)))
+    if (!(sc->possible[index] & (1 << colour))) {
+#ifdef SOLVER_DIAGNOSTICS
+        if (verbose)
+            printf("%*scannot place %c in region %d\n", 2*sc->depth, "",
+                   colnames[colour], index);
+#endif
        return FALSE;                  /* can't do it */
+    }
 
     sc->possible[index] = 1 << colour;
     colouring[index] = colour;
 
 #ifdef SOLVER_DIAGNOSTICS
     if (verbose)
-       printf("%s %c in region %d\n", verb, colnames[colour], index);
+       printf("%*s%s %c in region %d\n", 2*sc->depth, "",
+               verb, colnames[colour], index);
 #endif
 
     /*
@@ -889,7 +911,8 @@ static int place_colour(struct solver_scratch *sc,
        k = graph[j] - index*n;
 #ifdef SOLVER_DIAGNOSTICS
         if (verbose && (sc->possible[k] & (1 << colour)))
-            printf("  ruling out %c in region %d\n", colnames[colour], k);
+            printf("%*s  ruling out %c in region %d\n", 2*sc->depth, "",
+                   colnames[colour], k);
 #endif
        sc->possible[k] &= ~(1 << colour);
     }
@@ -925,24 +948,32 @@ static int map_solver(struct solver_scratch *sc,
 {
     int i;
 
-    /*
-     * Initialise scratch space.
-     */
-    for (i = 0; i < n; i++)
-       sc->possible[i] = (1 << FOUR) - 1;
+    if (sc->depth == 0) {
+        /*
+         * Initialise scratch space.
+         */
+        for (i = 0; i < n; i++)
+            sc->possible[i] = (1 << FOUR) - 1;
 
-    /*
-     * Place clues.
-     */
-    for (i = 0; i < n; i++)
-       if (colouring[i] >= 0) {
-           if (!place_colour(sc, colouring, i, colouring[i]
+        /*
+         * Place clues.
+         */
+        for (i = 0; i < n; i++)
+            if (colouring[i] >= 0) {
+                if (!place_colour(sc, colouring, i, colouring[i]
 #ifdef SOLVER_DIAGNOSTICS
-                              , "initial clue:"
+                                  , "initial clue:"
 #endif
-                              ))
-               return 0;              /* the clues aren't even consistent! */
-       }
+                                  )) {
+#ifdef SOLVER_DIAGNOSTICS
+                    if (verbose)
+                        printf("%*sinitial clue set is inconsistent\n",
+                               2*sc->depth, "");
+#endif
+                    return 0;         /* the clues aren't even consistent! */
+                }
+            }
+    }
 
     /*
      * Now repeatedly loop until we find nothing further to do.
@@ -960,21 +991,35 @@ static int map_solver(struct solver_scratch *sc,
        for (i = 0; i < n; i++) if (colouring[i] < 0) {
            int p = sc->possible[i];
 
-           if (p == 0)
+           if (p == 0) {
+#ifdef SOLVER_DIAGNOSTICS
+                if (verbose)
+                    printf("%*sregion %d has no possible colours left\n",
+                           2*sc->depth, "", i);
+#endif
                return 0;              /* puzzle is inconsistent */
+            }
 
            if ((p & (p-1)) == 0) {    /* p is a power of two */
-               int c;
+               int c, ret;
                for (c = 0; c < FOUR; c++)
                    if (p == (1 << c))
                        break;
                assert(c < FOUR);
-               if (!place_colour(sc, colouring, i, c
+               ret = place_colour(sc, colouring, i, c
 #ifdef SOLVER_DIAGNOSTICS
-                                  , "placing"
+                                   , "placing"
 #endif
-                                  ))
-                   return 0;          /* found puzzle to be inconsistent */
+                                   );
+                /*
+                 * place_colour() can only fail if colour c was not
+                 * even a _possibility_ for region i, and we're
+                 * pretty sure it was because we checked before
+                 * calling place_colour(). So we can safely assert
+                 * here rather than having to return a nice
+                 * friendly error code.
+                 */
+                assert(ret);
                done_something = TRUE;
            }
        }
@@ -1041,11 +1086,12 @@ static int map_solver(struct solver_scratch *sc,
                     if (verbose) {
                         char buf[80];
                         if (!started)
-                            printf("adjacent regions %d,%d share colours %s\n",
-                                   j1, j2, colourset(buf, v));
+                            printf("%*sadjacent regions %d,%d share colours"
+                                   " %s\n", 2*sc->depth, "", j1, j2,
+                                   colourset(buf, v));
                         started = TRUE;
-                        printf("  ruling out %s in region %d\n",
-                               colourset(buf, sc->possible[k] & v), k);
+                        printf("%*s  ruling out %s in region %d\n",2*sc->depth,
+                               "", colourset(buf, sc->possible[k] & v), k);
                     }
 #endif
                     sc->possible[k] &= ~v;
@@ -1176,13 +1222,15 @@ static int map_solver(struct solver_scratch *sc,
                                     char buf[80], *sep = "";
                                     int r;
 
-                                    printf("forcing chain, colour %s, ",
+                                    printf("%*sforcing chain, colour %s, ",
+                                           2*sc->depth, "",
                                            colourset(buf, origc));
                                     for (r = j; r != -1; r = sc->bfsprev[r]) {
                                         printf("%s%d", sep, r);
                                         sep = "-";
                                     }
-                                    printf("\n  ruling out %s in region %d\n",
+                                    printf("\n%*s  ruling out %s in region"
+                                           " %d\n", 2*sc->depth, "",
                                            colourset(buf, origc), k);
                                 }
 #endif
@@ -1206,14 +1254,25 @@ static int map_solver(struct solver_scratch *sc,
     for (i = 0; i < n; i++)
        if (colouring[i] < 0)
             break;
-    if (i == n)
+    if (i == n) {
+#ifdef SOLVER_DIAGNOSTICS
+        if (verbose)
+            printf("%*sone solution found\n", 2*sc->depth, "");
+#endif
         return 1;                      /* success! */
+    }
 
     /*
      * If recursion is not permissible, we now give up.
      */
-    if (difficulty < DIFF_RECURSE)
+    if (difficulty < DIFF_RECURSE) {
+#ifdef SOLVER_DIAGNOSTICS
+        if (verbose)
+            printf("%*sunable to proceed further without recursion\n",
+                   2*sc->depth, "");
+#endif
         return 2;                      /* unable to complete */
+    }
 
     /*
      * Now we've got to do something recursive. So first hunt for a
@@ -1247,6 +1306,11 @@ static int map_solver(struct solver_scratch *sc,
 
         assert(best >= 0);             /* or we'd be solved already */
 
+#ifdef SOLVER_DIAGNOSTICS
+        if (verbose)
+            printf("%*srecursing on region %d\n", 2*sc->depth, "", best);
+#endif
+
         /*
          * Now iterate over the possible colours for this region.
          */
@@ -1262,11 +1326,27 @@ static int map_solver(struct solver_scratch *sc,
             if (!(sc->possible[best] & (1 << i)))
                 continue;
 
+            memcpy(rsc->possible, sc->possible, n);
             memcpy(subcolouring, origcolouring, n * sizeof(int));
-            subcolouring[best] = i;
+
+            place_colour(rsc, subcolouring, best, i
+#ifdef SOLVER_DIAGNOSTICS
+                         , "trying"
+#endif
+                         );
+
             subret = map_solver(rsc, graph, n, ngraph,
                                 subcolouring, difficulty);
 
+#ifdef SOLVER_DIAGNOSTICS
+            if (verbose) {
+                printf("%*sretracting %c in region %d; found %s\n",
+                       2*sc->depth, "", colnames[i], best,
+                       subret == 0 ? "no solutions" :
+                       subret == 1 ? "one solution" : "multiple solutions");
+            }
+#endif
+
             /*
              * If this possibility turned up more than one valid
              * solution, or if it turned up one and we already had
@@ -1296,6 +1376,14 @@ static int map_solver(struct solver_scratch *sc,
         sfree(subcolouring);
         free_scratch(rsc);
 
+#ifdef SOLVER_DIAGNOSTICS
+        if (verbose && sc->depth == 0) {
+            printf("%*s%s found\n",
+                   2*sc->depth, "",
+                   ret == 0 ? "no solutions" :
+                   ret == 1 ? "one solution" : "multiple solutions");
+        }
+#endif
         return ret;
     }
 }
@@ -1621,8 +1709,7 @@ static char *parse_edge_list(game_params *params, char **desc, int *map)
     int i, k, pos, state;
     char *p = *desc;
 
-    for (i = 0; i < wh; i++)
-       map[wh+i] = i;
+    dsf_init(map+wh, wh);
 
     pos = -1;
     state = 0;
@@ -1794,7 +1881,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc)
      * outlines by the judicious use of diagonally divided squares.
      */
     {
-        random_state *rs = random_init(desc, strlen(desc));
+        random_state *rs = random_new(desc, strlen(desc));
         int *squares = snewn(wh, int);
         int done_something;
 
@@ -2095,6 +2182,7 @@ static void free_game(game_state *state)
        sfree(state->map->regiony);
        sfree(state->map);
     }
+    sfree(state->pencil);
     sfree(state->colouring);
     sfree(state);
 }
@@ -2165,7 +2253,16 @@ static char *game_text_format(game_state *state)
 }
 
 struct game_ui {
-    int drag_colour;                   /* -1 means no drag active */
+    /*
+     * drag_colour:
+     * 
+     *  - -2 means no drag currently active.
+     *  - >=0 means we're dragging a solid colour.
+     *         - -1 means we're dragging a blank space, and drag_pencil
+     *           might or might not add some pencil-mark stipples to that.
+     */
+    int drag_colour;
+    int drag_pencil;
     int dragx, dragy;
     int show_numbers;
 };
@@ -2243,7 +2340,7 @@ static int region_from_coords(game_state *state, game_drawstate *ds,
 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
                            int x, int y, int button)
 {
-    char buf[80];
+    char *bufp, buf[256];
 
     /*
      * Enable or disable numeric labels on regions.
@@ -2256,10 +2353,15 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
        int r = region_from_coords(state, ds, x, y);
 
-        if (r >= 0)
+        if (r >= 0) {
             ui->drag_colour = state->colouring[r];
-        else
+           ui->drag_pencil = state->pencil[r];
+           if (ui->drag_colour >= 0)
+               ui->drag_pencil = 0;  /* should be already, but double-check */
+       } else {
             ui->drag_colour = -1;
+           ui->drag_pencil = 0;
+       }
         ui->dragx = x;
         ui->dragy = y;
         return "";
@@ -2276,6 +2378,8 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
         ui->drag_colour > -2) {
        int r = region_from_coords(state, ds, x, y);
         int c = ui->drag_colour;
+       int p = ui->drag_pencil;
+       int oldp;
 
         /*
          * Cancel the drag, whatever happens.
@@ -2289,15 +2393,37 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
        if (state->map->immutable[r])
            return "";                 /* can't change this region */
 
-        if (state->colouring[r] == c)
+        if (state->colouring[r] == c && state->pencil[r] == p)
             return "";                 /* don't _need_ to change this region */
 
-       if (button == RIGHT_RELEASE && state->colouring[r] >= 0)
-           return "";                 /* can't pencil on a coloured region */
+       if (button == RIGHT_RELEASE) {
+           if (state->colouring[r] >= 0) {
+               /* Can't pencil on a coloured region */
+               return "";
+           } else if (c >= 0) {
+               /* Right-dragging from colour to blank toggles one pencil */
+               p = state->pencil[r] ^ (1 << c);
+               c = -1;
+           }
+           /* Otherwise, right-dragging from blank to blank is equivalent
+            * to left-dragging. */
+       }
+
+       bufp = buf;
+       oldp = state->pencil[r];
+       if (c != state->colouring[r]) {
+           bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
+           if (c >= 0)
+               oldp = 0;
+       }
+       if (p != oldp) {
+           int i;
+           for (i = 0; i < FOUR; i++)
+               if ((oldp ^ p) & (1 << i))
+                   bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r);
+       }
 
-       sprintf(buf, "%s%c:%d", (button == RIGHT_RELEASE ? "p" : ""),
-                (int)(c < 0 ? 'C' : '0' + c), r);
-       return dupstr(buf);
+       return dupstr(buf+1);          /* ignore first semicolon */
     }
 
     return NULL;
@@ -2400,22 +2526,29 @@ static void game_set_size(drawing *dr, game_drawstate *ds,
 {
     ds->tilesize = tilesize;
 
-    if (ds->bl)
-        blitter_free(dr, ds->bl);
+    assert(!ds->bl);                   /* set_size is never called twice */
     ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
 }
 
 const float map_colours[FOUR][3] = {
+#ifdef VIVID_COLOURS
+    /* Use more vivid colours (e.g. on the Pocket PC) */
+    {0.75F, 0.25F, 0.25F},
+    {0.3F,  0.7F,  0.3F},
+    {0.3F,  0.3F,  0.7F},
+    {0.85F, 0.85F, 0.1F},
+#else
     {0.7F, 0.5F, 0.4F},
     {0.8F, 0.7F, 0.4F},
     {0.5F, 0.6F, 0.4F},
     {0.55F, 0.45F, 0.35F},
+#endif
 };
 const int map_hatching[FOUR] = {
     HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
 };
 
-static float *game_colours(frontend *fe, game_state *state, int *ncolours)
+static float *game_colours(frontend *fe, int *ncolours)
 {
     float *ret = snewn(3 * NCOLOURS, float);
 
@@ -2502,11 +2635,11 @@ static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
 
 static void draw_square(drawing *dr, game_drawstate *ds,
                        game_params *params, struct map *map,
-                       int x, int y, int v)
+                       int x, int y, unsigned long v)
 {
     int w = params->w, h = params->h, wh = w*h;
-    int tv, bv, xo, yo, errs, pencil, i, j, oldj;
-    int show_numbers;
+    int tv, bv, xo, yo, i, j, oldj;
+    unsigned long errs, pencil, show_numbers;
 
     errs = v & ERR_MASK;
     v &= ~ERR_MASK;
@@ -2559,7 +2692,9 @@ static void draw_square(drawing *dr, game_drawstate *ds,
                 xo < 2 ? LE : RE);
            ee = map->map[e * wh + y*w+x];
 
-           c = (yo & 1) * 2 + (xo & 1);
+           if (xo != (yo * 2 + 1) % 5)
+               continue;
+           c = yo;
 
            if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
                continue;
@@ -2571,9 +2706,9 @@ static void draw_square(drawing *dr, game_drawstate *ds,
                (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
                continue;              /* avoid BL-TR diagonal line */
 
-           draw_rect(dr, COORD(x) + (5*xo+1)*TILESIZE/20,
-                     COORD(y) + (5*yo+1)*TILESIZE/20,
-                     4*TILESIZE/20, 4*TILESIZE/20, COL_0 + c);
+           draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
+                       COORD(y) + (yo+1)*TILESIZE/5,
+                       TILESIZE/7, COL_0 + c, COL_0 + c);
        }
 
     /*
@@ -2675,7 +2810,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
        for (x = 0; x < w; x++) {
            int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
            int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
-            int v;
+            unsigned long v;
 
            if (tv < 0)
                tv = FOUR;
@@ -2758,7 +2893,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
      */
     for (y = 0; y < h; y++)
        for (x = 0; x < w; x++) {
-           int v = ds->todraw[y*w+x];
+           unsigned long v = ds->todraw[y*w+x];
            if (ds->drawn[y*w+x] != v) {
                draw_square(dr, ds, &state->p, state->map, x, y, v);
                ds->drawn[y*w+x] = v;
@@ -2775,6 +2910,11 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
         draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
                     (ui->drag_colour < 0 ? COL_BACKGROUND :
                      COL_0 + ui->drag_colour), COL_GRID);
+       for (i = 0; i < FOUR; i++)
+           if (ui->drag_pencil & (1 << i))
+               draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10,
+                           ui->dragy + (i*2-3) * TILESIZE/10,
+                           TILESIZE/8, COL_0 + i, COL_0 + i);
         draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
         ds->drag_visible = TRUE;
     }
@@ -2804,11 +2944,6 @@ static float game_flash_length(game_state *oldstate, game_state *newstate,
        return 0.0F;
 }
 
-static int game_wants_statusbar(void)
-{
-    return FALSE;
-}
-
 static int game_timing_state(game_state *state, game_ui *ui)
 {
     return TRUE;
@@ -2837,6 +2972,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize)
 
     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
     struct { int tilesize; } ads, *ds = &ads;
+    /* We can't call game_set_size() here because we don't want a blitter */
     ads.tilesize = tilesize;
 
     ink = print_mono_colour(dr, 0);
@@ -2970,7 +3106,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize)
 #endif
 
 const struct game thegame = {
-    "Map", "games.map",
+    "Map", "games.map", "map",
     default_params,
     game_fetch_preset,
     decode_params,
@@ -3001,52 +3137,13 @@ const struct game thegame = {
     game_anim_length,
     game_flash_length,
     TRUE, TRUE, game_print_size, game_print,
-    game_wants_statusbar,
+    FALSE,                            /* wants_statusbar */
     FALSE, game_timing_state,
-    0,                                /* mouse_priorities */
+    0,                                /* flags */
 };
 
 #ifdef STANDALONE_SOLVER
 
-#include <stdarg.h>
-
-void frontend_default_colour(frontend *fe, float *output) {}
-void draw_text(drawing *dr, int x, int y, int fonttype, int fontsize,
-               int align, int colour, char *text) {}
-void draw_rect(drawing *dr, int x, int y, int w, int h, int colour) {}
-void draw_line(drawing *dr, int x1, int y1, int x2, int y2, int colour) {}
-void draw_polygon(drawing *dr, int *coords, int npoints,
-                  int fillcolour, int outlinecolour) {}
-void draw_circle(drawing *dr, int cx, int cy, int radius,
-                 int fillcolour, int outlinecolour) {}
-void clip(drawing *dr, int x, int y, int w, int h) {}
-void unclip(drawing *dr) {}
-void start_draw(drawing *dr) {}
-void draw_update(drawing *dr, int x, int y, int w, int h) {}
-void end_draw(drawing *dr) {}
-blitter *blitter_new(drawing *dr, int w, int h) {return NULL;}
-void blitter_free(drawing *dr, blitter *bl) {}
-void blitter_save(drawing *dr, blitter *bl, int x, int y) {}
-void blitter_load(drawing *dr, blitter *bl, int x, int y) {}
-int print_mono_colour(drawing *dr, int grey) { return 0; }
-int print_rgb_colour(drawing *dr, int hatch, float r, float g, float b)
-{ return 0; }
-void print_line_width(drawing *dr, int width) {}
-
-void fatal(char *fmt, ...)
-{
-    va_list ap;
-
-    fprintf(stderr, "fatal error: ");
-
-    va_start(ap, fmt);
-    vfprintf(stderr, fmt, ap);
-    va_end(ap);
-
-    fprintf(stderr, "\n");
-    exit(1);
-}
-
 int main(int argc, char **argv)
 {
     game_params *p;