/*
Chain Reaction 2.2.  A strategy game.
Copyright (C) 2003 Neil Fraser
http://neil.fraser.name/software/chain/

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation.

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 General Public License (www.gnu.org) for more details.

This program compiles with JDK1.1.  It also compiles with JDK1.0,
but one must first comment out all the "setCursor(...)" lines.
*/

import java.awt.*;
import java.util.Vector;
import java.lang.Math;
import java.lang.Error;
import java.net.URL;

public class chain extends java.applet.Applet implements Runnable {

	// Dimensions of the playing field
	int MaxX = 6;     // number of columns in the playing field
	int MaxY = 5;     // number of rows in the playing field
	int Quantum = 64; // width/height of each square
	int Offset = 32;  // margin from top and left

	// Predrawn images of bomb clusters
	Image YellowBombs[] = {null, null, null, null, null, null, null};
	Image BlueBombs[] = {null, null, null, null, null, null, null};

	// There are many playing field objects, but this one is the onscreen version.
	// (The others are used by the CPU for min-max simulations)
	field LiveField;

	// Who's turn is it anyway?
	int Turn = 0;

	// How many moves have happened so far (not including the current one)?
	int MoveNumber = 0;

	// Demo (0) - Single player (1) - Two player (2)
	int Mode = 0;

	// Computer difficulty level (0-3)
	int Level = 1;

	// Is the 'Doom' level (3) available?
	boolean Doom = false;

	// Is the computer player responsible for this move?
	boolean ComputerTurn;

	// A string used to log the game results.  Used by me for statistics.
	String Log = "";

	// Avoid setting the cursor if no change is needed (slight speedup).
	int CursorX = -1;
	int CursorY = -1;

	// To interrupt a game, kill this thread.
	Thread GameThread;

	// Define the buttons.
	Button buttonLevel0;
	Button buttonLevel1;
	Button buttonLevel2;
	Button buttonLevel3;
	Button buttonHelp;
	Button buttonExit;
	Button buttonAbout;
	Button buttonOne;
	Button buttonTwo;

	// Define the popup.
	Panel popupPanel = null;
	Panel popupShadow = null;
	Button popupButton = null;

	// Status bar at the bottom.
	Label Statusbar;

	public void init() {
		super.init();

		setLayout(null);
		resize(MaxX*Quantum+2*Offset,MaxY*Quantum+2*Offset);
		setBackground(Color.black);

		Statusbar = new Label();
		Statusbar.setForeground(Color.white);
		int statusbarHeight = getGraphics().getFontMetrics().getHeight();
		Statusbar.reshape(Offset, bounds().height-statusbarHeight, MaxX*Quantum, statusbarHeight);
		add(Statusbar);

		Color buttonColor = new Color(12632256);
		buttonLevel0 = new Button("Easy");
		buttonLevel0.reshape(327,80,51,33);
		buttonLevel0.setBackground(buttonColor);
		buttonLevel0.hide();
		add(buttonLevel0);
		buttonLevel1 = new Button("Normal");
		buttonLevel1.reshape(327,144,51,33);
		buttonLevel1.setBackground(buttonColor);
		buttonLevel1.hide();
		add(buttonLevel1);
		buttonLevel2 = new Button("Hard");
		buttonLevel2.reshape(327,208,51,33);
		buttonLevel2.setBackground(buttonColor);
		buttonLevel2.hide();
		add(buttonLevel2);
		buttonLevel3 = new Button("Doom");
		buttonLevel3.reshape(327,272,51,33);
		buttonLevel3.setBackground(buttonColor);
		buttonLevel3.hide();
		add(buttonLevel3);
		buttonHelp = new Button("Help");
		buttonHelp.reshape(135,272,51,33);
		buttonHelp.setBackground(buttonColor);
		add(buttonHelp);
		buttonAbout = new Button("About");
		buttonAbout.reshape(199,272,51,33);
		buttonAbout.setBackground(buttonColor);
		add(buttonAbout);
		buttonExit = new Button("Exit");
		buttonExit.reshape(263,272,51,33);
		buttonExit.setBackground(buttonColor);
		add(buttonExit);
		buttonOne = new Button("Single player");
		buttonOne.reshape(168,80,113,33);
		buttonOne.setBackground(buttonColor);
		add(buttonOne);
		buttonTwo = new Button("Two player");
		buttonTwo.reshape(168,144,113,33);
		buttonTwo.setBackground(buttonColor);
		add(buttonTwo);
		buttonOne.requestFocus();

		// Draw off-screen images of bomb clusters for later use
		for (int z = 0; z <= 6; z++) {
			YellowBombs[z] = getBombImage(z, 1);
			BlueBombs[z] = getBombImage(z, 2);
		}

		// Create an empty board
		LiveField = new field(MaxX, MaxY);
	}

