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 (tennessb@unbc.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 #include <X11/Intrinsic.h>
  21
  22 #ifdef STANDALONE
  23 # define PROGCLASS        "Queens"
  24 # define HACK_INIT        init_queens
  25 # define HACK_DRAW        draw_queens
  26 # define HACK_RESHAPE     reshape_queens
  27 # define HACK_HANDLE_EVENT queens_handle_event
  28 # define EVENT_MASK       PointerMotionMask
  29 # define queens_opts  xlockmore_opts
  30
  31 #define DEFAULTS       "*delay:       20000       \n" \
  32                        "*showFPS:       False       \n" \
  33                        "*wireframe:     False     \n"   \
  34
  35 # include "xlockmore.h"
  36
  37 #else
  38 # include "xlock.h"
  39 #endif
  40
  41 #ifdef USE_GL
  42
  43 #include <GL/glu.h>
  44 #include "gltrackball.h"
  45
  46 #undef countof
  47 #define countof(x) (sizeof((x))/sizeof((*x)))
  48
  49 static XrmOptionDescRec opts[] = {
  50   {"+rotate", ".queens.rotate", XrmoptionNoArg, (caddr_t) "false" },
  51   {"-rotate", ".queens.rotate", XrmoptionNoArg, (caddr_t) "true" },
  52 /*   {"-white", ".queens.white", XrmoptionSepArg, (cadd_t) NULL }, */
  53 /*   {"-black", ".queens.white", XrmoptionSepArg, (cadd_t) NULL }, */
  54 };
  55
  56 int rotate, wire, clearbits;
  57
  58 static argtype vars[] = {
  59   {(caddr_t *) &rotate, "rotate", "Rotate", "True", t_Bool},
  60 };
  61
  62 ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
  63
  64 #ifdef USE_MODULES
  65 ModStruct   queens_description =
  66 {"queens", "init_queens", "draw_queens", "release_queens",
  67  "draw_queens", "init_queens", NULL, &queens_opts,
  68  1000, 1, 2, 1, 4, 1.0, "",
  69  "Queens", 0, NULL};
  70
  71 #endif
  72
  73 typedef struct {
  74   GLXContext *glx_context;
  75   Window window;
  76   trackball_state *trackball;
  77   Bool button_down_p;
  78 } Queenscreen;
  79
  80 static Queenscreen *qs = NULL;
  81
  82 #include <math.h>
  83 #include <sys/time.h>
  84 #include <stdio.h>
  85 #include <stdlib.h>
  86
  87 #ifndef M_PI
  88 #define M_PI 3.14159265
  89 #endif
  90
  91 #define NONE 0
  92 #define QUEEN 1
  93 #define MINBOARD 5
  94 #define MAXBOARD 10
  95 #define COLORSETS 5
  96
  97 /* definition of white/black colors */
  98 GLfloat colors[COLORSETS][2][3] =
  99   {
 100     {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
 101     {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
 102     {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
 103     {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
 104     {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
 105   };
 106
 107 int board[MAXBOARD][MAXBOARD];
 108 int steps = 0, colorset = 0, BOARDSIZE = 8; /* 8 cuz its classic */
 109
 110 Bool
 111 queens_handle_event (ModeInfo *mi, XEvent *event)
 112 {
 113   Queenscreen *c = &qs[MI_SCREEN(mi)];
 114
 115   if (event->xany.type == ButtonPress &&
 116       event->xbutton.button & Button1)
 117     {
 118       c->button_down_p = True;
 119       gltrackball_start (c->trackball,
 120                          event->xbutton.x, event->xbutton.y,
 121                          MI_WIDTH (mi), MI_HEIGHT (mi));
 122       return True;
 123     }
 124   else if (event->xany.type == ButtonRelease &&
 125            event->xbutton.button & Button1)
 126     {
 127       c->button_down_p = False;
 128       return True;
 129     }
 130   else if (event->xany.type == MotionNotify &&
 131            c->button_down_p)
 132     {
 133       gltrackball_track (c->trackball,
 134                          event->xmotion.x, event->xmotion.y,
 135                          MI_WIDTH (mi), MI_HEIGHT (mi));
 136       return True;
 137     }
 138
 139   return False;
 140 }
 141
 142
 143
 144 /* returns true if placing a queen on column c causes a conflict */
 145 int conflictsCols(int c) {
 146   int i;
 147
 148   for(i = 0; i < BOARDSIZE; ++i)
 149     if(board[i][c])
 150       return 1;
 151
 152   return 0;
 153 }
 154
 155 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 156 int conflictsDiag(int r, int c) {
 157   int i;
 158
 159   /* positive slope */
 160   int n = r < c ? r : c;
 161   for(i = 0; i < BOARDSIZE-abs(r-c); ++i)
 162     if(board[r-n+i][c-n+i])
 163       return 1;
 164
 165   /* negative slope */
 166   n = r < BOARDSIZE - (c+1) ? r : BOARDSIZE - (c+1);
 167   for(i = 0; i < BOARDSIZE-abs(BOARDSIZE - (1+r+c)); ++i)
 168     if(board[r-n+i][c+n-i])
 169       return 1;
 170
 171   return 0;
 172 }
 173
 174 /* returns true if placing a queen at (r,c) causes a conflict */
 175 int conflicts(int r, int c) {
 176   return !conflictsCols(c) ? conflictsDiag(r, c) : 1;
 177 }
 178
 179 /* clear board */
 180 void blank(void) {
 181   int i, j;
 182
 183   for(i = 0; i < MAXBOARD; ++i)
 184     for(j = 0; j < MAXBOARD; ++j)
 185       board[i][j] = NONE;
 186 }
 187
 188 /* recursively determine solution */
 189 int findSolution(int row, int col) {
 190   if(row == BOARDSIZE)
 191     return 1;
 192
 193   while(col < BOARDSIZE) {
 194     if(!conflicts(row, col)) {
 195       board[row][col] = 1;
 196
 197       if(findSolution(row+1, 0))
 198         return 1;
 199
 200       board[row][col] = 0;
 201     }
 202
 203     ++col;
 204   }
 205
 206   return 0;
 207 }
 208
 209 /** driver for finding solution */
 210 void go(void) { while(!findSolution(0, random()%BOARDSIZE)); }
 211
 212 /* lighting variables */
 213 GLfloat front_shininess[] = {80.0};
 214 GLfloat front_specular[] = {0.5, 0.5, 0.5, 1.0};
 215 GLfloat ambient[] = {0.5, 0.5, 0.5, 1.0};
 216 GLfloat ambient2[] = {0.1, 0.1, 0.1, 1.0};
 217 GLfloat diffuse[] = {0.7, 0.7, 0.7, 1.0};
 218 GLfloat position0[] = {0.0, 7.0, 0.0, 1.0};
 219 GLfloat position1[] = {8.0, 7.0, 8.0, 1.0};
 220 GLfloat lmodel_ambient[] = {0.6, 0.6, 0.6, 1.0};
 221 GLfloat lmodel_twoside[] = {GL_TRUE};
 222
 223 /* configure lighting */
 224 void setup_lights(void) {
 225
 226   /* setup twoside lighting */
 227   glLightfv(GL_LIGHT0, GL_AMBIENT, ambient2);
 228   glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
 229   glLightfv(GL_LIGHT0, GL_POSITION, position0);
 230   glLightfv(GL_LIGHT1, GL_AMBIENT, ambient2);
 231   glLightfv(GL_LIGHT1, GL_DIFFUSE, diffuse);
 232   glLightfv(GL_LIGHT1, GL_POSITION, position1);
 233   glEnable(GL_LIGHTING);
 234   glEnable(GL_LIGHT0);
 235   glEnable(GL_LIGHT1);
 236
 237   /* setup material properties */
 238   glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
 239   glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
 240
 241   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 242 }
 243
 244 /* return alpha value for fading */
 245 GLfloat findAlpha(void) {
 246   return steps < 128 ? steps/128.0 : steps < 512-128 ? 1.0 : (512-steps)/128.0;
 247 }
 248
 249 /* draw pieces */
 250 void drawPieces(void) {
 251   int i, j;
 252
 253   for(i = 0; i < BOARDSIZE; ++i) {
 254     for(j = 0; j < BOARDSIZE; ++j) {
 255       if(board[i][j]) {
 256         glColor3fv(colors[colorset][i%2]);
 257         glCallList(QUEEN);
 258       }
 259
 260       glTranslatef(1.0, 0.0, 0.0);
 261     }
 262
 263     glTranslatef(-1.0*BOARDSIZE, 0.0, 1.0);
 264   }
 265 }
 266
 267 /** reflectionboard */
 268 void draw_reflections(void) {
 269   int i, j;
 270
 271   glEnable(GL_STENCIL_TEST);
 272   glStencilFunc(GL_ALWAYS, 1, 1);
 273   glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
 274   glColorMask(0,0,0,0);
 275   glDisable(GL_CULL_FACE);
 276
 277   glDisable(GL_DEPTH_TEST);
 278   glBegin(GL_QUADS);
 279
 280   /* only draw white squares */
 281   for(i = 0; i < BOARDSIZE; ++i) {
 282     for(j = (BOARDSIZE+i) % 2; j < BOARDSIZE; j += 2) {
 283       glVertex3f(i, 0.0, j + 1.0);
 284       glVertex3f(i + 1.0, 0.0, j + 1.0);
 285       glVertex3f(i + 1.0, 0.0, j);
 286       glVertex3f(i, 0.0, j);
 287     }
 288   }
 289   glEnd();
 290   glEnable(GL_DEPTH_TEST);
 291
 292   glColorMask(1, 1, 1, 1);
 293   glStencilFunc(GL_EQUAL, 1, 1);
 294   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
 295
 296   glPushMatrix();
 297   glScalef(1.0, -1.0, 1.0);
 298   glTranslatef(0.5, 0.001, 0.5);
 299   glLightfv(GL_LIGHT0, GL_POSITION, position0);
 300   glLightfv(GL_LIGHT1, GL_POSITION, position1);
 301   drawPieces();
 302   glPopMatrix();
 303   glDisable(GL_STENCIL_TEST);
 304
 305   /* replace lights */
 306   glLightfv(GL_LIGHT0, GL_POSITION, position0);
 307   glLightfv(GL_LIGHT1, GL_POSITION, position1);
 308
 309   glEnable(GL_CULL_FACE);
 310   glCullFace(GL_BACK);
 311   glColorMask(1,1,1,1);
 312 }
 313
 314 /* draw board */
 315 void drawBoard(void) {
 316   int i, j;
 317
 318   glBegin(GL_QUADS);
 319
 320   for(i = 0; i < BOARDSIZE; ++i)
 321     for(j = 0; j < BOARDSIZE; ++j) {
 322       int par = (i-j+BOARDSIZE)%2;
 323       glColor4f(colors[colorset][par][0],
 324                 colors[colorset][par][1],
 325                 colors[colorset][par][2],
 326                 0.60);
 327       glNormal3f(0.0, 1.0, 0.0);
 328       glVertex3f(i, 0.0, j + 1.0);
 329       glVertex3f(i + 1.0, 0.0, j + 1.0);
 330       glVertex3f(i + 1.0, 0.0, j);
 331       glVertex3f(i, 0.0, j);
 332     }
 333
 334   glEnd();
 335 }
 336
 337 double theta = 0.0;
 338
 339 void display(Queenscreen *c) {
 340   glClear(clearbits);
 341
 342   glMatrixMode(GL_MODELVIEW);
 343   glLoadIdentity();
 344
 345   glEnable(GL_LIGHTING);
 346   glEnable(GL_COLOR_MATERIAL);
 347   glLightfv(GL_LIGHT0, GL_POSITION, position0);
 348   glLightfv(GL_LIGHT1, GL_POSITION, position1);
 349   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 1.0/(0.01+findAlpha()));
 350   glLightf(GL_LIGHT1, GL_CONSTANT_ATTENUATION, 1.0/(0.01+findAlpha()));
 351
 352   /** setup perspectif */
 353   glTranslatef(0.0, 0.0, -1.5*BOARDSIZE);
 354   glRotatef(30.0, 1.0, 0.0, 0.0);
 355   gltrackball_rotate (c->trackball);
 356   glRotatef(theta*100, 0.0, 1.0, 0.0);
 357   glTranslatef(-0.5*BOARDSIZE, 0.0, -0.5*BOARDSIZE);
 358
 359   /* draw reflections */
 360   draw_reflections();
 361   glEnable(GL_BLEND);
 362   drawBoard();
 363   glDisable(GL_BLEND);
 364
 365   position1[0] = BOARDSIZE+2.0;
 366   position1[2] = BOARDSIZE+2.0;
 367   glLightfv(GL_LIGHT0, GL_POSITION, position0);
 368   glLightfv(GL_LIGHT1, GL_POSITION, position1);
 369
 370   glTranslatef(0.5, 0.0, 0.5);
 371   drawPieces();
 372
 373   /* rotate camera */
 374   if(!c->button_down_p)
 375     theta += .002;
 376
 377   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 378   if(++steps == 512) {
 379     steps = 0;
 380     blank();
 381     BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 382     colorset = (colorset+1)%COLORSETS;
 383     go();
 384   }
 385 }
 386
 387 int schunks = 15;
 388 GLfloat spidermodel[][3] =
 389   {
 390     {0.48, 0.48, 0.22},
 391     {0.48, 0.34, 0.18},
 392     {0.34, 0.34, 0.10},
 393     {0.34, 0.18, 0.30},
 394     {0.18, 0.14, 0.38},
 395     {0.14, 0.29, 0.01},
 396     {0.29, 0.18, 0.18},
 397     {0.18, 0.18, 0.16},
 398     {0.18, 0.20, 0.26},
 399     {0.20, 0.27, 0.14},
 400     {0.27, 0.24, 0.08},
 401     {0.24, 0.17, 0.00},
 402     {0.17, 0.095, 0.08},
 403     {0.095, 0.07, 0.00},
 404     {0.07, 0.00, 0.12},
 405   };
 406
 407 #define EPSILON 0.001
 408
 409 /** draws cylindermodel */
 410 void draw_model(int chunks, GLfloat model[][3], int r) {
 411   int i = 0;
 412   GLUquadricObj *quadric = gluNewQuadric();
 413   glPushMatrix();
 414   glRotatef(-90.0, 1.0, 0.0, 0.0);
 415
 416   for(i = 0; i < chunks; ++i) {
 417     if(model[i][0] > EPSILON || model[i][1] > EPSILON)
 418       gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 419     glTranslatef(0.0, 0.0, model[i][2]);
 420   }
 421
 422   glPopMatrix();
 423 }
 424
 425 void reshape_queens(ModeInfo *mi, int width, int height) {
 426   GLfloat h = (GLfloat) height / (GLfloat) width;
 427   glViewport(0,0, width, height);
 428   glMatrixMode(GL_PROJECTION);
 429   glLoadIdentity();
 430   gluPerspective(45, 1/h, 2.0, 30.0);
 431   glMatrixMode(GL_MODELVIEW);
 432 }
 433
 434 void init_queens(ModeInfo *mi) {
 435   int screen = MI_SCREEN(mi);
 436   Queenscreen *c;
 437   wire = MI_IS_WIREFRAME(mi);
 438
 439   if(!qs &&
 440      !(qs = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 441     return;
 442
 443   c = &qs[screen];
 444   c->window = MI_WINDOW(mi);
 445   c->trackball = gltrackball_init ();
 446
 447   if((c->glx_context = init_GL(mi)))
 448     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 449   else
 450     MI_CLEARWINDOW(mi);
 451
 452   glClearColor(0.0, 0.0, 0.0, 0.0);
 453   glNewList(QUEEN, GL_COMPILE);
 454   draw_model(schunks, spidermodel, 24);
 455   glEndList();
 456
 457   clearbits = GL_COLOR_BUFFER_BIT;
 458
 459   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 460   glEnable(GL_COLOR_MATERIAL);
 461
 462   if(!wire) {
 463     setup_lights();
 464     glEnable(GL_DEPTH_TEST);
 465     clearbits |= GL_DEPTH_BUFFER_BIT;
 466     clearbits |= GL_STENCIL_BUFFER_BIT;
 467     glEnable(GL_CULL_FACE);
 468     glCullFace(GL_BACK);
 469   }
 470   else
 471     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 472
 473   /* find a solution */
 474   go();
 475 }
 476
 477 void draw_queens(ModeInfo *mi) {
 478   Queenscreen *c = &qs[MI_SCREEN(mi)];
 479   Window w = MI_WINDOW(mi);
 480   Display *disp = MI_DISPLAY(mi);
 481
 482   if(!c->glx_context)
 483     return;
 484
 485   glXMakeCurrent(disp, w, *(c->glx_context));
 486
 487   display(c);
 488
 489   if(mi->fps_p) do_fps(mi);
 490   glFinish();
 491   glXSwapBuffers(disp, w);
 492 }
 493
 494 void release_queens(ModeInfo *mi) {
 495   if(qs)
 496     free((void *) qs);
 497
 498   FreeAllGL(MI);
 499 }
 500
 501 #endif