planarity/graph_generate_mesh1.c

   1 /*
   2  *
   3  *  gPlanarity:
   4  *     The geeky little puzzle game with a big noodly crunch!
   5  *
   6  *     gPlanarity copyright (C) 2005 Monty <monty@xiph.org>
   7  *     Original Flash game by John Tantalo <john.tantalo@case.edu>
   8  *     Original game concept by Mary Radcliffe
   9  *
  10  *  gPlanarity is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2, or (at your option)
  13  *  any later version.
  14  *
  15  *  gPlanarity is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with Postfish; see the file COPYING.  If not, write to the
  22  *  Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  23  *
  24  *
  25  */
  26
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <math.h>
  30
  31 #include "graph.h"
  32 #include "random.h"
  33 #include "gameboard.h"
  34 #include "graph_generate.h"
  35 #include "graph_arrange.h"
  36
  37 typedef struct {
  38   vertex **v;
  39   edge_list *embed_list;
  40   int width;
  41   int height;
  42 } mesh;
  43
  44 typedef struct {
  45   int vnum[8];
  46   vertex *center;
  47   mesh   *m;
  48 } neighbors_grid;
  49
  50 typedef struct {
  51   int vnum[8];
  52   int num;
  53 } neighbors_list;
  54
  55 /* The 'embed_list' is a set of edges that don't obey or neighboring
  56    intersection calculation mode and are thus tracked
  57    seperately/explicitly.  They're added to the main graph after the
  58    rest of the graph is generated. */
  59
  60 /* add edge to the embed_list */
  61 static void embedlist_add_edge(mesh *m, vertex *A, vertex *B){
  62   edge *e = new_edge(A,B);
  63   m->embed_list = add_edge_to_list(m->embed_list,e);
  64 }
  65
  66 /* move embed_list edges into the real graph */
  67 static void embedlist_add_to_mesh(graph *g, mesh *m){
  68   edge_list *el = m->embed_list;
  69
  70   /* move the edges out of the embed_list and add them to the main graph */
  71   while(el){
  72     edge *e = el->edge;
  73     el->edge = 0;
  74
  75     insert_edge(g,e);
  76     el=el->next;
  77   }
  78
  79   release_edge_list(m->embed_list);
  80   m->embed_list=0; /* be pedantic */
  81
  82 }
  83
  84 static int embedlist_intersects(mesh *m, vertex *A, vertex *B){
  85   edge_list *el = m->embed_list;
  86   double dummy_x,dummy_y;
  87
  88   while(el){
  89     edge *e = el->edge;
  90
  91     if(intersectsV(A,B,e->A,e->B,&dummy_x,&dummy_y))
  92       return 1;
  93
  94     el=el->next;
  95   }
  96   return 0;
  97
  98 }
  99
 100 static void embedlist_filter_intersections(neighbors_grid *ng){
 101   int i;
 102   vertex *A = ng->center;
 103
 104   for(i=0;i<8;i++){
 105     if(ng->vnum[i] != -1){
 106       vertex *B = ng->m->v[ng->vnum[i]];
 107
 108       if(embedlist_intersects(ng->m,A,B))
 109         ng->vnum[i]=-1;
 110     }
 111   }
 112 }
 113
 114 static int embedlist_contains_vertex(mesh *m,vertex *v){
 115   edge_list *el = m->embed_list;
 116
 117   while(el){
 118     edge *e = el->edge;
 119
 120     if(e->A == v) return 1;
 121     if(e->B == v) return 1;
 122
 123     el=el->next;
 124   }
 125   return 0;
 126 }
 127
 128 static int embedlist_vertex_poisoned(mesh *m, vertex *v){
 129   return v->selected;
 130 }
 131
 132 static void poison_vertex(mesh *m, vertex *v){
 133   v->selected=1;
 134 }
 135
 136 /* neighboring intersection model */
 137
 138 static void populate_neighbors(int vnum, mesh *m,
 139                                neighbors_grid *ng){
 140   int width = m->width;
 141   int y = vnum/width;
 142   int x = vnum - (y*width);
 143   int i;
 144
 145   for(i=0;i<8;i++)ng->vnum[i]=-1;
 146
 147
 148   ng->center = m->v[vnum];
 149   ng->m = m;
 150
 151   if(y-1 >= 0){
 152     if(x-1 >= 0)        ng->vnum[0]= (y-1)*width+(x-1);
 153                         ng->vnum[1]= (y-1)*width+x;
 154     if(x+1 <  m->width) ng->vnum[2]= (y-1)*width+(x+1);
 155   }
 156
 157   if(x-1   >= 0)        ng->vnum[3]= y*width+(x-1);
 158   if(x+1   <  m->width) ng->vnum[4]= y*width+(x+1);
 159
 160   if(y+1   < m->height){
 161     if(x-1 >= 0)        ng->vnum[5]= (y+1)*width+(x-1);
 162                         ng->vnum[6]= (y+1)*width+x;
 163     if(x+1 <  m->width) ng->vnum[7]= (y+1)*width+(x+1);
 164   }
 165
 166 }
 167
 168 // eliminate from neighbor structs the verticies that already have at
 169 // least one edge
 170 static void filter_spanned_neighbors(neighbors_grid *ng,
 171                                      neighbors_list *nl){
 172   int i;
 173   int count=0;
 174   for(i=0;i<8;i++)
 175     if(ng->vnum[i]==-1 || ng->m->v[ng->vnum[i]]->edges){
 176       ng->vnum[i]=-1;
 177     }else{
 178       nl->vnum[count++]=ng->vnum[i];
 179     }
 180   nl->num=count;
 181
 182 }
 183
 184 // eliminate from neighbor struct any verticies to which we can't make
 185 // an edge without crossing another edge.  Only 0,2,5,7 possible.
 186 static void filter_intersections(neighbors_grid *ng){
 187   int i;
 188   for(i=0;i<8;i++){
 189     switch(i){
 190     case 0:
 191       if(ng->vnum[1] != -1 &&
 192          ng->vnum[3] != -1 &&
 193          exists_edge(ng->m->v[ng->vnum[1]],
 194                      ng->m->v[ng->vnum[3]]))
 195         ng->vnum[i]=-1;
 196       break;
 197
 198     case 2:
 199       if(ng->vnum[1] != -1 &&
 200          ng->vnum[4] != -1 &&
 201          exists_edge(ng->m->v[ng->vnum[1]],
 202                      ng->m->v[ng->vnum[4]]))
 203         ng->vnum[i]=-1;
 204       break;
 205
 206     case 5:
 207       if(ng->vnum[3] != -1 &&
 208          ng->vnum[6] != -1 &&
 209          exists_edge(ng->m->v[ng->vnum[3]],
 210                      ng->m->v[ng->vnum[6]]))
 211         ng->vnum[i]=-1;
 212       break;
 213
 214     case 7:
 215       if(ng->vnum[4] != -1 &&
 216          ng->vnum[6] != -1 &&
 217          exists_edge(ng->m->v[ng->vnum[4]],
 218                      ng->m->v[ng->vnum[6]]))
 219         ng->vnum[i]=-1;
 220       break;
 221     }
 222   }
 223   embedlist_filter_intersections(ng);
 224 }
 225
 226 /* eliminate verticies we've already connected to */
 227 static void filter_edges(neighbors_grid *ng,
 228                          neighbors_list *nl){
 229
 230   vertex *v=ng->center;
 231   int count=0,i;
 232   for(i=0;i<8;i++){
 233     if(ng->vnum[i]!=-1){
 234       if(!exists_edge(v,ng->m->v[ng->vnum[i]]))
 235         nl->vnum[count++]=ng->vnum[i];
 236       else
 237         ng->vnum[i]=-1;
 238     }
 239   }
 240   nl->num=count;
 241 }
 242
 243 static void random_populate(graph *g, int current, mesh *m, int min_connect, int prob_128){
 244   int num_edges=0,i;
 245   neighbors_grid ng;
 246   neighbors_list nl;
 247   populate_neighbors(current, m, &ng);
 248   filter_intersections(&ng);
 249   filter_edges(&ng,&nl);
 250
 251   {
 252     edge_list *el=m->v[current]->edges;
 253     while(el){
 254       num_edges++;
 255       el=el->next;
 256     }
 257   }
 258
 259   while(num_edges<min_connect && nl.num){
 260     int choice = random_number() % nl.num;
 261     add_edge(g,m->v[current], m->v[nl.vnum[choice]]);
 262     num_edges++;
 263     filter_intersections(&ng);
 264     filter_edges(&ng,&nl);
 265   }
 266
 267   for(i=0;i<nl.num;i++)
 268     if(random_yes(prob_128)){
 269       num_edges++;
 270       add_edge(g,m->v[current], m->v[nl.vnum[i]]);
 271     }
 272 }
 273
 274 static void span_depth_first(graph *g,int current, mesh *m){
 275   neighbors_grid ng;
 276   neighbors_list nl;
 277
 278   while(1){
 279     populate_neighbors(current, m, &ng);
 280     // don't reverse the order of the next two
 281     filter_intersections(&ng);
 282     filter_spanned_neighbors(&ng,&nl);
 283     if(nl.num == 0) break;
 284
 285     {
 286       int choice = random_number() % nl.num;
 287       add_edge(g,m->v[current], m->v[nl.vnum[choice]]);
 288
 289       span_depth_first(g,nl.vnum[choice], m);
 290     }
 291   }
 292 }
 293
 294 /* nastiness adds long edges along the outer perimeter to make it
 295    harder to rely on verticies always being near each other; mesh 2
 296    takes this further, but we can add some of the same flavor to
 297    mesh1. */
 298
 299 static void nasty_horizontal(graph *g, mesh *m, int A, int B, int limit){
 300   if(limit == 0) return;
 301   if(A+2 > B)return; /* adjacent is too close */
 302
 303   add_edge(g,m->v[A],m->v[B]);
 304
 305   A++;
 306   B--;
 307   nasty_horizontal(g,m,A,B,limit-1);
 308 }
 309
 310 static void nasty_vertical(graph *g, mesh *m, int A, int B, int limit){
 311   if(limit == 0) return;
 312   if(A+(m->width*2) > B)return; /* adjacent is too close */
 313
 314   add_edge(g,m->v[A],m->v[B]);
 315
 316   A+=m->width;
 317   B-=m->width;
 318   nasty_vertical(g,m,A,B,limit-1);
 319 }
 320
 321 /* Don't use this along with k5 embedding; the assumptions the
 322    nastiness algorithm makes about solvable conditions won't always
 323    coexist with the assumptions the k5 embedding makes about solvable
 324    conditions. */
 325 static void mesh_nastiness(graph *g, mesh *m, int limit){
 326
 327   nasty_horizontal(g,m,0,m->width-1, limit);
 328   nasty_horizontal(g,m,(m->height-1)*m->width,m->width*m->height-1, limit);
 329
 330   nasty_vertical(g,m,0,(m->height-1)*m->width,limit);
 331   nasty_vertical(g,m,m->width-1,m->width*m->height-1, limit);
 332 }
 333
 334 /* Embed one k5 in the solved graph */
 335 /* Don't use this along with 'nastiness'; the assumptions the
 336    nastiness algorithm makes about solvable conditions won't always
 337    coexist with the assumptions that non-planar embedding makes about
 338    solvable conditions. */
 339
 340 static void mesh_embed_k5(graph *g, mesh *m,int x, int y){
 341
 342   /* Add the k5s up front in their own special edge list; This list
 343      will also be checked explicitly by the various neighboring
 344      algorithms as the k5's edges don't all conceptually work within
 345      the implicit neighboring algorithm we're using.  Also, by using a
 346      special edge list and not adding the k5 edges to the vertex edge
 347      lists up front, we can still use the unmodified initial spanning
 348      walk algorithm. */
 349
 350   int w = m->width;
 351
 352   vertex *A = m->v[y*w+x+1];
 353   vertex *B = m->v[(y+1)*w+x+1];
 354   vertex *C = m->v[(y+1)*w+x+2];
 355   vertex *D = m->v[(y+1)*w+x+3];
 356   vertex *E = m->v[(y+2)*w+x];
 357
 358   // poisoned verticies are already inside another kernel (the regular
 359   // mesh is deflectable and thus not really regular)
 360   if(embedlist_vertex_poisoned(m,A))return;
 361   if(embedlist_vertex_poisoned(m,B))return;
 362   if(embedlist_vertex_poisoned(m,C))return;
 363   if(embedlist_vertex_poisoned(m,D))return;
 364   if(embedlist_vertex_poisoned(m,E))return;
 365
 366   // the way k5 works we don't need to poison the internal verticies
 367
 368   embedlist_add_edge(m, A,B);
 369   embedlist_add_edge(m, A,C);
 370   embedlist_add_edge(m, A,D);
 371   embedlist_add_edge(m, A,E);
 372   embedlist_add_edge(m, B,C);
 373   embedlist_add_edge(m, B,D);
 374   embedlist_add_edge(m, B,E);
 375   embedlist_add_edge(m, C,D);
 376   embedlist_add_edge(m, C,E);
 377   embedlist_add_edge(m, D,E);
 378   g->objective++;
 379 }
 380
 381 /* Embed one k3,3 in the solved graph */
 382 /* Don't use this along with 'nastiness'; the assumptions the
 383    nastiness algorithm makes about solvable conditions won't always
 384    coexist with the assumptions that k5 embedding makes about solvable
 385    conditions. */
 386 static void mesh_embed_k33(graph *g, mesh *m, int x, int y){
 387
 388   /* same disclaimers as k5 */
 389   /* the k3,3 embedding works with the standard walk algorithm only
 390      because an edge with an endpoint exactly on another edge is
 391      considered an intersection. */
 392   /* the way it is added, the walk/population can add additional edges
 393      inside the embedded kernel; this is fine, the population will be
 394      certain not to introduce intersections. */
 395
 396   int w = m->width;
 397
 398   vertex *A = m->v[y*w+x];
 399   vertex *B = m->v[y*w+x+1];
 400   vertex *C = m->v[y*w+x+2];
 401   vertex *D = m->v[(y+1)*w+x];
 402   vertex *E = m->v[(y+1)*w+x+1];
 403   vertex *F = m->v[(y+1)*w+x+2];
 404
 405   // poisoned verticies are already inside another kernel (the regular
 406   // mesh is deflectable and thus not really regular)
 407   if(embedlist_vertex_poisoned(m,A))return;
 408   if(embedlist_vertex_poisoned(m,B))return;
 409   if(embedlist_vertex_poisoned(m,C))return;
 410   if(embedlist_vertex_poisoned(m,D))return;
 411   if(embedlist_vertex_poisoned(m,E))return;
 412   if(embedlist_vertex_poisoned(m,F))return;
 413
 414   // check that verticies we want to poison ourselves are not already in use
 415   if(embedlist_contains_vertex(m,B))return;
 416   if(embedlist_contains_vertex(m,E))return;
 417   /* B and E are internal according to x/y, but according to the
 418      position in the mesh, they're on the outside.  Poison them so
 419      that they're explicitly marked inside. */
 420   poison_vertex(m,B);
 421   poison_vertex(m,E);
 422
 423   /* need to mode two of the intersections to avoid  unwanted
 424      intersections (not spurious; they are in fact intersections until
 425      moved) */
 426
 427   B->y+=2;
 428   E->y-=2;
 429
 430   embedlist_add_edge(m, A,C);
 431   embedlist_add_edge(m, A,D);
 432   embedlist_add_edge(m, A,E);
 433   embedlist_add_edge(m, B,C);
 434   embedlist_add_edge(m, B,D);
 435   embedlist_add_edge(m, B,E);
 436   embedlist_add_edge(m, C,F);
 437   embedlist_add_edge(m, D,F);
 438   embedlist_add_edge(m, E,F);
 439   g->objective++;
 440
 441 }
 442
 443 /* Embed one non-miminal k3,3 in the solved graph */
 444 /* Don't use this along with 'nastiness'; the assumptions the
 445    nastiness algorithm makes about solvable conditions won't always
 446    coexist with the assumptions that k5 embedding makes about solvable
 447    conditions. */
 448 static void mesh_embed_bigk33(graph *g, mesh *m, int x, int y){
 449
 450   /* as above */
 451
 452   int w = m->width;
 453
 454   vertex *A = m->v[(y+2)*w+x];
 455   vertex *B = m->v[(y+1)*w+x+2];
 456   vertex *C = m->v[y*w+x+4];
 457   vertex *D = m->v[(y+4)*w+x+1];
 458   vertex *E = m->v[(y+3)*w+x+3];
 459   vertex *F = m->v[(y+2)*w+x+5];
 460
 461   // poisoned verticies are already inside another kernel (the regular
 462   // mesh is deflectable and thus not really regular)
 463   if(embedlist_vertex_poisoned(m,A))return;
 464   if(embedlist_vertex_poisoned(m,B))return;
 465   if(embedlist_vertex_poisoned(m,C))return;
 466   if(embedlist_vertex_poisoned(m,D))return;
 467   if(embedlist_vertex_poisoned(m,E))return;
 468   if(embedlist_vertex_poisoned(m,F))return;
 469
 470   // check that verticies we want to poison ourselves are not already in use
 471   if(embedlist_contains_vertex(m,B))return;
 472   if(embedlist_contains_vertex(m,E))return;
 473   /* B and E are internal according to x/y, but according to the
 474      position in the mesh, they're on the outside.  Poison them so
 475      that they're explicitly marked inside. */
 476   poison_vertex(m,B);
 477   poison_vertex(m,E);
 478
 479   /* need to move two of the intersections to avoid  unwanted
 480      intersections (not spurious; they are in fact intersections until
 481      moved) */
 482
 483   B->y+=2;
 484   E->y-=2;
 485
 486   embedlist_add_edge(m, A,C);
 487   embedlist_add_edge(m, A,D);
 488   embedlist_add_edge(m, A,E);
 489   embedlist_add_edge(m, B,C);
 490   embedlist_add_edge(m, B,D);
 491   embedlist_add_edge(m, B,E);
 492   embedlist_add_edge(m, C,F);
 493   embedlist_add_edge(m, D,F);
 494   embedlist_add_edge(m, E,F);
 495
 496   g->objective++;
 497 }
 498
 499 static void mesh_embed_recurse(graph *g,mesh *m,int x, int y, int w, int h, int k5, int k33, int bigk33){
 500   int xd,yd,wd,hd;
 501
 502   // not minimal spacing; the k33 needs vertical offset, but the others are larger just to space them out.
 503   if( bigk33 && w>=6 && h>=5 ){
 504     wd = 5;
 505     hd = 4;
 506     xd = random_number() % (w-wd);
 507     yd = random_number() % (h-hd);
 508     mesh_embed_bigk33(g,m,x+xd,y+yd);
 509   }else if(k5 && w>=4 && h>=3){
 510     wd = 3;
 511     hd = 2;
 512     xd = random_number() % (w-wd);
 513     yd = random_number() % (h-hd);
 514     mesh_embed_k5(g,m,x+xd,y+yd);
 515   }else if(k33 && w>=3 && h>=2 ){
 516     wd = 2;
 517     hd = 1;
 518     xd = random_number() % (w-wd);
 519     yd = random_number() % (h-hd);
 520     mesh_embed_k33(g,m,x+xd,y+yd);
 521   }else
 522     return;
 523
 524   mesh_embed_recurse(g,m, x,         y,       w,    yd+1, k5,k33,bigk33);
 525   mesh_embed_recurse(g,m, x,   y+yd+hd,       w, h-yd-hd, k5,k33,bigk33);
 526
 527   mesh_embed_recurse(g,m, x,      y+yd,    xd+1,    hd+1, k5,k33,bigk33);
 528   mesh_embed_recurse(g,m, x+xd+wd,y+yd, w-xd-wd,    hd+1, k5,k33,bigk33);
 529 }
 530
 531 /* Embed k5s and k3,3s in the solved graph in such a way that we know each added
 532    non-planar kernel adds exactly one and only one certain intersection. */
 533 /* Don't use this along with 'nastiness'; the assumptions the
 534    nastiness algorithm makes about solvable conditions won't always
 535    coexist with the assumptions that non-planar embedding makes about
 536    solvable conditions. */
 537
 538
 539 static void mesh_embed_nonplanar(graph *g, mesh *m,int k5, int k33, int bigk33){
 540   // selection is used as a poison flag during embedding
 541   deselect_verticies(g);
 542   mesh_embed_recurse(g, m, 0,0,m->width,m->height, k5,k33,bigk33);
 543   deselect_verticies(g);
 544 }
 545
 546 /* Rogues are added lines inserted between verticies on neighboring
 547    rows/columns; the idea is to choose the longest ones that cross the
 548    smallest number of lines. */
 549 /* Right now, the rogue insertion doesn't take embedded kernel
 550    poisoning or niceness constraints into account, so don't mix
 551    them */
 552
 553 static int count_intersections(graph *g, vertex *A, vertex *B){
 554   edge *e=g->edges;
 555   double dummy_x,dummy_y;
 556   int count=0;
 557
 558   while(e){
 559     if(intersectsV(A,B,e->A,e->B,&dummy_x,&dummy_y))
 560       count++;
 561     e=e->next;
 562   }
 563   return count;
 564 }
 565
 566 static void scan_rogue(graph *g, mesh *m, int aoff,int boff, int step, int end,
 567                        float *metric, edge *best, int *cross){
 568   int a,b;
 569
 570   for(a=0;a+1<end;a++){
 571     for(b=a+1;b<end;b++){
 572       vertex *va = m->v[a*step+aoff];
 573       vertex *vb = m->v[b*step+boff];
 574
 575       if(!va->selected && !vb->selected){
 576         if(!exists_edge(va,vb)){
 577           int count = count_intersections(g,va,vb);
 578           if(count){
 579             float test = (b-a)/count;
 580             if(test>=*metric){
 581               *metric=test;
 582               best->A=va;
 583               best->B=vb;
 584               *cross=count;
 585             }
 586           }
 587         }
 588       }
 589     }
 590   }
 591 }
 592
 593 /* scan the entire mesh looking for the candidate edge with the highest rogue objective value */
 594 static void mesh_add_rogues(graph *g, mesh *m){
 595   int w = m->width;
 596   int h = m->height;
 597
 598   deselect_verticies(g);
 599   while(1){
 600     int i;
 601     edge best;
 602     float metric=2.1;
 603     int cross = 0;
 604     best.A=0;
 605     best.B=0;
 606
 607     for(i=0;i+1<h;i++){
 608       scan_rogue(g, m,(i+1)*w,i*w,1,w, &metric,&best,&cross);
 609       scan_rogue(g, m,i*w,(i+1)*w,1,w,  &metric,&best,&cross);
 610     }
 611
 612     for(i=0;i+1<w;i++){
 613       scan_rogue(g, m, i, i+1, w,h, &metric,&best,&cross);
 614       scan_rogue(g, m, i+1, i, w,h, &metric,&best,&cross);
 615     }
 616
 617     if(best.A && best.B){
 618       add_edge(g,best.A,best.B);
 619       // poison verticies against later selection
 620       best.A->selected=1;
 621       best.B->selected=1;
 622       g->objective+=cross;
 623       g->objective_lessthan = 1;
 624     }else{
 625       break;
 626     }
 627   }
 628   deselect_verticies(g);
 629 }
 630
 631 /* Initial generation setup */
 632
 633 static void mesh_setup(graph *g, mesh *m, int order, int divis){
 634   int flag=0;
 635   int wiggle=0;
 636   int n;
 637   m->width=3;
 638   m->height=2;
 639   {
 640     while(--order){
 641       if(flag){
 642         flag=0;
 643         m->height+=1;
 644       }else{
 645         flag=1;
 646         m->width+=2;
 647       }
 648     }
 649   }
 650   n=m->width*m->height;
 651
 652   // is this divisible by our requested divisor if any?
 653   if(divis>0 && n%divis){
 654     while(1){
 655       wiggle++;
 656
 657       if(!((n+wiggle)%divis)) break;
 658
 659       if(n-wiggle>6 && !((n-wiggle)%divis)){
 660         wiggle = -wiggle;
 661         break;
 662       }
 663     }
 664
 665     // refactor the rectangular mesh's dimensions.
 666     {
 667       int h = (int)sqrt(n+wiggle),w;
 668
 669       while( (n+wiggle)%h )h--;
 670
 671       if(h==1){
 672         // double it and be content with a working result
 673         h=2;
 674         w=(n+wiggle);
 675       }else{
 676         // good factoring
 677         w = (n+wiggle)/h;
 678       }
 679
 680       m->width=w;
 681       m->height=h;
 682     }
 683   }
 684
 685   new_board(g, m->width * m->height);
 686   m->embed_list=0;
 687
 688   // used for rogue calcs
 689   {
 690     int x,y;
 691     vertex *v = g->verticies;
 692     for(y=0;y<m->height;y++)
 693       for(x=0;x<m->width;x++){
 694         v->x=x*50; // not a random number; other things depend on this
 695         v->y=y*50; // not a random number; other things depend on this
 696         v=v->next;
 697       }
 698   }
 699
 700   g->objective = 0;
 701   g->objective_lessthan = 0;
 702
 703 }
 704
 705 static void mesh_flatten(graph *g,mesh *m){
 706   /* a flat vector is easier to address while building the mesh */
 707   int i;
 708   vertex *v=g->verticies;
 709   for(i=0;i<m->width*m->height;i++){
 710     m->v[i]=v;
 711     v=v->next;
 712   }
 713 }
 714
 715 static void generate_mesh(graph *g, mesh *m,
 716                           int density_128){
 717
 718   /* first walk a random spanning tree */
 719   span_depth_first(g, 0, m);
 720
 721   /* now iterate the whole mesh adding random edges */
 722   {
 723     int i;
 724     for(i=0;i<m->width*m->height;i++)
 725       random_populate(g, i, m, 2, density_128);
 726   }
 727 }
 728
 729 void generate_simple(graph *g, int order){
 730   mesh m;
 731   random_seed(order);
 732   mesh_setup(g,&m, order, 0);
 733   m.v=alloca(m.width*m.height * sizeof(*m.v));
 734   mesh_flatten(g,&m);
 735
 736   generate_mesh(g,&m,40);
 737   randomize_verticies(g);
 738
 739   if((m.width*m.height)&1)
 740     arrange_verticies_circle(g,0,0);
 741   else
 742     arrange_verticies_circle(g,M_PI/2,M_PI/2);
 743 }
 744
 745 void generate_sparse(graph *g, int order){
 746   mesh m;
 747   random_seed(order);
 748   mesh_setup(g,&m, order, 3);
 749   m.v=alloca(m.width*m.height * sizeof(*m.v));
 750   mesh_flatten(g,&m);
 751
 752   generate_mesh(g,&m,2);
 753   mesh_nastiness(g,&m,-1);
 754   randomize_verticies(g);
 755
 756   if((m.width*m.height)&1)
 757     arrange_verticies_circle(g,0,0);
 758   else
 759     arrange_verticies_circle(g,M_PI/2,M_PI/2);
 760 }
 761
 762 void generate_dense(graph *g, int order){
 763   mesh m;
 764   random_seed(order);
 765   mesh_setup(g,&m, order, 3);
 766   m.v=alloca(m.width*m.height * sizeof(*m.v));
 767   mesh_flatten(g,&m);
 768
 769   generate_mesh(g,&m,96);
 770   mesh_nastiness(g,&m,-1);
 771   randomize_verticies(g);
 772
 773   if((m.width*m.height)&1)
 774     arrange_verticies_circle(g,0,0);
 775   else
 776     arrange_verticies_circle(g,M_PI/2,M_PI/2);
 777 }
 778
 779 void generate_nasty(graph *g, int order){
 780   mesh m;
 781   random_seed(order+8236);
 782   mesh_setup(g,&m, order,4);
 783   m.v=alloca(m.width*m.height * sizeof(*m.v));
 784   mesh_flatten(g,&m);
 785
 786   generate_mesh(g,&m,32);
 787   mesh_nastiness(g,&m,-1);
 788   randomize_verticies(g);
 789   arrange_verticies_polycircle(g,3,0,.3,25,0,25);
 790 }
 791
 792 void generate_rogue(graph *g, int order){
 793   mesh m;
 794   random_seed(order+3005);
 795   mesh_setup(g,&m, order,5);
 796   m.v=alloca(m.width*m.height * sizeof(*m.v));
 797   mesh_flatten(g,&m);
 798
 799   generate_mesh(g,&m,24);
 800   mesh_add_rogues(g,&m);
 801   randomize_verticies(g);
 802
 803   if(order*.03<.3)
 804     arrange_verticies_polycircle(g,5,0,order*.03,0,0,0);
 805   else
 806     arrange_verticies_polycircle(g,5,0,.3,0,0,0);
 807 }
 808
 809 void generate_embed(graph *g, int order){
 810   mesh m;
 811   random_seed(order+347);
 812   mesh_setup(g,&m, order, 6);
 813   m.v=alloca(m.width*m.height * sizeof(*m.v));
 814   mesh_flatten(g,&m);
 815
 816   mesh_embed_nonplanar(g,&m,1,1,1);
 817   generate_mesh(g,&m,48);
 818   embedlist_add_to_mesh(g,&m);
 819
 820   randomize_verticies(g);
 821
 822   if(order*.03<.3)
 823     arrange_verticies_polycircle(g,6,0,order*.03,0,0,0);
 824   else
 825     arrange_verticies_polycircle(g,6,0,.3,0,0,0);
 826
 827 }
 828
 829 void generate_crest(graph *g, int order){
 830   int n;
 831   mesh m;
 832   random_seed(order);
 833   mesh_setup(g,&m, order,0);
 834   m.v=alloca(m.width*m.height * sizeof(*m.v));
 835   mesh_flatten(g,&m);
 836
 837   generate_mesh(g,&m,128);
 838   n=m.width*m.height;
 839   arrange_verticies_circle(g,M_PI/n,M_PI/n);
 840 }