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