The Game Development Framework

/*****************************************
 * GameFX (Game Development Framework)   *
 * Version 1.0 (Beta)                    *
 * Copyright © 2009 Henize Software      *
 *****************************************/

using System;
using System.Collections.Generic;

using HenizeSoftware.GameFX.TileMap;

namespace HenizeSoftware.GameFX.PathFinding
{
  /// <summary>
  /// The Node class is the basic unit of data that the SimplePathFinder works with. Each Node holds its coordinate on the TileMap, a Node knows where the goal
  /// is, it can do some basic cost of movement calculations, and it can create and initialize the set of Nodes that succeed it. 
  /// </summary>
  /// <typeparam name="TData">The type to use to store the Tile's information. Constrained by struct.</typeparam>
  public class Node<TData> : IEquatable<Node<TData>>, IComparable<Node<TData>> where TData : struct
  {
    #region Fields

    /// <summary>
    /// The instance of the A* pathfinding algorithm that this Node belongs to. 
    /// </summary>
    protected readonly SimplePathFinder<TData> _AStarAlg;

    /// <summary>
    /// This Nodes' parent Node.
    /// </summary>
    protected Node<TData> _parent;

    /// <summary>
    /// The coordinate of this Node.
    /// </summary>
    protected Coordinate _coordinate;

    /// <summary>
    /// The heuristic. The estimated cost of the move from this Node to the goal Node.
    /// </summary>
    protected uint _hCost;

    /// <summary>
    /// The movement cost. The cost to move to this Node from the parent Node.
    /// </summary>
    protected uint _gCost;

    /// <summary>
    /// The total cost. Heuristic + movement cost.
    /// </summary>
    protected uint _tCost;

    #endregion

    #region Operator Overloads

    /// <summary>
    /// Implements the operator ==.
    /// </summary>
    /// <param name="left">The left.</param>
    /// <param name="right">The right.</param>
    /// <returns>The result of the operator.</returns>
    public static bool operator ==(Node<TData> left, Node<TData> right)
    {
      return Object.Equals(left, right);
    }

    /// <summary>
    /// Implements the operator !=.
    /// </summary>
    /// <param name="left">The left.</param>
    /// <param name="right">The right.</param>
    /// <returns>The result of the operator.</returns>
    public static bool operator !=(Node<TData> left, Node<TData> right)
    {
      return !Object.Equals(left, right);
    }

    /// <summary>
    /// Implements the operator &lt;.
    /// </summary>
    /// <param name="left">The left.</param>
    /// <param name="right">The right.</param>
    /// <returns>The result of the operator.</returns>
    public static bool operator <(Node<TData> left, Node<TData> right)
    {
      return left.CompareTo(right) < 0;
    }

    /// <summary>
    /// Implements the operator &lt;=.
    /// </summary>
    /// <param name="left">The left.</param>
    /// <param name="right">The right.</param>
    /// <returns>The result of the operator.</returns>
    public static bool operator <=(Node<TData> left, Node<TData> right)
    {
      return left.CompareTo(right) <= 0;
    }

    /// <summary>
    /// Implements the operator &gt;.
    /// </summary>
    /// <param name="left">The left.</param>
    /// <param name="right">The right.</param>
    /// <returns>The result of the operator.</returns>
    public static bool operator >(Node<TData> left, Node<TData> right)
    {
      return left.CompareTo(right) > 0;
    }

    /// <summary>
    /// Implements the operator &gt;=.
    /// </summary>
    /// <param name="left">The left.</param>
    /// <param name="right">The right.</param>
    /// <returns>The result of the operator.</returns>
    public static bool operator >=(Node<TData> left, Node<TData> right)
    {
      return left.CompareTo(right) >= 0;
    }

    #endregion

    #region Constructors

