path: root/freecell.c

/* Copyright (C) 2019  C. McEnroe <june@causal.agency>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <SDL.h>
#include <cards.h>

#include "asset.h"
#include "stack.h"

typedef unsigned uint;

enum {
	Foundation1,
	Foundation2,
	Foundation3,
	Foundation4,
	Cell1,
	Cell2,
	Cell3,
	Cell4,
	Tableau1,
	Tableau2,
	Tableau3,
	Tableau4,
	Tableau5,
	Tableau6,
	Tableau7,
	Tableau8,
	StacksLen,
};

static struct Stack stacks[StacksLen];

static uint kingIndex = Cards_KingRight;

struct Move {
	uint dst;
	uint src;
};

enum { QueueLen = 16 };
static struct {
	struct Move moves[QueueLen];
	uint r, w, u;
} queue;

static void enqueue(uint dst, uint src) {
	queue.moves[queue.w % QueueLen].dst = dst;
	queue.moves[queue.w % QueueLen].src = src;
	queue.w++;
}

static void dequeue(void) {
	struct Move move = queue.moves[queue.r++ % QueueLen];
	push(&stacks[move.dst], pop(&stacks[move.src]));
	if (move.dst <= Foundation4) {
		kingIndex = Cards_KingRight;
	} else if (move.dst <= Cell4) {
		kingIndex = Cards_KingLeft;
	}
}

static bool undo(void) {
	uint len = queue.w - queue.u;
	if (!len || len > QueueLen) return false;
	for (uint i = len - 1; i < len; --i) {
		struct Move move = queue.moves[(queue.u + i) % QueueLen];
		push(&stacks[move.src], pop(&stacks[move.dst]));
	}
	queue.r = queue.w = queue.u;
	return true;
}

static uint lcgState = 1;
static uint lcgRand(void) {
	lcgState = (214013 * lcgState + 2531011) % (1 << 31);
	return lcgState / (1 << 16);
}

// <https://rosettacode.org/wiki/Deal_cards_for_FreeCell>
static void deal(uint game) {
	lcgState = game;

	queue.r = queue.w = queue.u = 0;
	for (uint i = 0; i < StacksLen; ++i) {
		clear(&stacks[i]);
	}
	kingIndex = Cards_KingRight;

	struct Stack deck = {0};
	for (Card i = Cards_A; i <= Cards_K; ++i) {
		push(&deck, Cards_Club + i);
		push(&deck, Cards_Diamond + i);
		push(&deck, Cards_Heart + i);
		push(&deck, Cards_Spade + i);
	}

	uint stack = 0;
	while (deck.len) {
		uint i = lcgRand() % deck.len;
		Card card = deck.cards[i];
		deck.cards[i] = deck.cards[--deck.len];
		push(&stacks[Tableau1 + stack++ % 8], card);
	}
}

static bool win(void) {
	for (uint i = Foundation1; i <= Foundation4; ++i) {
		if (stacks[i].len != 13) return false;
	}
	return true;
}

static bool valid(uint dst, Card card) {
	Card top = peek(&stacks[dst]);
	if (dst <= Foundation4) {
		if (!top) return rank(card) == Cards_A;
		return suit(card) == suit(top)
			&& rank(card) == rank(top) + 1;
	}
	if (!top) return true;
	if (dst >= Tableau1) {
		return color(card) != color(top)
			&& rank(card) == rank(top) - 1;
	}
	return false;
}

static void autoEnqueue(void) {
	Card min[] = { Cards_K, Cards_K };
	for (uint i = Cell1; i <= Tableau8; ++i) {
		for (uint j = 0; j < stacks[i].len; ++j) {
			Card card = stacks[i].cards[j];
			if (rank(card) < min[color(card)]) {
				min[color(card)] = rank(card);
			}
		}
	}

	for (uint src = Cell1; src <= Tableau8; ++src) {
		Card card = peek(&stacks[src]);
		if (!card) continue;
		if (rank(card) > Cards_2) {
			if (min[!color(card)] < rank(card)) continue;
		}
		for (uint dst = Foundation1; dst <= Foundation4; ++dst) {
			if (valid(dst, card)) {
				enqueue(dst, src);
				return;
			}
		}
	}
}

static void moveSingle(uint dst, uint src) {
	if (valid(dst, peek(&stacks[src]))) {
		queue.u = queue.w;
		enqueue(dst, src);
	}
}

static uint moveDepth(uint src) {
	struct Stack stack = stacks[src];
	if (stack.len < 2) return stack.len;
	uint n = 1;
	for (uint i = stack.len - 2; i < stack.len; --i, ++n) {
		if (color(stack.cards[i]) == color(stack.cards[i + 1])) break;
		if (rank(stack.cards[i]) != rank(stack.cards[i + 1]) + 1) break;
	}
	return n;
}

static uint freeCells(uint cells[], uint dst) {
	uint len = 0;
	for (uint i = Cell1; i <= Tableau8; ++i) {
		if (i == dst) continue;
		if (!stacks[i].len) cells[len++] = i;
	}
	return len;
}

static void moveColumn(uint dst, uint src) {
	uint cells[StacksLen];
	uint free = freeCells(cells, dst);

	uint depth;
	for (depth = moveDepth(src); depth; --depth) {
		if (free < depth - 1) continue;
		if (valid(dst, stacks[src].cards[stacks[src].len - depth])) break;
	}
	if (depth < 2 || dst <= Cell4) {
		moveSingle(dst, src);
		return;
	}

	queue.u = queue.w;
	for (uint i = 0; i < depth - 1; ++i) {
		enqueue(cells[i], src);
	}
	enqueue(dst, src);
	for (uint i = depth - 2; i < depth - 1; --i) {
		enqueue(dst, cells[i]);
	}
}

enum {
	CardWidth = Cards_CardWidth,
	CardHeight = Cards_CardHeight,

	CellX = 0,
	CellY = 0,

	KingMarginX = 13,
	KingX = CellX + 4 * CardWidth + KingMarginX,
	KingY = 18,
	KingPadX = 3,
	KingPadY = 3,
	KingWidth = Cards_KingWidth + 2 * KingPadX,
	KingHeight = Cards_KingHeight + 2 * KingPadY,

	FoundationX = KingX + KingWidth + KingMarginX,
	FoundationY = CellY,

	StackMarginX = 7,
	StackMarginY = 10,
	StackDeltaY = 17,

	TableauX = StackMarginX,
	TableauY = CellY + CardHeight + StackMarginY,

	KingWinMarginX = 10,
	KingWinMarginY = 10,
	KingWinX = KingWinMarginX,
	KingWinY = CellY + CardHeight + KingWinMarginY,
	KingWinWidth = 320,
	KingWinHeight = 320,

	WindowWidth = 8 * CardWidth + 9 * StackMarginX + 1,
	WindowHeight = KingWinY + KingWinHeight + KingWinMarginY,
};

static struct SDL_Rect rects[StacksLen];

static void initRects(void) {
	SDL_Rect rect = { CellX, CellY, CardWidth, CardHeight };
	for (uint i = Cell1; i <= Cell4; ++i) {
		rects[i] = rect;
		rect.x += CardWidth;
	}

	rect.x = FoundationX;
	rect.y = FoundationY;
	for (uint i = Foundation1; i <= Foundation4; ++i) {
		rects[i] = rect;
		rect.x += CardWidth;
	}

	rect.x = TableauX;
	rect.y = TableauY;
	rect.h = WindowHeight - TableauY;
	for (uint i = Tableau1; i <= Tableau8; ++i) {
		rects[i] = rect;
		rect.x += CardWidth + StackMarginX;
	}
}

static uint pointStack(SDL_Point point) {
	uint i;
	for (i = 0; i < StacksLen; ++i) {
		if (SDL_PointInRect(&point, &rects[i])) break;
	}
	return i;
}

static SDL_Window *window;

static void err(const char *title) {
	int error = SDL_ShowSimpleMessageBox(
		SDL_MESSAGEBOX_ERROR, title, SDL_GetError(), window
	);
	if (error) fprintf(stderr, "%s\n", SDL_GetError());
	exit(EXIT_FAILURE);
}

static bool playAgain(void) {
	SDL_MessageBoxButtonData buttons[] = {
		{ SDL_MESSAGEBOX_BUTTON_RETURNKEY_DEFAULT, true, "Yes" },
		{ SDL_MESSAGEBOX_BUTTON_ESCAPEKEY_DEFAULT, false, "No" },
	};
	SDL_MessageBoxData data = {
		.window = window,
		.title = "Game Over",
		.message = "Congratulations, you win!\n\nDo you want to play again?",
		.buttons = buttons,
		.numbuttons = SDL_arraysize(buttons),
	};
	int choice;
	if (SDL_ShowMessageBox(&data, &choice) < 0) err("SDL_ShowMessageBox");
	return choice;
}

enum Choice {
	Cancel,
	Column,
	Single,
};

static enum Choice chooseMove(void) {
	SDL_MessageBoxButtonData buttons[] = {
		{ SDL_MESSAGEBOX_BUTTON_RETURNKEY_DEFAULT, Column, "Move column" },
		{ 0, Single, "Move single card" },
		{ SDL_MESSAGEBOX_BUTTON_ESCAPEKEY_DEFAULT, Cancel, "Cancel" },
	};
	SDL_MessageBoxData data = {
		.window = window,
		.title = "Move to Empty Column...",
		.message = "",
		.buttons = buttons,
		.numbuttons = SDL_arraysize(buttons),
	};
	int choice;
	if (SDL_ShowMessageBox(&data, &choice) < 0) err("SDL_ShowMessageBox");
	return choice;
}

static void newGame(uint game) {
	if (!game) game = 1 + randUniform(32000);
	deal(game);
	char buf[sizeof("FreeCell Game #32000")];
	snprintf(buf, sizeof(buf), "FreeCell Game #%u", game);
	SDL_SetWindowTitle(window, buf);
}

static Card hiliteRank;
static SDL_Point revealPoint;
static uint fromStack = StacksLen;

static bool keyDown(SDL_KeyboardEvent key) {
	switch (key.keysym.sym) {
		case SDLK_F2: newGame(0); return true;
		case SDLK_BACKSPACE: return undo();
	}
	if (key.repeat) return false;
	switch (key.keysym.sym) {
		break; case SDLK_a: hiliteRank = Cards_A;
		break; case SDLK_2: hiliteRank = Cards_2;
		break; case SDLK_3: hiliteRank = Cards_3;
		break; case SDLK_4: hiliteRank = Cards_4;
		break; case SDLK_5: hiliteRank = Cards_5;
		break; case SDLK_6: hiliteRank = Cards_6;
		break; case SDLK_7: hiliteRank = Cards_7;
		break; case SDLK_8: hiliteRank = Cards_8;
		break; case SDLK_9: hiliteRank = Cards_9;
		break; case SDLK_1: hiliteRank = Cards_10;
		break; case SDLK_0: hiliteRank = Cards_10;
		break; case SDLK_j: hiliteRank = Cards_J;
		break; case SDLK_q: hiliteRank = Cards_Q;
		break; case SDLK_k: hiliteRank = Cards_K;
		break; default: return false;
	}
	return true;
}

static bool keyUp(SDL_KeyboardEvent key) {
	(void)key;
	if (hiliteRank) {
		hiliteRank = 0;
		return true;
	}
	return false;
}

static bool mouseButtonDown(SDL_MouseButtonEvent button) {
	if (button.button == SDL_BUTTON_RIGHT) {
		revealPoint.x = button.x;
		revealPoint.y = button.y;
		return true;
	}
	return false;
}

static bool mouseButtonUp(SDL_MouseButtonEvent button) {
	if (win() && playAgain()) {
		newGame(0);
		return true;
	}

	if (button.button == SDL_BUTTON_RIGHT && revealPoint.x) {
		revealPoint.x = 0;
		revealPoint.y = 0;
		return true;
	}

	SDL_Point point = { button.x, button.y };
	uint stack = pointStack(point);
	if (button.clicks % 2 == 0) {
		for (stack = Cell1; stack <= Cell4; ++stack) {
			if (!stacks[stack].len) break;
		}
	}

	if (fromStack < StacksLen && stack < StacksLen) {
		if (moveDepth(fromStack) > 1 && stack > Cell4 && !stacks[stack].len) {
			switch (chooseMove()) {
				break; case Single: moveSingle(stack, fromStack);
				break; case Column: moveColumn(stack, fromStack);
				break; case Cancel: break;
			}
		} else {
			moveColumn(stack, fromStack);
		}
	}

	if (fromStack < StacksLen) {
		fromStack = StacksLen;
		return true;
	}
	if (stack < StacksLen && stack > Foundation4 && stacks[stack].len) {
		fromStack = stack;
		return true;
	}

	return false;
}

static SDL_Renderer *render;
static struct {
	SDL_Texture *cards[Cards_Empty];
	SDL_Texture *hilites[Cards_Empty];
	SDL_Texture *kings[Cards_FreeCellCount];
} tex;

static void renderOutline(SDL_Rect rect, bool out) {
	int right = rect.x + rect.w - 1;
	int bottom = rect.y + rect.h - 1;
	SDL_Point topLeft[3] = {
		{ rect.x, bottom - 1 },
		{ rect.x, rect.y },
		{ right - 1, rect.y },
	};
	SDL_Point bottomRight[3] = {
		{ rect.x + 1, bottom },
		{ right, bottom },
		{ right, rect.y + 1 },
	};
	SDL_SetRenderDrawColor(render, 0x00, 0x00, 0x00, 0xFF);
	SDL_RenderDrawLines(render, out ? bottomRight : topLeft, 3);
	SDL_SetRenderDrawColor(render, 0x00, 0xFF, 0x00, 0xFF);
	SDL_RenderDrawLines(render, out ? topLeft : bottomRight, 3);
}

static void renderOutlines(void) {
	for (uint i = Foundation1; i <= Cell4; ++i) {
		renderOutline(rects[i], false);
	}
}

static void renderKing(void) {
	SDL_Rect box = { KingX, KingY, KingWidth, KingHeight };
	renderOutline(box, true);
	if (win()) {
		SDL_Rect king = { KingWinX, KingWinY, KingWinWidth, KingWinHeight };
		SDL_RenderCopy(render, tex.kings[Cards_KingWin], NULL, &king);
	} else {
		SDL_Rect king = {
			KingX + KingPadX, KingY + KingPadY,
			Cards_KingWidth, Cards_KingHeight,
		};
		SDL_RenderCopy(render, tex.kings[kingIndex], NULL, &king);
	}
}

static void renderCard(SDL_Rect rect, Card card, bool hilite) {
	SDL_Texture *texture = (hilite ? tex.hilites : tex.cards)[card];
	SDL_RenderCopy(render, texture, NULL, &rect);
}

static void renderStack(uint stack) {
	Card revealCard = 0;
	SDL_Rect revealRect = {0};
	SDL_Rect rect = { rects[stack].x, rects[stack].y, CardWidth, CardHeight };
	for (uint i = 0; i < stacks[stack].len; ++i) {
		Card card = stacks[stack].cards[i];
		if (SDL_PointInRect(&revealPoint, &rect)) {
			revealCard = card;
			revealRect = rect;
		}
		bool hilite = (stack == fromStack && i == stacks[stack].len - 1);
		renderCard(rect, card, hilite || rank(card) == hiliteRank);
		rect.y += StackDeltaY;
	}
	if (revealCard) {
		renderCard(revealRect, revealCard, false);
	}
}

static void renderStacks(void) {
	for (uint i = Foundation1; i <= Cell4; ++i) {
		Card card = peek(&stacks[i]);
		if (!card) continue;
		bool hilite = (i == fromStack || rank(card) == hiliteRank);
		renderCard(rects[i], card, hilite);
	}
	for (uint i = Tableau1; i <= Tableau8; ++i) {
		renderStack(i);
	}
}

int main(int argc, char *argv[]) {
	int error;

	if (SDL_Init(SDL_INIT_VIDEO) < 0) err("SDL_Init");
	atexit(SDL_Quit);

	struct Paths paths;
	if (assetPaths(&paths) < 0) err("SDL_GetPrefPath");

	bool haveFreeCell = false;
	struct {
		SDL_Surface *cards[Cards_Empty];
		SDL_Surface *freeCell[Cards_FreeCellCount];
	} res;

	SDL_RWops *rw = assetOpenCards(&paths);
	if (!rw) return EXIT_FAILURE;
	error = Cards_LoadCards(
		res.cards, Cards_Empty, rw,
		Cards_AlphaCorners | Cards_BlackBorders
	);
	if (error) err("Cards_LoadCards");
	SDL_RWclose(rw);

	rw = assetOpenFreeCell(&paths);
	if (rw) {
		haveFreeCell = true;
		error = Cards_LoadFreeCell(
			res.freeCell, Cards_FreeCellCount, rw,
			Cards_ColorKey
		);
		if (error) err("Cards_LoadFreeCell");
		SDL_RWclose(rw);
	}

	error = SDL_CreateWindowAndRenderer(
		WindowWidth, WindowHeight, SDL_WINDOW_ALLOW_HIGHDPI,
		&window, &render
	);
	if (error) err("SDL_CreateWindowAndRenderer");
	SDL_SetWindowTitle(window, "FreeCell");

	SDL_RenderSetIntegerScale(render, SDL_TRUE);
	SDL_RenderSetLogicalSize(render, WindowWidth, WindowHeight);

	for (uint i = 0; i < Cards_Empty; ++i) {
		if (!res.cards[i]) continue;

		tex.cards[i] = SDL_CreateTextureFromSurface(render, res.cards[i]);
		if (!tex.cards[i]) err("SDL_CreateTextureFromSurface");

		if (Cards_InvertSurface(res.cards[i]) < 0) err("Cards_hilitesurface");
		tex.hilites[i] = SDL_CreateTextureFromSurface(render, res.cards[i]);
		if (!tex.hilites[i]) err("SDL_CreateTextureFromSurface");

		SDL_FreeSurface(res.cards[i]);
	}

	if (haveFreeCell) {
		for (uint i = 0; i < Cards_FreeCellCount; ++i) {
			if (!res.freeCell[i]) continue;
			tex.kings[i] = SDL_CreateTextureFromSurface(render, res.freeCell[i]);
			if (!tex.kings[i]) err("SDL_CreateTextureFromSurface");
			SDL_FreeSurface(res.freeCell[i]);
		}
	}

	srand(time(NULL));
	newGame(argc > 1 ? strtoul(argv[1], NULL, 10) : 0);
	
	initRects();
	for (;;) {
		SDL_SetRenderDrawColor(render, 0x00, 0xAA, 0x55, 0xFF);
		SDL_RenderClear(render);
		renderOutlines();
		renderStacks();
		if (haveFreeCell) renderKing();
		SDL_RenderPresent(render);

		if (queue.r < queue.w) {
			dequeue();
			if (queue.r == queue.w) autoEnqueue();
			if (queue.r < queue.w) SDL_Delay(50);
			continue;
		}

		bool update = false;
		while (!update) {
			SDL_Event event;
			SDL_WaitEvent(&event);
			switch (event.type) {
				break; case SDL_QUIT: return EXIT_SUCCESS;
				break; case SDL_KEYDOWN: update = keyDown(event.key);
				break; case SDL_KEYUP: update = keyUp(event.key);
				break; case SDL_MOUSEBUTTONDOWN: {
					update = mouseButtonDown(event.button);
				}
				break; case SDL_MOUSEBUTTONUP: {
					update = mouseButtonUp(event.button);
				}
			}
		}
	}
}