work/gpstroke/find_line_indep.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <math.h>
   4 #include <string.h>
   5 #include <time.h>
   6 #include "c24lib/image/image.h"
   7 #include "c24lib/image/draw.h"
   8 #include "c24lib/image/pnm.h"
   9
  10 #include "pcb_draw.h"
  11 #include "gp.h"
  12
  13 #define DUMPDIR "/tmp/gpstroke/"
  14
  15
  16 /*
  17 #define OPTIMIZE_FROM 5000
  18 #define COOL_PERIOD 2000
  19 */
  20
  21 #define ITERATIONS 21000
  22 #define STROKE_PENALTY 1000
  23 #define MAX_TH 1
  24 #define MIN_TH 5
  25
  26 #define MAX_STROKES 64
  27 int max_strokes = 16;
  28 image_t *ref, *canvas;
  29
  30 typedef struct {
  31         int x1, y1, x2, y2, th;
  32 } stroke_t;
  33
  34 typedef struct {
  35         int len;
  36         stroke_t str[MAX_STROKES];
  37 } pcb_t;
  38
  39 #include "pcb_common.h"
  40
  41 static inline int pcb_num_strokes(pcb_t *p)
  42 {
  43         return p->len;
  44 }
  45
  46 static void pcb_dump_str(FILE *f, pcb_t *p)
  47 {
  48         int n;
  49         for(n = 0; n < p->len; n++)
  50                 fprintf(f,"stroke %d %d %d %d %d\n", p->str[n].x1, p->str[n].y1, p->str[n].x2, p->str[n].y2, p->str[n].th);
  51 }
  52
  53
  54 static inline void pcb_draw(image_t *img, pcb_t *p)
  55 {
  56         int n;
  57
  58         draw_color(pixel_black);
  59         for(n = 0; n < p->len; n++)
  60                 draw_pcb_line(img, p->str[n].x1, p->str[n].y1, p->str[n].x2, p->str[n].y2, clamp(p->str[n].th, MIN_TH, MAX_TH));
  61 }
  62
  63 static inline void rand_stroke(stroke_t *s)
  64 {
  65         s->x1 = myrand(0, ref->sx-1);
  66         s->x2 = myrand(0, ref->sx-1);
  67         s->y1 = myrand(0, ref->sy-1);
  68         s->y2 = myrand(0, ref->sy-1);
  69         s->th = myrand(1, MAX_TH);
  70 }
  71
  72 static pcb_t *load_str(char *fn)
  73 {
  74         char line[256];
  75         FILE *f = fopen(fn, "r");
  76         pcb_t *p;
  77         if (f == NULL)
  78                 return 0;
  79         p = calloc(sizeof(pcb_t), 1);
  80         while(fgets(line, sizeof(line), f) != NULL) {
  81                 char *s = line;
  82                 int x1, y1, x2, y2, th;
  83                 if (strncmp(s, "stroke", 6) == 0)
  84                         s+=6;
  85
  86                 if (sscanf(s, "%d %d %d %d %d", &x1, &y1, &x2, &y2, &th) == 5) {
  87                         stroke_t *s = &p->str[p->len];
  88                         s->x1 = x1;
  89                         s->y1 = y1;
  90                         s->x2 = x2;
  91                         s->y2 = y2;
  92                         s->th = th;
  93                         p->len++;
  94                 }
  95         }
  96         fclose(f);
  97         return p;
  98 }
  99
 100 void *pcb_create(void)
 101 {
 102         pcb_t *p = malloc(sizeof(pcb_t));
 103         int n;
 104
 105         if (default_new != NULL) {
 106                 memcpy(p, default_new, sizeof(pcb_t));
 107                 return p;
 108         }
 109
 110         p->len = myrand(1, max_strokes/2);
 111         for(n = 0; n < p->len; n++)
 112                 rand_stroke(&p->str[n]);
 113
 114         return p;
 115 }
 116
 117 static inline void pcb_mutate_add(pcb_t *p)
 118 {
 119         int loc, x, y;
 120         if (p->len >= MAX_STROKES)
 121                 return;
 122
 123         loc = myrand(0, black_len-1);
 124
 125         x = image_x(ref, ref->pixmap+black[loc]);
 126         y = image_y(ref, ref->pixmap+black[loc]);
 127
 128         p->str[p->len].x1 = x;
 129         p->str[p->len].y1 = y;
 130         p->str[p->len].x2 = x + myrand(2, 20) - 10;
 131         p->str[p->len].y2 = y + myrand(2, 20) - 10;
 132         p->str[p->len].th = myrand(3, 10);
 133         p->len++;
 134 }
 135
 136 static inline void pcb_del_stroke(pcb_t *p, int idx)
 137 {
 138         int rem;
 139         rem = p->len - idx - 1;
 140         if (rem > 0)
 141                 memmove(p->str+idx, p->str+idx+1, rem*sizeof(stroke_t));
 142         p->len--;
 143
 144 }
 145
 146 static inline void pcb_mutate_del(pcb_t *p)
 147 {
 148         if (p->len < 2)
 149                 return;
 150
 151         pcb_del_stroke(p, myrand(0, p->len-1));
 152 }
 153
 154 static inline void pcb_mutate_chg(pcb_t *p)
 155 {
 156         int idx = myrand(0, p->len-1);
 157         int fld = myrand(0, 5);
 158         int dirx = (rand() % 3) - 1;
 159         int diry = (rand() % 3) - 1;
 160         int dir = (rand() % 2) ? 1 : -1;
 161         int tmp;
 162
 163         switch(fld) {
 164                 case 0:
 165                         tune(p->str[idx].x1, 0, ref->sx, dirx);
 166                         tune(p->str[idx].y1, 0, ref->sy, diry);
 167                         break;
 168                 case 1:
 169                         tune(p->str[idx].x2, 0, ref->sx, dirx);
 170                         tune(p->str[idx].y2, 0, ref->sy, diry);
 171                         break;
 172                 case 2: tune(p->str[idx].th, MIN_TH, MAX_TH, dir); break;
 173                 case 3: rand_stroke(&p->str[idx]); break;
 174                 case 4:
 175                         tmp = p->str[idx].x1;
 176                         p->str[idx].x1 = p->str[idx].x2;
 177                         p->str[idx].x2 = tmp;
 178                         break;
 179                 case 5:
 180                         tmp = p->str[idx].y1;
 181                         p->str[idx].y1 = p->str[idx].y2;
 182                         p->str[idx].y2 = tmp;
 183                         break;
 184         }
 185 }
 186
 187 #define sqr(a) ((a) * (a))
 188
 189 #define dist2(s1, i1, s2, i2) \
 190         (sqr(s1.x ## i1 - s2.x ## i2) + sqr(s1.y ## i1 - s2.y ## i2))
 191
 192 static inline void pcb_mutate_merge(pcb_t *p)
 193 {
 194         int idx1 = myrand(0, p->len-1);
 195         int idx2 = myrand(0, p->len-1);
 196         int n, best, bestn, dst[4];
 197
 198         if (idx1 == idx2)
 199                 return;
 200
 201         /* merge the closest points */
 202         dst[0] = dist2(p->str[idx1], 1, p->str[idx2], 1);
 203         dst[1] = dist2(p->str[idx1], 1, p->str[idx2], 2);
 204         dst[2] = dist2(p->str[idx1], 2, p->str[idx2], 1);
 205         dst[3] = dist2(p->str[idx1], 2, p->str[idx2], 2);
 206
 207         best = sqr(ref->sx + ref->sy);
 208         for(n = 0; n < 4; n++) {
 209                 if (dst[n] < best) {
 210                         best = dst[n];
 211                         bestn = n;
 212                 }
 213         }
 214
 215         switch(bestn) {
 216                 case 0:
 217                         p->str[idx1].x2 = p->str[idx2].x1;
 218                         p->str[idx1].y2 = p->str[idx2].y1;
 219                         break;
 220                 case 1:
 221                         p->str[idx1].x2 = p->str[idx2].x2;
 222                         p->str[idx1].y2 = p->str[idx2].y2;
 223                         break;
 224                 case 2:
 225                         p->str[idx1].x1 = p->str[idx2].x1;
 226                         p->str[idx1].y1 = p->str[idx2].y1;
 227                         break;
 228                 case 3:
 229                         p->str[idx1].x1 = p->str[idx2].x2;
 230                         p->str[idx1].y1 = p->str[idx2].y2;
 231                         break;
 232         }
 233         pcb_del_stroke(p, idx2);
 234 }
 235
 236 void pcb_mutate(void *data)
 237 {
 238         int n=myrand(0, 100);
 239         if (n > 65)
 240                 pcb_mutate_chg(data);
 241         switch(n%3) {
 242                 case 0: pcb_mutate_add(data); break;
 243                 case 1: pcb_mutate_del(data); break;
 244                 case 2: pcb_mutate_merge(data); break;
 245         }
 246 }
 247
 248 gp_pop_t pop = {
 249         .len = 16,
 250         .weak_kill = 5,
 251         .clone_times = 2,
 252         .create = pcb_create,
 253         .score = pcb_score,
 254         .mutate = pcb_mutate,
 255         .clone = pcb_clone,
 256         .dump = pcb_dump
 257 };
 258
 259 int main(int argc, char *argv[])
 260 {
 261         int n, last_best = -1;
 262
 263         common_init(argc, argv);
 264
 265         gp_setup(&pop);
 266
 267         for(n = 0; n < ITERATIONS; n++) {
 268 #ifdef OPTIMIZE_FROM
 269                 if ((n >= OPTIMIZE_FROM) && ((n % COOL_PERIOD) == 0)) {
 270                         stroke_penalty *= 1.1;
 271                 }
 272 #endif
 273                 gp_iterate(&pop);
 274                 if (((pop.pop_cnt % 50) == 0) && (pop.indiv[0].fitness != last_best)) {
 275                         gp_dump(stdout, &pop, 1);
 276                         last_best = pop.indiv[0].fitness;
 277                 }
 278         }
 279         pnm_save(ref, DUMPDIR "ref.pnm");
 280         free(black);
 281 }