[xiph-commits] r10112 - trunk/planarity
xiphmont at svn.xiph.org
xiphmont at svn.xiph.org
Sun Oct 2 03:20:53 PDT 2005
Author: xiphmont
Date: 2005-10-02 03:20:49 -0700 (Sun, 02 Oct 2005)
New Revision: 10112
Modified:
trunk/planarity/gameboard_draw_main.c
trunk/planarity/gameboard_logic.c
trunk/planarity/gameboard_logic_fade.c
trunk/planarity/graph.c
trunk/planarity/graph.h
trunk/planarity/graph_arrange.c
trunk/planarity/graph_arrange.h
trunk/planarity/graph_generate.c
trunk/planarity/graph_generate.h
trunk/planarity/graph_generate_mesh1.c
trunk/planarity/levelstate.c
trunk/planarity/version.h
Log:
Two new board generation algorithms
Modified: trunk/planarity/gameboard_draw_main.c
===================================================================
--- trunk/planarity/gameboard_draw_main.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/gameboard_draw_main.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -73,7 +73,6 @@
/* verticies drawn over the edges */
{
vertex *v = g->g.verticies;
- fade_list *f = g->fade.head;
float alpha = 1.*g->fade.count/FADE_FRAMES;
int clipx = x-V_RADIUS;
@@ -95,31 +94,15 @@
draw_vertex(c,v,g->vertex_lit);
} else if (v->attached_to_grabbed && !g->group_drag){
draw_vertex(c,v,g->vertex_attached);
- }else
+ }else{
draw_vertex(c,v,g->vertex);
+ if(v->fading)
+ draw_vertex_with_alpha(c,v,g->vertex_attached,alpha);
+ }
}
v=v->next;
}
-
- while(f){
- v=f->v;
-
- /* is the vertex in the expose rectangle? */
- if(v->x>=clipx && v->x<=clipw &&
- v->y>=clipy && v->y<=cliph){
-
- /* only fade if not specially lit */
- if(!(v == g->grabbed_vertex && !g->group_drag) &&
- !(v->selected) &&
- !(v==g->lit_vertex) &&
- !(v->attached_to_grabbed && !g->group_drag))
-
- draw_vertex_with_alpha(c,v,g->vertex_attached,alpha);
-
- }
- f=f->next;
- }
}
}
Modified: trunk/planarity/gameboard_logic.c
===================================================================
--- trunk/planarity/gameboard_logic.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/gameboard_logic.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -259,6 +259,9 @@
// reactivate all the verticies
activate_verticies(&g->g);
+ // update the score
+ update_score(g);
+
// it's a reset; show lines is default. This also has the side
// effect of forcing a full board redraw and expose
set_hide_lines(g,0);
Modified: trunk/planarity/gameboard_logic_fade.c
===================================================================
--- trunk/planarity/gameboard_logic_fade.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/gameboard_logic_fade.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -45,6 +45,7 @@
pool=ret->next;
ret->v=v;
+ v->fading=1;
ret->next = f->head;
f->head = ret;
@@ -77,6 +78,9 @@
while(l){
fade_list *n = l->next;
+ /* unflag vertex */
+ l->v->fading=0;
+
/* invalidate the vertex */
invalidate_vertex(g,l->v);
Modified: trunk/planarity/graph.c
===================================================================
--- trunk/planarity/graph.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/graph.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -44,7 +44,7 @@
/* mesh/board state */
/************************ edge list maint operations ********************/
-static void add_edge_to_list(vertex *v, edge *e){
+edge_list *add_edge_to_list(edge_list *l, edge *e){
edge_list *ret;
if(edge_list_pool==0){
@@ -58,24 +58,28 @@
edge_list_pool=ret->next;
ret->edge=e;
- ret->next=v->edges;
- v->edges=ret;
+ ret->next=l;
+ return ret;
}
-static void release_edge_list(vertex *v){
- edge_list *el=v->edges;
-
+/* releases the edge list but not the edges */
+void release_edge_list(edge_list *el){
if(el){
edge_list *end=el;
while(end->next)end=end->next;
end->next = edge_list_pool;
edge_list_pool = el;
-
- v->edges=0;
}
}
+/* releases the edge list but not the edges */
+static void release_vertex_edge_list(vertex *v){
+ edge_list *el = v->edges;
+ release_edge_list(el);
+ v->edges=0;
+}
+
/************************ intersection maint operations ********************/
static intersection *new_intersection(){
@@ -155,8 +159,7 @@
}
/************************ edge maint operations ******************************/
-/* also adds to the edge list */
-edge *add_edge(graph *g, vertex *A, vertex *B){
+edge *new_edge(vertex *A, vertex *B){
edge *ret;
if(edge_pool==0){
@@ -173,17 +176,47 @@
ret->B=B;
ret->active=0;
ret->i.next=0;
+
+ return ret;
+}
+
+/* makes a new egde and adds it to the vertex and graph edge lists */
+edge *add_edge(graph *g, vertex *A, vertex *B){
+ edge *ret = new_edge(A,B);
+
ret->next=g->edges;
g->edges=ret;
- add_edge_to_list(A,ret);
- add_edge_to_list(B,ret);
+ A->edges=add_edge_to_list(A->edges,ret);
+ B->edges=add_edge_to_list(B->edges,ret);
g->num_edges++;
return ret;
}
+/* adds existing edge to the vertex and graph edge lists, but only if
+ it's not already there */
+void insert_edge(graph *g, edge *e){
+ vertex *A = e->A;
+ vertex *B = e->B;
+
+ if(exists_edge(A,B)){
+ // already a matching edge; release this one
+ release_intersection_list(e);
+ e->next=edge_pool;
+ edge_pool=e;
+ }else{
+ e->next=g->edges;
+ g->edges=e;
+
+ A->edges=add_edge_to_list(A->edges,e);
+ B->edges=add_edge_to_list(B->edges,e);
+
+ g->num_edges++;
+ }
+}
+
static void release_edges(graph *g){
edge *e = g->edges;
@@ -199,7 +232,7 @@
g->num_edges_active=0;
}
-static int intersects(vertex *L1, vertex *L2, vertex *M1, vertex *M2, double *xo, double *yo){
+int intersects(vertex *L1, vertex *L2, vertex *M1, vertex *M2, double *xo, double *yo){
/* y = ax + b */
float La=0;
float Lb=0;
@@ -401,6 +434,7 @@
ret->selected_volatile=0;
ret->grabbed=0;
ret->attached_to_grabbed=0;
+ ret->fading=0;
ret->edges=0;
ret->num=g->vertex_num++;
@@ -411,7 +445,7 @@
}
static void release_vertex(vertex *v){
- release_edge_list(v);
+ release_vertex_edge_list(v);
v->next=vertex_pool;
vertex_pool=v;
}
Modified: trunk/planarity/graph.h
===================================================================
--- trunk/planarity/graph.h 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/graph.h 2005-10-02 10:20:49 UTC (rev 10112)
@@ -40,6 +40,7 @@
int selected;
int grabbed;
int attached_to_grabbed;
+ int fading;
struct edge_list *edges;
struct vertex *next;
} vertex;
@@ -103,6 +104,15 @@
extern vertex *new_board(graph *g, int num_v);
extern vertex *find_vertex(graph *g, int x, int y);
+
+extern edge_list *add_edge_to_list(edge_list *l, edge *e);
+extern void release_edge_list(edge_list *el);
+extern edge *new_edge(vertex *A, vertex *B);
+extern void release_edge_list(edge_list *el);
+extern void insert_edge(graph *g, edge *e);
+extern int intersects(vertex *L1, vertex *L2, vertex *M1, vertex *M2,
+ double *xo, double *yo);
+
extern void move_vertex(graph *g, vertex *v, int x, int y);
extern void grab_vertex(graph *g, vertex *v);
extern void ungrab_vertex(graph *g,vertex *v);
Modified: trunk/planarity/graph_arrange.c
===================================================================
--- trunk/planarity/graph_arrange.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/graph_arrange.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -39,12 +39,50 @@
int radius=min(bw,bh)*.45;
int i;
for(i=0;i<n;i++){
- v->x = rint( radius * cos( i*M_PI*2./n +off1) + (bw>>1));
- v->y = rint( radius * sin( i*M_PI*2./n +off2) + (bh>>1));
+ v->x = rint( radius * sin( i*M_PI*2./n +off1) + (bw>>1));
+ v->y = rint( radius * -cos( i*M_PI*2./n +off2) + (bh>>1));
v=v->next;
}
}
+void arrange_verticies_polygon(graph *g, int sides, float angle, float rad,
+ int xoff, int yoff, float xstretch, float ystretch){
+ vertex *v = g->verticies;
+ int n = g->vertex_num;
+ int bw=g->orig_width;
+ int bh=g->orig_height;
+ int radius=min(bw,bh)*rad*.45;
+ float perleg,del,acc=0;
+ int i;
+
+ for(i=0;i<sides;i++){
+ int xA = sin(M_PI*2/sides*i+angle)*radius+bw/2+xoff;
+ int yA = -cos(M_PI*2/sides*i+angle)*radius+bh/2+yoff;
+ int xB = sin(M_PI*2/sides*(i+1)+angle)*radius+bw/2+xoff;
+ int yB = -cos(M_PI*2/sides*(i+1)+angle)*radius+bh/2+yoff;
+
+ float xD,yD;
+
+ if(i==0){
+ perleg = hypot((xA-xB),(yA-yB));
+ del = perleg*sides / n;
+ }
+
+ xD = (xB-xA) / perleg;
+ yD = (yB-yA) / perleg;
+
+ while(v && acc<=perleg){
+ v->x = rint(((xA + xD*acc) - bw/2) * xstretch + bw/2);
+ v->y = rint(((yA + yD*acc) - bh/2) * ystretch + bh/2);
+ v=v->next;
+ acc+=del;
+ }
+ acc-=perleg;
+ }
+
+}
+
+
void arrange_verticies_mesh(graph *g, int width, int height){
vertex *v = g->verticies;
int bw=g->orig_width;
@@ -64,6 +102,42 @@
}
}
+void arrange_verticies_nastymesh(graph *g, int w, int h, vertex **flat){
+ int A = 0;
+ int B = w-1;
+ int i;
+
+ arrange_verticies_mesh(g,w,h);
+
+ while(A<B){
+ for(i=0;i<=A;i++){
+ flat[i]->y-=10;
+ flat[B+i]->y-=10;
+
+ flat[i+(h-1)*w]->y+=10;
+ flat[B+i+(h-1)*w]->y+=10;
+ }
+ A++;
+ B--;
+ }
+
+ A = 0;
+ B = (h-1)*w;
+
+ while(A<B){
+ for(i=0;i<=A;i+=w){
+ flat[i]->x-=10;
+ flat[B+i]->x-=10;
+
+ flat[i +(w-1)]->x+=10;
+ flat[B+i+(w-1)]->x+=10;
+
+ }
+ A+=w;
+ B-=w;
+ }
+}
+
void arrange_verticies_cloud(graph *g){
vertex *v = g->verticies;
int n = g->vertex_num;
Modified: trunk/planarity/graph_arrange.h
===================================================================
--- trunk/planarity/graph_arrange.h 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/graph_arrange.h 2005-10-02 10:20:49 UTC (rev 10112)
@@ -25,5 +25,10 @@
*/
extern void arrange_verticies_circle(graph *g, float off1, float off2);
+extern void arrange_verticies_polygon(graph *g, int sides, float angle, float rad,
+ int xoff, int yoff, float xa, float ya);
+
extern void arrange_verticies_mesh(graph *g, int width, int height);
+extern void arrange_verticies_nastymesh(graph *g, int w, int h, vertex **flat);
+
extern void arrange_verticies_cloud(graph *g);
Modified: trunk/planarity/graph_generate.c
===================================================================
--- trunk/planarity/graph_generate.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/graph_generate.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -40,22 +40,41 @@
int unlock;
} gen_instance;
-#define FINITE_LEVELS 9
+#define FINITE_LEVELS 16
static gen_instance i_list[FINITE_LEVELS]={
- {"mesh1", 1, "A Small Beginning", generate_mesh_1, 1.,1., 1 }, // 1
- {"mesh1", 2, "My First Real Level(tm)", generate_mesh_1, 1.,1., 2 }, // 2
- {"data" , 0, "My First Mission Impossible(tm)", generate_data, 20.,1.,3 }, // 3
- {"mesh1", 3, "Larger, Not Harder", generate_mesh_1, 1.,1., 3 }, // 4
- {"meshC", 5, "The Trick Is It's Easy", generate_mesh_1C, 1.,1., 2 }, // 5
- {"meshM", 6, "If You Squint, It's a Brick", generate_mesh_1M, 1.,1., 1 }, // 6
- {"mesh1", 7, "Round but Straightforward", generate_mesh_1, 1.,1., 4 }, // 7
- {"meshS",10, "Tough and Stringy", generate_mesh_1S, 2.,1., 3 }, // 8
- {"cloud", 9, "More of a Mess Than Usual", generate_mesh_1_cloud, 2.,1., 3 }, // 9
+ {"simple", 1, "A Small Beginning", generate_simple, 1.,1., 1 }, // 1
+ {"simple", 2, "My First Real Level(tm)", generate_simple, 1.,1., 2 }, // 2
+ {"data", 0, "My First Mission Impossible(tm)", generate_data, 20.,1., 3 }, // 3
+ {"simple", 3, "Larger But Not Harder", generate_simple, 1.,1., 2 }, // 4
+ {"crest", 5, "The Trick Is It's Easy", generate_crest, 1.,1., 2 }, // 5
+
+ {"simple", 4, "Practice Before the Handbasket: One of Three", generate_simple, 1.,1., 1 }, // 6
+ {"simple", 5, "Practice Before the Handbasket: Two of Three", generate_simple, 1.,1., 1 }, // 7
+ {"simple", 6, "Practice Before the Handbasket: Three of Three", generate_simple, 1.,1., 1 }, // 8
+
+ {"sparse", 5, "Threadbare", generate_sparse, 1.,1., 2 }, // 9
+
+ {"nasty", 4, "The Pointy Circles Are Slightly More Difficult", generate_nasty, 1.2,1., 3 }, // 10
+ {"nasty", 5, "If You Squint, It's a Brick", generate_nasty, 1.2,1., 3 }, // 11
+ {"nasty", 6, "It Can Roll! Granted, Not Very Well", generate_nasty, 1.2,1., 3 }, // 12
+
+ {"embed", 4, "The Hexagon is a Subtle And Wily Beast", generate_embed, 1.5,1., 4 }, // 13
+ {"embed", 5, "No, Really, The Hexagon Puzzles Are Harder", generate_embed, 2., 1., 5 }, // 14
+ {"embed", 6, "Cursed? Call 1-800-HEX-A-GON Today!", generate_embed, 3., 1., 6 }, // 15
+
+ {"simple", 7, "Round but Straightforward", generate_simple, 1.,1., 4 }, // 16
+
+
+ //{"meshS",10, "Tough and Stringy", generate_mesh_1S, 2.,1., 3 }, // 8
+ //{"cloud", 9, "More of a Mess Than Usual", generate_mesh_1_cloud, 2.,1., 3 }, // 9
};
-#define LOOP_LEVELS 1
+#define LOOP_LEVELS 4
static gen_instance i_list_loop[LOOP_LEVELS]={
- {"mesh1", 10, "\"Original\" Board Number %d", generate_mesh_1, 1.,1., 2 }, // n
+ {"simple", 8, "Algorithm: \"Original\" Order: %d", generate_simple, 1.,1., 5 }, // n
+ {"sparse", 8, "Algorithm: \"Sparse\" Order: %d", generate_sparse, 1.2,1., 5 }, // n
+ {"nasty", 8, "Algorithm: \"Nasty\" Order: %d", generate_nasty, 1.5,1., 5 }, // n
+ {"embed", 8, "Algorithm: \"Embed\" Order: %d", generate_embed, 4.,1., 5 }, // n
};
int generate_find_number(char *id){
@@ -117,7 +136,7 @@
return -1;
}
- if(asprintf(&gm->id,"%s %d",i_list[classnum].class,ordernum)==-1){
+ if(asprintf(&gm->id,"%s %d",i_list_loop[classnum].class,ordernum)==-1){
fprintf(stderr,"Couldn't allocate memory for level name.\n");
return -1;
}
Modified: trunk/planarity/graph_generate.h
===================================================================
--- trunk/planarity/graph_generate.h 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/graph_generate.h 2005-10-02 10:20:49 UTC (rev 10112)
@@ -28,10 +28,12 @@
extern int generate_get_meta(int num, graphmeta *gm);
extern void generate_board(graph *g,int num);
-extern void generate_mesh_1(graph *g, int order);
-extern void generate_mesh_1M(graph *g, int order);
-extern void generate_mesh_1C(graph *g, int order);
-extern void generate_mesh_1S(graph *g, int order);
-extern void generate_mesh_1_cloud(graph *g, int order);
+extern void generate_simple(graph *g, int order);
+extern void generate_nasty(graph *g, int order);
+extern void generate_sparse(graph *g, int order);
+extern void generate_rogue(graph *g, int order);
+extern void generate_embed(graph *g, int order);
+extern void generate_crest(graph *g, int order);
+
extern void generate_data(graph *g, int order);
Modified: trunk/planarity/graph_generate_mesh1.c
===================================================================
--- trunk/planarity/graph_generate_mesh1.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/graph_generate_mesh1.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -36,6 +36,7 @@
typedef struct {
vertex **v;
+ edge_list *embed_list;
int width;
int height;
} mesh;
@@ -51,6 +52,89 @@
int num;
} neighbors_list;
+/* The 'embed_list' is a set of edges that don't obey or neighboring
+ intersection calculation mode and are thus tracked
+ seperately/explicitly. They're added to the main graph after the
+ rest of the graph is generated. */
+
+/* add edge to the embed_list */
+static void embedlist_add_edge(mesh *m, vertex *A, vertex *B){
+ edge *e = new_edge(A,B);
+ m->embed_list = add_edge_to_list(m->embed_list,e);
+}
+
+/* move embed_list edges into the real graph */
+static void embedlist_add_to_mesh(graph *g, mesh *m){
+ edge_list *el = m->embed_list;
+
+ /* move the edges out of the embed_list and add them to the main graph */
+ while(el){
+ edge *e = el->edge;
+ el->edge = 0;
+
+ insert_edge(g,e);
+ el=el->next;
+ }
+
+ release_edge_list(m->embed_list);
+ m->embed_list=0; /* be pedantic */
+
+}
+
+static int embedlist_intersects(mesh *m, vertex *A, vertex *B){
+ edge_list *el = m->embed_list;
+ double dummy_x,dummy_y;
+
+ while(el){
+ edge *e = el->edge;
+
+ if(intersects(A,B,e->A,e->B,&dummy_x,&dummy_y))
+ return 1;
+
+ el=el->next;
+ }
+ return 0;
+
+}
+
+static void embedlist_filter_intersections(neighbors_grid *ng){
+ int i;
+ vertex *A = ng->center;
+
+ for(i=0;i<8;i++){
+ if(ng->vnum[i] != -1){
+ vertex *B = ng->m->v[ng->vnum[i]];
+
+ if(embedlist_intersects(ng->m,A,B))
+ ng->vnum[i]=-1;
+ }
+ }
+}
+
+static int embedlist_contains_vertex(mesh *m,vertex *v){
+ edge_list *el = m->embed_list;
+
+ while(el){
+ edge *e = el->edge;
+
+ if(e->A == v) return 1;
+ if(e->B == v) return 1;
+
+ el=el->next;
+ }
+ return 0;
+}
+
+static int embedlist_vertex_poisoned(mesh *m, vertex *v){
+ return v->selected;
+}
+
+static void poison_vertex(mesh *m, vertex *v){
+ v->selected=1;
+}
+
+/* neighboring intersection model */
+
static void populate_neighbors(int vnum, mesh *m,
neighbors_grid *ng){
int width = m->width;
@@ -136,9 +220,10 @@
break;
}
}
+ embedlist_filter_intersections(ng);
}
-// eliminate verticies we've already connected to
+/* eliminate verticies we've already connected to */
static void filter_edges(neighbors_grid *ng,
neighbors_list *nl){
@@ -206,13 +291,266 @@
}
}
-static void generate_mesh(graph *g, mesh *m, int order, int density_128){
+/* nastiness adds long edges along the outer perimeter to make it
+ harder to rely on verticies always being near each other; mesh 2
+ takes this further, but we can add some of the same flavor to
+ mesh1. */
+
+static void nasty_horizontal(graph *g, mesh *m, int A, int B, int limit){
+ if(limit == 0) return;
+ if(A+2 > B)return; /* adjacent is too close */
+
+ add_edge(g,m->v[A],m->v[B]);
+
+ A++;
+ B--;
+ nasty_horizontal(g,m,A,B,limit-1);
+}
+
+static void nasty_vertical(graph *g, mesh *m, int A, int B, int limit){
+ if(limit == 0) return;
+ if(A+(m->width*2) > B)return; /* adjacent is too close */
+
+ add_edge(g,m->v[A],m->v[B]);
+
+ A+=m->width;
+ B-=m->width;
+ nasty_vertical(g,m,A,B,limit-1);
+}
+
+/* Don't use this along with k5 embedding; the assumptions the
+ nastiness algorithm makes about solvable conditions won't always
+ coexist with the assumptions the k5 embedding makes about solvable
+ conditions. */
+static void mesh_nastiness(graph *g, mesh *m, int limit){
+
+ nasty_horizontal(g,m,0,m->width-1, limit);
+ nasty_horizontal(g,m,(m->height-1)*m->width,m->width*m->height-1, limit);
+
+ nasty_vertical(g,m,0,(m->height-1)*m->width,limit);
+ nasty_vertical(g,m,m->width-1,m->width*m->height-1, limit);
+}
+
+/* Embed one k5 in the solved graph */
+/* Don't use this along with 'nastiness'; the assumptions the
+ nastiness algorithm makes about solvable conditions won't always
+ coexist with the assumptions that non-planar embedding makes about
+ solvable conditions. */
+
+static void mesh_embed_k5(graph *g, mesh *m,int x, int y){
+
+ /* Add the k5s up front in their own special edge list; This list
+ will also be checked explicitly by the various neighboring
+ algorithms as the k5's edges don't all conceptually work within
+ the implicit neighboring algorithm we're using. Also, by using a
+ special edge list and not adding the k5 edges to the vertex edge
+ lists up front, we can still use the unmodified initial spanning
+ walk algorithm. */
+
+ int w = m->width;
+
+ vertex *A = m->v[y*w+x+1];
+ vertex *B = m->v[(y+1)*w+x+1];
+ vertex *C = m->v[(y+1)*w+x+2];
+ vertex *D = m->v[(y+1)*w+x+3];
+ vertex *E = m->v[(y+2)*w+x];
+
+ // poisoned verticies are already inside another kernel (the regular
+ // mesh is deflectable and thus not really regular)
+ if(embedlist_vertex_poisoned(m,A))return;
+ if(embedlist_vertex_poisoned(m,B))return;
+ if(embedlist_vertex_poisoned(m,C))return;
+ if(embedlist_vertex_poisoned(m,D))return;
+ if(embedlist_vertex_poisoned(m,E))return;
+
+ // the way k5 works we don't need to poison the internal verticies
+
+ embedlist_add_edge(m, A,B);
+ embedlist_add_edge(m, A,C);
+ embedlist_add_edge(m, A,D);
+ embedlist_add_edge(m, A,E);
+ embedlist_add_edge(m, B,C);
+ embedlist_add_edge(m, B,D);
+ embedlist_add_edge(m, B,E);
+ embedlist_add_edge(m, C,D);
+ embedlist_add_edge(m, C,E);
+ embedlist_add_edge(m, D,E);
+ g->objective++;
+}
+
+/* Embed one k3,3 in the solved graph */
+/* Don't use this along with 'nastiness'; the assumptions the
+ nastiness algorithm makes about solvable conditions won't always
+ coexist with the assumptions that k5 embedding makes about solvable
+ conditions. */
+static void mesh_embed_k33(graph *g, mesh *m, int x, int y){
+
+ /* same disclaimers as k5 */
+ /* the k3,3 embedding works with the standard walk algorithm only
+ because an edge with an endpoint exactly on another edge is
+ considered an intersection. */
+ /* the way it is added, the walk/population can add additional edges
+ inside the embedded kernel; this is fine, the population will be
+ certain not to introduce intersections. */
+
+ int w = m->width;
+
+ vertex *A = m->v[y*w+x];
+ vertex *B = m->v[y*w+x+1];
+ vertex *C = m->v[y*w+x+2];
+ vertex *D = m->v[(y+1)*w+x];
+ vertex *E = m->v[(y+1)*w+x+1];
+ vertex *F = m->v[(y+1)*w+x+2];
+
+ // poisoned verticies are already inside another kernel (the regular
+ // mesh is deflectable and thus not really regular)
+ if(embedlist_vertex_poisoned(m,A))return;
+ if(embedlist_vertex_poisoned(m,B))return;
+ if(embedlist_vertex_poisoned(m,C))return;
+ if(embedlist_vertex_poisoned(m,D))return;
+ if(embedlist_vertex_poisoned(m,E))return;
+ if(embedlist_vertex_poisoned(m,F))return;
+
+ // check that verticies we want to poison ourselves are not already in use
+ if(embedlist_contains_vertex(m,B))return;
+ if(embedlist_contains_vertex(m,E))return;
+ /* B and E are internal according to x/y, but according to the
+ position in the mesh, they're on the outside. Poison them so
+ that they're explicitly marked inside. */
+ poison_vertex(m,B);
+ poison_vertex(m,E);
+
+ /* need to mode two of the intersections to avoid unwanted
+ intersections (not spurious; they are in fact intersections until
+ moved) */
+
+ B->y+=2;
+ E->y-=2;
+
+ embedlist_add_edge(m, A,C);
+ embedlist_add_edge(m, A,D);
+ embedlist_add_edge(m, A,E);
+ embedlist_add_edge(m, B,C);
+ embedlist_add_edge(m, B,D);
+ embedlist_add_edge(m, B,E);
+ embedlist_add_edge(m, C,F);
+ embedlist_add_edge(m, D,F);
+ embedlist_add_edge(m, E,F);
+ g->objective++;
+
+}
+
+/* Embed one non-miminal k3,3 in the solved graph */
+/* Don't use this along with 'nastiness'; the assumptions the
+ nastiness algorithm makes about solvable conditions won't always
+ coexist with the assumptions that k5 embedding makes about solvable
+ conditions. */
+static void mesh_embed_bigk33(graph *g, mesh *m, int x, int y){
+
+ /* as above */
+
+ int w = m->width;
+
+ vertex *A = m->v[(y+2)*w+x];
+ vertex *B = m->v[(y+1)*w+x+2];
+ vertex *C = m->v[y*w+x+4];
+ vertex *D = m->v[(y+4)*w+x+1];
+ vertex *E = m->v[(y+3)*w+x+3];
+ vertex *F = m->v[(y+2)*w+x+5];
+
+ // poisoned verticies are already inside another kernel (the regular
+ // mesh is deflectable and thus not really regular)
+ if(embedlist_vertex_poisoned(m,A))return;
+ if(embedlist_vertex_poisoned(m,B))return;
+ if(embedlist_vertex_poisoned(m,C))return;
+ if(embedlist_vertex_poisoned(m,D))return;
+ if(embedlist_vertex_poisoned(m,E))return;
+ if(embedlist_vertex_poisoned(m,F))return;
+
+ // check that verticies we want to poison ourselves are not already in use
+ if(embedlist_contains_vertex(m,B))return;
+ if(embedlist_contains_vertex(m,E))return;
+ /* B and E are internal according to x/y, but according to the
+ position in the mesh, they're on the outside. Poison them so
+ that they're explicitly marked inside. */
+ poison_vertex(m,B);
+ poison_vertex(m,E);
+
+ /* need to move two of the intersections to avoid unwanted
+ intersections (not spurious; they are in fact intersections until
+ moved) */
+
+ B->y+=2;
+ E->y-=2;
+
+ embedlist_add_edge(m, A,C);
+ embedlist_add_edge(m, A,D);
+ embedlist_add_edge(m, A,E);
+ embedlist_add_edge(m, B,C);
+ embedlist_add_edge(m, B,D);
+ embedlist_add_edge(m, B,E);
+ embedlist_add_edge(m, C,F);
+ embedlist_add_edge(m, D,F);
+ embedlist_add_edge(m, E,F);
+
+ g->objective++;
+}
+
+static void mesh_embed_recurse(graph *g,mesh *m,int x, int y, int w, int h, int k5, int k33, int bigk33){
+ int xd,yd,wd,hd;
+
+ // not minimal spacing; the k33 needs vertical offset, but the others are larger just to space them out.
+ if( bigk33 && w>=6 && h>=5 ){
+ wd = 5;
+ hd = 4;
+ xd = random_number() % (w-wd);
+ yd = random_number() % (h-hd);
+ mesh_embed_bigk33(g,m,x+xd,y+yd);
+ }else if(k5 && w>=4 && h>=3){
+ wd = 3;
+ hd = 2;
+ xd = random_number() % (w-wd);
+ yd = random_number() % (h-hd);
+ mesh_embed_k5(g,m,x+xd,y+yd);
+ }else if(k33 && w>=3 && h>=2 ){
+ wd = 2;
+ hd = 1;
+ xd = random_number() % (w-wd);
+ yd = random_number() % (h-hd);
+ mesh_embed_k33(g,m,x+xd,y+yd);
+ }else
+ return;
+
+ mesh_embed_recurse(g,m, x, y, w, yd+1, k5,k33,bigk33);
+ mesh_embed_recurse(g,m, x, y+yd+hd, w, h-yd-hd, k5,k33,bigk33);
+
+ mesh_embed_recurse(g,m, x, y+yd, xd+1, hd+1, k5,k33,bigk33);
+ mesh_embed_recurse(g,m, x+xd+wd,y+yd, w-xd-wd, hd+1, k5,k33,bigk33);
+}
+
+/* Embed k5s and k3,3s in the solved graph in such a way that we know each added
+ non-planar kernel adds exactly one and only one certain intersection. */
+/* Don't use this along with 'nastiness'; the assumptions the
+ nastiness algorithm makes about solvable conditions won't always
+ coexist with the assumptions that non-planar embedding makes about
+ solvable conditions. */
+
+
+static void mesh_embed_nonplanar(graph *g, mesh *m,int k5, int k33, int bigk33){
+ // selection is used as a poison flag during embedding
+ deselect_verticies(g);
+ mesh_embed_recurse(g, m, 0,0,m->width,m->height, k5,k33,bigk33);
+ deselect_verticies(g);
+}
+
+/* Initial generation setup */
+
+static void mesh_setup(graph *g, mesh *m, int order, int divis){
int flag=0;
+ int wiggle=0;
+ int n;
m->width=3;
m->height=2;
- vertex *vlist;
-
- random_seed(order);
{
while(--order){
if(flag){
@@ -224,20 +562,75 @@
}
}
}
+ n=m->width*m->height;
- vlist=new_board(g, m->width * m->height);
+ // is this divisible by our requested divisor if any?
+ if(divis>0 && n%divis){
+ while(1){
+ wiggle++;
- /* a flat vector is easier to address while building the mesh */
- {
- int i;
- vertex *v=vlist;
- m->v=alloca(m->width*m->height * sizeof(*m->v));
- for(i=0;i<m->width*m->height;i++){
- m->v[i]=v;
- v=v->next;
+ 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);
+ m->embed_list=0;
+
+ // used for rogue calcs
+ {
+ int x,y;
+ vertex *v = g->verticies;
+ for(y=0;y<m->height;y++)
+ for(x=0;x<m->width;x++){
+ v->x=x*50; // not a random number
+ v->y=y*50; // not a random number
+ v=v->next;
+ }
+ }
+
+ g->objective = 0;
+ g->objective_lessthan = 0;
+
+}
+
+static void mesh_flatten(graph *g,mesh *m){
+ /* a flat vector is easier to address while building the mesh */
+ int i;
+ vertex *v=g->verticies;
+ for(i=0;i<m->width*m->height;i++){
+ m->v[i]=v;
+ v=v->next;
+ }
+}
+
+static void generate_mesh(graph *g, mesh *m,
+ int order,
+ int density_128){
+
/* first walk a random spanning tree */
span_depth_first(g, 0, m);
@@ -247,44 +640,102 @@
for(i=0;i<m->width*m->height;i++)
random_populate(g, i, m, 2, density_128);
}
+}
- g->objective=0;
- g->objective_lessthan=0;
+void generate_simple(graph *g, int order){
+ mesh m;
+ random_seed(order);
+ mesh_setup(g,&m, order, 0);
+ m.v=alloca(m.width*m.height * sizeof(*m.v));
+ mesh_flatten(g,&m);
+ generate_mesh(g,&m,order,40);
+ randomize_verticies(g);
+
+ if((m.width*m.height)&1)
+ arrange_verticies_circle(g,0,0);
+ else
+ arrange_verticies_circle(g,M_PI/2,M_PI/2);
}
-void generate_mesh_1(graph *g, int order){
+void generate_sparse(graph *g, int order){
mesh m;
- generate_mesh(g,&m,order,32);
+ random_seed(order);
+ mesh_setup(g,&m, order, 3);
+ m.v=alloca(m.width*m.height * sizeof(*m.v));
+ mesh_flatten(g,&m);
+
+ generate_mesh(g,&m,order,2);
+ mesh_nastiness(g,&m,-1);
randomize_verticies(g);
- arrange_verticies_circle(g,0,0);
+ switch((order-1)%4){
+ case 0:
+ arrange_verticies_polygon(g,3,0,1.15,0,+65,1.1,1.);
+ break;
+ case 1:
+ arrange_verticies_polygon(g,3,-M_PI/2,1.,+40,0,1.1,1.);
+ break;
+ case 2:
+ arrange_verticies_polygon(g,3,-M_PI,1.15,0,-65,1.1,1.);
+ break;
+ case 3:
+ arrange_verticies_polygon(g,3,-M_PI*3/2,1.,-40,0,1.1,1.);
+ break;
+ }
}
-void generate_mesh_1M(graph *g, int order){
+void generate_nasty(graph *g, int order){
mesh m;
+ random_seed(order);
+ mesh_setup(g,&m, order,4);
+ m.v=alloca(m.width*m.height * sizeof(*m.v));
+ mesh_flatten(g,&m);
+
generate_mesh(g,&m,order,32);
+ mesh_nastiness(g,&m,-1);
randomize_verticies(g);
- arrange_verticies_mesh(g,m.width,m.height);
+ switch(order%2){
+ case 0:
+ arrange_verticies_polygon(g,4,0,1.,0,0,1.1,1.);
+ break;
+ case 1:
+ arrange_verticies_polygon(g,4,M_PI/4,1.,0,0,1.2,1.1);
+ break;
+ }
}
-void generate_mesh_1C(graph *g, int order){
- int n;
+void generate_embed(graph *g, int order){
mesh m;
- generate_mesh(g,&m,order,128);
- n=m.width*m.height;
- arrange_verticies_circle(g,M_PI/n - M_PI/2,M_PI/n - M_PI/2);
-}
+ random_seed(order+347);
+ mesh_setup(g,&m, order, 6);
+ m.v=alloca(m.width*m.height * sizeof(*m.v));
+ mesh_flatten(g,&m);
-void generate_mesh_1S(graph *g, int order){
- mesh m;
- generate_mesh(g,&m,order,2);
+ mesh_embed_nonplanar(g,&m,1,1,1);
+ generate_mesh(g,&m,order,48);
+ embedlist_add_to_mesh(g,&m);
+
randomize_verticies(g);
- arrange_verticies_circle(g,0,0);
+
+ switch(order%2){
+ case 0:
+ arrange_verticies_polygon(g,6,0,1.,0,0,1.1,1.);
+ break;
+ case 1:
+ arrange_verticies_polygon(g,6,M_PI/6,1.,0,0,1.1,1.);
+ break;
+ }
}
-void generate_mesh_1_cloud(graph *g, int order){
+void generate_crest(graph *g, int order){
+ int n;
mesh m;
- generate_mesh(g,&m,order,40);
- randomize_verticies(g);
- arrange_verticies_cloud(g);
+ random_seed(order);
+ mesh_setup(g,&m, order,0);
+ m.v=alloca(m.width*m.height * sizeof(*m.v));
+ mesh_flatten(g,&m);
+
+ generate_mesh(g,&m,order,128);
+ n=m.width*m.height;
+ arrange_verticies_circle(g,M_PI/n,M_PI/n);
}
Modified: trunk/planarity/levelstate.c
===================================================================
--- trunk/planarity/levelstate.c 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/levelstate.c 2005-10-02 10:20:49 UTC (rev 10112)
@@ -282,6 +282,10 @@
}
+ while(curr->gm.num >= level_limit){
+ levelstate_prev();
+ }
+
return 0;
}
Modified: trunk/planarity/version.h
===================================================================
--- trunk/planarity/version.h 2005-10-01 15:59:44 UTC (rev 10111)
+++ trunk/planarity/version.h 2005-10-02 10:20:49 UTC (rev 10112)
@@ -1,2 +1,2 @@
#define VERSION "$Id$ "
-/* DO NOT EDIT: Automated versioning hack [Thu Sep 29 06:57:55 EDT 2005] */
+/* DO NOT EDIT: Automated versioning hack [Sun Oct 2 06:10:44 EDT 2005] */
More information about the commits
mailing list