gamestate.js

/* jslint smarttabs:true */
// load the things we need
var mongoose = require('mongoose');
var moniker = require('moniker');
var Q = require('q');
var Tile = require('../models/tile');
var User = require('../models/user');

// Tile features are defined in terms of the cardinal directions they use
// Roads and cities potentially connect cardinal directions (N S E W)
// Fields potentially connect secondary-intercardinal directions (NNW NNE ENE ESE SSE SSW WSW WNW)

// NW NNW N NNE NE
// WNW         ENE
// W      *      E
// WSW         ESE
// SW SSW S SSE SE

// define the schema for our game model
var gamestateSchema = mongoose.Schema({
	name: String,
	expansions: [String],
	finished: { type: Boolean, default: false },
	messages: [{ username: String, message: { type: String, trim: true } }], // if there is no username this is a message generated by the game
	players: [{
		user: { type: mongoose.Schema.Types.ObjectId, ref: 'User' },
		points: Number,
		remainingMeeples: Number,
		hasLargeMeeple: Boolean,
		hasPigMeeple: Boolean,
		hasBuilderMeeple: Boolean,
		active: Boolean,
		color: String,
		acknowledgedGameEnd: Boolean,
		goods: {
			fabric: Number,
			wine: Number,
			wheat: Number
		},
		towers: Number,
		capturedMeeples: [{
			meepleType: String,
			playerIndex: Number
		}]
	}],
	unusedTiles: [{ type: mongoose.Schema.Types.ObjectId, ref: 'Tile' }],
	activeTile: {
		tile: { type: mongoose.Schema.Types.ObjectId, ref: 'Tile' },
		validPlacements: [{
			x: Number,
			y: Number,
			rotations: [{
				rotation: Number,
				meeples: [{
					meepleType: String, // 'normal', 'large', 'pig', 'builder', etc for different types of meeples
					locationType: String, // 'road', 'city', 'farm', or 'cloister'
					index: Number // which element of tiles[].roads/cities/farms (external schema)
				}]
			}]
		}],
		discardedTiles: [{ type: mongoose.Schema.Types.ObjectId, ref: 'Tile' }]
	},
	placedTiles: [{
		tile: { type: mongoose.Schema.Types.ObjectId, ref: 'Tile' },
		rotation: Number, // number of times tile is rotated clockwise
		meeples: [{
			playerIndex: Number, // references players
			placement: {
				locationType: String, // 'road', 'city', 'farm', or 'cloister'
				index: Number // which element of tiles[].roads/cities/farms (external schema)
			},
			meepleType: String, // 'normal', 'large', 'pig', 'builder', etc for different types of meeples
			scored: Boolean // whether the meeple has already had score assigned for it (only used at game end, otherwise the meeple is removed when it is scored)
		}],
		tower: {
			height: Number, // number of tower floors placed on this tower
			completed: Boolean,
			meepleType: String, // 'normal' or 'large', only followers can be used to complete a tower
			playerIndex: Number // which player completed this tower
		},
		northTileIndex: Number, // references placedTiles
		southTileIndex: Number,
		westTileIndex: Number,
		eastTileIndex: Number,
		x: Number,
		y: Number,
		playerIndex: Number // which player placed this tile
	}],
	lastModified: { type: Date, default: new Date() }
});

function getMeepleFlagFromType(meepleType) {
	return 'has' + meepleType.charAt(0).toUpperCase() + meepleType.slice(1) + 'Meeple';
}

gamestateSchema.methods.userIsInGame = function(user) {
	var gamestate = this;
	var userID = user;
	if(typeof user !== 'string') {
		userID = user._id.toHexString();
	}
	var inGame = false;
	for(var i = 0; i < gamestate.players.length; i++) {
		var id = gamestate.players[i].user._id || gamestate.players[i].user;
		inGame = inGame || id.equals(userID);
	}
	return inGame;
};

gamestateSchema.methods.userIsActive = function(user) {
	var gamestate = this;
	var userID = user;
	if(typeof user !== 'string') {
		userID = user._id.toHexString();
	}
	var active = false;
	for(var i = 0; i < gamestate.players.length; i++) {
		var id = gamestate.players[i].user._id || gamestate.players[i].user;
		active = active || (id.equals(userID) && gamestate.players[i].active);
	}
	return active;
};

function completeGame(gamestate) {
	// score and remove all currently placed meeples
	for(var i = 0; i < gamestate.placedTiles.length; i++) {
		var tile = gamestate.placedTiles[i];
		for(var k = 0; k < tile.meeples.length; k++) {
			if(!tile.meeples[k].scored &&
				(tile.meeples[k].meepleType === 'normal' || tile.meeples[k].meepleType === 'large')) {
				// console.log('finalizing meeple=>');
				// console.log(JSON.stringify(tile.meeples[k]));
				checkAndFinalizeFeature(tile, tile.meeples[k].placement.index, tile.meeples[k].placement.locationType, true, gamestate);
			}
		}
	}
	if(gamestate.expansions.indexOf('traders-and-builders') !== -1) {
		// add 10 points for the users with the most of each trade good
		var maxGoods = {
			fabric: 0,
			wine: 0,
			wheat: 0
		};
		// find the max number picked up for each token type
		for(var j = 0; j < gamestate.players.length; j++) {
			maxGoods.fabric = Math.max(gamestate.players[j].goods.fabric, maxGoods.fabric);
			maxGoods.wine = Math.max(gamestate.players[j].goods.wine, maxGoods.wine);
			maxGoods.wheat = Math.max(gamestate.players[j].goods.wheat, maxGoods.wheat);
		}
		// construct messages about scoring for the chat log
		var fabricMessage = '';
		var wineMessage = '';
		var wheatMessage = '';
		for(var l = 0; l < gamestate.players.length; l++) {
			if(gamestate.players[l].goods.fabric === maxGoods.fabric) {
				gamestate.players[l].points += 10;
				if(fabricMessage !== '') {
					fabricMessage += ' and ';
				}
				fabricMessage += gamestate.players[l].user.username + ' (' + gamestate.players[l].points + ')';
			}
			if(gamestate.players[l].goods.wine === maxGoods.wine) {
				gamestate.players[l].points += 10;
				if(wineMessage !== '') {
					wineMessage += ' and ';
				}
				wineMessage += gamestate.players[l].user.username + ' (' + gamestate.players[l].points + ')';
			}
			if(gamestate.players[l].goods.wheat === maxGoods.wheat) {
				gamestate.players[l].points += 10;
				if(wheatMessage !== '') {
					wheatMessage += ' and ';
				}
				wheatMessage += gamestate.players[l].user.username + ' (' + gamestate.players[l].points + ')';
			}
		}
		fabricMessage += ' scored 10 points for having the most fabric tokens';
		wineMessage += ' scored 10 points for having the most wine tokens';
		wheatMessage += ' scored 10 points for having the most wheat tokens';
		gamestate.messages.push({ username: null, message: fabricMessage });
		gamestate.messages.push({ username: null, message: wineMessage });
		gamestate.messages.push({ username: null, message: wheatMessage });
	}
	gamestate.finished = true;
}

