[xiph-commits] r10113 - trunk/planarity
xiphmont at svn.xiph.org
xiphmont at svn.xiph.org
Sun Oct 2 22:59:55 PDT 2005
Author: xiphmont
Date: 2005-10-02 22:59:50 -0700 (Sun, 02 Oct 2005)
New Revision: 10113
Added:
trunk/planarity/graph_generate_mesh2.c
Modified:
trunk/planarity/Makefile
trunk/planarity/dialog_finish.c
trunk/planarity/gameboard_draw_score.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/graph_score.c
trunk/planarity/version.h
Log:
New Shapes
New Algorithms (rogue, mesh2)
Modified: trunk/planarity/Makefile
===================================================================
--- trunk/planarity/Makefile 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/Makefile 2005-10-03 05:59:50 UTC (rev 10113)
@@ -25,7 +25,7 @@
gameboard_draw_score.c main.c gameboard_draw_selection.c\
timer.c gameboard_draw_vertex.c levelstate.c dialog_level.c\
dialog_level_icons.c gameboard_draw_text.c random.c graph_generate_data.c\
- gameboard_logic_fade.c
+ gameboard_logic_fade.c graph_generate_mesh2.c
OBJ = dialog_finish.o gameboard_logic.o dialog_pause.o gameboard_logic_button.o\
gameboard.o gameboard_logic_buttonbar.o gameboard_draw_box.o\
gameboard_logic_mouse.o gameboard_draw_button.o gameboard_logic_push.o\
@@ -35,7 +35,7 @@
gameboard_draw_score.o main.o gameboard_draw_selection.o\
timer.o gameboard_draw_vertex.o levelstate.o dialog_level.o\
dialog_level_icons.o gameboard_draw_text.o random.o graph_generate_data.o\
- gameboard_logic_fade.o
+ gameboard_logic_fade.o graph_generate_mesh2.o
GCF = `pkg-config --static --cflags "gtk+-2.0 >= 2.7.2"`
# uncomment below for a normal dynamic build
Modified: trunk/planarity/dialog_finish.c
===================================================================
--- trunk/planarity/dialog_finish.c 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/dialog_finish.c 2005-10-03 05:59:50 UTC (rev 10113)
@@ -174,9 +174,21 @@
render_bordertext_centered(c,buffer, w/2,y);y+=24;
- snprintf(buffer,160,"Base score: %d points",graphscore_get_score(&g->g));
+ snprintf(buffer,160,"Base score: %d points",graphscore_get_raw_score(&g->g));
render_bordertext_centered(c,buffer, w/2,y);y+=24;
+ if(graphscore_get_multiplier(&g->g)>1){
+ cairo_save(c);
+ cairo_select_font_face (c, "Arial",
+ CAIRO_FONT_SLANT_NORMAL,
+ CAIRO_FONT_WEIGHT_BOLD);
+ cairo_set_source_rgba (c, HIGH_COLOR);
+
+ snprintf(buffer,160,"Objective Exceeded! x%d",graphscore_get_multiplier(&g->g));
+ render_bordertext_centered(c,buffer, w/2,y);y+=24;
+ cairo_restore(c);
+ }
+
snprintf(buffer,160,"Time bonus: %d points",time_bonus);
render_bordertext_centered(c,buffer, w/2,y);y+=35;
@@ -189,11 +201,11 @@
if(graphscore_get_score(&g->g)+time_bonus >= levelstate_get_hiscore()){
cairo_set_source_rgba (c, HIGH_COLOR);
- render_bordertext_centered(c,"A high score!", w/2,y);y+=45;
+ render_bordertext_centered(c,"A high score!", w/2,y);y+=43;
cairo_set_source_rgba (c, TEXT_COLOR);
}else{
snprintf(buffer,160,"Previous best: %ld points",levelstate_get_hiscore());
- render_bordertext_centered(c,buffer, w/2,y);y+=45;
+ render_bordertext_centered(c,buffer, w/2,y);y+=43;
}
Modified: trunk/planarity/gameboard_draw_score.c
===================================================================
--- trunk/planarity/gameboard_draw_score.c 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/gameboard_draw_score.c 2005-10-03 05:59:50 UTC (rev 10113)
@@ -40,10 +40,12 @@
void draw_score(Gameboard *g){
char level_string[160];
char score_string[160];
+ char mult_string[160];
char int_string[160];
char obj_string[160];
cairo_text_extents_t extentsL;
cairo_text_extents_t extentsS;
+ cairo_text_extents_t extentsM;
cairo_text_extents_t extentsO;
cairo_text_extents_t extentsI;
cairo_matrix_t m;
@@ -68,7 +70,8 @@
cairo_set_source_rgba (c, TEXT_COLOR);
snprintf(level_string,160,"Level %d: %s",get_level_num()+1,get_level_desc());
- snprintf(score_string,160,"Score: %d",graphscore_get_score(&g->g));
+ snprintf(score_string,160,"Score: %d",graphscore_get_raw_score(&g->g));
+ snprintf(mult_string,160,"x%d",graphscore_get_multiplier(&g->g));
snprintf(int_string,160,"Intersections: %ld",g->g.active_intersections);
snprintf(obj_string,160,"Objective: %s",graphscore_objective_string(&g->g));
@@ -76,6 +79,7 @@
cairo_text_extents (c, obj_string, &extentsO);
cairo_text_extents (c, int_string, &extentsI);
cairo_text_extents (c, score_string, &extentsS);
+ cairo_text_extents (c, mult_string, &extentsM);
/*
text_h = extentsL.height;
@@ -91,6 +95,13 @@
cairo_show_text (c, int_string);
cairo_move_to (c, 15, ty2);
cairo_show_text (c, score_string);
+ if(graphscore_get_multiplier(&g->g)>1){
+ cairo_save(c);
+ cairo_set_source_rgba (c, HIGH_COLOR);
+ cairo_move_to (c, 15 + extentsS.width+10, ty2);
+ cairo_show_text (c, mult_string);
+ cairo_restore(c);
+ }
cairo_move_to (c, g->g.width-extentsL.width-15, ty1);
cairo_show_text (c, level_string);
Modified: trunk/planarity/graph.h
===================================================================
--- trunk/planarity/graph.h 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph.h 2005-10-03 05:59:50 UTC (rev 10113)
@@ -140,5 +140,7 @@
extern void graph_release(graph *g);
extern int graphscore_get_score(graph *g);
+extern int graphscore_get_raw_score(graph *g);
+extern int graphscore_get_multiplier(graph *g);
extern int graphscore_get_bonus(graph *g);
extern char *graphscore_objective_string(graph *g);
Modified: trunk/planarity/graph_arrange.c
===================================================================
--- trunk/planarity/graph_arrange.c 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph_arrange.c 2005-10-03 05:59:50 UTC (rev 10113)
@@ -82,7 +82,72 @@
}
+void arrange_verticies_polycircle(graph *g, int sides, float angle, float split,
+ int radplus,int xoff,int yoff){
+ vertex *v = g->verticies;
+ int n = g->vertex_num;
+ int bw=g->orig_width;
+ int bh=g->orig_height;
+ int radius=min(bw,bh)*.45+radplus;
+ float perleg,perarc,del,acc=0;
+ int i;
+
+ for(i=0;i<sides;i++){
+ float ang0 = M_PI*2/sides*i + angle;
+ float ang1 = M_PI*2/sides*i + (M_PI/sides*split) + angle;
+ float ang2 = M_PI*2/sides*(i+1) - (M_PI/sides*split) + angle;
+
+ int xA = sin(ang1)*radius+bw/2;
+ int yA = -cos(ang1)*radius+bh/2;
+ int xB = sin(ang2)*radius+bw/2;
+ int yB = -cos(ang2)*radius+bh/2;
+
+ float xD,yD,aD;
+
+ if(i==0){
+ perleg = hypot((xA-xB),(yA-yB));
+ perarc = 2*radius*M_PI * split / sides;
+ del = (perleg+perarc)*sides / n;
+ }
+
+ // populate the first arc segment
+ aD = (ang1-ang0)/perarc*2;
+ while(v && acc<=perarc/2){
+ v->x = rint( sin(ang0 + aD*acc)*radius+bw/2)+xoff;
+ v->y = rint(-cos(ang0 + aD*acc)*radius+bh/2)+yoff;
+ v=v->next;
+ acc+=del;
+ }
+ acc-=perarc/2;
+
+ // populate the line segment
+ xD = (xB-xA) / perleg;
+ yD = (yB-yA) / perleg;
+
+ while(v && acc<=perleg){
+ v->x = rint(xA + xD*acc)+xoff;
+ v->y = rint(yA + yD*acc)+yoff;
+ v=v->next;
+ acc+=del;
+ }
+ acc-=perleg;
+
+ // populate the second arc segment
+ while(v && acc<=perarc/2){
+ v->x = rint( sin(ang2 + aD*acc)*radius+bw/2)+xoff;
+ v->y = rint(-cos(ang2 + aD*acc)*radius+bh/2)+yoff;
+ v=v->next;
+ acc+=del;
+ }
+ acc-=perarc/2;
+
+
+ }
+
+}
+
+
void arrange_verticies_mesh(graph *g, int width, int height){
vertex *v = g->verticies;
int bw=g->orig_width;
Modified: trunk/planarity/graph_arrange.h
===================================================================
--- trunk/planarity/graph_arrange.h 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph_arrange.h 2005-10-03 05:59:50 UTC (rev 10113)
@@ -27,6 +27,8 @@
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_polycircle(graph *g, int sides, float angle, float split,
+ int radplus,int xoff,int yoff);
extern void arrange_verticies_mesh(graph *g, int width, int height);
extern void arrange_verticies_nastymesh(graph *g, int w, int h, vertex **flat);
Modified: trunk/planarity/graph_generate.c
===================================================================
--- trunk/planarity/graph_generate.c 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph_generate.c 2005-10-03 05:59:50 UTC (rev 10113)
@@ -40,8 +40,9 @@
int unlock;
} gen_instance;
-#define FINITE_LEVELS 16
+#define FINITE_LEVELS 23
static gen_instance i_list[FINITE_LEVELS]={
+
{"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
@@ -52,29 +53,43 @@
{"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
+ {"sparse", 4, "Tough and Stringy", generate_sparse, 1.2,1., 2 }, // 9
+ {"sparse", 5, "Threadbare", generate_sparse, 1.2,1., 2 }, // 10
- {"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
+ {"nasty", 4, "The Bumpy Circles Are Slightly More Difficult", generate_nasty, 1.5,1., 3 }, // 11
+ {"nasty", 5, "Three is a Magic Mumber", generate_nasty, 1.5,1., 3 }, // 12
+ {"nasty", 6, "Last Call For (Sort of) Triangles (For Now)", generate_nasty, 1.5,1., 3 }, // 13
- {"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
+ {"free", 4, "Something Only Subtly Different", generate_freeform, 1.5,1., 3 }, // 14
+ {"free", 5, "It Can Roll! Granted, Not Very Well", generate_freeform, 1.5,1., 3 }, // 15
+ {"free", 6, "If you squint, It's a Rounded Brick", generate_freeform, 1.5,1., 3 }, // 16
- {"simple", 7, "Round but Straightforward", generate_simple, 1.,1., 4 }, // 16
+ {"rogue", 5, "A New Objective", generate_rogue, 1.6,1., 3 }, // 17
+ {"rogue", 6, "How Low Can You Go?", generate_rogue, 1.6,1., 3 }, // 18
+ {"rogue", 7, "Industrial Military Complex", generate_rogue, 1.6,1., 4 }, // 19
+ {"embed", 4, "The Hexagon is a Subtle And Wily Beast", generate_embed, 2.,1., 4 }, // 20
+ {"embed", 5, "No, Really, The Hexagon Puzzles Are Harder", generate_embed, 3.,1., 5 }, // 21
+ {"embed", 6, "Cursed? Call 1-800-HEX-A-GON Today!", generate_embed, 4.,1., 6 }, // 22
+ {"simple", 7, "Round but Straightforward", generate_simple, 1.,1., 4 }, // 23
+
+
+
+
//{"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 4
+#define LOOP_LEVELS 7
static gen_instance i_list_loop[LOOP_LEVELS]={
- {"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
+ {"dense", 8, "Algorithm: Original/Dense (Order: %d)", generate_dense, .8,1., 5 }, // n
+ {"simple", 8, "Algorithm: Original (Order: %d)", generate_simple, 1.,1., 5 }, // n
+ {"sparse", 8, "Algorithm: Original/Sparse (Order: %d)",generate_sparse, 1.2,1., 5 }, // n
+ {"nasty", 8, "Algorithm: Nasty (Order: %d)", generate_nasty, 1.5,1., 5 }, // n
+ {"free", 8, "Algorithm: Freeform/4 (Order: %d)", generate_freeform, 1.5,1., 5 }, // n
+ {"rogue", 8, "Algorithm: Rogue (Order: %d)", generate_rogue, 1.6,1., 5 }, // n
+ {"embed", 8, "Algorithm: Embed (Order: %d)", generate_embed, 4.,1., 5 }, // n
};
int generate_find_number(char *id){
Modified: trunk/planarity/graph_generate.h
===================================================================
--- trunk/planarity/graph_generate.h 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph_generate.h 2005-10-03 05:59:50 UTC (rev 10113)
@@ -31,9 +31,11 @@
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_dense(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_freeform(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-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph_generate_mesh1.c 2005-10-03 05:59:50 UTC (rev 10113)
@@ -543,6 +543,91 @@
deselect_verticies(g);
}
+/* Rogues are added lines inserted between verticies on neighboring
+ rows/columns; the idea is to choose the longest ones that cross the
+ smallest number of lines. */
+/* Right now, the rogue insertion doesn't take embedded kernel
+ poisoning or niceness constraints into account, so don't mix
+ them */
+
+static int count_intersections(graph *g, vertex *A, vertex *B){
+ edge *e=g->edges;
+ double dummy_x,dummy_y;
+ int count=0;
+
+ while(e){
+ if(intersects(A,B,e->A,e->B,&dummy_x,&dummy_y))
+ count++;
+ e=e->next;
+ }
+ return count;
+}
+
+static void scan_rogue(graph *g, mesh *m, int aoff,int boff, int step, int end,
+ float *metric, edge *best, int *cross){
+ int a,b;
+
+ for(a=0;a+1<end;a++){
+ for(b=a+1;b<end;b++){
+ vertex *va = m->v[a*step+aoff];
+ vertex *vb = m->v[b*step+boff];
+
+ if(!va->selected && !vb->selected){
+ if(!exists_edge(va,vb)){
+ int count = count_intersections(g,va,vb);
+ if(count){
+ float test = (b-a)/count;
+ if(test>=*metric){
+ *metric=test;
+ best->A=va;
+ best->B=vb;
+ *cross=count;
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+/* scan the entire mesh looking for the candidate edge with the highest rogue objective value */
+static void mesh_add_rogues(graph *g, mesh *m){
+ int w = m->width;
+ int h = m->height;
+
+ deselect_verticies(g);
+ while(1){
+ int i;
+ edge best;
+ float metric=2.1;
+ int cross = 0;
+ best.A=0;
+ best.B=0;
+
+ for(i=0;i+1<h;i++){
+ scan_rogue(g, m,(i+1)*w,i*w,1,w, &metric,&best,&cross);
+ scan_rogue(g, m,i*w,(i+1)*w,1,w, &metric,&best,&cross);
+ }
+
+ for(i=0;i+1<w;i++){
+ scan_rogue(g, m, i, i+1, w,h, &metric,&best,&cross);
+ scan_rogue(g, m, i+1, i, w,h, &metric,&best,&cross);
+ }
+
+ if(best.A && best.B){
+ add_edge(g,best.A,best.B);
+ // poison verticies against later selection
+ best.A->selected=1;
+ best.B->selected=1;
+ g->objective+=cross;
+ g->objective_lessthan = 1;
+ }else{
+ break;
+ }
+ }
+ deselect_verticies(g);
+}
+
/* Initial generation setup */
static void mesh_setup(graph *g, mesh *m, int order, int divis){
@@ -606,8 +691,8 @@
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->x=x*50; // not a random number; other things depend on this
+ v->y=y*50; // not a random number; other things depend on this
v=v->next;
}
}
@@ -628,7 +713,6 @@
}
static void generate_mesh(graph *g, mesh *m,
- int order,
int density_128){
/* first walk a random spanning tree */
@@ -649,7 +733,7 @@
m.v=alloca(m.width*m.height * sizeof(*m.v));
mesh_flatten(g,&m);
- generate_mesh(g,&m,order,40);
+ generate_mesh(g,&m,40);
randomize_verticies(g);
if((m.width*m.height)&1)
@@ -665,45 +749,63 @@
m.v=alloca(m.width*m.height * sizeof(*m.v));
mesh_flatten(g,&m);
- generate_mesh(g,&m,order,2);
+ generate_mesh(g,&m,2);
mesh_nastiness(g,&m,-1);
randomize_verticies(g);
- 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;
- }
+
+ 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_dense(graph *g, int order){
+ mesh m;
+ 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,96);
+ mesh_nastiness(g,&m,-1);
+ 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_nasty(graph *g, int order){
mesh m;
- random_seed(order);
+ random_seed(order+8236);
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);
+ generate_mesh(g,&m,32);
mesh_nastiness(g,&m,-1);
randomize_verticies(g);
- 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;
- }
+ arrange_verticies_polycircle(g,3,0,.3,25,0,25);
}
+void generate_rogue(graph *g, int order){
+ mesh m;
+ random_seed(order+3005);
+ mesh_setup(g,&m, order,5);
+ m.v=alloca(m.width*m.height * sizeof(*m.v));
+ mesh_flatten(g,&m);
+
+ generate_mesh(g,&m,24);
+ mesh_add_rogues(g,&m);
+ randomize_verticies(g);
+
+ if(order*.03<.3)
+ arrange_verticies_polycircle(g,5,0,order*.03,0,0,0);
+ else
+ arrange_verticies_polycircle(g,5,0,.3,0,0,0);
+}
+
void generate_embed(graph *g, int order){
mesh m;
random_seed(order+347);
@@ -712,19 +814,16 @@
mesh_flatten(g,&m);
mesh_embed_nonplanar(g,&m,1,1,1);
- generate_mesh(g,&m,order,48);
+ generate_mesh(g,&m,48);
embedlist_add_to_mesh(g,&m);
randomize_verticies(g);
+
+ if(order*.03<.3)
+ arrange_verticies_polycircle(g,6,0,order*.03,0,0,0);
+ else
+ arrange_verticies_polycircle(g,6,0,.3,0,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_crest(graph *g, int order){
@@ -735,7 +834,7 @@
m.v=alloca(m.width*m.height * sizeof(*m.v));
mesh_flatten(g,&m);
- generate_mesh(g,&m,order,128);
+ generate_mesh(g,&m,128);
n=m.width*m.height;
arrange_verticies_circle(g,M_PI/n,M_PI/n);
}
Added: trunk/planarity/graph_generate_mesh2.c
===================================================================
--- trunk/planarity/graph_generate_mesh2.c 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph_generate_mesh2.c 2005-10-03 05:59:50 UTC (rev 10113)
@@ -0,0 +1,321 @@
+/*
+ *
+ * gPlanarity:
+ * The geeky little puzzle game with a big noodly crunch!
+ *
+ * gPlanarity copyright (C) 2005 Monty <monty at xiph.org>
+ * Original Flash game by John Tantalo <john.tantalo at 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"
+
+/* 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;
+} mesh;
+
+// check for intersections with other edges
+static int check_intersects_edge(mesh *m, edge *e){
+ edge *ge = m->g->edges;
+ while(ge){
+ double xo,yo;
+ if(intersects(ge->A,ge->B,e->A,e->B,&xo,&yo))return 1;
+ ge=ge->next;
+ }
+ return 0;
+}
+
+static float dot(vertex *A, vertex *B, vertex *C){
+ return (float)(B->x-A->x)*(float)(C->x-B->x) +
+ (float)(B->y-A->y)*(float)(C->y-B->y);
+}
+
+static float cross(vertex *A, vertex *B, vertex *C){
+ return (float)(B->x-A->x)*(float)(C->y-A->y) -
+ (float)(B->y-A->y)*(float)(C->x-A->x);
+}
+
+static float sq_point_distance(vertex *A, vertex *B){
+ float xd = A->x-B->x;
+ float yd = A->y-B->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!=e->A && v!=e->B && sq_line_distance(e,v)<100)return 1;
+ v=v->next;
+ }
+
+ return 0;
+}
+
+// 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. */
+static void span_depth_first2(mesh *m,vertex *current, float length_limit){
+
+ while(1){
+ // Mark/count all possible choices
+ int count=0;
+ int count2=0;
+ int choice;
+ vertex *v = m->g->verticies;
+
+ while(v){
+ v->selected = 0;
+ if(!v->edges && v!=current){
+ if(sq_point_distance(v,current)<=length_limit){
+ edge e;
+ e.A = v;
+ e.B = current;
+ if(!check_intersects_edge(m,&e)){
+ if(!check_intersects_vertex(m,&e)){
+ v->selected = 1;
+ count++;
+ }
+ }
+ }
+ }
+ v=v->next;
+ }
+
+ if(count == 0) return;
+
+ choice = random_number()%count;
+ count2 = 0;
+ 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){
+ int num_edges=0,count=0;
+ edge_list *el=current->edges;
+ vertex *v = m->g->verticies;
+ while(el){
+ num_edges++;
+ el=el->next;
+ }
+
+ // mark all possible choices
+ while(v){
+ v->selected = 0;
+ if(v!=current){
+ if(sq_point_distance(v,current)<=length_limit){
+ if(!exists_edge(v,current)){
+ edge e;
+ e.A = v;
+ e.B = current;
+ if(!check_intersects_edge(m,&e)){
+ if(!check_intersects_vertex(m,&e)){
+ v->selected=1;
+ count++;
+ }
+ }
+ }
+ }
+ }
+ v=v->next;
+ }
+
+ // make sure no vertex is a leaf
+ if(num_edges<2){
+ int choice = random_number() % count;
+ count = 0;
+
+ v = m->g->verticies;
+ while(v){
+ if(v->selected){
+ if(count++ == choice){
+ add_edge(m->g,v,current);
+ v->selected=0;
+ break;
+ }
+ }
+ v=v->next;
+ }
+ }
+
+ // now, random populate
+ 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);
+
+ // 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->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 generate_mesh2(mesh *m, int density_128, float length_limit){
+ vertex *v;
+
+ length_limit*=50;
+ length_limit*=length_limit;
+
+ /* first walk a random spanning tree */
+ span_depth_first2(m, m->g->verticies, 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;
+ }
+ deselect_verticies(m->g);
+}
+
+void generate_freeform(graph *g, int order){
+ mesh m;
+ random_seed(order+1);
+ mesh_setup(g, &m, order, 0);
+
+ generate_mesh2(&m,48,5);
+ //arrange_verticies_mesh(g,m.width,m.height);
+
+ 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);
+}
Modified: trunk/planarity/graph_score.c
===================================================================
--- trunk/planarity/graph_score.c 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/graph_score.c 2005-10-03 05:59:50 UTC (rev 10113)
@@ -32,24 +32,28 @@
static char objective_string[160];
-int graphscore_get_score(graph *g){
- int intersection_score = (int)ceil((g->original_intersections- g->active_intersections)*
- g->intersection_mult);
+
+int graphscore_get_raw_score(graph *g){
+ return (int)ceil((g->original_intersections- g->active_intersections)*
+ g->intersection_mult);
+}
+
+int graphscore_get_multiplier(graph *g){
float obj_multiplier = 1;
if(g->objective_lessthan)
if(g->objective > g->active_intersections)
obj_multiplier += (g->objective-g->active_intersections)*g->objective_mult;
- return ceil( intersection_score * obj_multiplier );
+ return ceil( obj_multiplier );
}
+int graphscore_get_score(graph *g){
+ return graphscore_get_raw_score(g)*graphscore_get_multiplier(g);
+}
+
int graphscore_get_bonus(graph *g){
- float obj_multiplier = 1;
-
- if(g->objective_lessthan)
- if(g->objective > g->active_intersections)
- obj_multiplier += (g->objective-g->active_intersections)*g->objective_mult;
+ float obj_multiplier = graphscore_get_multiplier(g);
if(get_timer()< g->original_intersections*g->intersection_mult)
return ceil ((g->original_intersections*g->intersection_mult-get_timer()) * obj_multiplier);
Modified: trunk/planarity/version.h
===================================================================
--- trunk/planarity/version.h 2005-10-02 10:20:49 UTC (rev 10112)
+++ trunk/planarity/version.h 2005-10-03 05:59:50 UTC (rev 10113)
@@ -1,2 +1,2 @@
#define VERSION "$Id$ "
-/* DO NOT EDIT: Automated versioning hack [Sun Oct 2 06:10:44 EDT 2005] */
+/* DO NOT EDIT: Automated versioning hack [Mon Oct 3 01:57:42 EDT 2005] */
More information about the commits
mailing list