cairo-5c 1.14 / usr / share / doc / cairo-5c / connect-3.5c

/*
 * Copyright © 2012 Keith Packard
 *
 * This library is free software; you can redistribute it and/or
 * modify it either under the terms of the GNU Lesser General Public
 * License version 2.1 as published by the Free Software Foundation
 * (the "LGPL") or, at your option, under the terms of the Mozilla
 * Public License Version 1.1 (the "MPL"). If you do not alter this
 * notice, a recipient may use your version of this file under either
 * the MPL or the LGPL.
 *
 * You should have received a copy of the LGPL along with this library
 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 * You should have received a copy of the MPL along with this library
 * in the file COPYING-MPL-1.1
 *
 * The contents of this file are subject to the Mozilla Public License
 * Version 1.1 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
 * the specific language governing rights and limitations.
 *
 * The Original Code is the cairo graphics library.
 *
 * The Initial Developer of the Original Code is Keith Packard
 *
 * Contributor(s):
 *      Keith Packard <keithp@keithp.com>
 */

/*
 * Connect-3 in a 3x4 grid
 */

autoload Mutex;
autoimport Cairo;
autoimport PRNG;
autoimport Nichrome;
autoload Nichrome::Button;
autoload Nichrome::Label;
autoload Nichrome::Box;

import Widget;
import Nichrome;
import Button;
import Button;
import Box;
import Label;

dev_srandom (32);

typedef int piece_t;

piece_t piece__ = 0;
piece_t piece_x = 1;
piece_t piece_o = 2;

int cols = 3;
int rows = 4;
int row = min(cols,rows);

typedef piece_t[rows, cols] board_t;

typedef struct {
    int x, y;
} position_t;

/*
 * Encode the current game state, which is
 * either 'in progress' or 'player foo has
 * won with pieces from p1 to p2'
 */
typedef union {
    void    playing;
    struct {
	piece_t	    winner;
	position_t  p1, p2;
    } finished;
} status_t;

typedef status_t game_status_t;
/*
 * Game state
 */
typedef struct {
    mutex	    lock;
    bool	    quiting;
    semaphore	    waiter;
    board_t	    board;
    status_t	    status;
    piece_t	    turn;
    piece_t	    computer;
} game_t;

void
set_color (cairo_t cr, piece_t piece)
{
    switch (piece) {
    case piece_x:
	set_source_rgba (cr, 1, 0, 0, 1);
	break;
    case piece_o:
	set_source_rgba (cr, 0, 0, 1, 1);
	break;
    case piece__:
	break;
    }
}

/*
 * Set up cr to draw the game board
 */
void
scale_board (cairo_t cr)
{
    scale (cr, Cairo::width (cr), Cairo::height (cr));
}

void
draw_grid (cairo_t cr)
{
    set_source_rgba (cr, 0, 0, 0, 1);
    for (int line = 0; line < cols - 1; line++)
    {
	move_to (cr, (line + 1) / cols, .05);
	line_to (cr, (line + 1) / cols, rows/cols - .05);
    }
    for (int line = 0; line < rows - 1; line++)
    {    
	move_to (cr, .05, (line + 1) / rows * rows/cols);
	line_to (cr, .95, (line + 1) / rows * rows/cols);
    }
    stroke (cr);
}

void
draw_piece (cairo_t cr, piece_t piece)
{
    new_path (cr);
    set_line_width (cr, 0.2);
    set_line_cap (cr, line_cap_t.ROUND);
    switch (piece) {
    case piece__:
	return;
    case piece_x:
	move_to (cr, -.4, -.4);
	line_to (cr, .4, .4);
	move_to (cr, .4, -.4);
	line_to (cr, -.4, .4);
	break;
    case piece_o:
	arc (cr, 0, 0, 0.4, 0, 2 * pi);
	break;
    }
    set_color (cr, piece);
    stroke (cr);
}

/*
 * Draw the whole board
 */