	public void paint(Graphics g) {
		// Redraw the entire screen from scratch.

		// Start with the gray borders
		g.setColor(Color.lightGray);
		for (int x = Offset; x <= Offset+MaxX*Quantum; x += Quantum)
			drawDashedLine(g, x, Offset, x, Offset+MaxY*Quantum, 4);
		for (int y = Offset; y <= Offset+MaxY*Quantum; y += Quantum)
			drawDashedLine(g, Offset, y, Offset+MaxX*Quantum, y, 4);

		// Stamp out all the bomb clusters
		for (int x = 0; x < MaxX; x++) {
			for (int y = 0; y < MaxY; y++) {
				drawSquare(g, x, y);
			}
		}
	}

	private void drawSquare(Graphics g, int x, int y) {
		// Stamp out the (predrawn) image for the specified square.
		// Called by the applet's paint function and also when bombs are placed/moved.
		if (0 > x || x >= MaxX || 0 > y || y >= MaxY)
			throw new Error("Square isn't on the board.");
		square mySquare = LiveField.getSquare(x, y);
		Image myImage;
		if (mySquare.owner == 0)
			myImage = YellowBombs[Math.min(mySquare.bombs, YellowBombs.length-1)];
		else
			myImage = BlueBombs[Math.min(mySquare.bombs, BlueBombs.length-1)];
		g.drawImage(myImage, x*Quantum+Offset+1, y*Quantum+Offset+1, this);
	}

	private void drawDashedLine(Graphics g, int x1, int y1, int x2, int y2, int cycle) {
		// Draw a line from 'x1,y1' to 'x2,y2'.
		// The line is broken into segments which are each 'cycle' pixels long. 
		int counter = 0;
		int dx = x2-x1;
		int dy = y2-y1;
		double dz = Math.sqrt((double) (dx*dx + dy*dy));
		cycle = cycle * 2;
		for (int z = 0; z<=dz; z++) {
			int x = (int) (x1 + dx * z/dz);
			int y = (int) (y1 + dy * z/dz);
			if (z % cycle < cycle / 2) {
				g.drawLine(x, y, x, y);
			}
		}
	}

	private Image getBombImage(int bombs, int who) {
		// Render an image of 'bombs' number of bombs, belonging to 'who'.
		// This is executed once (for each combination) at the start,
		// with the output saved for rapid reuse.
		// If you want to use external PNGs of bomb clusters, this is where to add it.
		Image img = this.createImage(63, 63);
		Graphics g = img.getGraphics();
		g.setColor(Color.black);
		g.fillRect(0, 0, 64, 64);

		if (bombs==0) {
			// Done.
		} else if (bombs==1) {
			drawBomb(g, 20, 19, who);
		} else if (bombs==2) {
			drawBomb(g,  7, 19, who);
			drawBomb(g, 35, 19, who);
		} else if (bombs==3) {
			drawBomb(g,  7, 31, who);
			drawBomb(g, 21,  5, who);
			drawBomb(g, 35, 32, who);
		} else if (bombs==4) {
			drawBomb(g,  9,  5, who);
			drawBomb(g, 33, 33, who);
			drawBomb(g, 33,  5, who);
			drawBomb(g,  9, 33, who);
		} else if (bombs==5) {
			drawBomb(g,  1, 10, who);
			drawBomb(g, 21,  2, who);
			drawBomb(g, 41, 10, who);
			drawBomb(g,  9, 35, who);
			drawBomb(g, 33, 36, who);
		} else { // Six or more bombs
			drawBomb(g,  1, 10, who);
			drawBomb(g, 21,  2, who);
			drawBomb(g, 41, 10, who);
			drawBomb(g,  1, 36, who);
			drawBomb(g, 21, 28, who);
			drawBomb(g, 41, 36, who);
		}
		return img;
	}

	private void drawBomb(Graphics g, int x, int y, int who) {
		// Draw a single bomb at the given coordinates, coloured for the given player.
		// Only called by getBombImage which draws the clusters.
		Color c_fuse = Color.lightGray;
		Color c_text;
		Color c_body;
		if (who == 1) {
			c_text = Color.blue;
			c_body = Color.yellow;
		} else {
			c_text = Color.yellow;
			c_body = Color.blue;
		}

		g.setColor(c_body);
		g.fillOval(x+1, y+7, 19, 19);
		g.fillRect(x+6, y+5, 9, 10);

		g.setColor(c_text);
		g.drawLine(x+6, y+12, x+14, y+20);
		g.drawLine(x+6, y+20, x+14, y+12);
		g.drawLine(x+6, y+13, x+13, y+20);
		g.drawLine(x+6, y+19, x+13, y+12);
		g.drawLine(x+7, y+12, x+14, y+19);
		g.drawLine(x+7, y+20, x+14, y+13);

		g.drawLine(x+8, y+12, x+8, y+12);
		g.drawLine(x+12, y+12, x+12, y+12);
		g.drawLine(x+8, y+20, x+8, y+20);
		g.drawLine(x+12, y+20, x+12, y+20);

		g.setColor(c_fuse);
		g.drawLine(x+10, y+1, x+10, y+4);
		g.drawLine(x+11, y+0, x+14, y+0);
		g.drawLine(x+11, y+1, x+11, y+1);
	}

