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_COCOA
  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", "release_queens",
  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 (event->xany.type == ButtonPress &&
 115       event->xbutton.button == Button1)
 116     {
 117       qs->button_down_p = True;
 118       gltrackball_start (qs->trackball,
 119                          event->xbutton.x, event->xbutton.y,
 120                          MI_WIDTH (mi), MI_HEIGHT (mi));
 121       return True;
 122     }
 123   else if (event->xany.type == ButtonRelease &&
 124            event->xbutton.button == Button1)
 125     {
 126       qs->button_down_p = False;
 127       return True;
 128     }
 129   else if (event->xany.type == ButtonPress &&
 130            (event->xbutton.button == Button4 ||
 131             event->xbutton.button == Button5 ||
 132             event->xbutton.button == Button6 ||
 133             event->xbutton.button == Button7))
 134     {
 135       gltrackball_mousewheel (qs->trackball, event->xbutton.button, 5,
 136                               !event->xbutton.state);
 137       return True;
 138     }
 139   else if (event->xany.type == MotionNotify &&
 140            qs->button_down_p)
 141     {
 142       gltrackball_track (qs->trackball,
 143                          event->xmotion.x, event->xmotion.y,
 144                          MI_WIDTH (mi), MI_HEIGHT (mi));
 145       return True;
 146     }
 147
 148   return False;
 149 }
 150
 151
 152
 153 /* returns true if placing a queen on column c causes a conflict */
 154 static int conflictsCols(Queenscreen *qs, int c)
 155 {
 156   int i;
 157
 158   for(i = 0; i < qs->BOARDSIZE; ++i)
 159     if(qs->board[i][c])
 160       return 1;
 161
 162   return 0;
 163 }
 164
 165 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 166 static int conflictsDiag(Queenscreen *qs, int r, int c)
 167 {
 168   int i;
 169
 170   /* positive slope */
 171   int n = r < c ? r : c;
 172   for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
 173     if(qs->board[r-n+i][c-n+i])
 174       return 1;
 175
 176   /* negative slope */
 177   n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
 178   for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
 179     if(qs->board[r-n+i][c+n-i])
 180       return 1;
 181
 182   return 0;
 183 }
 184
 185 /* returns true if placing a queen at (r,c) causes a conflict */
 186 static int conflicts(Queenscreen *qs, int r, int c)
 187 {
 188   return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
 189 }
 190
 191 /* clear board */
 192 static void blank(Queenscreen *qs)
 193 {
 194   int i, j;
 195
 196   for(i = 0; i < MAXBOARD; ++i)
 197     for(j = 0; j < MAXBOARD; ++j)
 198       qs->board[i][j] = NONE;
 199 }
 200
 201 /* recursively determine solution */
 202 static int findSolution(Queenscreen *qs, int row, int col)
 203 {
 204   if(row == qs->BOARDSIZE)
 205     return 1;
 206
 207   while(col < qs->BOARDSIZE) {
 208     if(!conflicts(qs, row, col)) {
 209       qs->board[row][col] = 1;
 210
 211       if(findSolution(qs, row+1, 0))
 212         return 1;
 213
 214       qs->board[row][col] = 0;
 215     }
 216
 217     ++col;
 218   }
 219
 220   return 0;
 221 }
 222
 223 /** driver for finding solution */
 224 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
 225
 226 /* lighting variables */
 227 static const GLfloat front_shininess[] = {60.0};
 228 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
 229 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
 230 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
 231
 232 /* configure lighting */
 233 static void setup_lights(Queenscreen *qs)
 234 {
 235
 236   /* setup twoside lighting */
 237   glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
 238   glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
 239   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 240   glEnable(GL_LIGHTING);
 241   glEnable(GL_LIGHT0);
 242
 243   /* setup material properties */
 244   glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
 245   glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
 246
 247   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 248 }
 249
 250 #define    checkImageWidth 8
 251 #define    checkImageHeight 8
 252 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
 253
 254 /* return alpha value for fading */
 255 static GLfloat findAlpha(Queenscreen *qs)
 256 {
 257   return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
 258 }
 259
 260 /* draw pieces */
 261 static int drawPieces(Queenscreen *qs)
 262 {
 263   int i, j;
 264   int polys = 0;
 265
 266   for(i = 0; i < qs->BOARDSIZE; ++i) {
 267     for(j = 0; j < qs->BOARDSIZE; ++j) {
 268       if(qs->board[i][j]) {
 269         glColor3fv(colors[qs->colorset][i%2]);
 270         glCallList(qs->queen_list);
 271         polys += qs->queen_polys;
 272       }
 273
 274       glTranslatef(1.0, 0.0, 0.0);
 275     }
 276
 277     glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
 278   }
 279   return polys;
 280 }
 281
 282 /** reflectionboard */
 283 static int draw_reflections(Queenscreen *qs)
 284 {
 285   int i, j;
 286   int polys = 0;
 287
 288   glEnable(GL_STENCIL_TEST);
 289   glStencilFunc(GL_ALWAYS, 1, 1);
 290   glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
 291   glColorMask(0,0,0,0);
 292   glDisable(GL_CULL_FACE);
 293
 294   glDisable(GL_DEPTH_TEST);
 295   glBegin(GL_QUADS);
 296
 297   /* only draw white squares */
 298   for(i = 0; i < qs->BOARDSIZE; ++i) {
 299     for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
 300       glVertex3f(i, 0.0, j + 1.0);
 301       glVertex3f(i + 1.0, 0.0, j + 1.0);
 302       glVertex3f(i + 1.0, 0.0, j);
 303       glVertex3f(i, 0.0, j);
 304       polys++;
 305     }
 306   }
 307   glEnd();
 308   glEnable(GL_DEPTH_TEST);
 309
 310   glColorMask(1, 1, 1, 1);
 311   glStencilFunc(GL_EQUAL, 1, 1);
 312   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 313
 314   glPushMatrix();
 315   glScalef(1.0, -1.0, 1.0);
 316   glTranslatef(0.5, 0.001, 0.5);
 317   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 318   polys += drawPieces(qs);
 319   glPopMatrix();
 320   glDisable(GL_STENCIL_TEST);
 321
 322   /* replace lights */
 323   glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 324
 325   glEnable(GL_CULL_FACE);
 326   glCullFace(GL_BACK);
 327   glColorMask(1,1,1,1);
 328   return polys;
 329 }
 330
 331 /* draw board */
 332 static int drawBoard(Queenscreen *qs)
 333 {
 334   int i, j;
 335   int polys = 0;
 336
 337   glBegin(GL_QUADS);
 338
 339   for(i = 0; i < qs->BOARDSIZE; ++i)
 340     for(j = 0; j < qs->BOARDSIZE; ++j) {
 341       int par = (i-j+qs->BOARDSIZE)%2;
 342       glColor4f(colors[qs->colorset][par][0],
 343                 colors[qs->colorset][par][1],
 344                 colors[qs->colorset][par][2],
 345                 0.70);
 346       glNormal3f(0.0, 1.0, 0.0);
 347       glVertex3f(i, 0.0, j + 1.0);
 348       glVertex3f(i + 1.0, 0.0, j + 1.0);
 349       glVertex3f(i + 1.0, 0.0, j);
 350       glVertex3f(i, 0.0, j);
 351       polys++;
 352     }
 353
 354   glEnd();
 355
 356   {
 357     GLfloat off = 0.01;
 358     GLfloat w = qs->BOARDSIZE;
 359     GLfloat h = 0.1;
 360
 361     /* Give the board a slight lip. */
 362     /* #### oops, normals are wrong here, but you can't tell */
 363
 364     glColor3f(0.3, 0.3, 0.3);
 365     glBegin (GL_QUADS);
 366     glVertex3f (0,  0, 0);
 367     glVertex3f (0, -h, 0);
 368     glVertex3f (0, -h, w);
 369     glVertex3f (0,  0, w);
 370
 371     glVertex3f (0,  0, w);
 372     glVertex3f (0, -h, w);
 373     glVertex3f (w, -h, w);
 374     glVertex3f (w,  0, w);
 375
 376     glVertex3f (w,  0, w);
 377     glVertex3f (w, -h, w);
 378     glVertex3f (w, -h, 0);
 379     glVertex3f (w,  0, 0);
 380
 381     glVertex3f (w,  0, 0);
 382     glVertex3f (w, -h, 0);
 383     glVertex3f (0, -h, 0);
 384     glVertex3f (0,  0, 0);
 385
 386     glVertex3f (0, -h, 0);
 387     glVertex3f (w, -h, 0);
 388     glVertex3f (w, -h, w);
 389     glVertex3f (0, -h, w);
 390     glEnd();
 391     polys += 4;
 392
 393     /* Fill in the underside of the board with an invisible black box
 394        to hide the reflections that are not on tiles.  Probably there's
 395        a way to do this with stencils instead.
 396      */
 397     w -= off*2;
 398     h = 5;
 399
 400     glPushMatrix();
 401     glTranslatef (off, 0, off);
 402     glDisable(GL_LIGHTING);
 403     glColor3f(0,0,0);
 404     glBegin (GL_QUADS);
 405     glVertex3f (0,  0, 0);
 406     glVertex3f (0, -h, 0);
 407     glVertex3f (0, -h, w);
 408     glVertex3f (0,  0, w);
 409
 410     glVertex3f (0,  0, w);
 411     glVertex3f (0, -h, w);
 412     glVertex3f (w, -h, w);
 413     glVertex3f (w,  0, w);
 414
 415     glVertex3f (w,  0, w);
 416     glVertex3f (w, -h, w);
 417     glVertex3f (w, -h, 0);
 418     glVertex3f (w,  0, 0);
 419
 420     glVertex3f (w,  0, 0);
 421     glVertex3f (w, -h, 0);
 422     glVertex3f (0, -h, 0);
 423     glVertex3f (0,  0, 0);
 424
 425     glVertex3f (0, -h, 0);
 426     glVertex3f (w, -h, 0);
 427     glVertex3f (w, -h, w);
 428     glVertex3f (0, -h, w);
 429     glEnd();
 430     polys += 4;
 431     glPopMatrix();
 432     if (!wire)
 433       glEnable(GL_LIGHTING);
 434   }
 435
 436   return polys;
 437 }
 438
 439 static int display(Queenscreen *qs)
 440 {
 441   int max = 1024;
 442   int polys = 0;
 443   glClear(clearbits);
 444
 445   glMatrixMode(GL_MODELVIEW);
 446   glLoadIdentity();
 447
 448   glRotatef(current_device_rotation(), 0, 0, 1);
 449
 450   /* setup light attenuation */
 451   /* #### apparently this does nothing */
 452   glEnable(GL_COLOR_MATERIAL);
 453   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
 454   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
 455
 456   /** setup perspective */
 457   glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
 458   glRotatef(30.0, 1.0, 0.0, 0.0);
 459   gltrackball_rotate (qs->trackball);
 460   glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
 461   glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
 462
 463   /* find light positions */
 464   qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
 465   qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
 466   qs->position[1] = 6.0;
 467
 468   if(!wire) {
 469     glEnable(GL_LIGHTING);
 470     glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 471     glEnable(GL_LIGHT0);
 472   }
 473
 474   /* Since the lighting attenuation trick up there doesn't seem to be working,
 475      let's drop the old board down and drop the new board in. */
 476   if (qs->steps < (max/8.0)) {
 477     GLfloat y = qs->steps / (max/8.0);
 478     y = sin (M_PI/2 * y);
 479     glTranslatef (0, 10 - (y * 10), 0);
 480   } else if (qs->steps > max-(max/8.0)) {
 481     GLfloat y = (qs->steps - (max-(max/8.0))) / (GLfloat) (max/8.0);
 482     y = 1 - sin (M_PI/2 * (1-y));
 483     glTranslatef (0, -y * 15, 0);
 484   }
 485
 486   /* draw reflections */
 487   if(!wire) {
 488     polys += draw_reflections(qs);
 489     glEnable(GL_BLEND);
 490   }
 491   polys += drawBoard(qs);
 492   if(!wire)
 493     glDisable(GL_BLEND);
 494
 495   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
 496
 497   glTranslatef(0.5, 0.0, 0.5);
 498   polys += drawPieces(qs);
 499
 500   /* rotate camera */
 501   if(!qs->button_down_p)
 502     qs->theta += .002;
 503
 504   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 505   if(++qs->steps == max) {
 506     qs->steps = 0;
 507     blank(qs);
 508     qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 509     qs->colorset = (qs->colorset+1)%COLORSETS;
 510     go(qs);
 511   }
 512   return polys;
 513 }
 514
 515 static const GLfloat spidermodel[][3] =
 516   {
 517     {0.48, 0.48, 0.22},
 518     {0.48, 0.34, 0.18},
 519     {0.34, 0.34, 0.10},
 520     {0.34, 0.18, 0.30},
 521     {0.18, 0.14, 0.38},
 522     {0.14, 0.29, 0.01},
 523     {0.29, 0.18, 0.18},
 524     {0.18, 0.18, 0.16},
 525     {0.18, 0.20, 0.26},
 526     {0.20, 0.27, 0.14},
 527     {0.27, 0.24, 0.08},
 528     {0.24, 0.17, 0.00},
 529     {0.17, 0.095, 0.08},
 530     {0.095, 0.07, 0.00},
 531     {0.07, 0.00, 0.12},
 532   };
 533
 534
 535 #define EPSILON 0.001
 536
 537 #if 0
 538 /** draws cylindermodel */
 539 static int draw_model(int chunks, const GLfloat model[][3], int r)
 540 {
 541   int i = 0;
 542   int polys = 0;
 543   glPushMatrix();
 544   glRotatef(-90.0, 1.0, 0.0, 0.0);
 545
 546   for(i = 0; i < chunks; ++i) {
 547     if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
 548       polys += tube (0, 0, 0,
 549                      0, 0, model[i][1],
 550                      model[i][0], 0,
 551                      r, False, False, False);
 552 /*      gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 553       polys += r;*/
 554     }
 555     glTranslatef(0.0, 0.0, model[i][2]);
 556   }
 557
 558   glPopMatrix();
 559   return polys;
 560 }
 561 #endif
 562
 563 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
 564 {
 565   GLfloat h = (GLfloat) height / (GLfloat) width;
 566   glViewport(0,0, width, height);
 567   glMatrixMode(GL_PROJECTION);
 568   glLoadIdentity();
 569   gluPerspective(45, 1/h, 2.0, 30.0);
 570   glMatrixMode(GL_MODELVIEW);
 571 }
 572
 573 ENTRYPOINT void init_queens(ModeInfo *mi)
 574 {
 575   int screen = MI_SCREEN(mi);
 576   Queenscreen *qs;
 577   int poly_counts[PIECES];
 578   wire = MI_IS_WIREFRAME(mi);
 579
 580 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
 581   wire = 0;
 582 # endif
 583
 584   if(!qss &&
 585      !(qss = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 586     return;
 587
 588   qs = &qss[screen];
 589   qs->window = MI_WINDOW(mi);
 590
 591   if((qs->glx_context = init_GL(mi)))
 592     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 593   else
 594     MI_CLEARWINDOW(mi);
 595
 596   qs->trackball = gltrackball_init ();
 597
 598   qs->BOARDSIZE = 8; /* 8 cuz its classic */
 599
 600   chessmodels_gen_lists(-1, poly_counts);
 601   qs->queen_list = QUEEN;
 602   qs->queen_polys = poly_counts[QUEEN];
 603
 604   /* find a solution */
 605   go(qs);
 606 }
 607
 608 ENTRYPOINT void draw_queens(ModeInfo *mi)
 609 {
 610   Queenscreen *qs = &qss[MI_SCREEN(mi)];
 611   Window w = MI_WINDOW(mi);
 612   Display *disp = MI_DISPLAY(mi);
 613
 614   if(!qs->glx_context)
 615     return;
 616
 617   glXMakeCurrent(disp, w, *(qs->glx_context));
 618
 619   if(flat)
 620     glShadeModel(GL_FLAT);
 621
 622   clearbits = GL_COLOR_BUFFER_BIT;
 623
 624   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 625   glEnable(GL_COLOR_MATERIAL);
 626
 627   if(!wire) {
 628     setup_lights(qs);
 629     glEnable(GL_DEPTH_TEST);
 630     clearbits |= GL_DEPTH_BUFFER_BIT;
 631     clearbits |= GL_STENCIL_BUFFER_BIT;
 632     glEnable(GL_CULL_FACE);
 633     glCullFace(GL_BACK);
 634   }
 635   else
 636     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 637
 638   mi->polygon_count = display(qs);
 639   mi->recursion_depth = qs->BOARDSIZE;
 640
 641   if(mi->fps_p) do_fps(mi);
 642   glFinish();
 643   glXSwapBuffers(disp, w);
 644 }
 645
 646 ENTRYPOINT void release_queens(ModeInfo *mi)
 647 {
 648   if(qss)
 649     free((void *) qss);
 650   qss = 0;
 651
 652   FreeAllGL(mi);
 653 }
 654
 655 XSCREENSAVER_MODULE ("Queens", queens)
 656
 657 #endif