gamestateSchema.methods.drawTile = function(callback, autocomplete) {
	this.populate('unusedTiles placedTiles.tile players.user', function(err, gamestate) {
		// if we're out of tiles score/complete game
		if(gamestate.unusedTiles.length === 0 || autocomplete) {
			completeGame(gamestate);
		}
		// move one random tile from unused to active
		var potentialPlacements = [], discardedTiles = [];
		var currentTile, rotatedTile, activeTile;
		var rotatedPlacements;
		var rotatedTiles = gamestate.placedTiles.map(function getRotatedTileEdges(gamestateTile) {
			return gamestateTile.rotation === 0 ?
			{
				northEdge: gamestateTile.tile.northEdge,
				eastEdge: gamestateTile.tile.eastEdge,
				southEdge: gamestateTile.tile.southEdge,
				westEdge: gamestateTile.tile.westEdge
			}
			: gamestateTile.rotation === 1 ?
			{
				northEdge: gamestateTile.tile.westEdge,
				eastEdge: gamestateTile.tile.northEdge,
				southEdge: gamestateTile.tile.eastEdge,
				westEdge: gamestateTile.tile.southEdge
			}
			: gamestateTile.rotation === 2 ?
			{
				northEdge: gamestateTile.tile.southEdge,
				eastEdge: gamestateTile.tile.westEdge,
				southEdge: gamestateTile.tile.northEdge,
				westEdge: gamestateTile.tile.eastEdge
			}
			:
			{
				northEdge: gamestateTile.tile.eastEdge,
				eastEdge: gamestateTile.tile.southEdge,
				southEdge: gamestateTile.tile.westEdge,
				westEdge: gamestateTile.tile.northEdge
			};
		});
		while(potentialPlacements.length === 0 && gamestate.unusedTiles.length > 0 && !autocomplete) {
			// splice a random unused tile into the active tile
			activeTile = gamestate.unusedTiles.splice(Math.floor(Math.random()*gamestate.unusedTiles.length), 1)[0];
			// make sure mongoose sees the field as changed to save later
			gamestate.markModified('unusedTiles');
			// find out all the places we can place it
			for(var i = 0; i < gamestate.placedTiles.length; i++) {
				currentTile = gamestate.placedTiles[i];
				rotatedTile = rotatedTiles[i];
				if(currentTile.northTileIndex === undefined) {
					if(rotatedTile.northEdge === activeTile.northEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y - 1,
							rotation: 2,
							sourceIndex: i,
							directionToSource: 'S',
							directionFromSource: 'N'
						});
					}
					if(rotatedTile.northEdge === activeTile.eastEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y - 1,
							rotation: 1,
							sourceIndex: i,
							directionToSource: 'S',
							directionFromSource: 'N'
						});
					}
					if(rotatedTile.northEdge === activeTile.southEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y - 1,
							rotation: 0,
							sourceIndex: i,
							directionToSource: 'S',
							directionFromSource: 'N'
						});
					}
					if(rotatedTile.northEdge === activeTile.westEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y - 1,
							rotation: 3,
							sourceIndex: i,
							directionToSource: 'S',
							directionFromSource: 'N'
						});
					}
				}
				if(currentTile.eastTileIndex === undefined) {
					if(rotatedTile.eastEdge === activeTile.northEdge) {
						potentialPlacements.push({
							x: currentTile.x + 1,
							y: currentTile.y,
							rotation: 3,
							sourceIndex: i,
							directionToSource: 'W',
							directionFromSource: 'E'
						});
					}
					if(rotatedTile.eastEdge === activeTile.eastEdge) {
						potentialPlacements.push({
							x: currentTile.x + 1,
							y: currentTile.y,
							rotation: 2,
							sourceIndex: i,
							directionToSource: 'W',
							directionFromSource: 'E'
						});
					}
					if(rotatedTile.eastEdge === activeTile.southEdge) {
						potentialPlacements.push({
							x: currentTile.x + 1,
							y: currentTile.y,
							rotation: 1,
							sourceIndex: i,
							directionToSource: 'W',
							directionFromSource: 'E'
						});
					}
					if(rotatedTile.eastEdge === activeTile.westEdge) {
						potentialPlacements.push({
							x: currentTile.x + 1,
							y: currentTile.y,
							rotation: 0,
							sourceIndex: i,
							directionToSource: 'W',
							directionFromSource: 'E'
						});
					}
				}
				if(currentTile.southTileIndex === undefined) {
					if(rotatedTile.southEdge === activeTile.northEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y + 1,
							rotation: 0,
							sourceIndex: i,
							directionToSource: 'N',
							directionFromSource: 'S'
						});
					}
					if(rotatedTile.southEdge === activeTile.eastEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y + 1,
							rotation: 3,
							sourceIndex: i,
							directionToSource: 'N',
							directionFromSource: 'S'
						});
					}
					if(rotatedTile.southEdge === activeTile.southEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y + 1,
							rotation: 2,
							sourceIndex: i,
							directionToSource: 'N',
							directionFromSource: 'S'
						});
					}
					if(rotatedTile.southEdge === activeTile.westEdge) {
						potentialPlacements.push({
							x: currentTile.x,
							y: currentTile.y + 1,
							rotation: 1,
							sourceIndex: i,
							directionToSource: 'N',
							directionFromSource: 'S'
						});
					}
				}
				if(currentTile.westTileIndex === undefined) {
					if(rotatedTile.westEdge === activeTile.northEdge) {
						potentialPlacements.push({
							x: currentTile.x - 1,
							y: currentTile.y,
							rotation: 1,
							sourceIndex: i,
							directionToSource: 'E',
							directionFromSource: 'W'
						});
					}
					if(rotatedTile.westEdge === activeTile.eastEdge) {
						potentialPlacements.push({
							x: currentTile.x - 1,
							y: currentTile.y,
							rotation: 0,
							sourceIndex: i,
							directionToSource: 'E',
							directionFromSource: 'W'
						});
					}
					if(rotatedTile.westEdge === activeTile.southEdge) {
						potentialPlacements.push({
							x: currentTile.x - 1,
							y: currentTile.y,
							rotation: 3,
							sourceIndex: i,
							directionToSource: 'E',
							directionFromSource: 'W'
						});
					}
					if(rotatedTile.westEdge === activeTile.westEdge) {
						potentialPlacements.push({
							x: currentTile.x - 1,
							y: currentTile.y,
							rotation: 2,
							sourceIndex: i,
							directionToSource: 'E',
							directionFromSource: 'W'
						});
					}
				}
			}
			rotatedPlacements = potentialPlacements.map(function(currentPlacement) {
				return currentPlacement.rotation === 0 ?
					{
						northEdge: activeTile.northEdge,
						eastEdge: activeTile.eastEdge,
						southEdge: activeTile.southEdge,
						westEdge: activeTile.westEdge
					}
				: currentPlacement.rotation === 1 ?
					{
						northEdge: activeTile.westEdge,
						eastEdge: activeTile.northEdge,
						southEdge: activeTile.eastEdge,
						westEdge: activeTile.southEdge
					}
				: currentPlacement.rotation === 2 ?
					{
						northEdge: activeTile.southEdge,
						eastEdge: activeTile.westEdge,
						southEdge: activeTile.northEdge,
						westEdge: activeTile.eastEdge
					}
				:
					{
						northEdge: activeTile.eastEdge,
						eastEdge: activeTile.southEdge,
						southEdge: activeTile.westEdge,
						westEdge: activeTile.northEdge
					};
			});
			var invalidPlacementIndices = [];
			// remove placements which conflict with already placed tiles
			for(var k = 0; k < gamestate.placedTiles.length; k++) {
				currentTile = gamestate.placedTiles[k];
				rotatedTile = rotatedTiles[k];
				for(var j = 0; j < potentialPlacements.length; j++) {
					var placement = potentialPlacements[j];
					var rotatedPlacement = rotatedPlacements[j];
					if((currentTile.x === placement.x && currentTile.y - 1 === placement.y && rotatedTile.northEdge !== rotatedPlacement.southEdge) ||
					   (currentTile.x === placement.x && currentTile.y + 1 === placement.y && rotatedTile.southEdge !== rotatedPlacement.northEdge) ||
					   (currentTile.y === placement.y && currentTile.x - 1 === placement.x && rotatedTile.westEdge !== rotatedPlacement.eastEdge) ||
					   (currentTile.y === placement.y && currentTile.x + 1 === placement.x && rotatedTile.eastEdge !== rotatedPlacement.westEdge)) {
						invalidPlacementIndices.push(j);
					}
				}
			}
			potentialPlacements = potentialPlacements.filter(function(placement, index) {
				return invalidPlacementIndices.indexOf(index) === -1;
			});
			rotatedPlacements = rotatedPlacements.filter(function(placement, index) {
				return invalidPlacementIndices.indexOf(index) === -1;
			});
			if(potentialPlacements.length === 0) {
				// console.log('=======discarded tile=====');
				discardedTiles.push(activeTile);
			}
		}
		// calculate valid meeple placements for each valid tile placement
		for(var index = 0; index < potentialPlacements.length; index++) {
			var currentPlacement = potentialPlacements[index];
			var adjacentTile = gamestate.placedTiles[currentPlacement.sourceIndex];
			// console.log('calculating meeple placements: ' + currentPlacement.x + ',' + currentPlacement.y);
			currentPlacement.meeples = [];
			// meeple placement is valid if for all directions in a (rotated) feature
			// direction isn't pointed to the adjacent tile OR adjacent tile feature isn't owned
			var directions = ['N','E','S','W'];
			// check each city for valid meeple placements
			var valid, adjacentIndex, featureInfo, meepleIndex, placedTile;
			for(var index2 = 0; index2 < activeTile.cities.length; index2++) {
				// assume we can place unless we find that there are other meeples on this feature
				valid = true;
				featureInfo = null;
				// check the adjacent tile (in the direction the current tiles city is pointing) for conflicting meeples
				var rotatedCityDirections = activeTile.cities[index2].directions.map(function(direction) {
					return directions[(directions.indexOf(direction) + currentPlacement.rotation) % 4];
				});
				// if we find another city in that direction only remain valid if there are no other meeples on it
				if(rotatedCityDirections.indexOf(currentPlacement.directionToSource) !== -1) {
					adjacentIndex = getFeatureIndex(adjacentTile, 'city', currentPlacement.directionFromSource);
					featureInfo = getFeatureInfo(adjacentTile, adjacentIndex, 'city', gamestate);
					valid = featureInfo.tilesWithMeeples.length === 0;
					// if there was a city with meeples already on it and it is this (the active) player's add a valid placement for the builder
					for(var i1 = 0; i1 < featureInfo.tilesWithMeeples.length; i1++) {
						meepleIndex = featureInfo.tilesWithMeeples[i1].meepleIndex;
						placedTile = featureInfo.tilesWithMeeples[i1].placedTile;
						if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
							currentPlacement.meeples.push({
								meepleType: 'builder',
								locationType: 'city',
								index: index2
							});
							break;
						}
					}
				}
				if(valid) {
					// add to placement
					currentPlacement.meeples.push({
						meepleType: 'normal',
						locationType: 'city',
						index: index2
					});
				}
			}
			// check each road for valid meeple placements
			for(var index3 = 0; index3 < activeTile.roads.length; index3++) {
				// assume we can place unless we find that there are other meeples on this feature
				valid = true;
				featureInfo = null;
				// check the adjacent tile (in the direction the current tiles road is pointing) for conflicting meeples
				var rotatedRoadDirections = activeTile.roads[index3].directions.map(function(direction) {
					return directions[(directions.indexOf(direction) + currentPlacement.rotation) % 4];
				});
				// if we find another road in that direction only remain valid if there are no other meeples on it
				if(rotatedRoadDirections.indexOf(currentPlacement.directionToSource) !== -1) {
					adjacentIndex = getFeatureIndex(adjacentTile, 'road', currentPlacement.directionFromSource);
					featureInfo = getFeatureInfo(adjacentTile, adjacentIndex, 'road', gamestate);
					valid = featureInfo.tilesWithMeeples.length === 0;
					// if there was a road with meeples already on it and it is this (the active) player's add a valid placement for the builder
					for(var i2 = 0; i2 < featureInfo.tilesWithMeeples.length; i2++) {
						meepleIndex = featureInfo.tilesWithMeeples[i2].meepleIndex;
						placedTile = featureInfo.tilesWithMeeples[i2].placedTile;
						if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
							currentPlacement.meeples.push({
								meepleType: 'builder',
								locationType: 'road',
								index: index3
							});
							break;
						}
					}
				}
				if(valid) {
					// add to placement
					currentPlacement.meeples.push({
						meepleType: 'normal',
						locationType: 'road',
						index: index3
					});
				}
			}
			// check each farm for valid meeple placements
			var farmDirections = ['NNE','ENE','ESE','SSE','SSW','WSW','WNW','NNW'];
			for(var index4 = 0; index4 < activeTile.farms.length; index4++) {
				// console.log('checking farm: ' + index4 + ' ' + JSON.stringify(activeTile.farms[index4]));
				valid = true;
				var rotatedFarmDirections = activeTile.farms[index4].directions.map(function(direction) {
					return farmDirections[(farmDirections.indexOf(direction) + currentPlacement.rotation * 2) % 8];
				});
				if(currentPlacement.directionToSource === 'N') {
					// console.log('looking ' + currentPlacement.directionToSource);
					if(rotatedFarmDirections.indexOf('NNW') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'SSW'), 'farm', gamestate);
						for(var iSSW = 0; iSSW < featureInfo.tilesWithMeeples.length; iSSW++) {
							meepleIndex = featureInfo.tilesWithMeeples[iSSW].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iSSW].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('NNW ' + valid);
					}
					if(rotatedFarmDirections.indexOf('NNE') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'SSE'), 'farm', gamestate);
						for(var iSSE = 0; iSSE < featureInfo.tilesWithMeeples.length; iSSE++) {
							meepleIndex = featureInfo.tilesWithMeeples[iSSE].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iSSE].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('NNE ' + valid);
					}
				} else if(currentPlacement.directionToSource === 'E') {
					// console.log('looking ' + currentPlacement.directionToSource);
					if(rotatedFarmDirections.indexOf('ENE') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'WNW'), 'farm', gamestate);
						for(var iWNW = 0; iWNW < featureInfo.tilesWithMeeples.length; iWNW++) {
							meepleIndex = featureInfo.tilesWithMeeples[iWNW].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iWNW].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('ENE ' + valid);
					}
					if(rotatedFarmDirections.indexOf('ESE') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'WSW'), 'farm', gamestate);
						for(var iWSW = 0; iWSW < featureInfo.tilesWithMeeples.length; iWSW++) {
							meepleIndex = featureInfo.tilesWithMeeples[iWSW].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iWSW].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('ESE ' + valid);
					}
				} else if(currentPlacement.directionToSource === 'S') {
					// console.log('looking ' + currentPlacement.directionToSource);
					if(rotatedFarmDirections.indexOf('SSW') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'NNW'), 'farm', gamestate);
						for(var iNNW = 0; iNNW < featureInfo.tilesWithMeeples.length; iNNW++) {
							meepleIndex = featureInfo.tilesWithMeeples[iNNW].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iNNW].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('SSW ' + valid);
					}
					if(rotatedFarmDirections.indexOf('SSE') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'NNE'), 'farm', gamestate);
						for(var iNNE = 0; iNNE < featureInfo.tilesWithMeeples.length; iNNE++) {
							meepleIndex = featureInfo.tilesWithMeeples[iNNE].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iNNE].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('SSE ' + valid);
					}
				} else if(currentPlacement.directionToSource === 'W') {
					// console.log('looking ' + currentPlacement.directionToSource);
					if(rotatedFarmDirections.indexOf('WNW') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'ENE'), 'farm', gamestate);
						for(var iENE = 0; iENE < featureInfo.tilesWithMeeples.length; iENE++) {
							meepleIndex = featureInfo.tilesWithMeeples[iENE].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iENE].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('WNW ' + valid);
					}
					if(rotatedFarmDirections.indexOf('WSW') !== -1) {
						featureInfo = getFeatureInfo(adjacentTile, getFeatureIndex(adjacentTile, 'farm', 'ESE'), 'farm', gamestate);
						for(var iESE = 0; iESE < featureInfo.tilesWithMeeples.length; iESE++) {
							meepleIndex = featureInfo.tilesWithMeeples[iESE].meepleIndex;
							placedTile = featureInfo.tilesWithMeeples[iESE].placedTile;
							if(gamestate.players[placedTile.meeples[meepleIndex].playerIndex].active) {
								currentPlacement.meeples.push({
									meepleType: 'pig',
									locationType: 'farm',
									index: index4
								});
								break;
							}
						}
						valid = valid && featureInfo.tilesWithMeeples.length === 0;
						// console.log('WSW ' + valid);
					}
				}
				if(valid) {
					// add to placement
					currentPlacement.meeples.push({
						meepleType: 'normal',
						locationType: 'farm',
						index: index4
					});
				}
			}
			// if there is a cloister on the active tile it will always be valid for any rotation
			if(activeTile.cloister) {
				currentPlacement.meeples.push({
					meepleType: 'normal',
					locationType: 'cloister',
					index: 0
				});
			}
		}
		gamestate.activeTile.tile = activeTile;
		gamestate.activeTile.discarded = discardedTiles;
		// console.log('ungrouped placements =>' + JSON.stringify(potentialPlacements));
		// console.log('==========================');
		// remove duplicates while storing an array of potential rotations and meeple placements for each position
		// duplicates are created because the potential placement generation only looks at one adjacent tile each time
		// meeples for valid placements must be valid for ALL potential placements with same x/y/rotation
		// otherwise at some point there was a conflict for that meeple placement found
		var groupedPlacements = {};
		potentialPlacements.forEach(function(item) {
			var key = item.x + ',' + item.y;
			if(groupedPlacements[key]) {
				var matched = false;
				for(var i = 0; i < groupedPlacements[key].rotations.length; i++) {
					var currentRotation = groupedPlacements[key].rotations[i];
					// if this rotation has already been placed 
					if(currentRotation.rotation === item.rotation) {
						matched = true;
						// since non-normal meeples don't have disqualifying conditions (only qualifying ones aka an existing active meeple) allow all unless they would be duplicates
						for(var j = 0; j < item.meeples.length; j++) {
							var newMeeple = item.meeples[j];
							if(newMeeple.meepleType !== 'normal') {
								var duplicated = false;
								for(var k = 0; k < currentRotation.meeples.length; k++) {
									var existingMeeple = currentRotation.meeples[k];
									if(existingMeeple.meepleType === newMeeple.meepleType &&
									   existingMeeple.locationType === newMeeple.locationType &&
									   existingMeeple.index === newMeeple.index) {
										duplicated = true;
										break;
									}
								}
								if(!duplicated) {
									currentRotation.meeples.push(newMeeple);
								}
							}
						}
						// only keep normal meeple placements that are valid in both tile placements
						currentRotation.meeples = currentRotation.meeples.filter(function(meeple, index) {
							if(meeple.meepleType === 'normal') {
								for(var i = 0; i < item.meeples.length; i++) {
									if(item.meeples[i].meepleType === meeple.meepleType &&
									   item.meeples[i].locationType === meeple.locationType &&
									   item.meeples[i].index === meeple.index) {
										return true;
									}
								}
								return false;
							} else {
								return true;
							}
						});
						break;
					}
				}
				// if it hasn't been placed add it
				if(!matched) {
					groupedPlacements[key].rotations.push({
						rotation: item.rotation,
						meeples: item.meeples
					});
				}
			} else {
				groupedPlacements[key] = {
					x: item.x,
					y: item.y,
					rotations: [{
						rotation: item.rotation,
						meeples: item.meeples
					}]
				};
			}
		});
		// place each grouped item into the valid placements for the active tile
		gamestate.activeTile.validPlacements = [];
		for (var key in groupedPlacements) {
			gamestate.activeTile.validPlacements.push(groupedPlacements[key]);
		}
		gamestate.lastModified = new Date();
		gamestate.markModified('lastModified');
		if(autocomplete) {
			callback(null, gamestate);
			return;
		}
		gamestate.save(callback);
	});
};