	private boolean plantBomb(int x, int y) {
		// Add one bomb of 'Turn' colour to the live board at 'x'/'y'.
		if (0 > x || 0 > y || x >= MaxX || y >= MaxY)
			throw new Error("Out of range.");
		square mySquare = LiveField.getSquare(x, y);
		if (mySquare.bombs != 0 && mySquare.owner != Turn)
			return false;
		mySquare.addBomb(Turn);
		drawSquare(getGraphics(), x, y);
		Turn = (Turn == 1) ? 0 : 1;
		MoveNumber++;
		return true;
	}

	private void sequenceDetonations() {
		// Look for things to blow up.  Mathematically, the order doesn't matter.
		// Give priority (+2) to detonations that take out enemy squares (speeds up the end-game).
		// Give priority (+1) to detonations that neighbour previous detonation (looks more logical).
		// Add a random factor (0-1) so that order isn't deterministic.
		// Yes, this is overly picky, but the player spends a lot of time watching this.
		int lastX = -999;
		int lastY = -999;
		double bestScore;
		int bestX, bestY;
		boolean first = true;
		int owner;
		do {
			bestScore = -999;
			bestX = -999;
			bestY = -999;
			for (int x = 0; x < MaxX; x++)
				for (int y = 0; y < MaxY; y++)
					if (LiveField.getSquare(x, y).isOverloaded()) {
						owner = LiveField.getSquare(x, y).owner;
						double thisScore = Math.random();
						Vector neighbours = LiveField.neighbours(x, y);
						for (int n = 0; n < neighbours.size(); n++) {
							square neighbour = (square) neighbours.elementAt(n);
							if (neighbour.bombs != 0 && neighbour.owner != owner)
								thisScore += 2;
						}
						if (x == lastX && (y == lastY-1 || y == lastY+1)) thisScore++;
						if (y == lastY && (x == lastX-1 || x == lastX+1)) thisScore++;
						if (thisScore > bestScore) {
							bestScore = thisScore;
							bestX = x;
							bestY = y;
						}
					}
			if (bestScore != -999) {
				if (!first)
					try {Thread.currentThread().sleep(100);} catch (InterruptedException e) {}
				detonateWithGraphics(bestX, bestY);
				first = false;
				lastX = bestX;
				lastY = bestY;
				if (popupPanel == null && !buttonAbout.isVisible() && LiveField.isExterminated()) {
					buttonOne.show();
					buttonTwo.show();
					buttonAbout.show();
					buttonHelp.show();
					buttonExit.show();
					Statusbar.setText("");
					setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
					if (Mode == 1 && !Doom && Level == 2 && !ComputerTurn) {
						showPopup("Congratulations!\n\nYou beat Chain Reaction on the 'hard' level.\nNot many people can do that.  If 'hard'\nisn't hard enough for you, try playing\nthe 'doom' level which is now available\nin the single-player menu.\n\nGood Luck!");
						Doom = true;
					} else if (Mode == 1 && Level == 3 && !ComputerTurn) {
						showPopup("Wow!\n\nYou beat Chain Reaction on the 'doom' level.\nNot even I can do that.  Send me an email!");
					}
					if (Log.length() != 0) Log = Log + "_";
					Log = Log + Level + Mode + (ComputerTurn ? "C" : "H");
				}
			}
		} while (bestScore != -999);
		setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
	}

	private void detonateWithGraphics(int x, int y) {
		if (popupPanel == null && !buttonAbout.isVisible()) {
			Statusbar.setText("Detonating...");
			setCursor(new Cursor(Cursor.WAIT_CURSOR));
		}
		square victim = LiveField.getSquare(x, y);
		Vector neighbours = LiveField.neighbours(x, y);
		if (!victim.isOverloaded())
			throw new Error("Can't blow up non-overloaded square.");
		Graphics g = getGraphics();

		// Draw the implode sequence
		for (int n = 0; n < neighbours.size(); n++) {
			try {Thread.currentThread().sleep(100);} catch (InterruptedException e) {}
			victim.bombs--;
			drawSquare(g, x, y);
		}

		// Draw the explode sequence
		int gx = Quantum*x + Offset + Quantum/2 - 10;
		int gy = Quantum*y + Offset + Quantum/2 - 5;
		// XORMode draws with white, not the player's colour.
		// I don't know what I'm doing wrong.  -- Neil
		// Got it: it is just a bug in JDK1.0, JDK1.1 works fine.
		g.setColor(Color.black);
		g.setXORMode(victim.owner == 1 ? Color.blue : Color.yellow);
		for (int n = 8; n <= Quantum; n = n + 8) {
			if (x != 0) g.fillOval(gx - n, gy, 19, 19);
			if (x != MaxX-1) g.fillOval(gx + n, gy, 19, 19);
			if (y != 0) g.fillOval(gx, gy - n, 19, 19);
			if (y != MaxY-1) g.fillOval(gx, gy + n, 19, 19);
			try {Thread.currentThread().sleep(50);} catch (InterruptedException e) {}
			if (x != 0) g.fillOval(gx - n, gy, 19, 19);
			if (x != MaxX-1) g.fillOval(gx + n, gy, 19, 19);
			if (y != 0) g.fillOval(gx, gy - n, 19, 19);
			if (y != MaxY-1) g.fillOval(gx, gy + n, 19, 19);
		}
		g.setPaintMode();

		for (int n = 0; n < neighbours.size(); n++)
			((square) neighbours.elementAt(n)).addBomb(victim.owner);
		if (victim.bombs == 0)
			victim.owner = -1;
		if (x != 0) drawSquare(g, x-1, y);
		if (x != MaxX-1) drawSquare(g, x+1, y);
		if (y != 0) drawSquare(g, x, y-1);
		if (y != MaxY-1) drawSquare(g, x, y+1);
	}

