Swap code/variable declaration to be pre-C99 compliant.

[xiph/unicode.git] / planarity / graph_generate_mesh2.c

/*
 *
 *  gPlanarity: 
 *     The geeky little puzzle game with a big noodly crunch!
 *    
 *     gPlanarity copyright (C) 2005 Monty <monty@xiph.org>
 *     Original Flash game by John Tantalo <john.tantalo@case.edu>
 *     Original game concept by Mary Radcliffe
 *
 *  gPlanarity is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2, or (at your option)
 *  any later version.
 *   
 *  gPlanarity is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *   
 *  You should have received a copy of the GNU General Public License
 *  along with Postfish; see the file COPYING.  If not, write to the
 *  Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * 
 */

#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "graph.h"
#include "random.h"
#include "gameboard.h"
#include "graph_generate.h"
#include "graph_arrange.h"
#include "graph_region.h"

/* Mesh1 has three primary considerations in mind:
   1) By default, act like the algorithm in the original planarity
   2) Conform to a population contraint that is easy to work with/modify
   3) Playability; short edges result in graphs that are easier to solve.

   Mesh2 is intended to be a freeform populator with two different
   uses; harder levels that disrupt the easy solution algorithms that
   mesh1 allows, as well as being able to densely populate arbitrary
   regions.  */

typedef struct {
  graph *g;
  int width;
  int height;
  int active_current;
  int active_max;
} mesh;

// check for intersections with other edges
static int check_intersects_edge(mesh *m, edge *e, int intersections){
  edge *ge = m->g->edges;
  int count=0;

  while(ge){
    double xo,yo;

    // edges that aren't in this region don't exist (for
    // now) by definition
    if(ge->A->active == m->active_current || ge->B->active == m->active_current){
      // edges that share a vertex don't intersect by definition
      if(ge->A!=e->A && ge->A!=e->B && ge->B!=e->A && ge->B!=e->B)
        if(intersects(ge->A->orig_x,ge->A->orig_y,
                      ge->B->orig_x,ge->B->orig_y,
                      e->A->orig_x,e->A->orig_y,
                      e->B->orig_x,e->B->orig_y,
                      &xo,&yo)){
          count++;
          if(count>intersections)return 1;
        }
    }
    ge=ge->next;
  }
  return 0;
}

static float dot(vertex *A, vertex *B, vertex *C){
  return (float)(B->orig_x-A->orig_x)*(float)(C->orig_x-B->orig_x) + 
    (float)(B->orig_y-A->orig_y)*(float)(C->orig_y-B->orig_y);
}

static float cross(vertex *A, vertex *B, vertex *C){
  return (float)(B->orig_x-A->orig_x)*(float)(C->orig_y-A->orig_y) - 
    (float)(B->orig_y-A->orig_y)*(float)(C->orig_x-A->orig_x);
}

static float sq_point_distance(vertex *A, vertex *B){
  float xd = A->orig_x-B->orig_x;
  float yd = A->orig_y-B->orig_y;
  return xd*xd+yd*yd;
}

static float sq_line_distance(edge *e, vertex *v){

  if(dot(e->A,e->B,v) > 0)
    return sq_point_distance(e->B,v);
  if(dot(e->B,e->A,v) > 0)
    return sq_point_distance(e->A,v);

  {
    float c = cross(e->A,e->B,v);
    return c*c/sq_point_distance(e->A,e->B);
  }
}

// Does this edge pass within ten pixels of another vertex
static int check_intersects_vertex(mesh *m, edge *e){
  vertex *v = m->g->verticies;

  while(v){
    if(v->active == m->active_current)
      if(v!=e->A && v!=e->B && sq_line_distance(e,v)<16)return 1;
    v=v->next;
  }

  return 0;
}

static int select_available(mesh *m,vertex *current,float length_limit,int intersections){
  int count=0;
  vertex *v = m->g->verticies;

  // mark all possible choices
  while(v){
    v->selected = 0;
    if(v!=current && current->active == m->active_current){
      if(length_limit==0 || sq_point_distance(v,current)<=length_limit){
        if(!exists_edge(v,current)){
          edge e;
          e.A = v;
          e.B = current;
          if(!region_intersects(&e)){
            if(!check_intersects_edge(m,&e,intersections)){
              if(!check_intersects_vertex(m,&e)){
                v->selected=1;
                count++;
              }
            }
          }
        }
      }
    }
    v=v->next;
  }

  return count;
}

// Although very inefficient, it is simple and correct.  Even
// impossibly large boards generate in a fraction of a second on old
// boxen.  There's likely no need to bother optimizing this step of
// board creation. */

typedef struct insort{
  int metric;
  vertex *v;
} insort;

