planarity/graph_generate.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 #define _GNU_SOURCE
  28 #include <string.h>
  29 #include <stdlib.h>
  30 #include "graph.h"
  31 #include "graph_generate.h"
  32
  33 typedef struct {
  34   char *class;
  35   int instancenum;
  36   char *desc;
  37   void (*gen)(graph *g, int num);
  38   float intersection_mult;
  39   float objective_mult;
  40   int unlock;
  41 } gen_instance;
  42
  43 #define FINITE_LEVELS 79
  44 static gen_instance i_list[FINITE_LEVELS]={
  45
  46   {"simple",   1, "A Small Beginning",                              generate_simple,    1.,4., 1 }, // 1
  47   {"simple",   2, "My First Real Level(tm)",                        generate_simple,    1.,4., 2 }, // 2
  48   {"data",     0, "My First Mission Impossible(tm)",                generate_data,     20.,4., 3 }, // 3
  49   {"simple",   3, "Larger But Not Harder",                          generate_simple,    1.,4., 2 }, // 4
  50   {"crest",    5, "The Trick Is It's Easy",                         generate_crest,     1.,4., 2 }, // 5
  51
  52   {"simple",   4, "Practice Before the Handbasket: One of Three",   generate_simple,    1.,4., 2 }, // 6
  53   {"simple",   5, "Practice Before the Handbasket: Two of Three",   generate_simple,    1.,4., 2 }, // 7
  54   {"simple",   6, "Practice Before the Handbasket: Three of Three", generate_simple,    1.,4., 2 }, // 8
  55
  56   {"sparse",   4, "Tough and Stringy",                              generate_sparse,    1.2,4., 2 }, // 9
  57   {"sparse",   5, "Threadbare",                                     generate_sparse,    1.2,4., 2 }, // 10
  58
  59   {"nasty",    4, "The Bumpy Circles Are Slightly More Difficult",  generate_nasty,    1.5,4., 3 }, // 11
  60   {"nasty",    5, "Three is a Magic Number",                        generate_nasty,    1.5,4., 3 }, // 12
  61   {"nasty",    6, "Last Call For (Sort of) Triangles (For Now)",    generate_nasty,    1.5,4., 3 }, // 13
  62
  63   {"free",     4, "Something Only Subtly Different",                generate_freeform, 1.5,4., 3 }, // 14
  64   {"free",     5, "It Can Roll! Granted, Not Very Well",            generate_freeform, 1.5,4., 3 }, // 15
  65   {"free",     6, "If You Squint, It's a Round Brick",              generate_freeform, 1.5,4., 3 }, // 16
  66
  67   {"rogue",    5, "A New Objective",                                generate_rogue,    1.6,4., 3 }, // 17
  68   {"rogue",    6, "How Low Can You Go?",                            generate_rogue,    1.6,4., 3 }, // 18
  69   {"rogue",    7, "Military Industrial Complex",                    generate_rogue,    1.6,4., 4 }, // 19
  70
  71   {"embed",    4, "The Hexagon is a Subtle and Wily Beast",         generate_embed,     2.,4.,  4 }, // 20
  72   {"embed",    5, "No, Really, The Hexagon Puzzles Are Harder",     generate_embed,     3.,4.,  5 }, // 21
  73   {"embed",    6, "Cursed?  Call 1-800-HEX-A-GON Today!",           generate_embed,     4.,4.,  6 }, // 22
  74
  75   {"simple",   7, "Round but Straightforward",                      generate_simple,    1.,4.,  4 }, // 23
  76
  77   {"shape",    0, "A Star Is Born... Then Solved",                  generate_shape,    1.,2.,  6 }, // 24
  78   {"shape",    1, "Oh, Rain*bows*...",                              generate_shape,    1.,2.,  6 }, // 25
  79   {"shape",    2, "Solve Along the Dotted Line",                    generate_shape,    1.,2.,  6 }, // 26
  80   {"shape",    3, "Using All Available Space",                      generate_shape,    1.,2.,  6 }, // 27
  81   {"shape",    4, "Brainfreeze",                                    generate_shape,    1.,2.,  6 }, // 28
  82   {"shape",    6, "Tropical Storm Invest",                          generate_shape,    1.,2.,  6 }, // 30
  83
  84   {"dense",  8, "Algorithm: Original/Dense (Order: 8)", generate_dense,     .8,1., 5 }, // 31
  85   {"simple", 8, "Algorithm: Original (Order: 8)",       generate_simple,    1.,1., 6 }, // 32
  86   {"sparse", 8, "Algorithm: Original/Sparse (Order: 8)",generate_sparse,   1.2,1., 7 }, // 33
  87   {"nasty",  8, "Algorithm: Nasty (Order: 8)",          generate_nasty,    1.5,1., 8 }, // 34
  88   {"free",   8, "Algorithm: Freeform/4 (Order: 8)",     generate_freeform, 1.5,1., 9 }, // 35
  89   {"rogue",  8, "Algorithm: Rogue (Order: 8)",          generate_rogue,    1.6,1.,10 }, // 36
  90   {"embed",  8, "Algorithm: Embed (Order: 8)",          generate_embed,     4.,1.,10 }, // 37
  91   {"shape",  7, "Operator",                             generate_shape,     1.,2.,10 }, // 38
  92
  93   {"dense",  9, "Algorithm: Original/Dense (Order: 9)", generate_dense,     .8,1., 5 }, // 39
  94   {"simple", 9, "Algorithm: Original (Order: 9)",       generate_simple,    1.,1., 6 }, // 40
  95   {"sparse", 9, "Algorithm: Original/Sparse (Order: 9)",generate_sparse,   1.2,1., 7 }, // 41
  96   {"nasty",  9, "Algorithm: Nasty (Order: 9)",          generate_nasty,    1.5,1., 8 }, // 42
  97   {"free",   9, "Algorithm: Freeform/4 (Order: 9)",     generate_freeform, 1.5,1., 9 }, // 43
  98   {"rogue",  9, "Algorithm: Rogue (Order: 9)",          generate_rogue,    1.6,1.,10 }, // 44
  99   {"embed",  9, "Algorithm: Embed (Order: 9)",          generate_embed,     4.,1.,10 }, // 45
 100   {"shape",  8, "The Inside Is Pointy",                 generate_shape,     1.,2.,10 }, // 46
 101
 102   {"dense", 10, "Algorithm: Original/Dense (Order: 10)", generate_dense,     .8,1., 5 }, // 47
 103   {"simple",10, "Algorithm: Original (Order: 10)",       generate_simple,    1.,1., 6 }, // 48
 104   {"sparse",10, "Algorithm: Original/Sparse (Order: 10)",generate_sparse,   1.2,1., 7 }, // 49
 105   {"nasty", 10, "Algorithm: Nasty (Order: 10)",          generate_nasty,    1.5,1., 8 }, // 50
 106   {"free",  10, "Algorithm: Freeform/4 (Order: 10)",     generate_freeform, 1.5,1., 9 }, // 51
 107   {"rogue", 10, "Algorithm: Rogue (Order: 10)",          generate_rogue,    1.6,1.,10 }, // 52
 108   {"embed", 10, "Algorithm: Embed (Order: 10)",          generate_embed,     4.,1.,10 }, // 53
 109   {"shape",  9, "Riches and Good Luck",                  generate_shape,     1.,2.,10 }, // 54
 110
 111   {"dense", 11, "Algorithm: Original/Dense (Order: 11)", generate_dense,     .8,1., 5 }, // 55
 112   {"simple",11, "Algorithm: Original (Order: 11)",       generate_simple,    1.,1., 6 }, // 56
 113   {"sparse",11, "Algorithm: Original/Sparse (Order: 11)",generate_sparse,   1.2,1., 7 }, // 57
 114   {"nasty", 11, "Algorithm: Nasty (Order: 11)",          generate_nasty,    1.5,1., 8 }, // 58
 115   {"free",  11, "Algorithm: Freeform/4 (Order: 11)",     generate_freeform, 1.5,1., 9 }, // 59
 116   {"rogue", 11, "Algorithm: Rogue (Order: 11)",          generate_rogue,    1.6,1.,10 }, // 60
 117   {"embed", 11, "Algorithm: Embed (Order: 11)",          generate_embed,     4.,1.,10 }, // 61
 118   {"shape", 10, "Mmmm... Doughnut",                      generate_shape,     1.,2.,10 }, // 62
 119
 120   {"dense", 12, "Algorithm: Original/Dense (Order: 12)", generate_dense,     .8,1., 5 }, // 63
 121   {"simple",12, "Algorithm: Original (Order: 12)",       generate_simple,    1.,1., 6 }, // 64
 122   {"sparse",12, "Algorithm: Original/Sparse (Order: 12)",generate_sparse,   1.2,1., 7 }, // 65
 123   {"nasty", 12, "Algorithm: Nasty (Order: 12)",          generate_nasty,    1.5,1., 8 }, // 66
 124   {"free",  12, "Algorithm: Freeform/4 (Order: 12)",     generate_freeform, 1.5,1., 9 }, // 67
 125   {"rogue", 12, "Algorithm: Rogue (Order: 12)",          generate_rogue,    1.6,1.,10 }, // 68
 126   {"embed", 12, "Algorithm: Embed (Order: 12)",          generate_embed,     4.,1.,10 }, // 69
 127   {"shape", 11, "Quick and Dirty, or Slow and Steady",   generate_shape,     1.,1.,10 }, // 70
 128   {"shape",  5, "Little Fluffy Clouds",                   generate_shape,    1.,2., 6 }, // 29
 129
 130   {"dense", 13, "Algorithm: Original/Dense (Order: 13)", generate_dense,     .8,1., 5 }, // 71
 131   {"simple",13, "Algorithm: Original (Order: 13)",       generate_simple,    1.,1., 6 }, // 72
 132   {"sparse",13, "Algorithm: Original/Sparse (Order: 13)",generate_sparse,   1.2,1., 7 }, // 73
 133   {"nasty", 13, "Algorithm: Nasty (Order: 13)",          generate_nasty,    1.5,1., 8 }, // 74
 134   {"free",  13, "Algorithm: Freeform/4 (Order: 13)",     generate_freeform, 1.5,1., 9 }, // 75
 135   {"rogue", 13, "Algorithm: Rogue (Order: 13)",          generate_rogue,    1.6,1.,10 }, // 76
 136   {"embed", 13, "Algorithm: Embed (Order: 13)",          generate_embed,     4.,1.,10 }, // 77
 137   {"shape", 12, "A Sudden Urge To Go Shopping",          generate_shape,     1.,1.,10 }, // 78
 138   {"shape", 13, "Sweet Reward",                          generate_shape,     1.,1.,10 }, // 79
 139
 140 };
 141
 142 #define LOOP_LEVELS 8
 143 static gen_instance i_list_loop[LOOP_LEVELS]={
 144   {"dense", 14, "Algorithm: Original/Dense (Order: %d)", generate_dense,     .8,1., 5 }, // n
 145   {"simple",14, "Algorithm: Original (Order: %d)",       generate_simple,    1.,1., 6 }, // n
 146   {"sparse",14, "Algorithm: Original/Sparse (Order: %d)",generate_sparse,   1.2,1., 7 }, // n
 147   {"nasty", 14, "Algorithm: Nasty (Order: %d)",          generate_nasty,    1.5,1., 8 }, // n
 148   {"free",  14, "Algorithm: Freeform/4 (Order: %d)",     generate_freeform, 1.5,1., 9 }, // n
 149   {"rogue", 14, "Algorithm: Rogue (Order: %d)",          generate_rogue,    1.6,1.,10 }, // n
 150   {"embed", 14, "Algorithm: Embed (Order: %d)",          generate_embed,     4.,1.,10 }, // n
 151   {"shape", 14, "Algorithm: Region (Order: %d)",         generate_shape,     1.,2.,10 },
 152 };
 153
 154 int generate_find_number(char *id){
 155   int i;
 156   char buffer[160];
 157
 158   for(i=0;i<FINITE_LEVELS;i++){
 159     snprintf(buffer,160,"%s %d",i_list[i].class,i_list[i].instancenum);
 160     if(!strcmp(id,buffer))
 161       return i;
 162   }
 163
 164   {
 165     char *arg = strchr(id,' ');
 166     if(arg){
 167       unsigned int len = arg-id;
 168
 169       for(i=0;i<LOOP_LEVELS;i++){
 170         if(strlen(i_list_loop[i].class)==len &&
 171            !strncmp(i_list_loop[i].class,id,len)){
 172
 173           // class match, determine the level number
 174           int order = atoi(arg+1);
 175           return FINITE_LEVELS + (order - i_list_loop[i].instancenum)*LOOP_LEVELS + i;
 176
 177
 178         }
 179       }
 180     }
 181   }
 182
 183   return -1;
 184 }
 185
 186 int generate_get_meta(int num, graphmeta *gm){
 187   if(num<FINITE_LEVELS){
 188
 189     /* part of the finite list */
 190
 191     gm->num = num;
 192     gm->desc = i_list[num].desc;
 193     gm->unlock_plus = i_list[num].unlock+1;
 194     if(asprintf(&gm->id,"%s %d",i_list[num].class,i_list[num].instancenum)==-1){
 195       fprintf(stderr,"Couldn't allocate memory for level name.\n");
 196       return -1;
 197     }
 198     return 0;
 199   }else{
 200
 201     /* past the finite list; one of the loop levels */
 202     int classnum = (num - FINITE_LEVELS) % LOOP_LEVELS;
 203     int ordernum = (num - FINITE_LEVELS) / LOOP_LEVELS +
 204       i_list_loop[classnum].instancenum;
 205
 206     gm->num = num;
 207     gm->unlock_plus = i_list_loop[classnum].unlock+1;
 208     if(asprintf(&gm->desc,i_list_loop[classnum].desc,ordernum)==-1){
 209       fprintf(stderr,"Couldn't allocate memory for level desciption.\n");
 210       return -1;
 211     }
 212
 213     if(asprintf(&gm->id,"%s %d",i_list_loop[classnum].class,ordernum)==-1){
 214       fprintf(stderr,"Couldn't allocate memory for level name.\n");
 215       return -1;
 216     }
 217
 218     return 0;
 219
 220   }
 221 }
 222
 223 void generate_board(graph *g,int num){
 224   gen_instance *gi;
 225   if(num<FINITE_LEVELS){
 226     gi = i_list+num;
 227
 228     gi->gen(g,gi->instancenum);
 229   }else{
 230     int classnum = (num - FINITE_LEVELS) % LOOP_LEVELS;
 231     int ordernum = (num - FINITE_LEVELS) / LOOP_LEVELS +
 232       i_list_loop[classnum].instancenum;
 233
 234     gi = i_list_loop+classnum;
 235     gi->gen(g,ordernum);
 236   }
 237
 238   // clear out overloaded flags
 239   {
 240     vertex *v = g->verticies;
 241     while(v){
 242       v->active=0;
 243       v->selected=0;
 244       v->grabbed=0;
 245       v=v->next;
 246     }
 247   }
 248
 249   g->objective_mult = gi->objective_mult;
 250   g->intersection_mult = gi->intersection_mult;
 251 }