	public boolean mouseMove(Event event, int x, int y) {
		// Change the cursor depending on what it is on top of.
		if (popupPanel != null || buttonAbout.isVisible()) {
			setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
		} else if (Statusbar.getText().endsWith("...")) {
			// I'm busy.  Go away.
			setCursor(new Cursor(Cursor.WAIT_CURSOR));
		} else {
			int squareX = (x - Offset + Quantum) / Quantum - 1;
			int squareY = (y - Offset + Quantum) / Quantum - 1;
			if (CursorX != squareX || CursorY != squareY) {
				if (squareX >= 0 && squareY >= 0 && squareX < MaxX && squareY < MaxY) {
					square mySquare = LiveField.getSquare(squareX, squareY);
					if (mySquare.bombs == 0 || mySquare.owner == Turn) {
						setCursor(new Cursor(Cursor.HAND_CURSOR));
					} else {
						setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
					}
				} else {
					setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
				}
				CursorX = squareX;
				CursorY = squareY;
			}
		}
		return true;
	}

	public boolean mouseUp(Event event, int x, int y) {
		// Human setting up us the bomb.
		CursorX = -1;
		CursorY = -1;
		if (popupPanel != null || buttonAbout.isVisible()) {
			// Menu is up.
		} else if (Statusbar.getText().endsWith("...")) {
			// I'm busy.  Go away.
		} else {
			int squareX = (x - Offset + Quantum) / Quantum - 1;
			int squareY = (y - Offset + Quantum) / Quantum - 1;
			if (squareX >= 0 && squareY >= 0 && squareX < MaxX && squareY < MaxY) {
				square mySquare = LiveField.getSquare(squareX, squareY);
				if (mySquare.bombs == 0 || mySquare.owner == Turn) {
					ComputerTurn = false;
					plantBomb(squareX, squareY);
					start(); // Launch a thread to detonate bombs and possibly run the CPU player.
				} else {
					// The enemy owns this square.
				}
			} else {
				// Out of play area.
			}
		}
		return super.mouseUp(event, x, y);
	}

	public void start() {
		// Applet launched; start the CPU vs CPU game playing.
		GameThread = new Thread(this);
		GameThread.start();
	}

	public void stop() {
		// Applet closing; kill the game.
		GameThread.stop();
	}

	public void run() {
		if (Mode == 0) { // Demo game: play until extermination.
			while (!LiveField.isExterminated()) {
				try {Thread.currentThread().sleep(1000);} catch (InterruptedException e) {}
				CPUplay();
				sequenceDetonations();
			}
		} else if (Mode == 1) { // Single player: do any detonations, play the CPU, then do any detonations.
			sequenceDetonations();
			if (!LiveField.isExterminated()) {
				if (popupPanel == null && !buttonAbout.isVisible()) {
					Statusbar.setText("Thinking...");
					setCursor(new Cursor(Cursor.WAIT_CURSOR));
				}
				try {Thread.currentThread().sleep(500);} catch (InterruptedException e) {}
				CPUplay();
				sequenceDetonations();
				if (popupPanel == null && !buttonAbout.isVisible()) {
					Statusbar.setText("Your turn.");
					setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
				}
			}
		} else { // Two player: do any detonations.
			sequenceDetonations();
			if (popupPanel == null && !buttonAbout.isVisible()) {
				Statusbar.setText((Turn == 1 ? "Blue" : "Yellow") + " player's turn.");
				setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
			}
		}
	}