static int insort_c(const void *a, const void *b){
  insort *A=(insort *)a;
  insort *B=(insort *)b;
  return(A->metric-B->metric);
}

static vertex *vertex_num_sel(graph *g,int num){
  vertex *v=g->verticies;
  if(num<0)return 0;
  while(v){
    if(v->selected){
      if(!num)
        break;
      else
        num--;
    }
    v=v->next;
  }
  return v;
}

static void prepopulate(mesh *m,int length_limit){
  // sort all verticies in ascending order by their number of potential edges 
  int i=0;
  int num=0;
  insort index[m->g->vertex_num];
  vertex *v=m->g->verticies;

  while(v){
    if(v->active == m->active_current){
      index[num].v=v;
      index[num].metric = select_available(m,v,0,0);
      num++;
    }
    v=v->next;
  }
  qsort(index,num,sizeof(*index),insort_c);

  // populate in ascending order
  for(i=0;i<num;i++){
    int intersections=0;
    int edges=0;
    v = index[i].v;
    
    // does this vertex already have edges?
    {
      edge_list *el=v->edges;
      while(el){
        edges++;
        el=el->next;
        if(edges>=2)break;
      }
    }
    if(edges>=2)continue;

    // it's possible some intersections will be necessary, but go for
    // fewest possible
    while(edges<2 && intersections<10){
      int count = select_available(m,v,length_limit,intersections);
      if(count){
        vertex *short0=0;
        vertex *short1=0;
        vertex *w=m->g->verticies;
        long d0;
        long d1;
        
        if(length_limit){
          // choose two at random 
          int a=random_number()%count;
          int b=-1;

          if(count>1)
            while(b==-1){
              b=random_number()%count;
              if(b==a)b=-1;
            }

          short0=vertex_num_sel(m->g,a);
          short1=vertex_num_sel(m->g,b);

        }else{
          // used with region-constrined meshes
          // of the possible edges, choose the shortest two
          while(w){
            if(w!=v && w->selected){
              int xd=w->orig_x-v->orig_x;
              int yd=w->orig_y-v->orig_y;
              long d=xd*xd+yd*yd;
              if(!short0){
                short0=w;
                d0=d;
              }else if(!short1 || d<d1){
                if(d<d0){
                  short1=short0;
                  d1=d0;
                  short0=w;
                  d0=d;
                }else{
                  short1=w;
                  d1=d;
                }
              }
            }
            w=w->next;
          }
        }
        
        if(short0){
          add_edge(m->g,v,short0);
          edges++;
          m->g->objective +=intersections;
          if(intersections)m->g->objective_lessthan=1;
        }
        if(edges<2 && short1){
          add_edge(m->g,v,short1);
          edges++;
          m->g->objective +=intersections;
          if(intersections)m->g->objective_lessthan=1;
        }
      }
      intersections++;
    }
  }
}

// the spanning walk is to make an attempt at a single, connected graph.
static void span_depth_first2(mesh *m,vertex *current, float length_limit){
  
  current->grabbed=1; // overloaded; "we walked this already"
  while(1){
    // prefer walking along edges that already exist
    {
      edge_list *el=current->edges;
      
      while(el){
        edge *e=el->edge;
        vertex *v;
        if(e->A==current)
          v=e->B;
        else
          v=e->A;

        if(!v->grabbed){
          span_depth_first2(m, v, length_limit);
        }

        el=el->next;
      }
    }

    // now walk any possible edges that have not been walked
    {
      int count=select_available(m,current,length_limit,0);
      int count2=0;
      int choice;
      vertex *v = m->g->verticies;
      
      // filter out already-walked edges 
      while(v){
        if(v->grabbed && v->selected){ // grabbed is also overloaded to mean walked
          v->selected = 0;
          count--;
        }
        v=v->next;
      }
     
      if(count == 0) return;
      
      choice = random_number()%count;
      v = m->g->verticies;
      while(v){
        if(v->selected){
          if(count2++ == choice){
            add_edge(m->g,v,current);
            span_depth_first2(m,v, length_limit);
            break;
          }
        }
        v=v->next;
      }
    
      if(count == 1) return; // because we just took care of it
    }
  }
}

static void random_populate(mesh *m,vertex *current,int dense_128, float length_limit){
  if(current->active == m->active_current){
    int count=select_available(m,current,length_limit,0);
    if(count){
      vertex *v = m->g->verticies;
      while(v){
        if(v->selected && random_yes(dense_128)){
          add_edge(m->g,v,current);
          v->selected=0;
        }
        v=v->next;
      }
    }
  }
}

/* Initial generation setup */

