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