	public void CPUplay() {
		// Where shall the computer play?
		ComputerTurn = true;

		// Early in the game, the best move is to play the corners.
		// Level 0 is too stupid to know this, so upgrade to Level 1 for these obvious moves.
		// Level 1 and above will figure it out quickly.
		// Level 2+3 will figure it out too, but downgrading to Level 1 saves CPU time.
		if (MoveNumber < 4 && Level != 1) {
			int saveLevel = Level;
			Level = 1;
			CPUplay();
			Level = saveLevel;
			return;
		}
		// For the first few moves there's no real strategy, so Level 3 is overkill.
		if (MoveNumber < 14 && Level == 3) {
			Level = 2;
			CPUplay();
			Level = 3;
			return;
		}

		if (Level == 0) {
			// Easy level.
			// Pick a random (valid) move, and go with that.
			int x, y;
			do {
				x = (int) Math.floor(Math.random()*MaxX);
				y = (int) Math.floor(Math.random()*MaxY);
			} while (!plantBomb(x, y));

		} else if (Level == 1) {
			// Normal level.
			// (Level one Min-Max) Simulate a move in each possible square,
			// then pick the one that leaves the board in the most favourable state.
			int bestX = -999;
			int bestY = -999;
			double bestScore = -999;
			double squareScore;
			field testField = new field(MaxX, MaxY);
			for (int x = 0; x < MaxX; x++)
				for (int y = 0; y < MaxY; y++)
					if (LiveField.getSquare(x, y).owner == -1 || LiveField.getSquare(x, y).owner == Turn) {
						testField.clone(LiveField);
						testField.simulate(x, y, Turn);
						squareScore = testField.score(Turn, (Turn == 1) ? 0 : 1) + Math.random();
						if (squareScore > bestScore) {
							bestX = x;
							bestY = y;
							bestScore = squareScore;
						}
					}
			plantBomb(bestX, bestY);

		} else if (Level == 2) {
			// Hard level.
			// (Level two Min-Max) Simulate a move in each possible square,
			// then simulate the enemy's best counter-move,
			// then pick the one that leaves the board in the most favourable state.
			int bestX = -999;
			int bestY = -999;
			field testField1 = new field(MaxX, MaxY);
			field testField2 = new field(MaxX, MaxY);
			double bestScore1 = -999;
			double worstScore2 = 999;
			double squareScore;
			for (int x1 = 0; x1 < MaxX; x1++)
				for (int y1 = 0; y1 < MaxY; y1++)
					if (LiveField.getSquare(x1, y1).owner == -1 || LiveField.getSquare(x1, y1).owner == Turn) {
						testField1.clone(LiveField);
						testField1.simulate(x1, y1, Turn);
						if (testField1.isExterminated()) {
							// Woo hoo!  CPU will win this move.
							worstScore2 = 999;
						} else {
							// Compute the worst possible counter-move.
							worstScore2 = 999;
							for (int x2 = 0; x2 < MaxX; x2++)
								for (int y2 = 0; y2 < MaxY; y2++)
									if (testField1.getSquare(x2, y2).owner != Turn) {
										testField2.clone(testField1);
										testField2.simulate(x2, y2, (Turn == 1) ? 0 : 1);
										squareScore = testField2.score(Turn, Turn);
										if (squareScore < worstScore2)
											worstScore2 = squareScore;
									}
						}
						worstScore2 += Math.random(); // Determinism looks bad.
						if (worstScore2 > bestScore1) {
							bestX = x1;
							bestY = y1;
							bestScore1 = worstScore2;
						}
					}
			if (bestScore1 < 1) {
				// CPU will lose.  Go out with a bang instead of a random wimper.
				Level = 1;
				CPUplay();
				Level = 2;
			} else {
				plantBomb(bestX, bestY);
			}

		} else if (Level == 3) {
			// Doom level.
			// (Level three Min-Max) Simulate a move in each possible square,
			// then simulate the enemy's best counter-move,
			// then simulate our best counter-counter-move,
			// then pick the one that leaves the board in the most favourable state.
			int bestX = -999;
			int bestY = -999;
			field testField1 = new field(MaxX, MaxY);
			field testField2 = new field(MaxX, MaxY);
			field testField3 = new field(MaxX, MaxY);
			double bestScore1 = -999;
			double worstScore2 = 999;
			double bestScore3 = -999;
			double squareScore;
			for (int x1 = 0; x1 < MaxX; x1++)
				for (int y1 = 0; y1 < MaxY; y1++)
					if (LiveField.getSquare(x1, y1).owner == -1 || LiveField.getSquare(x1, y1).owner == Turn) {
						testField1.clone(LiveField);
						if (testField1.simulate(x1, y1, Turn)) {
							// Woo hoo!  CPU will win this move.
							worstScore2 = 999;
						} else {
							// Compute their worst possible counter-move.
							worstScore2 = 999;
							for (int x2 = 0; x2 < MaxX; x2++)
								for (int y2 = 0; y2 < MaxY; y2++)
									if (testField1.getSquare(x2, y2).owner != Turn) {
										testField2.clone(testField1);
										if (testField2.simulate(x2, y2, (Turn == 1) ? 0 : 1)) {
											// Human would win next move.
											bestScore3 = -999;
										} else {
											// Compute our best possible counter-counter-move.
											bestScore3 = -999;
											thirdLoop:
											for (int x3 = 0; x3 < MaxX; x3++)
												for (int y3 = 0; y3 < MaxY; y3++)
													if (testField2.getSquare(x3, y3).owner != ((Turn == 1) ? 0 : 1)) {
														testField3.clone(testField2);
														if (testField3.simulate(x3, y3, Turn)) {
															// CPU would win on its next move
															bestScore3 = 999;
															break thirdLoop;
														} else {
															squareScore = testField3.score(Turn, (Turn == 1) ? 0 : 1);
															if (squareScore > bestScore3)
																bestScore3 = squareScore;
														}
													}
										}
										if (bestScore3 < worstScore2)
											worstScore2 = bestScore3;
									}
						}
						worstScore2 += Math.random(); // Determinism looks bad.
						if (worstScore2 > bestScore1) {
							bestX = x1;
							bestY = y1;
							bestScore1 = worstScore2;
						}
					}
			plantBomb(bestX, bestY);
		}
	}

