ncurses 5.3
[ncurses.git] / test / knight.c
1 /*
2  * Knight's Tour - a brain game
3  *
4  * The original of this game was anonymous.  It had an unbelievably bogus
5  * interface, you actually had to enter square coordinates!  Redesign by
6  * Eric S. Raymond <esr@snark.thyrsus.com> July 22 1995.  Mouse support
7  * added September 20th 1995.
8  *
9  * $Id: knight.c,v 1.25 2002/06/29 23:32:18 tom Exp $
10  */
11
12 #include <ctype.h>
13
14 #include <test.priv.h>
15
16 /* board size */
17 #define BDEPTH  8
18 #define BWIDTH  8
19
20 /* where to start the instructions */
21 #define INSTRY  2
22 #define INSTRX  35
23
24 /* corner of board */
25 #define BOARDY  2
26 #define BOARDX  0
27
28 /* notification line */
29 #define NOTIFYY 21
30
31 /* virtual color values */
32 #define TRAIL_COLOR     1
33 #define PLUS_COLOR      2
34 #define MINUS_COLOR     3
35
36 #define CX(x)           (2 + 4 * (x))
37 #define CY(y)           (1 + 2 * (y))
38 #define cellmove(y, x)  wmove(boardwin, CY(y), CX(x))
39 #define CXINV(x)        (((x) - 1) / 4)
40 #define CYINV(y)        (((y) - 2) / 2)
41
42 typedef struct {
43     short x, y;
44 } cell;
45
46 static WINDOW *boardwin;        /* the board window */
47 static WINDOW *helpwin;         /* the help window */
48 static WINDOW *msgwin;          /* the message window */
49 static cell history[BDEPTH * BWIDTH + 1];       /* choice history */
50 static chtype minus = '-';      /* possible-move character */
51 static chtype oldch;
52 static chtype plus = '+';       /* cursor hot-spot character */
53 static chtype trail = '#';      /* trail character */
54 static int movecount;           /* count of moves so far */
55 static int trialcount;          /* count of trials so far */
56 static short board[BDEPTH][BWIDTH];     /* the squares */
57 /* *INDENT-OFF* */
58 static const struct {
59     int y;
60     int x;
61 } offsets[] = {
62     {  2,  1 },
63     {  1,  2 },
64     { -1,  2 },
65     { -2,  1 },
66     { -2, -1 },
67     { -1, -2 },
68     {  1, -2 },
69     {  2, -1 },
70 };
71 /* *INDENT-ON* */
72
73 static void
74 init_program(void)
75 {
76     setlocale(LC_ALL, "");
77
78     srand((unsigned) getpid());
79     initscr();
80     cbreak();                   /* immediate char return */
81     noecho();                   /* no immediate echo */
82     boardwin = newwin(BDEPTH * 2 + 1, BWIDTH * 4 + 1, BOARDY, BOARDX);
83     helpwin = newwin(0, 0, INSTRY, INSTRX);
84     msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0);
85     scrollok(msgwin, TRUE);
86     keypad(boardwin, TRUE);
87
88     if (has_colors()) {
89         int bg = COLOR_BLACK;
90
91         start_color();
92 #if HAVE_USE_DEFAULT_COLORS
93         if (use_default_colors() == OK)
94             bg = -1;
95 #endif
96
97         (void) init_pair(TRAIL_COLOR, COLOR_CYAN, bg);
98         (void) init_pair(PLUS_COLOR, COLOR_RED, bg);
99         (void) init_pair(MINUS_COLOR, COLOR_GREEN, bg);
100
101         trail |= COLOR_PAIR(TRAIL_COLOR);
102         plus |= COLOR_PAIR(PLUS_COLOR);
103         minus |= COLOR_PAIR(MINUS_COLOR);
104     }
105 #ifdef NCURSES_MOUSE_VERSION
106     (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL);
107 #endif /* NCURSES_MOUSE_VERSION */
108
109     oldch = minus;
110 }
111
112 static void
113 help1(void)
114 /* game explanation -- initial help screen */
115 {
116     (void) waddstr(helpwin, "Knight's move is a solitaire puzzle.  Your\n");
117     (void) waddstr(helpwin, "objective is to visit each square of the  \n");
118     (void) waddstr(helpwin, "chessboard exactly once by making knight's\n");
119     (void) waddstr(helpwin, "moves (one square right or left followed  \n");
120     (void) waddstr(helpwin, "by two squares up or down, or two squares \n");
121     (void) waddstr(helpwin, "right or left followed by one square up or\n");
122     (void) waddstr(helpwin, "down).  You may start anywhere.\n\n");
123
124     (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n");
125     (void) waddstr(helpwin, "When you want to move your knight to the \n");
126     (void) waddstr(helpwin, "cursor location, press <space> or Enter.\n");
127     (void) waddstr(helpwin, "Illegal moves will be rejected with an  \n");
128     (void) waddstr(helpwin, "audible beep.\n\n");
129     (void) waddstr(helpwin, "The program will detect if you solve the\n");
130     (void) waddstr(helpwin, "puzzle; also inform you when you run out\n");
131     (void) waddstr(helpwin, "of legal moves.\n\n");
132
133     (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
134                      "Press `?' to go to keystroke help.");
135 }
136
137 static void
138 help2(void)
139 /* keystroke help screen */
140 {
141     (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n");
142
143     (void) waddstr(helpwin, "You can move around with the arrow keys or\n");
144     (void) waddstr(helpwin, "with the rogue/hack movement keys.  Other\n");
145     (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n");
146     (void) waddstr(helpwin, "Your mouse may work; try left-button to\n");
147     (void) waddstr(helpwin, "move to the square under the pointer.\n\n");
148
149     (void) waddstr(helpwin, "x,q -- exit             y k u    7 8 9\n");
150     (void) waddstr(helpwin, "r -- redraw screen       \\|/      \\|/ \n");
151     (void) waddstr(helpwin, "bksp -- undo move       h-+-l    4-+-6\n");
152     (void) waddstr(helpwin, "a -- autojump            /|\\      /|\\ \n");
153     (void) waddstr(helpwin, "                        b j n    1 2 3\n");
154
155     (void) waddstr(helpwin, "\nYou can place your knight on the selected\n");
156     (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n");
157     (void) waddstr(helpwin, "center key.  Use F/B to review the path.\n");
158
159     (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
160                      "Press `?' to go to game explanation");
161 }
162
163 static void
164 show_help(bool * keyhelp)
165 {
166     werase(helpwin);
167     if (*keyhelp) {
168         help1();
169         *keyhelp = FALSE;
170     } else {
171         help2();
172         *keyhelp = TRUE;
173     }
174     wrefresh(helpwin);
175 }
176
177 static bool
178 chksqr(int r1, int c1)
179 {
180     if ((r1 < 0) || (r1 > BDEPTH - 1))
181         return (FALSE);
182     if ((c1 < 0) || (c1 > BWIDTH - 1))
183         return (FALSE);
184     return ((!board[r1][c1]) ? TRUE : FALSE);
185 }
186
187 static bool
188 chkmoves(int rw, int col)
189 /* check to see if valid moves are available */
190 {
191     unsigned n;
192
193     for (n = 0; n < SIZEOF(offsets); n++)
194         if (chksqr(rw + offsets[n].y, col + offsets[n].x))
195             return (TRUE);
196     return (FALSE);
197 }
198
199 static void
200 dosquares(void)
201 {
202     int i, j;
203
204     mvaddstr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
205
206     move(BOARDY, BOARDX);
207     waddch(boardwin, ACS_ULCORNER);
208     for (j = 0; j < 7; j++) {
209         waddch(boardwin, ACS_HLINE);
210         waddch(boardwin, ACS_HLINE);
211         waddch(boardwin, ACS_HLINE);
212         waddch(boardwin, ACS_TTEE);
213     }
214     waddch(boardwin, ACS_HLINE);
215     waddch(boardwin, ACS_HLINE);
216     waddch(boardwin, ACS_HLINE);
217     waddch(boardwin, ACS_URCORNER);
218
219     for (i = 1; i < BDEPTH; i++) {
220         move(BOARDY + i * 2 - 1, BOARDX);
221         waddch(boardwin, ACS_VLINE);
222         for (j = 0; j < BWIDTH; j++) {
223             waddch(boardwin, ' ');
224             waddch(boardwin, ' ');
225             waddch(boardwin, ' ');
226             waddch(boardwin, ACS_VLINE);
227         }
228         move(BOARDY + i * 2, BOARDX);
229         waddch(boardwin, ACS_LTEE);
230         for (j = 0; j < BWIDTH - 1; j++) {
231             waddch(boardwin, ACS_HLINE);
232             waddch(boardwin, ACS_HLINE);
233             waddch(boardwin, ACS_HLINE);
234             waddch(boardwin, ACS_PLUS);
235         }
236         waddch(boardwin, ACS_HLINE);
237         waddch(boardwin, ACS_HLINE);
238         waddch(boardwin, ACS_HLINE);
239         waddch(boardwin, ACS_RTEE);
240     }
241
242     move(BOARDY + i * 2 - 1, BOARDX);
243     waddch(boardwin, ACS_VLINE);
244     for (j = 0; j < BWIDTH; j++) {
245         waddch(boardwin, ' ');
246         waddch(boardwin, ' ');
247         waddch(boardwin, ' ');
248         waddch(boardwin, ACS_VLINE);
249     }
250
251     move(BOARDY + i * 2, BOARDX);
252     waddch(boardwin, ACS_LLCORNER);
253     for (j = 0; j < BWIDTH - 1; j++) {
254         waddch(boardwin, ACS_HLINE);
255         waddch(boardwin, ACS_HLINE);
256         waddch(boardwin, ACS_HLINE);
257         waddch(boardwin, ACS_BTEE);
258     }
259     waddch(boardwin, ACS_HLINE);
260     waddch(boardwin, ACS_HLINE);
261     waddch(boardwin, ACS_HLINE);
262     waddch(boardwin, ACS_LRCORNER);
263 }
264
265 static void
266 mark_possibles(int prow, int pcol, chtype mark)
267 {
268     unsigned n;
269
270     for (n = 0; n < SIZEOF(offsets); n++) {
271         if (chksqr(prow + offsets[n].y, pcol + offsets[n].x)) {
272             cellmove(prow + offsets[n].y, pcol + offsets[n].x);
273             waddch(boardwin, mark);
274         }
275     }
276 }
277
278 static void
279 find_next_move(int *y, int *x)
280 {
281     unsigned j, k;
282     int found = -1;
283     int first = -1;
284     int next = 0;
285     int oldy, oldx;
286     int newy, newx;
287
288     if (movecount > 1) {
289         oldy = history[movecount - 1].y;
290         oldx = history[movecount - 1].x;
291         for (j = 0; j < SIZEOF(offsets) * 2; j++) {
292             k = j % SIZEOF(offsets);
293             newy = oldy + offsets[k].y;
294             newx = oldx + offsets[k].x;
295             if (chksqr(newy, newx)) {
296                 if (first < 0)
297                     first = k;
298                 if (newy == *y
299                     && newx == *x) {
300                     found = k;
301                 } else if (found >= 0) {
302                     next = k;
303                     break;
304                 }
305             }
306         }
307         if (found < 0)
308             next = first;
309         if (next >= 0) {
310             *y = oldy + offsets[next].y;
311             *x = oldx + offsets[next].x;
312         }
313     } else {
314         beep();
315     }
316 }
317
318 static void
319 unmarkcell(int row, int column)
320 {
321     cellmove(row, column);
322     waddch(boardwin, '\b');
323     waddch(boardwin, ' ');
324     waddch(boardwin, minus);
325     waddch(boardwin, ' ');
326 }
327
328 static void
329 markcell(chtype tchar, int row, int column)
330 {
331     cellmove(row, column);
332     waddch(boardwin, '\b');
333     waddch(boardwin, tchar);
334     waddch(boardwin, tchar);
335     waddch(boardwin, tchar);
336 }
337
338 static void
339 drawmove(chtype tchar, int oldy, int oldx, int row, int column)
340 /* place the stars, update board & currents */
341 {
342     if (movecount <= 1) {
343         int i, j;
344
345         for (i = 0; i < BDEPTH; i++) {
346             for (j = 0; j < BWIDTH; j++) {
347                 if (movecount == 0) {
348                     unmarkcell(i, j);
349                 } else {
350                     cellmove(i, j);
351                     if (winch(boardwin) == minus)
352                         waddch(boardwin, movecount ? ' ' : minus);
353                 }
354             }
355         }
356     } else {
357         markcell(tchar, oldy, oldx);
358         mark_possibles(oldy, oldx, ' ');
359     }
360
361     if (row != -1 && column != -1) {
362         markcell(trail, row, column);
363         mark_possibles(row, column, minus);
364         board[row][column] = TRUE;
365     }
366
367     wprintw(msgwin, "\nMove %d", movecount);
368     if (trialcount != movecount)
369         wprintw(msgwin, " (%d tries)", trialcount);
370     wclrtoeol(msgwin);
371 }
372
373 static int
374 iabs(int num)
375 {
376     if (num < 0)
377         return (-num);
378     else
379         return (num);
380 }
381
382 static bool
383 evalmove(int row, int column)
384 /* evaluate move */
385 {
386     if (movecount == 1)
387         return (TRUE);
388     else if (board[row][column] == TRUE) {
389         waddstr(msgwin, "\nYou've already been there.");
390         return (FALSE);
391     } else {
392         int rdif = iabs(row - history[movecount - 1].y);
393         int cdif = iabs(column - history[movecount - 1].x);
394
395         if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
396             waddstr(msgwin, "\nThat's not a legal knight's move.");
397             return (FALSE);
398         }
399     }
400
401     return (TRUE);
402 }
403
404 static int
405 completed(void)
406 {
407     int i, j, count = 0;
408
409     for (i = 0; i < BDEPTH; i++)
410         for (j = 0; j < BWIDTH; j++)
411             if (board[i][j] != 0)
412                 count += 1;
413     return (count == (BWIDTH * BDEPTH) ? -1 : count);
414 }
415
416 static void
417 no_previous_move(void)
418 {
419     waddstr(msgwin, "\nNo previous move.");
420     beep();
421 }
422
423 static void
424 play(void)
425 /* play the game */
426 {
427     bool keyhelp;               /* TRUE if keystroke help is up */
428     int i, j, count;
429     int lastcol = 0;            /* last location visited */
430     int lastrow = 0;
431     int ny = 0, nx = 0;
432     int review = 0;             /* review history */
433     int rw = 0, col = 0;        /* current row and column */
434
435     do {
436         /* clear screen and draw board */
437         werase(boardwin);
438         werase(helpwin);
439         werase(msgwin);
440         dosquares();
441         help1();
442         wnoutrefresh(stdscr);
443         wnoutrefresh(helpwin);
444         wnoutrefresh(msgwin);
445         wnoutrefresh(boardwin);
446         doupdate();
447
448         movecount = 0;
449         for (i = 0; i < BDEPTH; i++) {
450             for (j = 0; j < BWIDTH; j++) {
451                 board[i][j] = FALSE;
452                 unmarkcell(i, j);
453             }
454         }
455         memset(history, 0, sizeof(history));
456         history[0].y = history[0].x = -1;
457         history[1].y = history[1].x = -1;
458         lastrow = lastcol = -2;
459         movecount = 1;
460         trialcount = 1;
461         keyhelp = FALSE;
462         show_help(&keyhelp);
463
464         for (;;) {
465             if (rw != lastrow || col != lastcol) {
466                 if (lastrow >= 0 && lastcol >= 0) {
467                     cellmove(lastrow, lastcol);
468                     if (board[lastrow][lastcol])
469                         waddch(boardwin, trail);
470                     else
471                         waddch(boardwin, oldch);
472                 }
473
474                 cellmove(rw, col);
475                 oldch = winch(boardwin);
476
477                 lastrow = rw;
478                 lastcol = col;
479             }
480             cellmove(rw, col);
481             waddch(boardwin, plus);
482             cellmove(rw, col);
483
484             wrefresh(msgwin);
485
486             switch (wgetch(boardwin)) {
487             case 'k':
488             case '8':
489             case KEY_UP:
490                 ny = rw + BDEPTH - 1;
491                 nx = col;
492                 break;
493             case 'j':
494             case '2':
495             case KEY_DOWN:
496                 ny = rw + 1;
497                 nx = col;
498                 break;
499             case 'h':
500             case '4':
501             case KEY_LEFT:
502                 ny = rw;
503                 nx = col + BWIDTH - 1;
504                 break;
505             case 'l':
506             case '6':
507             case KEY_RIGHT:
508                 ny = rw;
509                 nx = col + 1;
510                 break;
511             case 'y':
512             case '7':
513             case KEY_A1:
514                 ny = rw + BDEPTH - 1;
515                 nx = col + BWIDTH - 1;
516                 break;
517             case 'b':
518             case '1':
519             case KEY_C1:
520                 ny = rw + 1;
521                 nx = col + BWIDTH - 1;
522                 break;
523             case 'u':
524             case '9':
525             case KEY_A3:
526                 ny = rw + BDEPTH - 1;
527                 nx = col + 1;
528                 break;
529             case 'n':
530             case '3':
531             case KEY_C3:
532                 ny = rw + 1;
533                 nx = col + 1;
534                 break;
535
536 #ifdef NCURSES_MOUSE_VERSION
537             case KEY_MOUSE:
538                 {
539                     MEVENT myevent;
540
541                     getmouse(&myevent);
542                     if (myevent.y >= CY(0) && myevent.y <= CY(BDEPTH)
543                         && myevent.x >= CX(0) && myevent.x <= CX(BWIDTH)) {
544                         nx = CXINV(myevent.x);
545                         ny = CYINV(myevent.y);
546                         ungetch('\n');
547                         break;
548                     } else {
549                         beep();
550                         continue;
551                     }
552                 }
553 #endif /* NCURSES_MOUSE_VERSION */
554
555             case KEY_B2:
556             case '\n':
557             case ' ':
558                 review = 0;
559                 if (evalmove(rw, col)) {
560                     drawmove(trail,
561                              history[movecount - 1].y,
562                              history[movecount - 1].x,
563                              rw, col);
564                     history[movecount].y = rw;
565                     history[movecount].x = col;
566                     movecount++;
567                     trialcount++;
568
569                     if (!chkmoves(rw, col)) {
570                         if (completed() < 0) {
571                             waddstr(msgwin, "\nYou won.");
572                         } else {
573                             waddstr(msgwin,
574                                     "\nNo further moves are possible.");
575                         }
576                     }
577                 } else {
578                     beep();
579                 }
580                 break;
581
582             case KEY_UNDO:
583             case KEY_BACKSPACE:
584             case '\b':
585                 review = 0;
586                 if (movecount <= 0) {
587                     no_previous_move();
588                 } else if (movecount <= 1) {
589                     ny = history[movecount].y;
590                     nx = history[movecount].x;
591                     if (nx < 0 || ny < 0) {
592                         ny = lastrow;
593                         nx = lastcol;
594                     }
595                     movecount = 0;
596                     board[ny][nx] = FALSE;
597                     oldch = minus;
598                     drawmove(' ', ny, nx, -1, -1);
599                     movecount = 1;
600                     trialcount = 1;
601                     no_previous_move();
602                 } else {
603                     int oldy = history[movecount - 1].y;
604                     int oldx = history[movecount - 1].x;
605
606                     if (!board[rw][col]) {
607                         cellmove(rw, col);
608                         waddch(boardwin, ' ');
609                     }
610
611                     board[oldy][oldx] = FALSE;
612                     --movecount;
613                     ny = history[movecount - 1].y;
614                     nx = history[movecount - 1].x;
615                     if (nx < 0 || ny < 0) {
616                         ny = oldy;
617                         nx = oldx;
618                     }
619                     drawmove(' ', oldy, oldx, ny, nx);
620
621                     /* avoid problems if we just changed the current cell */
622                     cellmove(lastrow, lastcol);
623                     oldch = winch(boardwin);
624                 }
625                 break;
626
627             case 'a':
628                 nx = col;
629                 ny = rw;
630                 find_next_move(&ny, &nx);
631                 break;
632
633             case 'F':
634                 if (review > 0) {
635                     review--;
636                     ny = history[movecount - review - 1].y;
637                     nx = history[movecount - review - 1].x;
638                 } else {
639                     beep();
640                 }
641                 break;
642
643             case 'B':
644                 if (review < movecount - 2) {
645                     review++;
646                     ny = history[movecount - review - 1].y;
647                     nx = history[movecount - review - 1].x;
648                 } else {
649                     beep();
650                 }
651                 break;
652
653             case KEY_REDO:
654             case '\f':
655             case 'r':
656                 clearok(curscr, TRUE);
657                 wnoutrefresh(stdscr);
658                 wnoutrefresh(boardwin);
659                 wnoutrefresh(msgwin);
660                 wnoutrefresh(helpwin);
661                 doupdate();
662                 break;
663
664             case 'q':
665             case 'x':
666                 goto dropout;
667
668             case '?':
669                 show_help(&keyhelp);
670                 break;
671
672             default:
673                 beep();
674                 break;
675             }
676
677             col = nx % BWIDTH;
678             rw = ny % BDEPTH;
679         }
680
681       dropout:
682         if ((count = completed()) < 0)
683             wprintw(msgwin, "\nYou won.  Care to try again? ");
684         else
685             wprintw(msgwin, "\n%d squares filled.  Try again? ", count);
686         wclrtoeol(msgwin);
687     } while
688         (tolower(wgetch(msgwin)) == 'y');
689 }
690
691 int
692 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
693 {
694     init_program();
695
696     play();
697
698     endwin();
699     ExitProgram(EXIT_SUCCESS);
700 }
701
702 /* knight.c ends here */