/* --------------------------------------------------------------------

PuzzleNode Class

Copyright (c) 1996 by Christopher R. Waterson. All Rights Reserved.
Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and without
fee is hereby granted provided that this copyright notice
appears in all copies.

File:		PuzzleNode.java
Synopsis:	A graphical node in an eight-puzzle search tree.
Author:		Christopher R. Waterson <waterson@eecs.umich.edu>
Created:	26 Jan 1996
Modified:	31 Oct 1996

Description
-----------

Implements a graphical node in an eight-puzzle search tree.


-------------------------------------------------------------------- */

package eightpuzzle;


/**
 * A node in an eight-puzzle solver search tree
 */

public class PuzzleNode
{

	/**
	 * The eight puzzle that is the state associated with this node
	 */

	Puzzle m_puzzle;


	/**
	 * This node's parent
	 */

	PuzzleNode m_parent;


	/**
	 * This node's children
	 */

	PuzzleNode[] m_children;


	/**
	 * The number of children this node has
	 */

	int m_numChildren;


	/**
	 * The operator used to reach this node from its parent
	 */

	int m_operator;


	/**
	 * The total path cost from the initial state to this node, one per
	 * operator.
	 */

	int m_pathCost;


	/**
	 * This node's cost; varies depending on the search heuristic used
	 */

	int m_nodeCost;

	/**
	 * The x-coordinate at which the node is displayed on the canvas
	 */

	double m_x;

	/**
	 * The y-coordinate at which the node is displayed on the canvas
	 */

	double m_y;


	/**
	 * The direction in which the node was extended from its parent.
	 */

	double m_theta;


	/**
	 * The arc allowed for extending this node's children.
	 */

	double m_dTheta;


	/**
	 * The maximum number of children that the node can have
	 */

	public static final int MAX_CHILDREN = 4;


	/**
	 * This is used to fudge the graphics computation for the
	 * tree. If it's set to 1.0, then the tree will be such that
	 * branches will never overlap. Set to about 2.0 and it overlaps
	 * a little bit, but not to bad. Used in ComputeChildGraphics.
	 */

	public static final double TREE_BRANCH_FUDGE = 1.0;



	/**
	 * Create a new eight puzzle node from an eight puzzle state.
	 * @param puzzle The puzzle from which to construct the search tree node.
	 */

	public
	PuzzleNode(Puzzle puzzle) {
		m_puzzle = puzzle;
		m_pathCost = 0;
		m_nodeCost = 0;

		m_numChildren = 0;
		m_children = new PuzzleNode[MAX_CHILDREN];

		m_x = 0.0;
		m_y = 0.0;
		m_theta = 0;
		m_dTheta = 2 * Math.PI;
	}




	/**
	 * Computes the graphics information for the children of the current node.
	 */

	private void
	computeChildGraphics() {
		// The number of arcs that'll have to lead out of the parent node
		// is equal to the number of kids I have
		double numArcs = (double) m_numChildren;

		// If I'm not the root, then add one just to keep things neat.
		if (m_parent != null) numArcs += 1.0;

		// Gamma is the increment in degrees between individual child nodes
		double gamma = m_dTheta / numArcs;

		// ...and r is the distance that we'll have to extend the node
		// outwards to ensure that we can maintain a constant 1.0 distance
		// between nodes.
		//double r = 1.0 / (2.0 * Math.sin(gamma / 2.0));
		double r = 1.0;

		// Now re-compute the (x, y, theta, dTheta) values for my children
		for (int i = 0; i < m_numChildren; ++i) {
			// ThetaPrime is the new theta value that child[i] will get.
			double thetaPrime = m_theta - (m_dTheta / 2) + ((double) (i + 1) * gamma);

			m_children[i].m_x = m_x + Math.cos(thetaPrime) * r;
			m_children[i].m_y = m_y + Math.sin(thetaPrime) * r;
			m_children[i].m_theta = thetaPrime;
			m_children[i].m_dTheta = TREE_BRANCH_FUDGE * m_dTheta / numArcs;
		}
	}


	/**
	 * Expands the current eight-puzzle node, creating children that
	 * are one move away.
	 */

	public void
	expand() {
		// To expand the current node, try to move each tile.
		for (int i = 1; i <= 8; ++i) {

			// If the tile can be moved...
			if (m_puzzle.canMove(i)) {
				// Create a new eight-puzzle from *my* puzzle, and
				// apply operator i to it.
				Puzzle puzzle = new Puzzle(m_puzzle);
				puzzle.move(i);

				// Now create a new child node with the puzzle.
				PuzzleNode child = new PuzzleNode(puzzle);

				// Tie up all of the loose ends...
				child.m_parent = this;
				child.m_operator = i;
				child.m_pathCost = m_pathCost + 1;

				// Uniform cost search
				// child.m_nodeCost = m_pathCost;

				// A* search
				child.m_nodeCost = m_pathCost + puzzle.totalManhattanDistance();

				// Uniform-cost Search
				//child.m_nodeCost = m_pathCost;

				// Greedy Search
				//child.m_nodeCost = puzzle.TotalManhattanDistance();

				m_children[m_numChildren] = child;
				m_numChildren++;
			}
		}

		// Compute the graphic layout for the node.
		computeChildGraphics();
	}



	/**
	 * Return the x-coordinate associated with this node
	 */

	public double
	getX() { return m_x; }


	/**
	 * Return the y-coordinate associated with this node
	 */

	public double
	getY() { return m_y; }


	/**
	 * Return the eight-puzzle associated with this node
	 */

	public Puzzle
	getPuzzle() {
		return m_puzzle;
	}


	/**
	 * Return this node's parent
	 */

	public PuzzleNode
	getParent() {
		return (PuzzleNode) m_parent;
	}


	/**
	 * Return the number of children that this node has
	 */

	public int
	getNumChildren() {
		return m_numChildren;
	}


	/**
	 * Return the specified child of this node
	 */

	public PuzzleNode
	getChild(int which) {
		return (PuzzleNode) m_children[which];
	}


	/**
	 * Return the operator associated with this node
	 */

	public int
	getOperator() {
		return m_operator;
	}


	/**
	 * Return the node's cost.
	 */

	public int
	getCost() {
		return m_nodeCost;
	}
}