	public boolean handleEvent(Event event) {
		if (event.target == popupButton && event.id == Event.ACTION_EVENT) {
			hidePopup();
			return true;
		} else if (popupPanel != null && popupButton.isVisible()) {
			// The popup is modal.
		} else if (event.target == buttonOne && event.id == Event.ACTION_EVENT) {
			buttonLevel0.show();
			if (Level == 0) buttonLevel0.requestFocus();
			buttonLevel1.show();
			if (Level == 1) buttonLevel1.requestFocus();
			buttonLevel2.show();
			if (Level == 2) buttonLevel2.requestFocus();
			if (Doom) buttonLevel3.show();
			if (Level == 3) buttonLevel3.requestFocus();
			Statusbar.setText("Choose the computer's skill level.");
			buttonTwo.hide();
			buttonOne.disable();
			buttonOne.setForeground(Color.gray);
			buttonExit.setLabel("Back");
			return true;
		} else if (event.target == buttonTwo && event.id == Event.ACTION_EVENT) {
			human_human();
			return true;
		} else if (event.target == buttonLevel0 && event.id == Event.ACTION_EVENT) {
			Level = 0;
			human_cpu();
			return true;
		} else if (event.target == buttonLevel1 && event.id == Event.ACTION_EVENT) {
			Level = 1;
			human_cpu();
			return true;
		} else if (event.target == buttonLevel2 && event.id == Event.ACTION_EVENT) {
			Level = 2;
			human_cpu();
			return true;
		} else if (event.target == buttonLevel3 && event.id == Event.ACTION_EVENT) {
			Level = 3;
			human_cpu();
			return true;
		} else if (event.target == buttonHelp && event.id == Event.ACTION_EVENT) {
			showPopup("Help for Chain Reaction\n\nPlayers take turns placing bombs onto the\nplaying field.  Play continues until one player\nhas no more bombs on the field.\n\nHeavy concentrations of bombs will explode\ncausing a chain reaction:\n- corners can only hold one bomb\n- edges can only hold two bombs\n- central squares can hold three bombs");
			return true;
		} else if (event.target == buttonAbout && event.id == Event.ACTION_EVENT) {
			showPopup("Chain Reaction version 2.2\nAugust, 2003\n\nNeil D. Fraser\nroot"+"@"+"neil.fraser.name\nhttp://neil.fraser.name/software/chain/\nInverness, Scotland\n\nOpen source, based on a classic\nGWBASIC game (author unknown)\n\nEnjoy!");
			return true;
		} else if (event.target == buttonExit && event.id == Event.ACTION_EVENT) {
			if (buttonExit.getLabel() == "Back") {
				buttonLevel0.hide();
				buttonLevel1.hide();
				buttonLevel2.hide();
				buttonLevel3.hide();
				Statusbar.setText("");
				buttonTwo.show();
				buttonOne.enable();
				buttonOne.setForeground(Color.black);
				buttonExit.setLabel("Exit");
			} else {
				// Pressing the exit button closes the applet's window.  This is impossible.
				// So instead we load a page called exit.html which contains JavaScript which does the closing for us.
				// This also gives me the opportunity to transmit a log of the game results back to the server.
				// This allows me to see what level people are playing at, how much they play, etc.
				try {
					getAppletContext().showDocument(new URL(getDocumentBase(), "exit.html?"+Log));
				} catch (java.net.MalformedURLException e) {
					showPopup("Error:\n"+e);
				}
				// stop();
			}
			return true;
		}
		return super.handleEvent(event);
	}

	void initializeGame() {
		buttonLevel0.hide();
		buttonLevel1.hide();
		buttonLevel2.hide();
		buttonLevel3.hide();
		buttonOne.setForeground(Color.black);
		buttonOne.enable();
		buttonOne.hide();
		buttonTwo.hide();
		buttonAbout.hide();
		buttonHelp.hide();
		buttonExit.setLabel("Exit");
		buttonExit.hide();

		GameThread.stop();
		LiveField = new field(MaxX, MaxY);
		repaint();
		Turn = 0;
		MoveNumber = 0;
	}