gamestateSchema.methods.initializeNewGame = function(initialUser, friends, expansions, callback) {
	var newGame = this;
	// create a random name to identify the game
	newGame.name = moniker.choose();
	// record the expansions enabled for this game
	newGame.expansions = expansions;
	// add the initial players
	var allPlayers = friends.concat([initialUser._id]);
	newGame.players = allPlayers.map(function(userID) { return { user: userID }; });
	// add the game to the users' active games
	var userGamesUpdated = User.update({ _id: { $in: allPlayers }}, 
	                                   { $push: { activeGames: newGame._id }}, 
	                                   { multi: true }).exec();
	// grab the starting tile and make it the only placed tile
	var startTilePlaced = Tile.findOne({ startingTile: true, expansion: 'base-game' }).exec(function(err, startTile) {
		newGame.placedTiles.unshift({
			tile: startTile._id,
			rotation: 0,
			x: 0,
			y: 0
		});
	});
	// grab the rest of the tiles and put them in the unplaced list
	var unusedTilesLoaded = Tile.find({ expansion: { $in: expansions }}).exec(function(err, allTiles) {
		// load a copy of each unused tile based on their counts, skip one copy of the starting tile
		for(var i = 0; i < allTiles.length; i++) {
			var countToAdd = allTiles[i].startingTile ? allTiles[i].count - 1 : allTiles[i].count;
			for(var j = 0; j < countToAdd; j++) {
				newGame.unusedTiles.push(allTiles[i]._id);
			}
		}
	});
	Q.all([userGamesUpdated, startTilePlaced, unusedTilesLoaded]).then(function() {
		var colors = ['blue', 'green', 'purple', 'red', 'yellow'];
		// only use gray color if there is a 6th player
		if(newGame.players.length > 5) {
			colors.push('gray');
		}
		// choose a random player to start
		var startingPlayer = Math.floor(Math.random()*newGame.players.length);
		// set default attributes for each player
		for(var i = 0; i < newGame.players.length; i++) {
			newGame.players[i].active = (i === startingPlayer);
			newGame.players[i].points = 0;
			newGame.players[i].remainingMeeples = 7;
			// choose a random remaining color for this player
			newGame.players[i].color = colors.splice(Math.floor(Math.random()*colors.length), 1)[0];
			if(expansions.indexOf('inns-and-cathedrals') !== -1) {
				newGame.players[i].hasLargeMeeple = true;
			}
			if(expansions.indexOf('traders-and-builders') !== -1) {
				newGame.players[i].hasPigMeeple = true;
				newGame.players[i].hasBuilderMeeple = true;
				newGame.players[i].goods = {
					fabric: 0,
					wine: 0,
					wheat: 0
				};
			}
			if(expansions.indexOf('the-tower') !== -1) {
				newGame.players[i].towers = newGame.players.length === 1 ? 30 : // if playing solo let them have all the tower pieces
				                            newGame.players.length === 2 ? 10 :
				                            newGame.players.length === 3 ? 9 :
				                            newGame.players.length === 4 ? 7 :
				                            newGame.players.length === 5 ? 6 :
				                                                           5;
			}
		}
		// start the game by drawing the first tile
		newGame.drawTile(callback);
	});
};