void
draw_pieces (cairo_t cr, &board_t board)
{
    for (int y = 0; y < rows; y++)
	 for (int x = 0; x < cols; x++)
	 {
	    save (cr);
	    translate (cr, (x + 1/2) / cols, (y + 1/2) / rows * rows/cols);
	    scale (cr, 1/(cols * 4/3), 1/(rows * 4/3) * rows/cols);
	    draw_piece (cr, board[y,x]);
	    restore (cr);
	 }
}

/*
 * Draw a line through the three winning pieces
 */
void
draw_win_line (cairo_t cr, &status_t status)
{
    union switch (status) {
    case finished f:
	if (f.winner == piece__)
	    break;
	set_color (cr, f.winner);
	real x1, x2, y1, y2;
	if (f.p1.x == f.p2.x)
	    x2 = x1 = (f.p1.x + .5) / cols;
	else {
	    if (f.p1.x < f.p2.x) {
		x1 = f.p1.x / cols + 0.05;
		x2 = (f.p2.x + 1) / cols - 0.05;
	    } else {
		x1 = (f.p1.x + 1) / cols - 0.05;
		x2 = f.p2.x / cols + 0.05;
	    }
	}
	if (f.p1.y == f.p2.y)
	    y2 = y1 = (f.p1.y + .5) / rows;
	else {
	    y1 = f.p1.y / rows + 0.05;
	    y2 = (f.p2.y + 1) / rows - 0.05;
	}
	move_to (cr, x1, y1 * rows/cols);
	line_to (cr, x2, y2 * rows/cols);
	stroke (cr);
	break;
    case playing:
	break;
    }
}

/*
 * Figure out the current game status
 */
status_t get_status (&board_t board)
{
    position_t	p1, p2;
    
    bool in_a_row (piece_t piece, position_t p, position_t d) {
	p1 = p;
	for (int i = 0; i < row; i++) {
	    if (board[p.y,p.x] != piece)
		return false;
	    p2 = p;
	    p.x += d.x;
	    p.y += d.y;
	}
	return true;
    }
    
    static piece_t[*] pieces = { piece_x, piece_o };
    
    status_t make_winner (piece_t piece) {
	return (status_t) { finished = { winner = piece, p1 = p1, p2 = p2 } };
    }

    position_t make_pos (x, y) = (position_t) { x = x, y = y };
    
    for (int p = 0; p < dim (pieces); p++) {
	piece_t piece = pieces[p];
	for (int x = 0; x < cols; x++) {
	    for (int y = 0; y <= rows - row; y++) {
		if (in_a_row (piece, make_pos (x, y), make_pos (0, 1)))
		    return make_winner (piece);
	    }
	}
	for (int y = 0; y < rows; y++) {
	    for (int x = 0; x <= cols - row; x++) {
		if (in_a_row (piece, make_pos (x, y), make_pos (1, 0)))
		    return make_winner (piece);
	    }
	}
	for (int y = 0; y <= rows - row; y++) {
	    for (int x = 0; x <= cols - row; x++) {
		if (in_a_row (piece, make_pos (x, y), make_pos (1, 1)))
		    return make_winner (piece);
		if (in_a_row (piece, make_pos (x + row - 1, y), make_pos (-1, 1)))
		    return make_winner (piece);
	    }
	}
    }
    for (int y = 0; y < rows; y++)
	for (int x = 0; x < cols; x++)
	    if (board[y,x] == piece__)
		return (status_t) { playing = ◊ };
    return make_winner (piece__);
}

/*
 * Make a move and return true if the space is empty,
 * otherwise return false
 */
bool move (&board_t board, int x, int y, piece_t piece)
{
    if (board[y,x] != piece__)
	return false;
    if (y > 0 && board[y-1,x] == piece__)
	return false;
    board[y,x] = piece;
    return true;
}

piece_t other_player (piece_t piece)
{
    if (piece == piece_x)
	return piece_o;
    return piece_x;
}