static void mesh_setup(graph *g, mesh *m, int order, int divis){
  int flag=0;
  int wiggle=0;
  int n;
  m->g = g;
  m->width=3;
  m->height=2;

  {
    while(--order){
      if(flag){
        flag=0;
        m->height+=1;
      }else{
        flag=1;
        m->width+=2;
      }
    }
  }
  n=m->width*m->height;

  // is this divisible by our requested divisor if any?
  if(divis>0 && n%divis){
    while(1){
      wiggle++;

      if(!((n+wiggle)%divis)) break;

      if(n-wiggle>6 && !((n-wiggle)%divis)){
        wiggle = -wiggle;
        break;
      }
    }

    // refactor the rectangular mesh's dimensions.
    {
      int h = (int)sqrt(n+wiggle),w;

      while( (n+wiggle)%h )h--;

      if(h==1){
        // double it and be content with a working result
        h=2;
        w=(n+wiggle);
      }else{
        // good factoring
        w = (n+wiggle)/h;
      }

      m->width=w;
      m->height=h;
    }
  }

  new_board(g, m->width * m->height);
  region_init(); // clear it

  // used for intersection calcs
  {
    int x,y;
    vertex *v = g->verticies;
    for(y=0;y<m->height;y++)
      for(x=0;x<m->width;x++){
        v->orig_x=x*50; // not a random number
        v->orig_y=y*50; // not a random number
        v=v->next;
      }
  }

  g->objective = 0;
  g->objective_lessthan = 0;
  m->active_max=0;
}

static void generate_mesh2(mesh *m, int density_128, float length_limit){ 
  vertex *v;
  int i;

  length_limit*=50;
  length_limit*=length_limit;

  for(i=0;i<=m->active_max;i++){
    m->active_current=i;

    if(have_region())
      prepopulate(m,0);
    
    /* connect the graph into as few discrete sections as possible */
    v = m->g->verticies;
    while(v){
      v->grabbed = 0;
      v=v->next;
    }
    
    v = m->g->verticies;
    // make sure we walk all verticies
    while(v){
      if(v->active == m->active_current && !v->grabbed)
        span_depth_first2(m, m->g->verticies, length_limit);
      v=v->next;
    }
    
    if(!have_region())
      prepopulate(m,length_limit);
    
    /* now iterate the whole mesh adding random edges */
    v=m->g->verticies;
    while(v){
      random_populate(m, v, density_128, length_limit);
    v=v->next;
    }
  }
}

void generate_freeform(graph *g, int order){
  mesh m;
  random_seed(order+1);
  mesh_setup(g, &m, order, 0);

  generate_mesh2(&m,48,4);

  randomize_verticies(g);
  if(order*.03<.3)
    arrange_verticies_polycircle(g,4,0,order*.03,0,0,0);
  else
    arrange_verticies_polycircle(g,4,0,.3,0,0,0);

}

void generate_shape(graph *g, int order){
  int mod=0;
  int dens=64;
  int min=8;
  mesh m;
  random_seed(order+1);

  switch(order%13){
  case 0: // star
    mod=10; break;
  case 1:
    break;
  case 2: // dashed circle
    dens=48; break;
  case 3: // bifur
    dens=80; break;
  case 4:
    break;
  case 5:
    min = 12;
    dens = 10;
    break;
  case 6:
    min = 10;
    break;
  case 7:
    min = 10;
    break;
  case 8:
    min = 10;
    break;
  case 9:
    min = 10;
    break;
  case 10: // ring
    dens=128;
    min = 11;
    break;
  case 11:
    min = 12;
    break;
  case 12: // target
    min = 14;
    break;
  }

  mesh_setup(g, &m, (order>min?order:min), mod);
  randomize_verticies(g);

  switch(order % 13){
  case 0: // star
    arrange_region_star(g); break; //4
  case 1: // rainbow
    arrange_region_rainbow(g); break; //9
  case 2: // dashed circle
    arrange_region_dashed_circle(g); break; //0
  case 3: // bifur
    arrange_region_bifur(g); break; //0
  case 4: // dairyqueen
    arrange_region_dairyqueen(g); break; //0
  case 5: // cloud
    arrange_region_cloud(g); break; //0
  case 6: // storm
    arrange_region_storm(g); break; //11
  case 7: // plus;
      arrange_region_plus(g); break; //2
  case 8: 
    arrange_region_hole3(g); break; //4
  case 9: 
    arrange_region_hole4(g); break; //15
  case 10: // ring
    arrange_region_ring(g); break; //29
  case 11: 
    arrange_region_ovals(g); break; //95
  case 12: // target
    arrange_region_target(g); break; //108
  }

  m.active_max=region_layout(g);
  generate_mesh2(&m,dens,0);
}