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 HAVE_JWXYZ
  33 # include "jwxyz.h"
  34 #else
  35 # include <X11/Xlib.h>
  36 # include <GL/gl.h>
  37 # include <GL/glu.h>
  38 #endif
  39
  40 #ifdef HAVE_JWZGLES
  41 # include "jwzgles.h"
  42 #endif /* HAVE_JWZGLES */
  43
  44 #ifdef USE_GL
  45
  46 #include "gltrackball.h"
  47 #include "chessmodels.h"
  48
  49 #undef countof
  50 #define countof(x) (sizeof((x))/sizeof((*x)))
  51
  52 static XrmOptionDescRec opts[] = {
  53   {"+rotate", ".queens.rotate", XrmoptionNoArg, "false" },
  54   {"-rotate", ".queens.rotate", XrmoptionNoArg, "true" },
  55   {"+flat", ".queens.flat", XrmoptionNoArg, "false" },
  56   {"-flat", ".queens.flat", XrmoptionNoArg, "true" },
  57 };
  58
  59 static int rotate, wire, clearbits, flat;
  60
  61 static argtype vars[] = {
  62   {&rotate, "rotate", "Rotate", "True",  t_Bool},
  63   {&flat,   "flat",   "Flat",   "False", t_Bool},
  64 };
  65
  66 ENTRYPOINT ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
  67
  68 #ifdef USE_MODULES
  69 ModStruct   queens_description =
  70 {"queens", "init_queens", "draw_queens", NULL,
  71  "draw_queens", "init_queens", NULL, &queens_opts,
  72  1000, 1, 2, 1, 4, 1.0, "",
  73  "Queens", 0, NULL};
  74
  75 #endif
  76
  77 #define NONE 0
  78 #define MINBOARD 5
  79 #define MAXBOARD 10
  80 #define COLORSETS 5
  81
  82 typedef struct {
  83   GLXContext *glx_context;
  84   Window window;
  85   trackball_state *trackball;
  86   Bool button_down_p;
  87   GLfloat position[4];
  88   int queen_list;
  89
  90   int board[MAXBOARD][MAXBOARD];
  91   int steps, colorset, BOARDSIZE;
  92   double theta;
  93   int queen_polys;
  94
  95 } Queenscreen;
  96
  97 static Queenscreen *qss = NULL;
  98
  99 /* definition of white/black colors */
 100 static const GLfloat colors[COLORSETS][2][3] =
 101   {
 102     {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
 103     {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
 104     {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
 105     {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
 106     {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
 107   };
 108
 109 ENTRYPOINT Bool
 110 queens_handle_event (ModeInfo *mi, XEvent *event)
 111 {
 112   Queenscreen *qs = &qss[MI_SCREEN(mi)];
 113
 114   if (gltrackball_event_handler (event, qs->trackball,
 115                                  MI_WIDTH (mi), MI_HEIGHT (mi),
 116                                  &qs->button_down_p))
 117     return True;
 118   else if (screenhack_event_helper (MI_DISPLAY(mi), MI_WINDOW(mi), event))
 119     {
 120       qs->steps = 1024 - 1;
 121       return True;
 122     }
 123
 124   return False;
 125 }
 126
 127
 128
 129 /* returns true if placing a queen on column c causes a conflict */
 130 static int conflictsCols(Queenscreen *qs, int c)
 131 {
 132   int i;
 133
 134   for(i = 0; i < qs->BOARDSIZE; ++i)
 135     if(qs->board[i][c])
 136       return 1;
 137
 138   return 0;
 139 }
 140
 141 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 142 static int conflictsDiag(Queenscreen *qs, int r, int c)
 143 {
 144   int i;
 145
 146   /* positive slope */
 147   int n = r < c ? r : c;
 148   for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
 149     if(qs->board[r-n+i][c-n+i])
 150       return 1;
 151
 152   /* negative slope */
 153   n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
 154   for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
 155     if(qs->board[r-n+i][c+n-i])
 156       return 1;
 157
 158   return 0;
 159 }
 160
 161 /* returns true if placing a queen at (r,c) causes a conflict */
 162 static int conflicts(Queenscreen *qs, int r, int c)
 163 {
 164   return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
 165 }
 166
 167 /* clear board */
 168 static void blank(Queenscreen *qs)
 169 {
 170   int i, j;
 171
 172   for(i = 0; i < MAXBOARD; ++i)
 173     for(j = 0; j < MAXBOARD; ++j)
 174       qs->board[i][j] = NONE;
 175 }
 176
 177 /* recursively determine solution */
 178 static int findSolution(Queenscreen *qs, int row, int col)
 179 {
 180   if(row == qs->BOARDSIZE)
 181     return 1;
 182
 183   while(col < qs->BOARDSIZE) {
 184     if(!conflicts(qs, row, col)) {
 185       qs->board[row][col] = 1;
 186
 187       if(findSolution(qs, row+1, 0))
 188         return 1;
 189
 190       qs->board[row][col] = 0;
 191     }
 192
 193     ++col;
 194   }
 195
 196   return 0;
 197 }
 198
 199 /** driver for finding solution */
 200 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
 201
 202 /* lighting variables */
 203 static const GLfloat front_shininess[] = {60.0};
 204 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
 205 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
 206 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
 207
 208 /* configure lighting */
 209 static void setup_lights(Queenscreen *qs)
 210 {
 211
 212   /* setup twoside lighting */
 213   glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
 214   glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
 215   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 216   glEnable(GL_LIGHTING);
 217   glEnable(GL_LIGHT0);
 218
 219   /* setup material properties */
 220   glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
 221   glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
 222
 223   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 224 }
 225
 226 #define    checkImageWidth 8
 227 #define    checkImageHeight 8
 228 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
 229
 230 /* return alpha value for fading */
 231 static GLfloat findAlpha(Queenscreen *qs)
 232 {
 233   return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
 234 }
 235
 236 /* draw pieces */
 237 static int drawPieces(Queenscreen *qs)
 238 {
 239   int i, j;
 240   int polys = 0;
 241
 242   for(i = 0; i < qs->BOARDSIZE; ++i) {
 243     for(j = 0; j < qs->BOARDSIZE; ++j) {
 244       if(qs->board[i][j]) {
 245         glColor3fv(colors[qs->colorset][i%2]);
 246         glCallList(qs->queen_list);
 247         polys += qs->queen_polys;
 248       }
 249
 250       glTranslatef(1.0, 0.0, 0.0);
 251     }
 252
 253     glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
 254   }
 255   return polys;
 256 }
 257
 258 /** reflectionboard */
 259 static int draw_reflections(Queenscreen *qs)
 260 {
 261   int i, j;
 262   int polys = 0;
 263
 264   glEnable(GL_STENCIL_TEST);
 265   glStencilFunc(GL_ALWAYS, 1, 1);
 266   glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
 267   glColorMask(0,0,0,0);
 268   glDisable(GL_CULL_FACE);
 269
 270   glDisable(GL_DEPTH_TEST);
 271   glBegin(GL_QUADS);
 272
 273   /* only draw white squares */
 274   for(i = 0; i < qs->BOARDSIZE; ++i) {
 275     for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
 276       glVertex3f(i, 0.0, j + 1.0);
 277       glVertex3f(i + 1.0, 0.0, j + 1.0);
 278       glVertex3f(i + 1.0, 0.0, j);
 279       glVertex3f(i, 0.0, j);
 280       polys++;
 281     }
 282   }
 283   glEnd();
 284   glEnable(GL_DEPTH_TEST);
 285
 286   glColorMask(1, 1, 1, 1);
 287   glStencilFunc(GL_EQUAL, 1, 1);
 288   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 289
 290   glPushMatrix();
 291   glScalef(1.0, -1.0, 1.0);
 292   glTranslatef(0.5, 0.001, 0.5);
 293   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 294   polys += drawPieces(qs);
 295   glPopMatrix();
 296   glDisable(GL_STENCIL_TEST);
 297
 298   /* replace lights */
 299   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 300
 301   glEnable(GL_CULL_FACE);
 302   glCullFace(GL_BACK);
 303   glColorMask(1,1,1,1);
 304   return polys;
 305 }
 306
 307 /* draw board */
 308 static int drawBoard(Queenscreen *qs)
 309 {
 310   int i, j;
 311   int polys = 0;
 312
 313   glBegin(GL_QUADS);
 314
 315   for(i = 0; i < qs->BOARDSIZE; ++i)
 316     for(j = 0; j < qs->BOARDSIZE; ++j) {
 317       int par = (i-j+qs->BOARDSIZE)%2;
 318       glColor4f(colors[qs->colorset][par][0],
 319                 colors[qs->colorset][par][1],
 320                 colors[qs->colorset][par][2],
 321                 0.70);
 322       glNormal3f(0.0, 1.0, 0.0);
 323       glVertex3f(i, 0.0, j + 1.0);
 324       glVertex3f(i + 1.0, 0.0, j + 1.0);
 325       glVertex3f(i + 1.0, 0.0, j);
 326       glVertex3f(i, 0.0, j);
 327       polys++;
 328     }
 329
 330   glEnd();
 331
 332   {
 333     GLfloat off = 0.01;
 334     GLfloat w = qs->BOARDSIZE;
 335     GLfloat h = 0.1;
 336
 337     /* Give the board a slight lip. */
 338     /* #### oops, normals are wrong here, but you can't tell */
 339
 340     glColor3f(0.3, 0.3, 0.3);
 341     glBegin (GL_QUADS);
 342     glVertex3f (0,  0, 0);
 343     glVertex3f (0, -h, 0);
 344     glVertex3f (0, -h, w);
 345     glVertex3f (0,  0, w);
 346
 347     glVertex3f (0,  0, w);
 348     glVertex3f (0, -h, w);
 349     glVertex3f (w, -h, w);
 350     glVertex3f (w,  0, w);
 351
 352     glVertex3f (w,  0, w);
 353     glVertex3f (w, -h, w);
 354     glVertex3f (w, -h, 0);
 355     glVertex3f (w,  0, 0);
 356
 357     glVertex3f (w,  0, 0);
 358     glVertex3f (w, -h, 0);
 359     glVertex3f (0, -h, 0);
 360     glVertex3f (0,  0, 0);
 361
 362     glVertex3f (0, -h, 0);
 363     glVertex3f (w, -h, 0);
 364     glVertex3f (w, -h, w);
 365     glVertex3f (0, -h, w);
 366     glEnd();
 367     polys += 4;
 368
 369     /* Fill in the underside of the board with an invisible black box
 370        to hide the reflections that are not on tiles.  Probably there's
 371        a way to do this with stencils instead.
 372      */
 373     w -= off*2;
 374     h = 5;
 375
 376     glPushMatrix();
 377     glTranslatef (off, 0, off);
 378     glDisable(GL_LIGHTING);
 379     glColor3f(0,0,0);
 380     glBegin (GL_QUADS);
 381     glVertex3f (0,  0, 0);
 382     glVertex3f (0, -h, 0);
 383     glVertex3f (0, -h, w);
 384     glVertex3f (0,  0, w);
 385
 386     glVertex3f (0,  0, w);
 387     glVertex3f (0, -h, w);
 388     glVertex3f (w, -h, w);
 389     glVertex3f (w,  0, w);
 390
 391     glVertex3f (w,  0, w);
 392     glVertex3f (w, -h, w);
 393     glVertex3f (w, -h, 0);
 394     glVertex3f (w,  0, 0);
 395
 396     glVertex3f (w,  0, 0);
 397     glVertex3f (w, -h, 0);
 398     glVertex3f (0, -h, 0);
 399     glVertex3f (0,  0, 0);
 400
 401     glVertex3f (0, -h, 0);
 402     glVertex3f (w, -h, 0);
 403     glVertex3f (w, -h, w);
 404     glVertex3f (0, -h, w);
 405     glEnd();
 406     polys += 4;
 407     glPopMatrix();
 408     if (!wire)
 409       glEnable(GL_LIGHTING);
 410   }
 411
 412   return polys;
 413 }
 414
 415 static int display(ModeInfo *mi, Queenscreen *qs)
 416 {
 417   int max = 1024;
 418   int polys = 0;
 419   glClear(clearbits);
 420
 421   glMatrixMode(GL_MODELVIEW);
 422   glLoadIdentity();
 423
 424   glRotatef(current_device_rotation(), 0, 0, 1);
 425
 426   /* setup light attenuation */
 427   /* #### apparently this does nothing */
 428   glEnable(GL_COLOR_MATERIAL);
 429   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
 430   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
 431
 432   /** setup perspective */
 433   glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
 434   glRotatef(30.0, 1.0, 0.0, 0.0);
 435   gltrackball_rotate (qs->trackball);
 436   glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
 437   glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
 438
 439   /* find light positions */
 440   qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
 441   qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
 442   qs->position[1] = 6.0;
 443
 444   if(!wire) {
 445     glEnable(GL_LIGHTING);
 446     glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 447     glEnable(GL_LIGHT0);
 448   }
 449
 450   /* Since the lighting attenuation trick up there doesn't seem to be working,
 451      let's drop the old board down and drop the new board in. */
 452   if (qs->steps < (max/8.0)) {
 453     GLfloat y = qs->steps / (max/8.0);
 454     y = sin (M_PI/2 * y);
 455     glTranslatef (0, 10 - (y * 10), 0);
 456   } else if (qs->steps > max-(max/8.0)) {
 457     GLfloat y = (qs->steps - (max-(max/8.0))) / (GLfloat) (max/8.0);
 458     y = 1 - sin (M_PI/2 * (1-y));
 459     glTranslatef (0, -y * 15, 0);
 460   }
 461
 462   /* draw reflections */
 463   if(!wire) {
 464     polys += draw_reflections(qs);
 465     glEnable(GL_BLEND);
 466   }
 467   polys += drawBoard(qs);
 468   if(!wire)
 469     glDisable(GL_BLEND);
 470
 471   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
 472
 473   glTranslatef(0.5, 0.0, 0.5);
 474   polys += drawPieces(qs);
 475
 476   /* rotate camera */
 477   if(!qs->button_down_p)
 478     qs->theta += .002;
 479
 480   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 481   if(++qs->steps == max) {
 482     qs->steps = 0;
 483     blank(qs);
 484     qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 485     qs->colorset = (qs->colorset+1)%COLORSETS;
 486     go(qs);
 487   }
 488   return polys;
 489 }
 490
 491 #define EPSILON 0.001
 492
 493 #if 0
 494 /** draws cylindermodel */
 495 static int draw_model(int chunks, const GLfloat model[][3], int r)
 496 {
 497   int i = 0;
 498   int polys = 0;
 499   glPushMatrix();
 500   glRotatef(-90.0, 1.0, 0.0, 0.0);
 501
 502   for(i = 0; i < chunks; ++i) {
 503     if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
 504       polys += tube (0, 0, 0,
 505                      0, 0, model[i][1],
 506                      model[i][0], 0,
 507                      r, False, False, False);
 508 /*      gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 509       polys += r;*/
 510     }
 511     glTranslatef(0.0, 0.0, model[i][2]);
 512   }
 513
 514   glPopMatrix();
 515   return polys;
 516 }
 517 #endif
 518
 519 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
 520 {
 521   GLfloat h = (GLfloat) height / (GLfloat) width;
 522   glViewport(0,0, width, height);
 523   glMatrixMode(GL_PROJECTION);
 524   glLoadIdentity();
 525   gluPerspective(45, 1/h, 2.0, 30.0);
 526   glMatrixMode(GL_MODELVIEW);
 527 }
 528
 529 ENTRYPOINT void init_queens(ModeInfo *mi)
 530 {
 531   int screen = MI_SCREEN(mi);
 532   Queenscreen *qs;
 533   int poly_counts[PIECES];
 534   wire = MI_IS_WIREFRAME(mi);
 535
 536 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
 537   wire = 0;
 538 # endif
 539
 540   MI_INIT (mi, qss, NULL);
 541
 542   qs = &qss[screen];
 543   qs->window = MI_WINDOW(mi);
 544
 545   if((qs->glx_context = init_GL(mi)))
 546     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 547   else
 548     MI_CLEARWINDOW(mi);
 549
 550   qs->trackball = gltrackball_init (False);
 551
 552   qs->BOARDSIZE = 8; /* 8 cuz its classic */
 553
 554   chessmodels_gen_lists(-1, poly_counts);
 555   qs->queen_list = QUEEN;
 556   qs->queen_polys = poly_counts[QUEEN];
 557
 558   /* find a solution */
 559   go(qs);
 560 }
 561
 562 ENTRYPOINT void draw_queens(ModeInfo *mi)
 563 {
 564   Queenscreen *qs = &qss[MI_SCREEN(mi)];
 565   Window w = MI_WINDOW(mi);
 566   Display *disp = MI_DISPLAY(mi);
 567
 568   if(!qs->glx_context)
 569     return;
 570
 571   glXMakeCurrent(disp, w, *(qs->glx_context));
 572
 573   if(flat)
 574     glShadeModel(GL_FLAT);
 575
 576   clearbits = GL_COLOR_BUFFER_BIT;
 577
 578   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 579   glEnable(GL_COLOR_MATERIAL);
 580
 581   if(!wire) {
 582     setup_lights(qs);
 583     glEnable(GL_DEPTH_TEST);
 584     clearbits |= GL_DEPTH_BUFFER_BIT;
 585     clearbits |= GL_STENCIL_BUFFER_BIT;
 586     glEnable(GL_CULL_FACE);
 587     glCullFace(GL_BACK);
 588   }
 589   else
 590     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 591
 592   mi->polygon_count = display(mi, qs);
 593   mi->recursion_depth = qs->BOARDSIZE;
 594
 595   if(mi->fps_p) do_fps(mi);
 596   glFinish();
 597   glXSwapBuffers(disp, w);
 598 }
 599
 600 ENTRYPOINT void release_queens(ModeInfo *mi)
 601 {
 602   if(qss)
 603     free((void *) qss);
 604   qss = 0;
 605
 606   FreeAllGL(mi);
 607 }
 608
 609 XSCREENSAVER_MODULE ("Queens", queens)
 610
 611 #endif