Node Algorithm
The Node Stack Algorithm is a tree traversal technique that is widely used in computer science and programming for efficiently navigating through the structure of a tree, which is a popular data structure. Trees are hierarchical data structures consisting of nodes connected by edges, with each node having a single parent (except the root node) and zero or more children nodes. Tree traversal refers to the process of visiting each node of a tree and performing a specific operation or action on them. The Node Stack Algorithm is one of the well-known methods for performing the Depth-First Search (DFS) traversal, which explores the depth of each branch of the tree before backtracking.
The core idea behind the Node Stack Algorithm is to use a stack data structure to keep track of the nodes to be visited during the traversal process. The stack follows a Last-In-First-Out (LIFO) approach, meaning that the last node added to the stack is the first one to be processed and removed from the stack. The algorithm begins by pushing the root node of the tree onto the stack. Then, it enters a loop where it pops the top node from the stack, processes or visits it, and then pushes its children nodes onto the stack. This process is repeated until the stack becomes empty, which indicates that all the nodes in the tree have been visited. Since the algorithm explores the children of a node before backtracking to its parent node, it effectively implements a depth-first traversal approach. This algorithm is highly efficient and can be easily implemented in various programming languages, making it a popular choice for tree traversal problems in computer science.
using System;
namespace AStar
{
/// <summary>
/// A Node(former Location)
/// Contains Positional and other information about a single node.
/// </summary>
public class Node : IComparable<Node>, IEquatable<Node>
{
// Constructors
/// <summary>
/// Initializes a new instance of the <see cref="Node"/> class.
/// </summary>
/// <param name="position">Position of the node.</param>
/// <param name="traversable">Flag if the node is traversable.</param>
/// <param name="traverseMultiplier">Multiplier for traversal costs.</param>
public Node(VecN position, bool traversable, double traverseMultiplier)
{
Traversable = traversable;
Position = position;
TraversalCostMultiplier = traverseMultiplier;
}
// Properties
/// <summary>
/// Gets the Total cost of the Node.
/// The Current Costs + the estimated costs.
/// </summary>
public double TotalCost => EstimatedCost + CurrentCost;
/// <summary>
/// Gets or sets the Distance between this node and the target node.
/// </summary>
public double EstimatedCost { get; set; }
/// <summary>
/// Gets a value indicating whether how costly it is to traverse over this node.
/// </summary>
public double TraversalCostMultiplier { get; }
/// <summary>
/// Gets or sets a value indicating whether to go from the start node to this node.
/// </summary>
public double CurrentCost { get; set; }
/// <summary>
/// Gets or sets the state of the Node
/// Can be Unconsidered(Default), Open and Closed.
/// </summary>
public NodeState State { get; set; }
/// <summary>
/// Gets a value indicating whether the node is traversable.
/// </summary>
public bool Traversable { get; }
/// <summary>
/// Gets or sets a list of all connected nodes.
/// </summary>
public Node[] ConnectedNodes { get; set; } = new Node[0];
/// <summary>
/// Gets or sets he "previous" node that was processed before this node.
/// </summary>
public Node? Parent { get; set; }
/// <summary>
/// Gets the positional information of the node.
/// </summary>
public VecN Position { get; }
/// <summary>
/// TODO.
/// </summary>
/// <param name="left">TODO 2.</param>
/// <param name="right">TODO 3.</param>
/// <returns>TODO 4.</returns>
public static bool operator ==(Node left, Node right) => left?.Equals(right) != false;
/// <summary>
/// TODO.
/// </summary>
/// <param name="left">TODO 2.</param>
/// <param name="right">TODO 3.</param>
/// <returns>TODO 4.</returns>
public static bool operator >(Node left, Node right) => left.CompareTo(right) > 0;
/// <summary>
/// TODO.
/// </summary>
/// <param name="left">TODO 2.</param>
/// <param name="right">TODO 3.</param>
/// <returns>TODO 4.</returns>
public static bool operator <(Node left, Node right) => left.CompareTo(right) < 0;
/// <summary>
/// TODO.
/// </summary>
/// <param name="left">TODO 2.</param>
/// <param name="right">TODO 3.</param>
/// <returns>TODO 4.</returns>
public static bool operator !=(Node left, Node right) => !(left == right);
/// <summary>
/// TODO.
/// </summary>
/// <param name="left">TODO 2.</param>
/// <param name="right">TODO 3.</param>
/// <returns>TODO 4.</returns>
public static bool operator <=(Node left, Node right) => left.CompareTo(right) <= 0;
/// <summary>
/// TODO.
/// </summary>
/// <param name="left">TODO 2.</param>
/// <param name="right">TODO 3.</param>
/// <returns>TODO 4.</returns>
public static bool operator >=(Node left, Node right) => left.CompareTo(right) >= 0;
/// <summary>
/// Compares the Nodes based on their total costs.
/// Total Costs: A* Pathfinding.
/// Current: Djikstra Pathfinding.
/// Estimated: Greedy Pathfinding.
/// </summary>
/// <param name="other">The other node.</param>
/// <returns>A comparison between the costs.</returns>
public int CompareTo(Node other) => TotalCost.CompareTo(other.TotalCost);
/// <summary>
/// Equals Override.
/// </summary>
/// <param name="obj">The object to be checked against.</param>
/// <returns>True if Equal, False if Not Equal.</returns>
public override bool Equals(object obj) => (obj is Node other) && Equals(other);
/// <summary>
/// Useless override to shut up the automated testing.
/// </summary>
/// <returns>the default hash value.</returns>
public override int GetHashCode() => base.GetHashCode();
/// <summary>
/// Override for IEquatable.
/// </summary>
/// <param name="other">The object to be checked against.</param>
/// <returns>True if Equal, False if not Equal.</returns>
public bool Equals(Node other) => CompareTo(other) == 0;
/// <summary>
/// Returns the distance to the other node.
/// </summary>
/// <param name="other">The other node.</param>
/// <returns>Distance between this and other.</returns>
public double DistanceTo(Node other)
{
// Since we are only using the distance in comparison with other distances, we can skip using Math.Sqrt
return Position.SqrDistance(other.Position);
}
}
}
