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