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   return polys;
 356 }
 357
 358 static int display(Queenscreen *qs)
 359 {
 360   int polys = 0;
 361   glClear(clearbits);
 362
 363   glMatrixMode(GL_MODELVIEW);
 364   glLoadIdentity();
 365
 366   glRotatef(current_device_rotation(), 0, 0, 1);
 367
 368   /* setup light attenuation */
 369   glEnable(GL_COLOR_MATERIAL);
 370   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
 371   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
 372
 373   /** setup perspective */
 374   glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
 375   glRotatef(30.0, 1.0, 0.0, 0.0);
 376   glRotatef(-current_device_rotation(), 0, 0, 1);
 377   gltrackball_rotate (qs->trackball);
 378   glRotatef(current_device_rotation(), 0, 0, 1);
 379   glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
 380   glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
 381
 382   /* find light positions */
 383   qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
 384   qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
 385   qs->position[1] = 6.0;
 386
 387   if(!wire) {
 388     glEnable(GL_LIGHTING);
 389     glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
 390     glEnable(GL_LIGHT0);
 391   }
 392
 393   /* draw reflections */
 394   if(!wire) {
 395     polys += draw_reflections(qs);
 396     glEnable(GL_BLEND);
 397   }
 398   polys += drawBoard(qs);
 399   if(!wire)
 400     glDisable(GL_BLEND);
 401
 402   glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
 403
 404   glTranslatef(0.5, 0.0, 0.5);
 405   polys += drawPieces(qs);
 406
 407   /* rotate camera */
 408   if(!qs->button_down_p)
 409     qs->theta += .002;
 410
 411   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 412   if(++qs->steps == 1024) {
 413     qs->steps = 0;
 414     blank(qs);
 415     qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 416     qs->colorset = (qs->colorset+1)%COLORSETS;
 417     go(qs);
 418   }
 419   return polys;
 420 }
 421
 422 static const GLfloat spidermodel[][3] =
 423   {
 424     {0.48, 0.48, 0.22},
 425     {0.48, 0.34, 0.18},
 426     {0.34, 0.34, 0.10},
 427     {0.34, 0.18, 0.30},
 428     {0.18, 0.14, 0.38},
 429     {0.14, 0.29, 0.01},
 430     {0.29, 0.18, 0.18},
 431     {0.18, 0.18, 0.16},
 432     {0.18, 0.20, 0.26},
 433     {0.20, 0.27, 0.14},
 434     {0.27, 0.24, 0.08},
 435     {0.24, 0.17, 0.00},
 436     {0.17, 0.095, 0.08},
 437     {0.095, 0.07, 0.00},
 438     {0.07, 0.00, 0.12},
 439   };
 440
 441
 442 #define EPSILON 0.001
 443
 444 #if 0
 445 /** draws cylindermodel */
 446 static int draw_model(int chunks, const GLfloat model[][3], int r)
 447 {
 448   int i = 0;
 449   int polys = 0;
 450   glPushMatrix();
 451   glRotatef(-90.0, 1.0, 0.0, 0.0);
 452
 453   for(i = 0; i < chunks; ++i) {
 454     if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
 455       polys += tube (0, 0, 0,
 456                      0, 0, model[i][1],
 457                      model[i][0], 0,
 458                      r, False, False, False);
 459 /*      gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 460       polys += r;*/
 461     }
 462     glTranslatef(0.0, 0.0, model[i][2]);
 463   }
 464
 465   glPopMatrix();
 466   return polys;
 467 }
 468 #endif
 469
 470 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
 471 {
 472   GLfloat h = (GLfloat) height / (GLfloat) width;
 473   glViewport(0,0, width, height);
 474   glMatrixMode(GL_PROJECTION);
 475   glLoadIdentity();
 476   gluPerspective(45, 1/h, 2.0, 30.0);
 477   glMatrixMode(GL_MODELVIEW);
 478 }
 479
 480 ENTRYPOINT void init_queens(ModeInfo *mi)
 481 {
 482   int screen = MI_SCREEN(mi);
 483   Queenscreen *qs;
 484   int poly_counts[PIECES];
 485   wire = MI_IS_WIREFRAME(mi);
 486
 487   if(!qss &&
 488      !(qss = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 489     return;
 490
 491   qs = &qss[screen];
 492   qs->window = MI_WINDOW(mi);
 493
 494   if((qs->glx_context = init_GL(mi)))
 495     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 496   else
 497     MI_CLEARWINDOW(mi);
 498
 499   qs->trackball = gltrackball_init ();
 500
 501   qs->BOARDSIZE = 8; /* 8 cuz its classic */
 502
 503   gen_model_lists(-1, poly_counts);
 504   qs->queen_list = QUEEN;
 505   qs->queen_polys = poly_counts[QUEEN];
 506
 507   /* find a solution */
 508   go(qs);
 509 }
 510
 511 ENTRYPOINT void draw_queens(ModeInfo *mi)
 512 {
 513   Queenscreen *qs = &qss[MI_SCREEN(mi)];
 514   Window w = MI_WINDOW(mi);
 515   Display *disp = MI_DISPLAY(mi);
 516
 517   if(!qs->glx_context)
 518     return;
 519
 520   glXMakeCurrent(disp, w, *(qs->glx_context));
 521
 522   if(flat)
 523     glShadeModel(GL_FLAT);
 524
 525   clearbits = GL_COLOR_BUFFER_BIT;
 526
 527   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 528   glEnable(GL_COLOR_MATERIAL);
 529
 530   if(!wire) {
 531     setup_lights(qs);
 532     glEnable(GL_DEPTH_TEST);
 533     clearbits |= GL_DEPTH_BUFFER_BIT;
 534     clearbits |= GL_STENCIL_BUFFER_BIT;
 535     glEnable(GL_CULL_FACE);
 536     glCullFace(GL_BACK);
 537   }
 538   else
 539     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 540
 541   mi->polygon_count = display(qs);
 542   mi->recursion_depth = qs->BOARDSIZE;
 543
 544   if(mi->fps_p) do_fps(mi);
 545   glFinish();
 546   glXSwapBuffers(disp, w);
 547 }
 548
 549 ENTRYPOINT void release_queens(ModeInfo *mi)
 550 {
 551   if(qss)
 552     free((void *) qss);
 553   qss = 0;
 554
 555   FreeAllGL(mi);
 556 }
 557
 558 XSCREENSAVER_MODULE ("Queens", queens)
 559
 560 #endif