	void human_cpu() {
		// Start a game between a human and the computer.
		initializeGame();
		Mode = 1;
		if (Math.random() > 0.5) { // %50 of the time the computer plays first.
			Statusbar.setText("Thinking...");
			setCursor(new Cursor(Cursor.WAIT_CURSOR));
			CPUplay();
			// Detonations not possible after one turn.
		}
		Statusbar.setText("Your turn.");
		setCursor(new Cursor(Cursor.DEFAULT_CURSOR));
		// Execution will resume in mouseUp() when the human clicks a square.
	}

	void human_human() {
		// Start a game
		initializeGame();
		Mode = 2;
		Statusbar.setText((Turn == 1 ? "Blue" : "Yellow") + " player's turn.");
		// Execution will resume in mouseUp() when the human clicks a square.
	}

	void showPopup(String msg) {
		// Creates a simple (fake) popup alert window with a message.
		int popupHeight = 4*Quantum;
		int popupWidth = 5*Quantum;
		popupShadow = new Panel();
		popupShadow.reshape((this.size().width-popupWidth)/2-1,Offset+Quantum/2-1,popupWidth+2,popupHeight+2);
		popupShadow.setBackground(Color.gray);
		popupPanel = new Panel();
		popupPanel.reshape(1,1,popupWidth,popupHeight);
		popupPanel.setForeground(Color.black);
		popupPanel.setBackground(Color.white);

		String msgLine;
		Label msgLabel;
		int y = 0;
		int dy = getGraphics().getFontMetrics().getHeight();
		while (msg.length() != 0) {
			if (msg.indexOf("\n") == -1) {
				msgLine = msg;
				msg = "";
			} else {
				msgLine = msg.substring(0, msg.indexOf("\n"));
				msg = msg.substring(msg.indexOf("\n")+1);
			}
			y = y + dy;
			msgLabel = new Label(msgLine);
			msgLabel.reshape(10, y, popupWidth, dy);
			popupPanel.add(msgLabel);
		}

		popupButton = new Button("Ok");
		popupButton.reshape((popupWidth-50)/2,popupHeight-35,50,25);

		popupPanel.add(popupButton);
		popupShadow.add(popupPanel);
		this.add(popupShadow);

		buttonLevel0.hide();
		buttonLevel1.hide();
		buttonLevel2.hide();
		buttonLevel3.hide();
		buttonOne.hide();
		buttonTwo.hide();
		buttonAbout.hide();
		buttonHelp.hide();
		buttonExit.hide();

		popupButton.requestFocus(); // May or may not succeed.
	}

	void hidePopup() {
		// Destroys the simple (fake) popup window.
		this.remove(popupPanel);
		this.remove(popupShadow);
		popupButton = null;
		popupPanel = null;
		popupShadow = null;

		buttonOne.show();
		buttonAbout.show();
		buttonHelp.show();
		buttonExit.show();
		if (buttonOne.isEnabled()) {
			buttonTwo.show();
		} else {
			buttonLevel0.show();
			buttonLevel1.show();
			buttonLevel2.show();
			if (Doom) buttonLevel3.show();
		}
	}
}


class field {
	// This class represents the entire playing field.
	private square[][] squares;

	public field(int maxX, int maxY) {
		// Create a new, empty playing field.
		squares = new square[maxX][maxY];
		for (int x = 0; x < maxX; x++)
			for (int y = 0; y < maxY; y++)
				squares[x][y] = new square(neighbours(x, y).size());
	}

	// This function works fine, but isn't used anymore because clone() is faster.
	//public field(field master, int maxX, int maxY) {
	//	// Create a new field, identical to the master field (makes a copy).
	//	squares = new square[maxX][maxY];
	//	for (int x = 0; x < maxX; x++)
	//		for (int y = 0; y < maxY; y++)
	//			squares[x][y] = new square(master.getSquare(x, y), neighbours(x, y).size());
	//}

	public void clone(field master) {
		// Reconfigure the existing field so that it is identical to the master field (makes a copy).
		for (int x = 0; x < squares.length; x++)
			for (int y = 0; y < squares[x].length; y++) {
				squares[x][y].owner = master.getSquare(x, y).owner;
				squares[x][y].bombs = master.getSquare(x, y).bombs;
			}
	}

	public Vector neighbours(int x, int y) {
		// Return a vector containing the 2, 3 or 4 neighbouring squares.
		Vector neighbourVector = new Vector(4);
		if (x != 0)
			neighbourVector.addElement(squares[x-1][y]);
		if (y != 0)
			neighbourVector.addElement(squares[x][y-1]);
		if (x != squares.length-1)
			neighbourVector.addElement(squares[x+1][y]);
		if (y != squares[x].length-1)
			neighbourVector.addElement(squares[x][y+1]);
		return neighbourVector;
	}

	public square getSquare(int x, int y) {
		// Return the requested square.
		return squares[x][y];
	}

