git.hungrycats.org Git - xscreensaver/blob - hacks/glx/queens.c

   1 /*
   2  * queens - solves n queens problem, displays
   3  * i make no claims that this is an optimal solution to the problem,
   4  * good enough for xss
   5  * hacked from glchess
   6  *
   7  * version 1.0 - May 10, 2002
   8  *
   9  * Copyright (C) 2002 Blair Tennessy (tennessy@cs.ubc.ca)
  10  *
  11  * Permission to use, copy, modify, distribute, and sell this software and its
  12  * documentation for any purpose is hereby granted without fee, provided that
  13  * the above copyright notice appear in all copies and that both that
  14  * copyright notice and this permission notice appear in supporting
  15  * documentation.  No representations are made about the suitability of this
  16  * software for any purpose.  It is provided "as is" without express or
  17  * implied warranty.
  18  */
  19
  20 #ifdef STANDALONE
  21 #define DEFAULTS       "*delay:       20000 \n" \
  22                        "*showFPS:     False \n" \
  23                        "*wireframe:   False \n" \
  24
  25 # define refresh_queens 0
  26 # include "xlockmore.h"
  27
  28 #else
  29 # include "xlock.h"
  30 #endif
  31
  32 #ifdef USE_GL
  33
  34 #include "gltrackball.h"
  35
  36 #undef countof
  37 #define countof(x) (sizeof((x))/sizeof((*x)))
  38
  39 static XrmOptionDescRec opts[] = {
  40   {"+rotate", ".queens.rotate", XrmoptionNoArg, "false" },
  41   {"-rotate", ".queens.rotate", XrmoptionNoArg, "true" },
  42   {"+flat", ".queens.flat", XrmoptionNoArg, "false" },
  43   {"-flat", ".queens.flat", XrmoptionNoArg, "true" },
  44 };
  45
  46 static int rotate, wire, clearbits, flat;
  47
  48 static argtype vars[] = {
  49   {&rotate, "rotate", "Rotate", "True",  t_Bool},
  50   {&flat,   "flat",   "Flat",   "False", t_Bool},
  51 };
  52
  53 ENTRYPOINT ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
  54
  55 #ifdef USE_MODULES
  56 ModStruct   queens_description =
  57 {"queens", "init_queens", "draw_queens", "release_queens",
  58  "draw_queens", "init_queens", NULL, &queens_opts,
  59  1000, 1, 2, 1, 4, 1.0, "",
  60  "Queens", 0, NULL};
  61
  62 #endif
  63
  64 #define NONE 0
  65 #define QUEEN 1
  66 #define MINBOARD 5
  67 #define MAXBOARD 10
  68 #define COLORSETS 5
  69
  70 typedef struct {
  71   GLXContext *glx_context;
  72   Window window;
  73   trackball_state *trackball;
  74   Bool button_down_p;
  75   GLfloat position[4];
  76
  77   int board[MAXBOARD][MAXBOARD];
  78   int steps, colorset, BOARDSIZE;
  79   double theta;
  80   int queen_polys;
  81
  82 } Queenscreen;
  83
  84 static Queenscreen *qss = NULL;
  85
  86 /* definition of white/black colors */
  87 static const GLfloat colors[COLORSETS][2][3] =
  88   {
  89     {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
  90     {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
  91     {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
  92     {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
  93     {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
  94   };
  95
  96 ENTRYPOINT Bool
  97 queens_handle_event (ModeInfo *mi, XEvent *event)
  98 {
  99   Queenscreen *qs = &qss[MI_SCREEN(mi)];
 100
 101   if (event->xany.type == ButtonPress &&
 102       event->xbutton.button == Button1)
 103     {
 104       qs->button_down_p = True;
 105       gltrackball_start (qs->trackball,
 106                          event->xbutton.x, event->xbutton.y,
 107                          MI_WIDTH (mi), MI_HEIGHT (mi));
 108       return True;
 109     }
 110   else if (event->xany.type == ButtonRelease &&
 111            event->xbutton.button == Button1)
 112     {
 113       qs->button_down_p = False;
 114       return True;
 115     }
 116   else if (event->xany.type == ButtonPress &&
 117            (event->xbutton.button == Button4 ||
 118             event->xbutton.button == Button5 ||
 119             event->xbutton.button == Button6 ||
 120             event->xbutton.button == Button7))
 121     {
 122       gltrackball_mousewheel (qs->trackball, event->xbutton.button, 5,
 123                               !event->xbutton.state);
 124       return True;
 125     }
 126   else if (event->xany.type == MotionNotify &&
 127            qs->button_down_p)
 128     {
 129       gltrackball_track (qs->trackball,
 130                          event->xmotion.x, event->xmotion.y,
 131                          MI_WIDTH (mi), MI_HEIGHT (mi));
 132       return True;
 133     }
 134
 135   return False;
 136 }
 137
 138
 139
 140 /* returns true if placing a queen on column c causes a conflict */
 141 static int conflictsCols(Queenscreen *qs, int c)
 142 {
 143   int i;
 144
 145   for(i = 0; i < qs->BOARDSIZE; ++i)
 146     if(qs->board[i][c])
 147       return 1;
 148
 149   return 0;
 150 }
 151
 152 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 153 static int conflictsDiag(Queenscreen *qs, int r, int c)
 154 {
 155   int i;
 156
 157   /* positive slope */
 158   int n = r < c ? r : c;
 159   for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
 160     if(qs->board[r-n+i][c-n+i])
 161       return 1;
 162
 163   /* negative slope */
 164   n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
 165   for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
 166     if(qs->board[r-n+i][c+n-i])
 167       return 1;
 168
 169   return 0;
 170 }
 171
 172 /* returns true if placing a queen at (r,c) causes a conflict */
 173 static int conflicts(Queenscreen *qs, int r, int c)
 174 {
 175   return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
 176 }
 177
 178 /* clear board */
 179 static void blank(Queenscreen *qs)
 180 {
 181   int i, j;
 182
 183   for(i = 0; i < MAXBOARD; ++i)
 184     for(j = 0; j < MAXBOARD; ++j)
 185       qs->board[i][j] = NONE;
 186 }
 187
 188 /* recursively determine solution */
 189 static int findSolution(Queenscreen *qs, int row, int col)
 190 {
 191   if(row == qs->BOARDSIZE)
 192     return 1;
 193
 194   while(col < qs->BOARDSIZE) {
 195     if(!conflicts(qs, row, col)) {
 196       qs->board[row][col] = 1;
 197
 198       if(findSolution(qs, row+1, 0))
 199         return 1;
 200
 201       qs->board[row][col] = 0;
 202     }
 203
 204     ++col;
 205   }
 206
 207   return 0;
 208 }
 209
 210 /** driver for finding solution */
 211 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
 212
 213 /* lighting variables */
 214 static const GLfloat front_shininess[] = {60.0};
 215 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
 216 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
 217 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
 218
 219 /* configure lighting */
 220 static void setup_lights(Queenscreen *qs)
 221 {
 222
 223   /* setup twoside lighting */
 224   glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
 225   glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
 226   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 227   glEnable(GL_LIGHTING);
 228   glEnable(GL_LIGHT0);
 229
 230   /* setup material properties */
 231   glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
 232   glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
 233
 234   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 235 }
 236
 237 #define    checkImageWidth 8
 238 #define    checkImageHeight 8
 239 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
 240
 241 /* return alpha value for fading */
 242 static GLfloat findAlpha(Queenscreen *qs)
 243 {
 244   return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
 245 }
 246
 247 /* draw pieces */
 248 static int drawPieces(Queenscreen *qs)
 249 {
 250   int i, j;
 251   int polys = 0;
 252
 253   for(i = 0; i < qs->BOARDSIZE; ++i) {
 254     for(j = 0; j < qs->BOARDSIZE; ++j) {
 255       if(qs->board[i][j]) {
 256         glColor3fv(colors[qs->colorset][i%2]);
 257         glCallList(QUEEN);
 258         polys += qs->queen_polys;
 259       }
 260
 261       glTranslatef(1.0, 0.0, 0.0);
 262     }
 263
 264     glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
 265   }
 266   return polys;
 267 }
 268
 269 /** reflectionboard */
 270 static int draw_reflections(Queenscreen *qs)
 271 {
 272   int i, j;
 273   int polys = 0;
 274
 275   glEnable(GL_STENCIL_TEST);
 276   glStencilFunc(GL_ALWAYS, 1, 1);
 277   glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
 278   glColorMask(0,0,0,0);
 279   glDisable(GL_CULL_FACE);
 280
 281   glDisable(GL_DEPTH_TEST);
 282   glBegin(GL_QUADS);
 283
 284   /* only draw white squares */
 285   for(i = 0; i < qs->BOARDSIZE; ++i) {
 286     for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
 287       glVertex3f(i, 0.0, j + 1.0);
 288       glVertex3f(i + 1.0, 0.0, j + 1.0);
 289       glVertex3f(i + 1.0, 0.0, j);
 290       glVertex3f(i, 0.0, j);
 291       polys++;
 292     }
 293   }
 294   glEnd();
 295   glEnable(GL_DEPTH_TEST);
 296
 297   glColorMask(1, 1, 1, 1);
 298   glStencilFunc(GL_EQUAL, 1, 1);
 299   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 300
 301   glPushMatrix();
 302   glScalef(1.0, -1.0, 1.0);
 303   glTranslatef(0.5, 0.001, 0.5);
 304   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 305   polys += drawPieces(qs);
 306   glPopMatrix();
 307   glDisable(GL_STENCIL_TEST);
 308
 309   /* replace lights */
 310   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 311
 312   glEnable(GL_CULL_FACE);
 313   glCullFace(GL_BACK);
 314   glColorMask(1,1,1,1);
 315   return polys;
 316 }
 317
 318 /* draw board */
 319 static int drawBoard(Queenscreen *qs)
 320 {
 321   int i, j;
 322   int polys = 0;
 323
 324   glBegin(GL_QUADS);
 325
 326   for(i = 0; i < qs->BOARDSIZE; ++i)
 327     for(j = 0; j < qs->BOARDSIZE; ++j) {
 328       int par = (i-j+qs->BOARDSIZE)%2;
 329       glColor4f(colors[qs->colorset][par][0],
 330                 colors[qs->colorset][par][1],
 331                 colors[qs->colorset][par][2],
 332                 0.70);
 333       glNormal3f(0.0, 1.0, 0.0);
 334       glVertex3f(i, 0.0, j + 1.0);
 335       glVertex3f(i + 1.0, 0.0, j + 1.0);
 336       glVertex3f(i + 1.0, 0.0, j);
 337       glVertex3f(i, 0.0, j);
 338       polys++;
 339     }
 340
 341   glEnd();
 342   return polys;
 343 }
 344
 345 static int display(Queenscreen *qs)
 346 {
 347   int polys = 0;
 348   glClear(clearbits);
 349
 350   glMatrixMode(GL_MODELVIEW);
 351   glLoadIdentity();
 352
 353   /* setup light attenuation */
 354   glEnable(GL_COLOR_MATERIAL);
 355   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
 356   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
 357
 358   /** setup perspective */
 359   glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
 360   glRotatef(30.0, 1.0, 0.0, 0.0);
 361   gltrackball_rotate (qs->trackball);
 362   glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
 363   glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
 364
 365   /* find light positions */
 366   qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
 367   qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
 368   qs->position[1] = 6.0;
 369
 370   if(!wire) {
 371     glEnable(GL_LIGHTING);
 372     glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 373     glEnable(GL_LIGHT0);
 374   }
 375
 376   /* draw reflections */
 377   if(!wire) {
 378     polys += draw_reflections(qs);
 379     glEnable(GL_BLEND);
 380   }
 381   polys += drawBoard(qs);
 382   if(!wire)
 383     glDisable(GL_BLEND);
 384
 385   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
 386
 387   glTranslatef(0.5, 0.0, 0.5);
 388   polys += drawPieces(qs);
 389
 390   /* rotate camera */
 391   if(!qs->button_down_p)
 392     qs->theta += .002;
 393
 394   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 395   if(++qs->steps == 1024) {
 396     qs->steps = 0;
 397     blank(qs);
 398     qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 399     qs->colorset = (qs->colorset+1)%COLORSETS;
 400     go(qs);
 401   }
 402   return polys;
 403 }
 404
 405 static const GLfloat spidermodel[][3] =
 406   {
 407     {0.48, 0.48, 0.22},
 408     {0.48, 0.34, 0.18},
 409     {0.34, 0.34, 0.10},
 410     {0.34, 0.18, 0.30},
 411     {0.18, 0.14, 0.38},
 412     {0.14, 0.29, 0.01},
 413     {0.29, 0.18, 0.18},
 414     {0.18, 0.18, 0.16},
 415     {0.18, 0.20, 0.26},
 416     {0.20, 0.27, 0.14},
 417     {0.27, 0.24, 0.08},
 418     {0.24, 0.17, 0.00},
 419     {0.17, 0.095, 0.08},
 420     {0.095, 0.07, 0.00},
 421     {0.07, 0.00, 0.12},
 422   };
 423
 424
 425 #define EPSILON 0.001
 426
 427 /** draws cylindermodel */
 428 static int draw_model(int chunks, const GLfloat model[][3], int r)
 429 {
 430   int i = 0;
 431   int polys = 0;
 432   GLUquadricObj *quadric = gluNewQuadric();
 433   glPushMatrix();
 434   glRotatef(-90.0, 1.0, 0.0, 0.0);
 435
 436   for(i = 0; i < chunks; ++i) {
 437     if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
 438       gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 439       polys += r;
 440     }
 441     glTranslatef(0.0, 0.0, model[i][2]);
 442   }
 443
 444   glPopMatrix();
 445   return polys;
 446 }
 447
 448 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
 449 {
 450   GLfloat h = (GLfloat) height / (GLfloat) width;
 451   glViewport(0,0, width, height);
 452   glMatrixMode(GL_PROJECTION);
 453   glLoadIdentity();
 454   gluPerspective(45, 1/h, 2.0, 30.0);
 455   glMatrixMode(GL_MODELVIEW);
 456 }
 457
 458 ENTRYPOINT void init_queens(ModeInfo *mi)
 459 {
 460   int screen = MI_SCREEN(mi);
 461   Queenscreen *qs;
 462   wire = MI_IS_WIREFRAME(mi);
 463
 464   if(!qss &&
 465      !(qss = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 466     return;
 467
 468   qs = &qss[screen];
 469   qs->window = MI_WINDOW(mi);
 470   qs->trackball = gltrackball_init ();
 471
 472   qs->BOARDSIZE = 8; /* 8 cuz its classic */
 473
 474   if((qs->glx_context = init_GL(mi)))
 475     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 476   else
 477     MI_CLEARWINDOW(mi);
 478
 479   glClearColor(0.0, 0.0, 0.0, 0.0);
 480   glNewList(QUEEN, GL_COMPILE);
 481   qs->queen_polys = draw_model(countof(spidermodel), spidermodel, 24);
 482   glEndList();
 483
 484   if(flat)
 485     glShadeModel(GL_FLAT);
 486
 487   clearbits = GL_COLOR_BUFFER_BIT;
 488
 489   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 490   glEnable(GL_COLOR_MATERIAL);
 491
 492   if(!wire) {
 493     setup_lights(qs);
 494     glEnable(GL_DEPTH_TEST);
 495     clearbits |= GL_DEPTH_BUFFER_BIT;
 496     clearbits |= GL_STENCIL_BUFFER_BIT;
 497     glEnable(GL_CULL_FACE);
 498     glCullFace(GL_BACK);
 499   }
 500   else
 501     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 502
 503   /* find a solution */
 504   go(qs);
 505 }
 506
 507 ENTRYPOINT void draw_queens(ModeInfo *mi)
 508 {
 509   Queenscreen *qs = &qss[MI_SCREEN(mi)];
 510   Window w = MI_WINDOW(mi);
 511   Display *disp = MI_DISPLAY(mi);
 512
 513   if(!qs->glx_context)
 514     return;
 515
 516   glXMakeCurrent(disp, w, *(qs->glx_context));
 517
 518   mi->polygon_count = display(qs);
 519
 520   if(mi->fps_p) do_fps(mi);
 521   glFinish();
 522   glXSwapBuffers(disp, w);
 523 }
 524
 525 ENTRYPOINT void release_queens(ModeInfo *mi)
 526 {
 527   if(qss)
 528     free((void *) qss);
 529   qss = 0;
 530
 531   FreeAllGL(mi);
 532 }
 533
 534 XSCREENSAVER_MODULE ("Queens", queens)
 535
 536 #endif