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
  81 } Queenscreen;
  82
  83 static Queenscreen *qss = NULL;
  84
  85 /* definition of white/black colors */
  86 static const GLfloat colors[COLORSETS][2][3] =
  87   {
  88     {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
  89     {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
  90     {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
  91     {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
  92     {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
  93   };
  94
  95 ENTRYPOINT Bool
  96 queens_handle_event (ModeInfo *mi, XEvent *event)
  97 {
  98   Queenscreen *qs = &qss[MI_SCREEN(mi)];
  99
 100   if (event->xany.type == ButtonPress &&
 101       event->xbutton.button == Button1)
 102     {
 103       qs->button_down_p = True;
 104       gltrackball_start (qs->trackball,
 105                          event->xbutton.x, event->xbutton.y,
 106                          MI_WIDTH (mi), MI_HEIGHT (mi));
 107       return True;
 108     }
 109   else if (event->xany.type == ButtonRelease &&
 110            event->xbutton.button == Button1)
 111     {
 112       qs->button_down_p = False;
 113       return True;
 114     }
 115   else if (event->xany.type == ButtonPress &&
 116            (event->xbutton.button == Button4 ||
 117             event->xbutton.button == Button5))
 118     {
 119       gltrackball_mousewheel (qs->trackball, event->xbutton.button, 5,
 120                               !event->xbutton.state);
 121       return True;
 122     }
 123   else if (event->xany.type == MotionNotify &&
 124            qs->button_down_p)
 125     {
 126       gltrackball_track (qs->trackball,
 127                          event->xmotion.x, event->xmotion.y,
 128                          MI_WIDTH (mi), MI_HEIGHT (mi));
 129       return True;
 130     }
 131
 132   return False;
 133 }
 134
 135
 136
 137 /* returns true if placing a queen on column c causes a conflict */
 138 static int conflictsCols(Queenscreen *qs, int c)
 139 {
 140   int i;
 141
 142   for(i = 0; i < qs->BOARDSIZE; ++i)
 143     if(qs->board[i][c])
 144       return 1;
 145
 146   return 0;
 147 }
 148
 149 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 150 static int conflictsDiag(Queenscreen *qs, int r, int c)
 151 {
 152   int i;
 153
 154   /* positive slope */
 155   int n = r < c ? r : c;
 156   for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
 157     if(qs->board[r-n+i][c-n+i])
 158       return 1;
 159
 160   /* negative slope */
 161   n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
 162   for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
 163     if(qs->board[r-n+i][c+n-i])
 164       return 1;
 165
 166   return 0;
 167 }
 168
 169 /* returns true if placing a queen at (r,c) causes a conflict */
 170 static int conflicts(Queenscreen *qs, int r, int c)
 171 {
 172   return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
 173 }
 174
 175 /* clear board */
 176 static void blank(Queenscreen *qs)
 177 {
 178   int i, j;
 179
 180   for(i = 0; i < MAXBOARD; ++i)
 181     for(j = 0; j < MAXBOARD; ++j)
 182       qs->board[i][j] = NONE;
 183 }
 184
 185 /* recursively determine solution */
 186 static int findSolution(Queenscreen *qs, int row, int col)
 187 {
 188   if(row == qs->BOARDSIZE)
 189     return 1;
 190
 191   while(col < qs->BOARDSIZE) {
 192     if(!conflicts(qs, row, col)) {
 193       qs->board[row][col] = 1;
 194
 195       if(findSolution(qs, row+1, 0))
 196         return 1;
 197
 198       qs->board[row][col] = 0;
 199     }
 200
 201     ++col;
 202   }
 203
 204   return 0;
 205 }
 206
 207 /** driver for finding solution */
 208 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
 209
 210 /* lighting variables */
 211 static const GLfloat front_shininess[] = {60.0};
 212 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
 213 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
 214 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
 215
 216 /* configure lighting */
 217 static void setup_lights(Queenscreen *qs)
 218 {
 219
 220   /* setup twoside lighting */
 221   glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
 222   glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
 223   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 224   glEnable(GL_LIGHTING);
 225   glEnable(GL_LIGHT0);
 226
 227   /* setup material properties */
 228   glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
 229   glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
 230
 231   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 232 }
 233
 234 #define    checkImageWidth 8
 235 #define    checkImageHeight 8
 236 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
 237
 238 /* return alpha value for fading */
 239 static GLfloat findAlpha(Queenscreen *qs)
 240 {
 241   return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
 242 }
 243
 244 /* draw pieces */
 245 static void drawPieces(Queenscreen *qs)
 246 {
 247   int i, j;
 248
 249   for(i = 0; i < qs->BOARDSIZE; ++i) {
 250     for(j = 0; j < qs->BOARDSIZE; ++j) {
 251       if(qs->board[i][j]) {
 252         glColor3fv(colors[qs->colorset][i%2]);
 253         glCallList(QUEEN);
 254       }
 255
 256       glTranslatef(1.0, 0.0, 0.0);
 257     }
 258
 259     glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
 260   }
 261 }
 262
 263 /** reflectionboard */
 264 static void draw_reflections(Queenscreen *qs)
 265 {
 266   int i, j;
 267
 268   glEnable(GL_STENCIL_TEST);
 269   glStencilFunc(GL_ALWAYS, 1, 1);
 270   glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
 271   glColorMask(0,0,0,0);
 272   glDisable(GL_CULL_FACE);
 273
 274   glDisable(GL_DEPTH_TEST);
 275   glBegin(GL_QUADS);
 276
 277   /* only draw white squares */
 278   for(i = 0; i < qs->BOARDSIZE; ++i) {
 279     for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
 280       glVertex3f(i, 0.0, j + 1.0);
 281       glVertex3f(i + 1.0, 0.0, j + 1.0);
 282       glVertex3f(i + 1.0, 0.0, j);
 283       glVertex3f(i, 0.0, j);
 284     }
 285   }
 286   glEnd();
 287   glEnable(GL_DEPTH_TEST);
 288
 289   glColorMask(1, 1, 1, 1);
 290   glStencilFunc(GL_EQUAL, 1, 1);
 291   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 292
 293   glPushMatrix();
 294   glScalef(1.0, -1.0, 1.0);
 295   glTranslatef(0.5, 0.001, 0.5);
 296   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 297   drawPieces(qs);
 298   glPopMatrix();
 299   glDisable(GL_STENCIL_TEST);
 300
 301   /* replace lights */
 302   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 303
 304   glEnable(GL_CULL_FACE);
 305   glCullFace(GL_BACK);
 306   glColorMask(1,1,1,1);
 307 }
 308
 309 /* draw board */
 310 static void drawBoard(Queenscreen *qs)
 311 {
 312   int i, j;
 313
 314   glBegin(GL_QUADS);
 315
 316   for(i = 0; i < qs->BOARDSIZE; ++i)
 317     for(j = 0; j < qs->BOARDSIZE; ++j) {
 318       int par = (i-j+qs->BOARDSIZE)%2;
 319       glColor4f(colors[qs->colorset][par][0],
 320                 colors[qs->colorset][par][1],
 321                 colors[qs->colorset][par][2],
 322                 0.70);
 323       glNormal3f(0.0, 1.0, 0.0);
 324       glVertex3f(i, 0.0, j + 1.0);
 325       glVertex3f(i + 1.0, 0.0, j + 1.0);
 326       glVertex3f(i + 1.0, 0.0, j);
 327       glVertex3f(i, 0.0, j);
 328     }
 329
 330   glEnd();
 331 }
 332
 333 static void display(Queenscreen *qs)
 334 {
 335   glClear(clearbits);
 336
 337   glMatrixMode(GL_MODELVIEW);
 338   glLoadIdentity();
 339
 340   /* setup light attenuation */
 341   glEnable(GL_COLOR_MATERIAL);
 342   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
 343   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
 344
 345   /** setup perspective */
 346   glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
 347   glRotatef(30.0, 1.0, 0.0, 0.0);
 348   gltrackball_rotate (qs->trackball);
 349   glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
 350   glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
 351
 352   /* find light positions */
 353   qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
 354   qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
 355   qs->position[1] = 6.0;
 356
 357   if(!wire) {
 358     glEnable(GL_LIGHTING);
 359     glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 360     glEnable(GL_LIGHT0);
 361   }
 362
 363   /* draw reflections */
 364   if(!wire) {
 365     draw_reflections(qs);
 366     glEnable(GL_BLEND);
 367   }
 368   drawBoard(qs);
 369   if(!wire)
 370     glDisable(GL_BLEND);
 371
 372   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
 373
 374   glTranslatef(0.5, 0.0, 0.5);
 375   drawPieces(qs);
 376
 377   /* rotate camera */
 378   if(!qs->button_down_p)
 379     qs->theta += .002;
 380
 381   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 382   if(++qs->steps == 1024) {
 383     qs->steps = 0;
 384     blank(qs);
 385     qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 386     qs->colorset = (qs->colorset+1)%COLORSETS;
 387     go(qs);
 388   }
 389 }
 390
 391 static const GLfloat spidermodel[][3] =
 392   {
 393     {0.48, 0.48, 0.22},
 394     {0.48, 0.34, 0.18},
 395     {0.34, 0.34, 0.10},
 396     {0.34, 0.18, 0.30},
 397     {0.18, 0.14, 0.38},
 398     {0.14, 0.29, 0.01},
 399     {0.29, 0.18, 0.18},
 400     {0.18, 0.18, 0.16},
 401     {0.18, 0.20, 0.26},
 402     {0.20, 0.27, 0.14},
 403     {0.27, 0.24, 0.08},
 404     {0.24, 0.17, 0.00},
 405     {0.17, 0.095, 0.08},
 406     {0.095, 0.07, 0.00},
 407     {0.07, 0.00, 0.12},
 408   };
 409
 410
 411 #define EPSILON 0.001
 412
 413 /** draws cylindermodel */
 414 static void draw_model(int chunks, const GLfloat model[][3], int r)
 415 {
 416   int i = 0;
 417   GLUquadricObj *quadric = gluNewQuadric();
 418   glPushMatrix();
 419   glRotatef(-90.0, 1.0, 0.0, 0.0);
 420
 421   for(i = 0; i < chunks; ++i) {
 422     if(model[i][0] > EPSILON || model[i][1] > EPSILON)
 423       gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 424     glTranslatef(0.0, 0.0, model[i][2]);
 425   }
 426
 427   glPopMatrix();
 428 }
 429
 430 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
 431 {
 432   GLfloat h = (GLfloat) height / (GLfloat) width;
 433   glViewport(0,0, width, height);
 434   glMatrixMode(GL_PROJECTION);
 435   glLoadIdentity();
 436   gluPerspective(45, 1/h, 2.0, 30.0);
 437   glMatrixMode(GL_MODELVIEW);
 438 }
 439
 440 ENTRYPOINT void init_queens(ModeInfo *mi)
 441 {
 442   int screen = MI_SCREEN(mi);
 443   Queenscreen *qs;
 444   wire = MI_IS_WIREFRAME(mi);
 445
 446   if(!qss &&
 447      !(qss = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 448     return;
 449
 450   qs = &qss[screen];
 451   qs->window = MI_WINDOW(mi);
 452   qs->trackball = gltrackball_init ();
 453
 454   qs->BOARDSIZE = 8; /* 8 cuz its classic */
 455
 456   if((qs->glx_context = init_GL(mi)))
 457     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 458   else
 459     MI_CLEARWINDOW(mi);
 460
 461   glClearColor(0.0, 0.0, 0.0, 0.0);
 462   glNewList(QUEEN, GL_COMPILE);
 463   draw_model(countof(spidermodel), spidermodel, 24);
 464   glEndList();
 465
 466   if(flat)
 467     glShadeModel(GL_FLAT);
 468
 469   clearbits = GL_COLOR_BUFFER_BIT;
 470
 471   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 472   glEnable(GL_COLOR_MATERIAL);
 473
 474   if(!wire) {
 475     setup_lights(qs);
 476     glEnable(GL_DEPTH_TEST);
 477     clearbits |= GL_DEPTH_BUFFER_BIT;
 478     clearbits |= GL_STENCIL_BUFFER_BIT;
 479     glEnable(GL_CULL_FACE);
 480     glCullFace(GL_BACK);
 481   }
 482   else
 483     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 484
 485   /* find a solution */
 486   go(qs);
 487 }
 488
 489 ENTRYPOINT void draw_queens(ModeInfo *mi)
 490 {
 491   Queenscreen *qs = &qss[MI_SCREEN(mi)];
 492   Window w = MI_WINDOW(mi);
 493   Display *disp = MI_DISPLAY(mi);
 494
 495   if(!qs->glx_context)
 496     return;
 497
 498   glXMakeCurrent(disp, w, *(qs->glx_context));
 499
 500   display(qs);
 501
 502   if(mi->fps_p) do_fps(mi);
 503   glFinish();
 504   glXSwapBuffers(disp, w);
 505 }
 506
 507 ENTRYPOINT void release_queens(ModeInfo *mi)
 508 {
 509   if(qss)
 510     free((void *) qss);
 511   qss = 0;
 512
 513   FreeAllGL(mi);
 514 }
 515
 516 XSCREENSAVER_MODULE ("Queens", queens)
 517
 518 #endif