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 3
  96
  97 /* definition of white/black colors */
  98 GLfloat colors[COLORSETS][2][3] =
  99   {
 100     {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
 101     {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
 102     {{1.0, 0.5, 0.0}, {0.5, 0.5, 0.5}},
 103   };
 104
 105 int board[MAXBOARD][MAXBOARD];
 106 int steps = 0, colorset = 0, BOARDSIZE = 8; /* 8 cuz its classic */
 107
 108 Bool
 109 queens_handle_event (ModeInfo *mi, XEvent *event)
 110 {
 111   Queenscreen *c = &qs[MI_SCREEN(mi)];
 112
 113   if (event->xany.type == ButtonPress &&
 114       event->xbutton.button & Button1)
 115     {
 116       c->button_down_p = True;
 117       gltrackball_start (c->trackball,
 118                          event->xbutton.x, event->xbutton.y,
 119                          MI_WIDTH (mi), MI_HEIGHT (mi));
 120       return True;
 121     }
 122   else if (event->xany.type == ButtonRelease &&
 123            event->xbutton.button & Button1)
 124     {
 125       c->button_down_p = False;
 126       return True;
 127     }
 128   else if (event->xany.type == MotionNotify &&
 129            c->button_down_p)
 130     {
 131       gltrackball_track (c->trackball,
 132                          event->xmotion.x, event->xmotion.y,
 133                          MI_WIDTH (mi), MI_HEIGHT (mi));
 134       return True;
 135     }
 136
 137   return False;
 138 }
 139
 140
 141
 142 /* returns true if placing a queen on column c causes a conflict */
 143 int conflictsCols(int c) {
 144   int i;
 145
 146   for(i = 0; i < BOARDSIZE; ++i)
 147     if(board[i][c])
 148       return 1;
 149
 150   return 0;
 151 }
 152
 153 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
 154 int conflictsDiag(int r, int c) {
 155   int i;
 156
 157   /* positive slope */
 158   int n = r < c ? r : c;
 159   for(i = 0; i < BOARDSIZE-abs(r-c); ++i)
 160     if(board[r-n+i][c-n+i])
 161       return 1;
 162
 163   /* negative slope */
 164   n = r < BOARDSIZE - (c+1) ? r : BOARDSIZE - (c+1);
 165   for(i = 0; i < BOARDSIZE-abs(BOARDSIZE - (1+r+c)); ++i)
 166     if(board[r-n+i][c+n-i])
 167       return 1;
 168
 169   return 0;
 170 }
 171
 172 /* returns true if placing a queen at (r,c) causes a conflict */
 173 int conflicts(int r, int c) {
 174   return !conflictsCols(c) ? conflictsDiag(r, c) : 1;
 175 }
 176
 177 /* clear board */
 178 void blank(void) {
 179   int i, j;
 180
 181   for(i = 0; i < MAXBOARD; ++i)
 182     for(j = 0; j < MAXBOARD; ++j)
 183       board[i][j] = NONE;
 184 }
 185
 186 /* recursively determine solution */
 187 int findSolution(int row, int col) {
 188   if(row == BOARDSIZE)
 189     return 1;
 190
 191   while(col < BOARDSIZE) {
 192     if(!conflicts(row, col)) {
 193       board[row][col] = 1;
 194
 195       if(findSolution(row+1, 0))
 196         return 1;
 197
 198       board[row][col] = 0;
 199     }
 200
 201     ++col;
 202   }
 203
 204   return 0;
 205 }
 206
 207 /** driver for finding solution */
 208 void go(void) { while(!findSolution(0, random()%BOARDSIZE)); }
 209
 210 /* configure lighting */
 211 void setup_lights(void) {
 212   GLfloat position[] = { 4.0, 8.0, 4.0, 1.0 };
 213
 214   glEnable(GL_LIGHTING);
 215   glLightfv(GL_LIGHT0, GL_POSITION, position);
 216   glEnable(GL_LIGHT0);
 217 }
 218
 219 /* return alpha value for fading */
 220 GLfloat findAlpha(void) {
 221   return steps < 128 ? steps/128.0 : steps < 512-128 ? 1.0 : (512-steps)/128.0;
 222 }
 223
 224 /* draw pieces */
 225 void drawPieces(void) {
 226   int i, j;
 227
 228   for(i = 0; i < BOARDSIZE; ++i) {
 229     for(j = 0; j < BOARDSIZE; ++j) {
 230       if(board[i][j]) {
 231         glColor3fv(colors[colorset][i%2]);
 232         glCallList(QUEEN);
 233       }
 234
 235       glTranslatef(1.0, 0.0, 0.0);
 236     }
 237
 238     glTranslatef(-1.0*BOARDSIZE, 0.0, 1.0);
 239   }
 240 }
 241
 242 /* draw board */
 243 void drawBoard(void) {
 244   int i, j;
 245
 246   glBegin(GL_QUADS);
 247
 248   for(i = 0; i < BOARDSIZE; ++i)
 249     for(j = 0; j < BOARDSIZE; ++j) {
 250       int par = (i-j+BOARDSIZE)%2;
 251       glColor3fv(colors[colorset][par]);
 252       glNormal3f(0.0, 1.0, 0.0);
 253       glVertex3f(i, 0.0, j + 1.0);
 254       glVertex3f(i + 1.0, 0.0, j + 1.0);
 255       glVertex3f(i + 1.0, 0.0, j);
 256       glVertex3f(i, 0.0, j);
 257
 258       /* draw the bottom, too */
 259       glNormal3f(0.0, -1.0, 0.0);
 260       glVertex3f(i, 0.0, j);
 261       glVertex3f(i + 1.0, 0.0, j);
 262       glVertex3f(i + 1.0, 0.0, j + 1.0);
 263       glVertex3f(i, 0.0, j + 1.0);
 264     }
 265
 266   glEnd();
 267 }
 268
 269 double theta = 0.0;
 270
 271 void display(Queenscreen *c) {
 272   glClear(clearbits);
 273
 274   glMatrixMode(GL_MODELVIEW);
 275   glLoadIdentity();
 276
 277   glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha()));
 278
 279   /** setup perspectif */
 280   glTranslatef(0.0, 0.0, -1.5*BOARDSIZE);
 281   glRotatef(30.0, 1.0, 0.0, 0.0);
 282   gltrackball_rotate (c->trackball);
 283   glRotatef(theta*100, 0.0, 1.0, 0.0);
 284   glTranslatef(-0.5*BOARDSIZE, 0.0, -0.5*BOARDSIZE);
 285
 286   drawBoard();
 287   glTranslatef(0.5, 0.01, 0.5);
 288   drawPieces();
 289
 290   if (!c->button_down_p)
 291     theta += .002;
 292
 293   /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
 294   if(++steps == 512) {
 295     steps = 0;
 296     blank();
 297     BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
 298     colorset = (colorset+1)%COLORSETS;
 299     go();
 300   }
 301 }
 302
 303 int schunks = 15;
 304 GLfloat spidermodel[][3] =
 305   {
 306     {0.48, 0.48, 0.22},
 307     {0.48, 0.34, 0.18},
 308     {0.34, 0.34, 0.10},
 309     {0.34, 0.18, 0.30},
 310     {0.18, 0.14, 0.38},
 311     {0.14, 0.29, 0.01},
 312     {0.29, 0.18, 0.18},
 313     {0.18, 0.18, 0.16},
 314     {0.18, 0.20, 0.26},
 315     {0.20, 0.27, 0.14},
 316     {0.27, 0.24, 0.08},
 317     {0.24, 0.17, 0.00},
 318     {0.17, 0.095, 0.08},
 319     {0.095, 0.07, 0.00},
 320     {0.07, 0.00, 0.12},
 321   };
 322
 323 #define EPSILON 0.001
 324
 325 /** draws cylindermodel */
 326 void draw_model(int chunks, GLfloat model[][3], int r) {
 327   int i = 0;
 328   GLUquadricObj *quadric = gluNewQuadric();
 329   glPushMatrix();
 330   glRotatef(-90.0, 1.0, 0.0, 0.0);
 331
 332   for(i = 0; i < chunks; ++i) {
 333     if(model[i][0] > EPSILON || model[i][1] > EPSILON)
 334       gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
 335     glTranslatef(0.0, 0.0, model[i][2]);
 336   }
 337
 338   glPopMatrix();
 339 }
 340
 341 void reshape_queens(ModeInfo *mi, int width, int height) {
 342   GLfloat h = (GLfloat) height / (GLfloat) width;
 343   glViewport(0,0, width, height);
 344   glMatrixMode(GL_PROJECTION);
 345   glLoadIdentity();
 346   gluPerspective(45, 1/h, 2.0, 30.0);
 347   glMatrixMode(GL_MODELVIEW);
 348 }
 349
 350 void init_queens(ModeInfo *mi) {
 351   int screen = MI_SCREEN(mi);
 352   Queenscreen *c;
 353   wire = MI_IS_WIREFRAME(mi);
 354
 355   if(!qs &&
 356      !(qs = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
 357     return;
 358
 359   c = &qs[screen];
 360   c->window = MI_WINDOW(mi);
 361   c->trackball = gltrackball_init ();
 362
 363   if((c->glx_context = init_GL(mi)))
 364     reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
 365   else
 366     MI_CLEARWINDOW(mi);
 367
 368   glClearColor(0.0, 0.0, 0.0, 0.0);
 369   glNewList(1, GL_COMPILE);
 370   draw_model(schunks, spidermodel, 24);
 371   glEndList();
 372
 373   clearbits = GL_COLOR_BUFFER_BIT;
 374
 375   glColorMaterial(GL_FRONT, GL_DIFFUSE);
 376   glEnable(GL_COLOR_MATERIAL);
 377
 378   if(!wire) {
 379     setup_lights();
 380     glEnable(GL_DEPTH_TEST);
 381     clearbits |= GL_DEPTH_BUFFER_BIT;
 382     glEnable(GL_CULL_FACE);
 383     glCullFace(GL_BACK);
 384   }
 385   else
 386     glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
 387
 388   /* find a solution */
 389   go();
 390 }
 391
 392 void draw_queens(ModeInfo *mi) {
 393   Queenscreen *c = &qs[MI_SCREEN(mi)];
 394   Window w = MI_WINDOW(mi);
 395   Display *disp = MI_DISPLAY(mi);
 396
 397   if(!c->glx_context)
 398     return;
 399
 400   glXMakeCurrent(disp, w, *(c->glx_context));
 401
 402   display(c);
 403
 404   if(mi->fps_p) do_fps(mi);
 405   glFinish();
 406   glXSwapBuffers(disp, w);
 407 }
 408
 409 void release_queens(ModeInfo *mi) {
 410   if(qs)
 411     free((void *) qs);
 412
 413   FreeAllGL(MI);
 414 }
 415
 416 #endif