/*
 * Minmax score computation -- very simple, just 0, 2, -2
 * depending on whether the game is in progress, won by us,
 * or won by the other player. A special -1 value is returned
 * for a cats game
 */
int score (&board_t board, piece_t turn)
{
    status_t	status = get_status (&board);

    union switch (status) {
    case playing:
	return 0;
    case finished f:
	if (f.winner == piece__)
	    return -1;
	else if (f.winner == turn)
	    return 2;
	else
	    return -2;
    }
}

typedef struct {
    position_t	position;
    int		score;
} move_t;

int moves = 0;
int memos = 0;
int rands = 0;

move_t[board_t] memo;

void reset_stats () {
    moves = 0;
    memos = 0;
    rands = 0;
}

bool pick_random () {
    ++rands;
    return randbits(1) != 0;
}

/*
 * Compute the best move using minmax search
 */
move_t best_move (&board_t board, piece_t turn) {
    ++moves;

    move_t  best = {
	position = { x = -1, y = -1 },
	score = score(&board, turn)
    };
    
    if (best.score != 0) {
	return best;
    }
    
    /*
     * Check to see if this position has already
     * been scored
     */
    if (hash_test (memo, board)) {
	++memos;
	return memo[board];
    }
    
    piece_t next_turn = other_player (turn);
    
    best.score = -3;
    /*
     * Search the whole board for possible moves
     */
    for (int y = 0; y < rows; y++)
	for (int x = 0; x < cols; x++) {
	    if (move (&board, x, y, turn)) {
		move_t next = best_move (&board, next_turn);
		/*
		 * Minimize our opponents best possible move.
		 * When two moves are equal, pick randomly
		 */
		if (-next.score > best.score || 
		    -next.score == best.score && pick_random())
		{
		    best.position.x = x;
		    best.position.y = y;
		    best.score = -next.score;
		}
		/*
		 * Undo this move
		 */
		board[y,x] = piece__;
	    }
	}
    
    /*
     * Remember this move for next time
     */
    memo[board] = best;
    return best;
}

void reset_game (&game_t game)
{
    game.board = (board_t) { { piece__ ... } ... };
    game.status.playing = ◊;
    game.turn = piece_x;
    memo = (move_t[board_t]) {};
    Semaphore::signal (game.waiter);
}

bool make_move (&game_t game, int x, int y)
{
    if (move (&game.board, x, y, game.turn))
    {
	game.turn = other_player (game.turn);
	game.status = get_status (&game.board);
        Semaphore::signal (game.waiter);
	return true;
    }
    return false;
}

void computer_player (&game_t game, &label_t label)
{
    Mutex::acquire (game.lock);
    while (!game.quiting) {
	Mutex::release (game.lock);
	Semaphore::wait (game.waiter);
	Mutex::acquire (game.lock);
	if (game.status == game_status_t.playing &&
	    game.turn == game.computer) 
	{
	    Label::relabel (&label, "thinking...");
	    Widget::redraw (&label);
	    board_t best_board = game.board;
	    move_t computer = best_move (&best_board, game.turn);
	    assert (computer.position.x != -1, "no move");
	    make_move (&game, computer.position.x, computer.position.y);
	    Label::relabel (&label, sprintf("score: %d", computer.score));
	    Widget::redraw (&label);
	}
    }
    Mutex::release (game.lock);
}

void set_computer (&game_t game, piece_t player)
{
    twixt (Mutex::acquire (game.lock); Mutex::release (game.lock)) {
	game.computer = player;
        Semaphore::signal (game.waiter);
    }
}