//TODO: remove all autocomplete
gamestateSchema.methods.placeTile = function(move, callback, autocomplete) {
	/* move: {
	 *     placement: {    // x and y of where the tile is to be placed
	 *         x: Number,
	 *         y: Number,
	 *     },
	 *     rotation: Number, // number of clockwise 90° rotations
	 *     meeple: {
	 *         meepleType: String, // 'normal', 'large', 'pig', etc
	 *         locationType: String, 
	 *         index: Number
	 *     },
	 *     tower: {
	 *         meepleType: String, // 'normal' or 'large', only set if tower is being completed instead of added to
	 *         tileIndex: Number, // index of tile tower or completing meeple is being placed on
	 *         capture: {
	 *             tileIndex: Number, // index in placedTiles of tile whose meeple is being captured
	 *             meepleIndex: Number, // index in placedTiles.meeples of meeple being captured
	 *             exchangeType: String
	 *         }
	 *     }
	 * }
	 */
	this.populate('activeTile.tile players.user', function(err, gamestate) {
		var validPlacement = false;
		// get the active player
		var activePlayer, activePlayerIndex;
		for(var i1 = 0; i1 < gamestate.players.length; i1++) {
			if(gamestate.players[i1].active) {
				activePlayer = gamestate.players[i1];
				activePlayerIndex = i1;
				break;
			}
		}
		// if move is using older move format still (due to cached page) convert it to the new format
		if(move && move.meeple && !move.meeple.meepleType) {
			move.meeple.meepleType = move.meeple.large ? 'large' : 'normal';
		}
		// validate tile and meeple placement
		for(var i2 = 0; i2 < gamestate.activeTile.validPlacements.length; i2++) {
			var placement = gamestate.activeTile.validPlacements[i2];
			if(placement.x === move.placement.x &&
			   placement.y === move.placement.y) {
				for(var i3 = 0; i3 < placement.rotations.length; i3++) {
					if(placement.rotations[i3].rotation === move.rotation) {
						// the placement is valid if this x/y/rotation was previously added to the active tiles valid placements
						// and either there wasn't a meeple placed
						// or there was a meeple placed and the user has at least 1 normal meeple or the has(MeepleType)Meeple flag is true for their player
						if(!move.meeple) {
							validPlacement = true;
						} else if((move.meeple.meepleType === 'normal' && activePlayer.remainingMeeples > 0) ||
						          (move.meeple.meepleType !== 'normal' && activePlayer[getMeepleFlagFromType(move.meeple.meepleType)])) {
							var meepleType = move.meeple.meepleType === 'large' ? 'normal' : move.meeple.meepleType;
							for(var i4 = 0; i4 < placement.rotations[i3].meeples.length; i4++) {
								if(placement.rotations[i3].meeples[i4].meepleType === meepleType &&
								   placement.rotations[i3].meeples[i4].locationType === move.meeple.locationType &&
								   placement.rotations[i3].meeples[i4].index === move.meeple.index) {
									validPlacement = true;
									break;
								}
							}
						}
						break;
					}
				}
				break;
			}
		}
		if(validPlacement) {
			// add tile creating proper north/south/east/west links to the existing placed tiles
			var newTile = {
				_id: mongoose.Types.ObjectId(),
				tile: gamestate.activeTile.tile,
				rotation: move.rotation,
				x: move.placement.x,
				y: move.placement.y,
				playerIndex: activePlayerIndex
			};
			// validate that the player has the proper type of meeple for placement
			if(move.meeple) {
				if(move.meeple.meepleType === 'normal' && activePlayer.remainingMeeples > 0) {
					activePlayer.remainingMeeples -= 1;
					newTile.meeples = [{
						playerIndex: activePlayerIndex,
						placement: {
							locationType: move.meeple.locationType,
							index: move.meeple.index
						},
						meepleType: move.meeple.meepleType
					}];
				} else if(move.meeple.meepleType !== 'normal') {
					var meepleFlagName = getMeepleFlagFromType(move.meeple.meepleType);
					if(activePlayer[meepleFlagName] === true) {
						activePlayer[meepleFlagName] = false;
						newTile.meeples = [{
							playerIndex: activePlayerIndex,
							placement: {
								locationType: move.meeple.locationType,
								index: move.meeple.index
							},
							meepleType: move.meeple.meepleType
						}];
					}
				}
			}
			// set up the base tower with no tokens if this tile has a tower
			// since mongoose creates the entire schema structure check a primitive for undefined rather than "tile.tower"
			if(newTile.tile.tower.offset.x) {
				newTile.tower = {
					height: 0,
					completed: false
				};
			}
			// create links between the new tile and existing placed tiles
			for(var i5 = 0; i5 < gamestate.placedTiles.length; i5++) {
				var placedTile = gamestate.placedTiles[i5];
				if(placedTile.x === newTile.x) {
					if(placedTile.y === newTile.y - 1) {
						newTile.northTileIndex = i5;
						placedTile.southTileIndex = gamestate.placedTiles.length;
					} else if(placedTile.y === newTile.y + 1) {
						newTile.southTileIndex = i5;
						placedTile.northTileIndex = gamestate.placedTiles.length;
					}
				} else if(placedTile.y === newTile.y) {
					if(placedTile.x === newTile.x - 1) {
						newTile.westTileIndex = i5;
						placedTile.eastTileIndex = gamestate.placedTiles.length;
					} else if(placedTile.x === newTile.x + 1) {
						newTile.eastTileIndex = i5;
						placedTile.westTileIndex = gamestate.placedTiles.length;
					}
				}
			}
			// and then add it to the placed tiles
			gamestate.placedTiles.push(newTile);
			// if the user sent in a move with a tower placement or completion
			if(move && move.tower && !move.meeple) {
				var tower = gamestate.placedTiles[move.tower.tileIndex].tower;
				// if a tower is being completed by a meeple
				if(move.tower.meepleType) {
					// if the player has the appropriate meeple remove it
					var towerCompleted = false;
					if(move.tower.meepleType === 'normal' && activePlayer.remainingMeeples > 0) {
						activePlayer.remainingMeeples -= 1;
						towerCompleted = true;
					} else if(move.tower.meepleType !== 'normal' && move.tower.meepleType !== 'builder' && move.tower.meepleType !== 'pig') {
						var towerMeepleFlagName = getMeepleFlagFromType(move.tower.meepleType);
						if(activePlayer[towerMeepleFlagName] === true) {
							activePlayer[towerMeepleFlagName] = false;
							towerCompleted = true;
						}
					}
					// and mark the tower as complete
					if(towerCompleted) {
						tower.completed = true;
						tower.meepleType = move.tower.meepleType;
						tower.playerIndex = activePlayerIndex;
					}
				} else if(activePlayer.towers > 0) {
					// a tower floor is being placed so increase the tower height and remove one of their tokens
					tower.height += 1;
					activePlayer.towers -= 1;
					// if a meeple was captured remove it and check for exchanges
					if(move.tower.capture) {
						var capturedMeeple = gamestate.placedTiles[tower.capture.tileIndex].meeples.splice(tower.capture.meepleIndex, 1)[0];
						// add a message about the capture to the game messages
						var message = activePlayer.user.username + ' captured a ' + capturedMeeple.meepleType + ' meeple from ' + gamestate.players[capturedMeeple.playerIndex].user.username;
						gamestate.messages.push({ username: null, message: message });
						// exchange this meeple if possible
						var meepleIndexForExchange;
						var playerBeingCapturedFrom = gamestate.players[capturedMeeple.playerIndex];
						for(var i = 0; i < playerBeingCapturedFrom.capturedMeeples.length; i++) {
							var meepleForExchange = playerBeingCapturedFrom.capturedMeeples[i];
							if(move.tower.capture.exchangeType === meepleForExchange.meepleType) {
								// if this meeple is the type specified by the user get it
								meepleIndexForExchange = i;
							} else if(move.tower.capture.exchangeType === undefined) {
								// if the user didn't specify a type to capture
								if(meepleIndexForExchange === undefined) {
									// capture the first meeple we find
									meepleIndexForExchange = i;
								} else if(playerBeingCapturedFrom.capturedMeeples[meepleIndexForExchange].meepleType === 'normal' &&
													playerBeingCapturedFrom.capturedMeeples[i].meepleType === 'large') {
									// and if we are currently getting a normal meeple back and find a large one get that instead
									meepleIndexForExchange = i;
								}
							}
						}
						// if we found a meeple to exchange refund both players their meeples and remove them, otherwise record the meeple as captured
						//TODO: validate that this doesn't need any markModified calls to store to backend
						if(meepleIndexForExchange) {
							if(capturedMeeple.meepleType === 'normal') {
								gamestate.players[capturedMeeple.playerIndex].remainingMeeples++;
							} else {
								gamestate.players[capturedMeeple.playerIndex][getMeepleFlagFromType(capturedMeeple.meepleType)] = true;
							}
							var returnedMeeple = playerBeingCapturedFrom.capturedMeeples.splice(meepleIndexForExchange, 1)[0];
							if(returnedMeeple.meepleType === 'normal') {
								gamestate.players[returnedMeeple.playerIndex].remainingMeeples++;
							} else {
								gamestate.players[returnedMeeple.playerIndex][getMeepleFlagFromType(returnedMeeple.meepleType)] = true;
							}
						} else {
							activePlayer.capturedMeeples.push({
								playerIndex: capturedMeeple.playerIndex,
								meepleType: capturedMeeple.meepleType
							});
						}
					}
				}
			}
			gamestate.populate('placedTiles.tile players.user', function(err, gamestate) {
				var builderActivated = false;
				var featureInfo, meepleIndex, meepleTile;
				var newlyPlacedTile = gamestate.placedTiles[gamestate.placedTiles.length - 1];
				// console.log('gamestate before cities =>' + JSON.stringify(gamestate));
				// console.log('==========================');
				// check for cities with meeples on them connected to the active tile which may have been completed by the placement
				for(var i = 0; i < newlyPlacedTile.tile.cities.length; i++) {
					// if not placing a builder in this move check for an activated builder on this feature
					if(move.meeple === undefined || move.meeple.meepleType !== 'builder') {
						featureInfo = getFeatureInfo(newlyPlacedTile, i, 'city', gamestate);
						for(var i1 = 0; i1 < featureInfo.tilesWithMeeples.length; i1++) {
							meepleIndex = featureInfo.tilesWithMeeples[i1].meepleIndex;
							meepleTile = featureInfo.tilesWithMeeples[i1].placedTile;
							if(meepleTile.meeples[meepleIndex].meepleType === 'builder' && meepleTile.meeples[meepleIndex].playerIndex === activePlayerIndex) {
								builderActivated = true;
								break;
							}
						}
					}
					checkAndFinalizeFeature(newlyPlacedTile, i, 'city', false, gamestate);
				}
				// console.log('gamestate after cities =>' + JSON.stringify(gamestate));
				// console.log('==========================');
				// and check for roads
				for(var k = 0; k < newlyPlacedTile.tile.roads.length; k++) {
					// if not placing a builder in this move check for an activated builder on this feature
					if(move.meeple === undefined || move.meeple.meepleType !== 'builder') {
						featureInfo = getFeatureInfo(newlyPlacedTile, k, 'road', gamestate);
						for(var k1 = 0; k1 < featureInfo.tilesWithMeeples.length; k1++) {
							meepleIndex = featureInfo.tilesWithMeeples[k1].meepleIndex;
							meepleTile = featureInfo.tilesWithMeeples[k1].placedTile;
							if(meepleTile.meeples[meepleIndex].meepleType === 'builder' && meepleTile.meeples[meepleIndex].playerIndex === activePlayerIndex) {
								builderActivated = true;
								break;
							}
						}
					}
					checkAndFinalizeFeature(newlyPlacedTile, k, 'road', false, gamestate);
				}
				// check for any completed cloisters caused by the tile placement both on this tile and on any nearby tiles
				var northTile, northwestTile, northEastTile, westTile, eastTile, southTile, southwestTile, southeastTile;
				if(newlyPlacedTile.northTileIndex !== undefined) {
					northTile = gamestate.placedTiles[newlyPlacedTile.northTileIndex];
					if(northTile.tile.cloister) {
						checkAndFinalizeFeature(northTile, 1, 'cloister', false, gamestate);
					}
					if(northTile.westTileIndex !== undefined) {
						northwestTile = gamestate.placedTiles[northTile.westTileIndex];
						if(northwestTile.tile.cloister) {
							checkAndFinalizeFeature(northwestTile, 1, 'cloister', false, gamestate);
						}
					}
					if(northTile.eastTileIndex !== undefined) {
						northEastTile = gamestate.placedTiles[northTile.eastTileIndex];
						if(northEastTile.tile.cloister) {
							checkAndFinalizeFeature(northEastTile, 1, 'cloister', false, gamestate);
						}
					}
				}
				if(newlyPlacedTile.southTileIndex !== undefined) {
					southTile = gamestate.placedTiles[newlyPlacedTile.southTileIndex];
					if(southTile.tile.cloister) {
						checkAndFinalizeFeature(southTile, 1, 'cloister', false, gamestate);
					}
					if(southTile.westTileIndex !== undefined) {
						southwestTile = gamestate.placedTiles[southTile.westTileIndex];
						if(southwestTile.tile.cloister) {
							checkAndFinalizeFeature(southwestTile, 1, 'cloister', false, gamestate);
						}
					}
					if(southTile.eastTileIndex !== undefined) {
						southeastTile = gamestate.placedTiles[southTile.eastTileIndex];
						if(southeastTile.tile.cloister) {
							checkAndFinalizeFeature(southeastTile, 1, 'cloister', false, gamestate);
						}
					}
				}
				if(newlyPlacedTile.eastTileIndex !== undefined) {
					eastTile = gamestate.placedTiles[newlyPlacedTile.eastTileIndex];
					if(eastTile.tile.cloister) {
						checkAndFinalizeFeature(eastTile, 1, 'cloister', false, gamestate);
					}
				}
				if(newlyPlacedTile.westTileIndex !== undefined) {
					westTile = gamestate.placedTiles[newlyPlacedTile.westTileIndex];
					if(westTile.tile.cloister) {
						checkAndFinalizeFeature(westTile, 1, 'cloister', false, gamestate);
					}
				}
				if(newlyPlacedTile.tile.cloister) {
					checkAndFinalizeFeature(newlyPlacedTile, 1, 'cloister', false, gamestate);
				}
				// console.log('gamestate after cloisters =>' + JSON.stringify(gamestate));
				// console.log('==========================');
				// change the active player if the builder wasn't activated (or if it was and the active player already had an extra turn)
				if(!builderActivated || gamestate.placedTiles[gamestate.placedTiles.length - 2].playerIndex === activePlayerIndex) {
					gamestate.players[activePlayerIndex].active = false;
					gamestate.players[(activePlayerIndex + 1) % gamestate.players.length].active = true;
				}
				gamestate.drawTile(callback, autocomplete);
			});
		}
	});
};