    /// <summary>
    /// Initializes a new instance of the <see cref="Node&lt;TData&gt;"/> class.
    /// </summary>
    /// <param name="workingAlg">The working alg.</param>
    /// <param name="parentNode">The parent node.</param>
    /// <param name="x">The horizontal position.</param>
    /// <param name="y">The vertical position.</param>
    public Node(SimplePathFinder<TData> workingAlg, Node<TData> parentNode, ushort x, ushort y)
      : this(workingAlg, parentNode, new Coordinate(x, y))
    {

    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Node&lt;TData&gt;"/> class.
    /// </summary>
    /// <param name="workingAlg">The working alg.</param>
    /// <param name="parentNode">The parent node.</param>
    /// <param name="coordinate">The coordinate.</param>
    public Node(SimplePathFinder<TData> workingAlg, Node<TData> parentNode, Coordinate coordinate)
    {
      if (workingAlg == null)
        throw new ArgumentNullException("workingAlg");

      _AStarAlg = workingAlg;
      _parent = parentNode;
      _coordinate = coordinate;

      CalculateCost();
    }

    #endregion

    #region Properties

    /// <summary>
    /// Gets or sets the parent.
    /// </summary>
    /// <value>The parent.</value>
    public virtual Node<TData> Parent
    {
      get { return _parent; }
      set { _parent = value; }
    }

    /// <summary>
    /// Gets the heuristic (The estimated cost from this Node's position to the end Node's position).
    /// </summary>
    /// <value>The heuristic.</value>
    public uint Heuristic
    {
      get { return _hCost; }
    }

    /// <summary>
    /// Gets the movement cost from here to the next Node.
    /// </summary>
    /// <value>The movement cost.</value>
    public uint MovementCost
    {
      get { return _gCost; }
    }

    /// <summary>
    /// Gets the total cost of the movement from here to the next Node (Heuristic + MovementCost).
    /// </summary>
    /// <value>The total cost.</value>
    public ulong TotalCost
    {
      get { return _tCost; }
    }

    /// <summary>
    /// Gets or sets the horizontal position of this Node.
    /// </summary>
    /// <value>The horizontal position.</value>
    public virtual ushort X
    {
      get { return _coordinate.X; }
      set { _coordinate.X = value; CalculateCost(); }
    }

    /// <summary>
    /// Gets or sets the vertical position of this Node.
    /// </summary>
    /// <value>The vertical position.</value>
    public virtual ushort Y
    {
      get { return _coordinate.Y; }
      set { _coordinate.Y = value; CalculateCost(); }
    }

    #endregion

    #region Public Methods


    /// <summary>
    /// Determines whether this Node is ajacent to the specified other.
    /// </summary>
    /// <returns>
    /// 	<c>true</c> if is ajacent to the specified other; otherwise, <c>false</c>.
    /// </returns>
    /// <param name="other">The other Node.</param>
    public virtual bool IsAjacentTo(Node<TData> other)
    {
      if (other._coordinate == this._coordinate) return false;

      for (sbyte iy = -1; iy <= 1; iy++)
        for (sbyte ix = -1; ix <= 1; ix++)
          if (ix != 0 && iy != 0)
            if (other.X == this.X + ix && other.Y == this.Y + iy) 
              return true;

      return false;
    }

    /// <summary>
    /// Determines whether this Node is diagonal to the specified other.
    /// </summary>
    /// <param name="other">The other Node.</param>
    /// <returns>
    /// 	<c>true</c> if is diagonal to the specified other; otherwise, <c>false</c>.
    /// </returns>
    public virtual bool IsDiagonalTo(Node<TData> other)
    {
      return ((other.X == this.X - 1 && other.Y == this.Y - 1) || //upper left
              (other.X == this.X + 1 && other.Y == this.Y - 1) || //upper right
              (other.X == this.X - 1 && other.Y == this.Y + 1) || //lower left
              (other.X == this.X + 1 && other.Y == this.Y + 1));  //lower right
    }

    /// <summary>
    /// Gets the successors of this Node.
    /// </summary>
    /// <returns>The array of successor Nodes</returns>
    public virtual Node<TData>[] GetSuccessors()
    {
      Stack<Node<TData>> successors = new Stack<Node<TData>>();

      Node<TData>[] openList = _AStarAlg.GetOpenListRegestry();
      byte[] resistanceMap = _AStarAlg.GetResistanceMap();

      for (sbyte iy = -1; iy <= 1; iy++)
      {
        for (sbyte ix = -1; ix <= 1; ix++)
        {
          if ((X + ix) < 0                           ||
              (X + ix) >= _AStarAlg.WorkingMap.Width ||
              (Y + iy) < 0                           ||
              (Y + iy) >= _AStarAlg.WorkingMap.Height) { continue; }

          uint index = TileMap<TData>.IndexOf((ushort)(X + ix), (ushort)(Y + iy), _AStarAlg.WorkingMap.Width);

          if (openList[index] != null || resistanceMap[index] == 255) continue;

          Node<TData> n = new Node<TData>(_AStarAlg, this, (ushort)(X + ix), (ushort)(Y + iy));

          if (_AStarAlg.AllowDiagonals == false && n.IsDiagonalTo(this)) continue;

          if (n != _parent && n != this)
            successors.Push(n);
        }
      }

      return successors.ToArray();
    }

    /// <summary>
    /// Gets the coordinate of this Node.
    /// </summary>
    /// <returns></returns>
    public Coordinate GetCoordinate()
    {
      return _coordinate;
    }

    #region Object Overrides

    /// <summary>
    /// Determines whether the specified <see cref="System.Object"/> is equal to this instance.
    /// </summary>
    /// <param name="obj">The <see cref="System.Object"/> to compare with this instance.</param>
    /// <returns>
    /// 	<c>true</c> if the specified <see cref="System.Object"/> is equal to this instance; otherwise, <c>false</c>.
    /// </returns>
    /// <exception cref="T:System.NullReferenceException">
    /// The <paramref name="obj"/> parameter is null.
    /// </exception>
    public override bool Equals(object obj)
    {
      return !ReferenceEquals(null, obj) &&
             (ReferenceEquals(this, obj) || obj.GetType() == typeof(Node<TData>) && Equals((Node<TData>)obj));
    }

    /// <summary>
    /// Returns a hash code for this instance.
    /// </summary>
    /// <returns>
    /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table. 
    /// </returns>
    public override int GetHashCode()
    {
        return _coordinate.GetHashCode();
    }

    /// <summary>
    /// Returns a <see cref="System.String"/> that represents this instance.
    /// </summary>
    /// <returns>
    /// A <see cref="System.String"/> that represents this instance.
    /// </returns>
    public override string ToString()
    {
      return String.Format("{0} : {1}", _coordinate.ToString(), TotalCost.ToString());
    }

    #endregion

    #region IEquatable<Node<TData>> Members

    /// <summary>
    /// Test for equality of coordinates.
    /// </summary>
    /// <param name="other">The other Node to compare to.</param>
    /// <returns></returns>
    public bool Equals(Node<TData> other)
    {
        return !ReferenceEquals(null, other) &&
               (ReferenceEquals(this, other) ||
                _coordinate == other._coordinate);
    }

    #region IComparable<Node<TData>> Members

    /// <summary>
    /// Compares the total cost of this and the other.
    /// </summary>
    /// <param name="other">The other Node.</param>
    /// <returns>-1 of less than, 0 if equal, 1 if greater than.</returns>
    public int CompareTo(Node<TData> other)
    {
        return (int)(this.TotalCost - other.TotalCost);
    }

    #endregion

    #endregion

    #endregion

    #region Protected Methods

    /// <summary>
    /// Calculates the cost of moving to this Node in relation to its parent.
    /// </summary>
    protected virtual void CalculateCost()
    {
      if (_parent == null) return;

      byte[] resistanceMap = _AStarAlg.GetResistanceMap();

      if (IsDiagonalTo(_parent))
        _gCost = 14;
      else
        _gCost = 10;

      _gCost = _parent._gCost + _gCost + resistanceMap[TileMap<TData>.IndexOf(this.GetCoordinate(), _AStarAlg.WorkingMap.Width)];
      _hCost = (_AStarAlg.End != null) ? (uint)((Math.Abs(_AStarAlg.End.X - this.X) + Math.Abs(_AStarAlg.End.Y - this.Y)) * 10) : 0;
      _tCost = _gCost + _hCost;
    } 
    
    #endregion
  }
}