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