Homework 3, CSE 490ra

Due Tuesday, October 21, 11:59 am

Tic-Tac-Toe

This assignment is to create a tic-tac-toe program for the Tablet PC. However, the role of the program is to mediate between two players - not to play the game. The goal is to develop a natural User Interface for Tic-Tac-Toe, where the players play the game with ink.

In order to initialize the game, one player will need to draw the board out on the specified ink pad in order to “initialize” the playing surface. Players will take turns drawing X’s and O’s in order on the game board. If a player wins by connecting three X’s or O’s in order, then the Tablet should recognize this and send a “game over” message to the players. If the game ends in a tie and no user wins, then the application will end the current game. You will also need to build some kind of GUI or interface that supports your commands. As a brief summary, the required objectives are:

Let one user draw the game board in order to “initialize it”.
Players alternate drawing X’s and O’s. If an X or O is not recognized, or the player tries to fill a filled square, throw an error message.
If a player makes three in a row, draw a line through the three symbols and display a message.

The rest of the details are up to you, as long as the application meets the mentioned specifications. IMPT: PLEASE WRITE YOUR OWN RECOGNITION FUNCTIONS FOR THIS ASSIGNMENT. DO NOT USE THE SDK’S RECOGNITION’S ENGINE. You are of course welcome to add any of your own functionality if you want. Just be sure to document it in your turn-in. The players should use the board that you have drawn, and the regions should be roughly the regions that are drawn.

Hints

Your recognition should pick out things that look like X's and things that look like O's. A reasonable definition of an X is two strokes that cross. My initial attempt at recognizing O's was to have a single stroke that intersected itself - however, I found that it was very common to draw O's that didn't close, so I changed the recognition to allow for that as well.
For assigning positions to the X's and O's, I derived a single point from each. I used the center of mass, which is easy to implement, and does the right thing.
By far the hardest part of the assignment (for me) was getting the geometry right to determine when a point was in one of the nine cells of the tic-tac-toe board. My basic approach was to use the four intersection points to define four directed lines, Lower, Upper, Right, and Left. Given a new point, I would determine which side it was of each of the lines, and then based on this information, it would be assigned to a cell.

Below is some sample code, which might, or might not be of use. The geometric code tests if a point p3 is to the left of the line that goes from p1 to p2. This test is convenient to use, once you have the lines oriented properly. Another source of confusion (for me, at least) is the coordinates have the origin at the upper left.

         {
		// CCW test - return true if p3 is to the left of p1->p2 (a ccw turn)
		public static bool CcwTest(Point p1, Point p2, Point p3){
			int q1 = (p1.Y - p2.Y)*(p3.X - p1.X);
			int q2 = (p2.X - p1.X)*(p3.Y - p1.Y);
			return q1 + q2 < 0;      // The use of the inverted coordinate system reverses the sign on the test.
		}



		// Find the game region of a point
		// The board is considered to be ordered 
		//  0, 1, 2
		//  3, 4, 5
		//  6, 7, 8
		//  However, the lookup tests are done by checking position wrt to the lines
		//  so this position might infact be rotated by 90 degrees
		private int RegionLookup(int x, int y){
			Point p = new Point(x, y);
			Point pInk = ScreenToInk(p);
			return CellLookup(pInk);
		}

		// Lookup a cell in Ink Coordinates
		private int CellLookup(Point pInk){

			bool lowerTest = this.lowerLine.LeftOf(pInk);
			bool rightTest = this.rightLine.LeftOf(pInk);
			bool upperTest = this.upperLine.LeftOf(pInk);
			bool leftTest = this.leftLine.LeftOf(pInk);

			// Now implement a decision tree.  This is accurate if the lines don't
			// cross - arbitrary results for ambiguous regions
			if (lowerTest){
				if (rightTest){
					if (upperTest){
						if (leftTest)
							return 4;
						else
							return 3;
					}
					else {
						if (leftTest)
							return 1;
						else
							return 0;
					}
				}
				else {
					if (upperTest)
						return 5;
					else 
						return 2;
				}
			}
			else {
				if (rightTest){
					if (leftTest)
						return 7;
					else 
						return 6;
				}
				else
					return 8;
			}


		}
        }


	public class Segment {
		Point p1;
		Point p2;

		public Segment(Point p1, Point p2){
			this.p1 = p1;
			this.p2 = p2;
		}

		// Check if a point is Left, or right of a line
		public bool LeftOf(Point p3){
			return GameForm.CcwTest(p1, p2, p3);
		}

Creativity

Feel free to extend this assignment as you wish.

Submission

Submit a screen shot by the deadline by email to the instructor (anderson@cs.washington.edu). Also, submit a zipped directory of your code, project files, and executable.