	private void detonateLogically(int x, int y) {
		// Blow up the specified square non-graphcially.
		// Used internally be the CPU player.
		square victim = squares[x][y];
		//if (!victim.isOverloaded())
		//	throw new Error("Can't blow up non-overloaded square.");
		Vector neighbours = neighbours(x, y);
		victim.bombs -= neighbours.size();
		for (int n = 0; n < neighbours.size(); n++)
			((square) neighbours.elementAt(n)).addBomb(victim.owner);
		if (victim.bombs == 0)
			victim.owner = -1;
	}

	public boolean simulate(int x, int y, int turn) {
		// Simulates the effects of droping a bomb belonging to 'Turn' on x/y.
		// Used internally by the CPU player on disposable copies of the board.
		// Returns true if this move wipes out the other player.
		//if (0 > x || 0 > y || x >= squares.length || y >= squares[x].length)
		//	throw new Error("Out of range.");
		square mySquare = this.getSquare(x, y);
		//if (mySquare.bombs != 0 && mySquare.owner != turn)
		//	throw new Error("Illegal move.");
		mySquare.addBomb(turn);
		if (!mySquare.isOverloaded())
			return false;
		detonateLogically(x, y);
		boolean stable;
		boolean exterminated;
		do {
			stable = true;
			for (int scanX = 0; scanX < squares.length; scanX++)
				for (int scanY = 0; scanY < squares[scanX].length; scanY++)
					if (this.getSquare(scanX, scanY).isOverloaded()) {
						detonateLogically(scanX, scanY);
						stable = false;
					}
			exterminated = this.isExterminated();
		} while (!stable && !exterminated);
		return exterminated;
	}

	public boolean isExterminated() {
		// Has one player exterminated the other?
		int who = -1;
		boolean multiple = false;
		for (int x = 0; x < squares.length; x++)
			for (int y = 0; y < squares[x].length; y++)
				if (squares[x][y].bombs != 0)
					if (who == -1)
						who = squares[x][y].owner; // first bomb found
					else if (who == squares[x][y].owner)
						multiple = true; // there's more than one square with bombs
					else
						return false; // there's more than one player
		// There's only one player on the board.
		// But that's ok if there's only one square filled
		// (meaning the other player hasn't had its first turn yet).
		return multiple;
	}

	public double score(int who, int nextWho) {
		// Calculates a percentage which is designed to indicate how healthy a player's position is.
		// Used internally by the CPU player to rank the results of hypothetical moves.
		// Changes to this function can have a profound effect on the CPU player.
		int us = 0;
		int them = 0;
		int squareScore;
		for (int x = 0; x < squares.length; x++)
			for (int y = 0; y < squares[x].length; y++)
				if (squares[x][y].bombs != 0) {
					squareScore = 1; // One point for owning the square.
					squareScore += squares[x][y].bombs; // One point for each bomb.

					// Inventory our neighbourhood enemies.
					int enemy = 0;
					int enemyCritical = 0;
					Vector neighbours = neighbours(x, y);
					for (int n = 0; n < neighbours.size(); n++) {
						square neighbour = (square) neighbours.elementAt(n);
						if (neighbour.bombs != 0 && neighbour.owner != squares[x][y].owner) {
							enemy++;
							if (neighbour.isCritical())
								enemyCritical++;
						}
					}
					if (enemyCritical != 0)
						if (squares[x][y].isCritical())
							if (squares[x][y].owner == nextWho) // We are in control.
								squareScore += (enemyCritical * 2) + 1;
							else // We can be hijacked.
								squareScore = 1-squareScore;
						else // We can be wiped out.
							squareScore = 1;
					else if (squares[x][y].isCritical()) // Being critical is good.
						squareScore += enemy + 1; // We can wipe any enemy out.

					if (squares[x][y].owner == who)
						us += squareScore;
					else
						them += squareScore;
				}

		while (us <= 0 || them <= 0) {
			us++;
			them++;
		}
		return (double) us / (double) (us + them) * 100;
	}
}


class square {
	// This class represents one square on the playing field. 
	public int neighbourcount;
	public int bombs = 0;
	public int owner = -1;

	public square(int newNeighbourcount) {
		// Create a new square with the specified number of neighbours.
		neighbourcount = newNeighbourcount;
	}

	// This function works fine, but isn't used anymore because field.clone() is faster.
	//public square(square master, int newNeighbourcount) {
	//	// Create a new square identical to the master square (makes a copy).
	//	neighbourcount = newNeighbourcount;
	//	bombs = master.bombs;
	//	owner = master.owner;
	//}

	public void addBomb(int who) {
		// Add one bomb belonging to 'who' to this square.
		// Called when a player moves, and when a neighbouring square explodes.
		owner = who;
		bombs++;
	}

	public boolean isCritical() {
		// Is this square currently at maximum capacity?
		return bombs + 1 == neighbourcount;
	}

	public boolean isOverloaded() {
		// Is this square currently beyond maximum capacity?
		return bombs >= neighbourcount;
	}
}