function getFeatureInfo(currentTile, featureIndex, featureType, gamestate, checked) {
	var results;
	if(featureType === 'cloister') {
		results = {
			points: 0,
			tilesWithMeeples: []
		};
		// iteratively check this tile and all those around it
		// add a point for every tile in range
		for(var ind = 0; ind < gamestate.placedTiles.length; ind++) {
			if((gamestate.placedTiles[ind].x <= currentTile.x + 1 && gamestate.placedTiles[ind].x >= currentTile.x - 1) &&
			   (gamestate.placedTiles[ind].y <= currentTile.y + 1 && gamestate.placedTiles[ind].y >= currentTile.y - 1)) {
				results.points++;
			}
		}
		// grab the potential reference to the cloister meeple
		for(var ind2 = 0; ind2 < currentTile.meeples.length; ind2++) {
			if(currentTile.meeples[ind2].placement.locationType === 'cloister') {
				results.tilesWithMeeples.push({
					placedTile: currentTile,
					meepleIndex: ind2
				});
				break;
			}
		}
		results.complete = (results.points === 9);
		return results;
	} else if(featureType === 'road' || featureType === 'city' || featureType === 'farm') {
		// recursively calculate feature (road or city) completeness, point value
		// and record tiles with placed meeples for potential removal and scoring
		var initialCall;
		if(!checked) {
			checked = {};
			if(featureType === 'farm') {
				checked.cities = {};
			}
			initialCall = true;
		}
		results = {
			complete: true,
			points: 0,
			tilesWithMeeples: [],
			goods: []
		};
		// if we have already examined this feature skip checking and add zero points
		if(checked[currentTile] &&
		   checked[currentTile].features.indexOf(featureIndex) !== -1) {
			// console.log('seen this tile');
			return results;
		}
		// otherwise record the feature index of the tile as checked
		if(checked[currentTile]) {
			checked[currentTile].features.push(featureIndex);
		} else {
			checked[currentTile] = {
				tile: currentTile,
				features: [featureIndex]
			};
			// only add points for cities and roads if this is the first time encountering the tile
			if(featureType === 'city') {
				results.points = currentTile.tile.doublePoints === true || currentTile.tile.doublePoints === featureIndex  ? 2 : 1;
			} else if(featureType === 'road') {
				results.points = 1;
			}
		}
		// if looking for farms add three points for each adjacent complete city
		if(featureType === 'farm') {
			// console.log('checking farm: ' + featureIndex);
			// console.log('farm tile: ' + JSON.stringify(currentTile));
			// find any complete cities adjacent to this field which have not been recorded yet
			if(currentTile.tile.farms[featureIndex].adjacentCityIndices) {
				// for each adjacent city
				for(var k = 0; k < currentTile.tile.farms[featureIndex].adjacentCityIndices.length; k++) {
					// get the completeness
					var cityIndex = currentTile.tile.farms[featureIndex].adjacentCityIndices[k];
					// console.log('checking adjacent city: ' + cityIndex);
					var info = getFeatureInfo(currentTile, cityIndex, 'city', gamestate);
					// console.log('city: ' + JSON.stringify(info));
					if(info.complete) {
						var unseen = true;
						// check each of the features visited when gathering the info on the city against previously seen cities
						// this prevents cities from being counted twice during the farm point calculation
						// console.log('checked: ' + JSON.stringify(checked));
						for(var f = 0; f < info.visitedFeatures.length; f++) {
							if(checked.cities[info.visitedFeatures[f].tile]) {
								for(var g = 0; g < info.visitedFeatures[f].features.length; g++) {
									var visitedIndex = info.visitedFeatures[f].features[g];
									if(checked.cities[info.visitedFeatures[f].tile].features.indexOf(visitedIndex) !== -1) {
										unseen = false;
									} else {
										checked.cities[info.visitedFeatures[f].tile].features.push(visitedIndex);
									}
								}
							} else {
								checked.cities[info.visitedFeatures[f].tile] = {
									tile: info.visitedFeatures[f].tile,
									features: info.visitedFeatures[f].features
								};
							}
						}
						if(unseen) {
							results.points += 3;
							// console.log('**found unseen city**');
						}
					}
				}
			}
		}
		// console.log('checking meeples =>' + JSON.stringify(currentTile.meeples));
		// console.log('==========================');
		// record the locations of any meeples on this feature
		for(var i = 0; i < currentTile.meeples.length; i++) {
			if(currentTile.meeples[i].placement.locationType === featureType &&
			   currentTile.meeples[i].placement.index === featureIndex) {
				results.tilesWithMeeples.push({
					placedTile: currentTile,
					meepleIndex: i
				});
			}
		}
		// grab the definition of the current feature from the tile
		var pluralType = featureType === 'city' ? 'cities' : featureType + 's';
		var currentFeature = currentTile.tile[pluralType][featureIndex];
		// console.log('found feature ' + (featureType === 'city' ? 'cities' : featureType + 's') + ',' + featureIndex + '=>' + JSON.stringify(currentFeature));
		// console.log('==========================');
		// if this tile has trade goods on it add them to a list of all the trade goods
		if(featureType === 'city' && currentFeature.goods) {
			results.goods.push(currentFeature.goods);
		}
		// if this tile has an inn or a cathedral mark it as such in the results
		if(featureType === 'city' && currentTile.tile.cathedral) {
			results.cathedral = true;
		}
		if(featureType === 'road' && currentFeature.inn) {
			results.inn = true;
		}
		// for each side this feature has try and extend to connected tiles searching for
		// meeples to record, points to score, or to detect incompleteness
		for(var j = 0; j < currentFeature.directions.length; j++) {
			// apply the tiles rotation to the feature definition to determine which tile to check next
			var direction = currentFeature.directions[j];
			var connectedTile, flippedDirection;
			var directions = featureType === 'farm' ?  ['NNE','ENE','ESE','SSE','SSW','WSW','WNW','NNW'] : ['N','E','S','W'];
			var rotatedDirection = directions[(directions.indexOf(direction) + currentTile.rotation * (featureType === 'farm' ? 2 : 1)) % directions.length];
			if(rotatedDirection.charAt(0) === 'N') {
				connectedTile = gamestate.placedTiles[currentTile.northTileIndex];
				// flip the rotated direction since we are getting the feature index from the perspective of the connected tile
				flippedDirection = rotatedDirection.replace(/N/g,'S');
			} else if(rotatedDirection.charAt(0) === 'E') {
				connectedTile = gamestate.placedTiles[currentTile.eastTileIndex];
				// flip the rotated direction since we are getting the feature index from the perspective of the connected tile
				flippedDirection = rotatedDirection.replace(/E/g,'W');
			} else if(rotatedDirection.charAt(0) === 'S') {
				connectedTile = gamestate.placedTiles[currentTile.southTileIndex];
				// flip the rotated direction since we are getting the feature index from the perspective of the connected tile
				flippedDirection = rotatedDirection.replace(/S/g,'N');
			} else if(rotatedDirection.charAt(0) === 'W') {
				connectedTile = gamestate.placedTiles[currentTile.westTileIndex];
				// flip the rotated direction since we are getting the feature index from the perspective of the connected tile
				flippedDirection = rotatedDirection.replace(/W/g,'E');
			}
			if(!connectedTile) {
				// console.log('no connection: ' + rotatedDirection);
				// console.log('==========================');
				// if the feature extends in this direction and there is no tile the feature is not complete
				results.complete = false;
			} else {
				// console.log('moving: ' + rotatedDirection);
				// console.log('==========================');
				// traverse over to it summing up inn/cathedral status, completeness, points, and meeples
				var connectedIndex = getFeatureIndex(connectedTile, featureType, flippedDirection);
				var neighborResults = getFeatureInfo(connectedTile, connectedIndex, featureType, gamestate, checked);
				results.goods = results.goods.concat(neighborResults.goods);
				results.cathedral = results.cathedral || neighborResults.cathedral;
				results.inn = results.inn || neighborResults.inn;
				results.complete = results.complete && neighborResults.complete;
				results.points = results.points + neighborResults.points;
				for(var z = 0; z < neighborResults.tilesWithMeeples.length; z++) {
					results.tilesWithMeeples.push(neighborResults.tilesWithMeeples[z]);
				}
			}
		}
		// after we're all done compile a list of each feature we visited
		if(initialCall) {
			results.visitedFeatures = [];
			for(var key in checked) {
				results.visitedFeatures.push({
					tile: checked[key].tile,
					features: checked[key].features
				});
			}
		}
		return results;
	}
}