extend namespace Nichrome {
    public namespace Gridwidget {
	public typedef widget_t + struct {
	    int down_x, down_y;
	    &game_t game;
	} grid_widget_t;

	/*
	 * Draw the current state of the game
	 */

	void draw (cairo_t cr, &grid_widget_t widget) {
	    scale (cr, widget.geometry.width, -widget.geometry.height*cols/rows);
	    translate (cr, 0, -rows/cols);
	    set_line_width (cr, 0.05);
	    set_line_cap (cr, line_cap_t.ROUND);
	    draw_grid (cr);
	    draw_pieces (cr, &widget.game.board);
	    draw_win_line (cr, &widget.game.status);
	}

	void outline (cairo_t cr, &grid_widget_t widget) {
	    rectangle (cr, 0, 0, widget.geometry.width,
		       widget.geometry.height);
	}
	    
	void natural (cairo_t cr, &grid_widget_t widget)
	{
	    rectangle (cr, 0, 0, cols * 100, rows * 100);
	}
	
	void button (&grid_widget_t widget, &button_event_t event) {
	    &game_t game = &widget.game;
	    int x_i = floor (event.x * cols / widget.geometry.width);
	    int y_i = rows - 1 - floor (event.y * rows / widget.geometry.height);
	    if (event.type == button_type_t.press) {
		widget.down_x = x_i;
		widget.down_y = y_i;
	    } else {
		Mutex::acquire (game.lock);
		if (widget.game.status == game_status_t.playing &&
		    widget.game.turn != widget.game.computer &&
		    x_i == widget.down_x &&
		    y_i == widget.down_y)
		{
		    if (make_move (&widget.game, x_i, y_i))
			Widget::redraw (&widget);
		}
		Mutex::release (game.lock);
	    }
	}
	
	public *grid_widget_t new (&nichrome_t nichrome, &game_t game) {
	    grid_widget_t    widget;
	    
	    Widget::init (&nichrome, &widget);
	    widget.button = button;
	    widget.draw = draw;
	    widget.outline = outline;
	    widget.natural = natural;
	    &widget.game = &game;
	    return &widget;
	}
    }
}

import Nichrome::Gridwidget;

/*
 * Play tic tac toe
 */
void play ()
{
    Widget::default_font = "Comic Sans MS-16";
    &nichrome_t	    nichrome = Nichrome::new ("Connect-3");
    game_t  game = {
	lock = Mutex::new (),
	waiter = Semaphore::new (),
	quiting = false,
	board = { { piece__ ... } ... },
	status = { playing = ◊ },
	turn = piece_x,
	computer = piece_o,
    };
    
    &button_t	    quit = Nichrome::Button::new (&nichrome, "Quit",
						void func (&widget_t w, bool state) {
						    w.nichrome.running = false;
						    game.quiting = true;
						    Semaphore::signal (game.waiter);
						});

    &button_t	    new = Nichrome::Button::new (&nichrome, "New",
					       void func (&widget_t w, bool state) {
						    reset_game (&game);
					       });
    &button_t	    computer;
    void computer_callback (&widget_t w, bool state) {
	set_computer (&game,
		      other_player (game.computer));
	Button::relabel (&computer,
			 "Computer: " + 
			 (game.computer == piece_x ? "x" : "o"));
    }
    
    &computer = Nichrome::Button::new (&nichrome, "Computer: o",
					void func (&widget_t w, bool state) {
					    set_computer (&game,
							  other_player (game.computer));
					    Button::relabel (&computer,
							     "Computer: " + 
							     (game.computer == piece_x ? "x" : "o"));
					});

    &label_t	    thinking = Nichrome::Label::new (&nichrome, "");
    
    &grid_widget_t   widget = Nichrome::Gridwidget::new (&nichrome, &game);
	
    &box_t	    menu = Nichrome::Box::new (Box::dir_t.horizontal,
					       Box::widget_item (&new, 0),
					       Box::widget_item (&quit, 0),
					       Box::widget_item (&computer, 0),
					       Box::glue_item (1),
					       Box::widget_item (&thinking, 0));
    &box_t	    box = Nichrome::Box::new (Box::dir_t.vertical,
					      Box::box_item (&menu),
					      Box::widget_item (&widget));
    Nichrome::set_box (&nichrome, &box);
    fork computer_player (&game, &thinking);
    Nichrome::main_loop (&nichrome);
}

play ();