stb/tests/grid_reachability.c

   1 #define STB_CONNECTED_COMPONENTS_IMPLEMENTATION
   2 #define STBCC_GRID_COUNT_X_LOG2  10
   3 #define STBCC_GRID_COUNT_Y_LOG2  10
   4 #include "stb_connected_components.h"
   5
   6 #ifdef GRID_TEST
   7
   8 #include <windows.h>
   9 #include <stdio.h>
  10 #include <direct.h>
  11
  12 //#define STB_DEFINE
  13 #include "stb.h"
  14
  15 //#define STB_IMAGE_IMPLEMENTATION
  16 #include "stb_image.h"
  17
  18 //#define STB_IMAGE_WRITE_IMPLEMENTATION
  19 #include "stb_image_write.h"
  20
  21 typedef struct
  22 {
  23    uint16 x,y;
  24 } point;
  25
  26 point leader[1024][1024];
  27 uint32 color[1024][1024];
  28
  29 point find(int x, int y)
  30 {
  31    point p,q;
  32    p = leader[y][x];
  33    if (p.x == x && p.y == y)
  34       return p;
  35    q = find(p.x, p.y);
  36    leader[y][x] = q;
  37    return q;
  38 }
  39
  40 void onion(int x1, int y1, int x2, int y2)
  41 {
  42    point p = find(x1,y1);
  43    point q = find(x2,y2);
  44
  45    if (p.x == q.x && p.y == q.y)
  46       return;
  47
  48    leader[p.y][p.x] = q;
  49 }
  50
  51 void reference(uint8 *map, int w, int h)
  52 {
  53    int i,j;
  54
  55    for (j=0; j < h; ++j) {
  56       for (i=0; i < w; ++i) {
  57          leader[j][i].x = i;
  58          leader[j][i].y = j;
  59       }
  60    }
  61
  62    for (j=1; j < h-1; ++j) {
  63       for (i=1; i < w-1; ++i) {
  64          if (map[j*w+i] == 255) {
  65             if (map[(j+1)*w+i] == 255) onion(i,j, i,j+1);
  66             if (map[(j)*w+i+1] == 255) onion(i,j, i+1,j);
  67          }
  68       }
  69    }
  70
  71    for (j=0; j < h; ++j) {
  72       for (i=0; i < w; ++i) {
  73          uint32 c = 0xff000000;
  74          if (leader[j][i].x == i && leader[j][i].y == j) {
  75             if (map[j*w+i] == 255)
  76                c = stb_randLCG() | 0xff404040;
  77          }
  78          color[j][i] = c;
  79       }
  80    }
  81
  82    for (j=0; j < h; ++j) {
  83       for (i=0; i < w; ++i) {
  84          if (leader[j][i].x != i || leader[j][i].y != j) {
  85             point p = find(i,j);
  86             color[j][i] = color[p.y][p.x];
  87          }
  88       }
  89    }
  90 }
  91
  92 void write_map(stbcc_grid *g, int w, int h, char *filename)
  93 {
  94    int i,j;
  95    for (j=0; j < h; ++j) {
  96       for (i=0; i < w; ++i) {
  97          unsigned int c;
  98          c = stbcc_get_unique_id(g,i,j);
  99          c = stb_rehash_improved(c)&0xffffff;
 100          if (c == STBCC_NULL_UNIQUE_ID)
 101             c = 0xff000000;
 102          else
 103             c = (~c)^0x555555;
 104          if (i % 32 == 0 || j %32 == 0) {
 105             int r = (c >> 16) & 255;
 106             int g = (c >> 8) & 255;
 107             int b = c & 255;
 108             r = (r+130)/2;
 109             g = (g+130)/2;
 110             b = (b+130)/2;
 111             c = 0xff000000 + (r<<16) + (g<<8) + b;
 112          }
 113          color[j][i] = c;
 114       }
 115    }
 116    stbi_write_png(filename, w, h, 4, color, 4*w);
 117 }
 118
 119 void test_connected(stbcc_grid *g)
 120 {
 121    int n = stbcc_query_grid_node_connection(g, 512, 90, 512, 871);
 122    //printf("%d ", n);
 123 }
 124
 125 static char *message;
 126 LARGE_INTEGER start;
 127
 128 void start_timer(char *s)
 129 {
 130    message = s;
 131    QueryPerformanceCounter(&start);
 132 }
 133
 134 void end_timer(void)
 135 {
 136    LARGE_INTEGER end, freq;
 137    double tm;
 138
 139    QueryPerformanceCounter(&end);
 140    QueryPerformanceFrequency(&freq);
 141
 142    tm = (end.QuadPart - start.QuadPart) / (double) freq.QuadPart;
 143    printf("%6.4lf ms: %s\n", tm * 1000, message);
 144 }
 145
 146 extern void quicktest(void);
 147
 148 int loc[5000][2];
 149 int main(int argc, char **argv)
 150 {
 151    stbcc_grid *g;
 152
 153    int w,h, i,j,k=0, count=0, r;
 154    uint8 *map = stbi_load("data/map_03.png", &w, &h, 0, 1);
 155
 156    assert(map);
 157    quicktest();
 158
 159    for (j=0; j < h; ++j)
 160       for (i=0; i < w; ++i)
 161          map[j*w+i] = ~map[j*w+i];
 162
 163    for (i=0; i < w; ++i)
 164       for (j=0; j < h; ++j)
 165          //map[j*w+i] = (((i+1) ^ (j+1)) >> 1) & 1 ? 255 : 0;
 166          map[j*w+i] = stb_max(abs(i-w/2),abs(j-h/2)) & 1 ? 255 : 0;
 167          //map[j*w+i] = (((i ^ j) >> 5) ^ (i ^ j)) & 1 ? 255 : 0;
 168          //map[j*w+i] = stb_rand() & 1 ? 255 : 0;
 169
 170    #if 1
 171    for (i=0; i < 100000; ++i)
 172       map[(stb_rand()%h)*w + stb_rand()%w] ^= 255;
 173    #endif
 174
 175    _mkdir("tests/output/stbcc");
 176
 177    stbi_write_png("tests/output/stbcc/reference.png", w, h, 1, map, 0);
 178
 179    //reference(map, w, h);
 180
 181    g = malloc(stbcc_grid_sizeof());
 182    printf("Size: %d\n", stbcc_grid_sizeof());
 183
 184 #if 0
 185    memset(map, 0, w*h);
 186    stbcc_init_grid(g, map, w, h);
 187    {
 188       int n;
 189       char **s = stb_stringfile("c:/x/clockwork_update.txt", &n);
 190       write_map(g, w, h, "tests/output/stbcc/base.png");
 191       for (i=1; i < n; i += 1) {
 192          int x,y,t;
 193          sscanf(s[i], "%d %d %d", &x, &y, &t);
 194          if (i == 571678)
 195             write_map(g, w, h, stb_sprintf("tests/output/stbcc/clockwork_good.png", i));
 196          stbcc_update_grid(g, x, y, t);
 197          if (i == 571678)
 198             write_map(g, w, h, stb_sprintf("tests/output/stbcc/clockwork_bad.png", i));
 199          //if (i > 571648 && i <= 571712)
 200             //write_map(g, w, h, stb_sprintf("tests/output/stbcc/clockwork_%06d.png", i));
 201       }
 202       write_map(g, w, h, stb_sprintf("tests/output/stbcc/clockwork_%06d.png", i-1));
 203    }
 204    return 0;
 205 #endif
 206
 207
 208    start_timer("init");
 209    stbcc_init_grid(g, map, w, h);
 210    end_timer();
 211    //g = stb_file("c:/x/clockwork_path.bin", 0);
 212    write_map(g, w, h, "tests/output/stbcc/base.png");
 213
 214    for (i=0; i < 5000;) {
 215       loc[i][0] = stb_rand() % w;
 216       loc[i][1] = stb_rand() % h;
 217       if (stbcc_query_grid_open(g, loc[i][0], loc[i][1]))
 218          ++i;
 219    }
 220
 221    r = 0;
 222    start_timer("reachable");
 223    for (i=0; i < 2000; ++i) {
 224       for (j=0; j < 2000; ++j) {
 225          int x1 = loc[i][0], y1 = loc[i][1];
 226          int x2 = loc[2000+j][0], y2 = loc[2000+j][1];
 227          r += stbcc_query_grid_node_connection(g, x1,y1, x2,y2);
 228       }
 229    }
 230    end_timer();
 231    printf("%d reachable\n", r);
 232
 233    printf("Cluster size: %d,%d\n", STBCC__CLUSTER_SIZE_X, STBCC__CLUSTER_SIZE_Y);
 234
 235    #if 1
 236    for (j=0; j < 10; ++j) {
 237       for (i=0; i < 5000; ++i) {
 238          loc[i][0] = stb_rand() % w;
 239          loc[i][1] = stb_rand() % h;
 240       }
 241       start_timer("updating 2500");
 242       for (i=0; i < 2500; ++i) {
 243          if (stbcc_query_grid_open(g, loc[i][0], loc[i][1]))
 244             stbcc_update_grid(g, loc[i][0], loc[i][1], 1);
 245          else
 246             stbcc_update_grid(g, loc[i][0], loc[i][1], 0);
 247       }
 248       end_timer();
 249       write_map(g, w, h, stb_sprintf("tests/output/stbcc/update_random_%d.png", j*i));
 250    }
 251    #endif
 252
 253    #if 0
 254    start_timer("removing");
 255    count = 0;
 256    for (i=0; i < 1800; ++i) {
 257       int x,y,a,b;
 258       x = stb_rand() % (w-32);
 259       y = stb_rand() % (h-32);
 260
 261       if (i & 1) {
 262          for (a=0; a < 32; ++a)
 263             for (b=0; b < 1; ++b)
 264                if (stbcc_query_grid_open(g, x+a, y+b)) {
 265                   stbcc_update_grid(g, x+a, y+b, 1);
 266                   ++count;
 267                }
 268       } else {
 269          for (a=0; a < 1; ++a)
 270             for (b=0; b < 32; ++b)
 271                if (stbcc_query_grid_open(g, x+a, y+b)) {
 272                   stbcc_update_grid(g, x+a, y+b, 1);
 273                   ++count;
 274                }
 275       }
 276
 277       //if (i % 100 == 0) write_map(g, w, h, stb_sprintf("tests/output/stbcc/open_random_%d.png", i+1));
 278    }
 279    end_timer();
 280    printf("Removed %d grid spaces\n", count);
 281    write_map(g, w, h, stb_sprintf("tests/output/stbcc/open_random_%d.png", i));
 282
 283
 284    r = 0;
 285    start_timer("reachable");
 286    for (i=0; i < 1000; ++i) {
 287       for (j=0; j < 1000; ++j) {
 288          int x1 = loc[i][0], y1 = loc[i][1];
 289          int x2 = loc[j][0], y2 = loc[j][1];
 290          r += stbcc_query_grid_node_connection(g, x1,y1, x2,y2);
 291       }
 292    }
 293    end_timer();
 294    printf("%d reachable\n", r);
 295
 296    start_timer("adding");
 297    count = 0;
 298    for (i=0; i < 1800; ++i) {
 299       int x,y,a,b;
 300       x = stb_rand() % (w-32);
 301       y = stb_rand() % (h-32);
 302
 303       if (i & 1) {
 304          for (a=0; a < 32; ++a)
 305             for (b=0; b < 1; ++b)
 306                if (!stbcc_query_grid_open(g, x+a, y+b)) {
 307                   stbcc_update_grid(g, x+a, y+b, 0);
 308                   ++count;
 309                }
 310       } else {
 311          for (a=0; a < 1; ++a)
 312             for (b=0; b < 32; ++b)
 313                if (!stbcc_query_grid_open(g, x+a, y+b)) {
 314                   stbcc_update_grid(g, x+a, y+b, 0);
 315                   ++count;
 316                }
 317       }
 318
 319       //if (i % 100 == 0) write_map(g, w, h, stb_sprintf("tests/output/stbcc/close_random_%d.png", i+1));
 320    }
 321    end_timer();
 322    write_map(g, w, h, stb_sprintf("tests/output/stbcc/close_random_%d.png", i));
 323    printf("Added %d grid spaces\n", count);
 324    #endif
 325
 326
 327    #if 0  // for map_02.png
 328    start_timer("process");
 329    for (k=0; k < 20; ++k) {
 330       for (j=0; j < h; ++j) {
 331          int any=0;
 332          for (i=0; i < w; ++i) {
 333             if (map[j*w+i] > 10 && map[j*w+i] < 250) {
 334                //start_timer(stb_sprintf("open %d,%d", i,j));
 335                stbcc_update_grid(g, i, j, 0);
 336                test_connected(g);
 337                //end_timer();
 338                any = 1;
 339             }
 340          }
 341          if (any) write_map(g, w, h, stb_sprintf("tests/output/stbcc/open_row_%04d.png", j));
 342       }
 343
 344       for (j=0; j < h; ++j) {
 345          int any=0;
 346          for (i=0; i < w; ++i) {
 347             if (map[j*w+i] > 10 && map[j*w+i] < 250) {
 348                //start_timer(stb_sprintf("close %d,%d", i,j));
 349                stbcc_update_grid(g, i, j, 1);
 350                test_connected(g);
 351                //end_timer();
 352                any = 1;
 353             }
 354          }
 355          if (any) write_map(g, w, h, stb_sprintf("tests/output/stbcc/close_row_%04d.png", j));
 356       }
 357    }
 358    end_timer();
 359    #endif
 360
 361    return 0;
 362 }
 363 #endif