ba14cc7be888a03cbc4dde3f4d29edaf1b2170c7
[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 (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