//TODO: instead of recalculating every time store feature info in gamestate and update with each placed tile
function checkAndFinalizeFeature(placedTile, featureIndex, featureType, gameFinished, gamestate) {
	// score this feature
	if((placedTile.tile.cloister && featureType === 'cloister') ||
	   featureType === 'road' ||
	   featureType === 'city' ||
	   featureType === 'farm') {
		var featureInfo = getFeatureInfo(placedTile, featureIndex, featureType, gamestate);
		// if the feature is done and there were meeples remove and score them
		if((featureInfo.complete || gameFinished) && featureInfo.tilesWithMeeples.length > 0) {
			// the points only go to the player(s) with the most meeples on the feature
			var meepleCount = {};
			var playersWithMeeples = [];
			var playersWithPigMeeple = [];
			var maxNumberOfMeeples = 1;
			for(var i = 0; i < featureInfo.tilesWithMeeples.length; i++) {
				// find the player this meeple belongs to
				var playerIndex = featureInfo.tilesWithMeeples[i].placedTile.meeples[featureInfo.tilesWithMeeples[i].meepleIndex].playerIndex;
				var meepleType = featureInfo.tilesWithMeeples[i].placedTile.meeples[featureInfo.tilesWithMeeples[i].meepleIndex].meepleType;
				// if the game is over just mark these meeples as scored, otherwise pick them up (remove them)
				if(gameFinished) {
					featureInfo.tilesWithMeeples[i].placedTile.meeples[featureInfo.tilesWithMeeples[i].meepleIndex].scored = true;
				} else {
					// remove the meeple from the placed tile
					featureInfo.tilesWithMeeples[i].placedTile.meeples.splice(featureInfo.tilesWithMeeples[i].meepleIndex, 1);
					// refund scored meeples if the game isn't over
					if(meepleType === 'normal') {
						gamestate.players[playerIndex].remainingMeeples += 1;
					} else {
						gamestate.players[playerIndex][getMeepleFlagFromType(meepleType)] = true;
					}
				}
				// if this is a farm record the players with a pig meeple
				if(featureType === 'farm' && meepleType === 'pig') {
					playersWithPigMeeple.push(playerIndex);
				}
				// increase this players count of meeples on this feature
				if(playersWithMeeples.indexOf(playerIndex) === -1) {
					playersWithMeeples.push(playerIndex);
					meepleCount[playerIndex] = 0;
				}
				if(meepleType === 'normal') {
					meepleCount[playerIndex]++;
				} else if(meepleType === 'large') {
					meepleCount[playerIndex] += 2;
				}
				// and update the max number of meeples if needed (for checking feature ownership)
				if(meepleCount[playerIndex] > maxNumberOfMeeples) {
					maxNumberOfMeeples = meepleCount[playerIndex];
				}
			}
			// score meeples on this feature for each player with the max number of meeples
			var scoringPlayers = [];
			var scoringPlayersWithPig = [];
			var scoredPoints = featureInfo.points;
			// if this is an uncomplete road with an inn or an uncomplete city with a cathedral zero the points
			if(!featureInfo.complete && (featureInfo.cathedral || featureInfo.inn)) {
				scoredPoints *= 0;
			}
			// if this is a complete city with a cathedral triple the points
			if(featureInfo.complete && featureInfo.cathedral) {
				scoredPoints *= 3;
			}
			// if this is a complete city without a cathedral double the points
			if(featureInfo.complete && featureType === 'city' && !featureInfo.cathedral) {
				scoredPoints *= 2;
			}
			// if this is a complete road with an inn double the points
			if(featureInfo.complete && featureInfo.inn) {
				scoredPoints *= 2;
			}
			for(var k = 0; k < gamestate.players.length; k++) {
				if(meepleCount[k]) {
					if(meepleCount[k] === maxNumberOfMeeples) {
						// if this player has a pig meeple on the farm score it as 4 points per city not 3
						if(featureType === 'farm' && playersWithPigMeeple.indexOf(k) !== -1) {
							gamestate.players[k].points += scoredPoints * 4 / 3;
							scoringPlayersWithPig.push(gamestate.players[k]);
						} else {
							gamestate.players[k].points += scoredPoints;
							scoringPlayers.push(gamestate.players[k]);
						}
						// console.log('=======');
						// console.log('scoring ' + featureInfo.points * (featureType === 'city' && !gameFinished ? 2 : 1) + ' points for player ' + k + ' ' + featureType);
						// console.log('-------');
						// console.log('feature info: ' + JSON.stringify(featureInfo));
					}
				}
			}

			// create the message to add to the chatlog to record the scoring
			var message;
			if(scoringPlayers.length > 0 && scoredPoints > 0) {
				message = scoringPlayers.map(function(player) {
					return player.user.username + ' (' + player.points + ')';
				}).join(' and ') + ' scored ' + scoredPoints + ' for ' + (featureType === 'farm' ? ' a ' : gameFinished ? 'an uncomplete ' : 'a completed ') + featureType;
				if(featureInfo.cathedral) {
					message += ' with a cathedral';
				} else if(featureInfo.inn) {
					message += ' with an inn';
				}
				gamestate.messages.push({ username: null, message: message });
			}
			if(scoringPlayersWithPig.length > 0) {
				message = scoringPlayersWithPig.map(function(player) {
					return player.user.username + ' (' + player.points + ')';
				}).join(' and ') + ' scored ' + (scoredPoints * 4 / 3) + ' for a farm with a pig';
				gamestate.messages.push({ username: null, message: message });
			}

			// assign any trade goods on a city to the player who completed the city (active player)
			if(featureInfo.complete && featureType === 'city' && featureInfo.goods.length > 0) {
				// get the active player
				var activePlayer;
				for(var i1 = 0; i1 < gamestate.players.length; i1++) {
					if(gamestate.players[i1].active) {
						activePlayer = gamestate.players[i1];
						break;
					}
				}
				// add the appropriate goods from the feature
				for(var j = 0; j < featureInfo.goods.length; j++) {
					activePlayer.goods[featureInfo.goods[j]]++;
				}
				var groupedGoods = {};
				featureInfo.goods.map(function(item) {
					if(item in groupedGoods) {
						groupedGoods[item]++;
					} else {
						groupedGoods[item] = 1;
					}
				});
				// create the message for the chat log saying who picked up what
				var goodsMessage = '';
				for(var good in groupedGoods) {
					if(goodsMessage !== '') {
						goodsMessage += ' and ';
					}
					goodsMessage += groupedGoods[good] + ' ' + good;
				}
				goodsMessage = activePlayer.user.username + ' picked up ' + goodsMessage;
				gamestate.messages.push({ username: null, message: goodsMessage });
			}
		}
	}
}

function getFeatureIndex(placedTile, type, direction) {
	// get the index of a feature based on a tile and the rotated direction on the tile (placed direction)
	// type must be 'city', 'farm', or 'road'
	var directions, unrotatedDirection, currentFeature;
	var pluralType = (type === 'city' ? 'cities' : type + 's');
	if(type === 'city' || type === 'road') {
		// take into account the tile rotation (which isn't applied to the feature definitions)
		directions = ['N','E','S','W'];
		unrotatedDirection = directions[((directions.indexOf(direction) - placedTile.rotation) % 4 + 4) % 4];
		// console.log('feature index find =>' + unrotatedDirection);
		// console.log('feature index find =>' + JSON.stringify(placedTile));
		// console.log('==========================');
		for(var i = 0; i < placedTile.tile[pluralType].length; i++) {
			currentFeature = placedTile.tile[pluralType][i];
			if(currentFeature.directions.indexOf(unrotatedDirection) !== -1) {
				return i;
			}
		}
	} else if(type === 'farm') {
		directions = ['NNE','ENE','ESE','SSE','SSW','WSW','WNW','NNW'];
		unrotatedDirection = directions[((directions.indexOf(direction) - placedTile.rotation * 2) % 8 + 8) % 8];
		for(var k = 0; k < placedTile.tile[pluralType].length; k++) {
			currentFeature = placedTile.tile[pluralType][k];
			if(currentFeature.directions.indexOf(unrotatedDirection) !== -1) {
				return k;
			}
		}
	} else if(type === 'cloister') {
		return 1;
	}
	throw new Error("couldn't find feature index for: " + placedTile.x + ',' + placedTile.y + ' ' + type + ':' + direction);
}

// create the model for game information and expose it to our app
module.exports = mongoose.model('Gamestate', gamestateSchema);