Skip to content

8-Puzzle Problem Using A* in C# and Unity

8-Puzzle Problem Using A* in C# and Unity

Page 4 – Implementing the A* Path Finder

This tutorial is divided into 5 pages.

  • Page 1: The first page of the tutorial introduces the 8-Puzzle game and its integration with A* pathfinding in Unity. It covers the problem’s history, its complexity, and heuristic search methods like A*. It also explains the puzzle’s state representation and neighbor construction for pathfinding, providing foundational knowledge for implementing and solving the 8-Puzzle.
  • Page 2: The second of the tutorial guides you through creating a new Unity 3D project named “8-Puzzle”. It details setting up the main camera, importing assets, and configuring a tile prefab. You create a puzzle board frame using cubes with wood textures and set up a basic UI with four buttons and two text fields for randomization, image cycling, resetting, and solving the puzzle using A*.
  • Page 3: The third covers the implementation of the PuzzleState class for the 8-puzzle game in C#. This class represents a unique puzzle state with an array of tile indices and includes constructors, equality checks, a hash code generator, and methods for finding the empty tile, swapping tiles, and calculating Manhattan cost. Additionally, it details creating neighbor indices for grid cells and generating neighboring puzzle states by moving the empty tile.
  • Page 4: In the fourth page, we implement the Path Finder using the three commonly used path finding algorithms, viz., the Dijkstra, the A* and the Gree-best-first search algorithms.
  • Page 5: In the fifth page, we apply the A* Path Finder to solve our 8-Puzzle game. We also create the necessary functionality to interactively play the game using the basic UI created in Page 2.

Contact me


Find the GitHub repository of this tutorial at https://github.com/shamim-akhtar/gamdev-unity/tree/8-puzzle.


View the tutorial on YouTube.


Implementing the Path Finder

Right-click on the project window and create a new folder named Scripts. Now, right-click and create a new C# file in the Scripts folder. Name it, PathFinder. Double-click PathFinder and open the file in Visual Studio or your favourite editor. 

Remove MonoBehavior, then remove the Start and Update methods. We want our class to be plain C# class and not derived from MonoBehavior.

The Path Finder Status

We start by adding an enumerator type called PathFinderStatus. This enum defines the different states that the pathfinder can be in during its operation. 

The first state is NOT_INITIALISED. This status indicates that the pathfinder has not been initialised yet. Initialisation typically involves setting up the start and goal nodes for the pathfinding operation and preparing any necessary data structures. When the Pathfinder is in this state, it’s not ready to start searching for a path.

The next state is SUCCESS. This state indicates that the Pathfinder has successfully found a path from the start node to the goal node. It means that the pathfinding algorithm has completed its task and identified a valid path that meets the specified criteria.

We then add the state FAILURE. This state indicates that the pathfinder has been unable to find a valid path from the start node to the goal node. It could occur due to various reasons, such as an unreachable destination, blocked paths, or limitations of the pathfinding algorithm. 

Finally, we add the state RUNNING. This state indicates that the Pathfinder is currently searching for a path. 

The Node Class

We then define an abstract class called Node. Making it abstract means we can’t create instances of Node directly. Instead, it serves as a blueprint for other classes. Also, it uses a generic type T, which means it can work with any type of data, making it really flexible. We can create nodes to hold different kinds of information.

// The Node class.
// It is an abstract class that provides the base class
// for any type of vertex that you want to implement in
// your pathfinding problem.
abstract public class Node<T>

Then, we have a property called Value. This property is where we store the actual data that the node represents. The “get” allows us to read the value. The “set” is marked as private, meaning we can only set the value within this class itself, not from outside.

{
  // We store a reference to the T as Value.
  public T Value { get; private set; }

We then define the constructor for our Node class. It takes a parameter value of type T, which we then use to set it to the Value property.

  // The constructor for the Node class.
  public Node(T value)
  {
    Value = value;
  }

And finally, we have a method called GetNeighbours. It is marked as abstract, which means any class that inherits from Node will have to implement this method. This method is responsible for finding all the neighbouring nodes connected to this node. But because it’s abstract, we don’t provide an implementation here. Instead, each subclass of Node will define its logic for finding neighbours. Depending on how we represent map data, either as a grid or as a graph, we will have a specific implementation of this method.

  // Get the neighbours for this node.
  // This is the most important function that
  // your concrete vertex class should implement.
  abstract public List<Node<T>> GetNeighbours();

The Path Finder Class

We now create a class named PathFinder. It is marked as abstract, just like the Node class we saw earlier. That means we can’t directly create an instance of PathFinder. Instead, it’s meant to be used as a blueprint for other classes that will perform pathfinding algorithms.

abstract public class PathFinder<T>

We use a region to organise our code visually. Think of them as section dividers. 

#region Delegates for cost calculation

First, we define some delegates. Delegates are like function pointers in C++. They’re used here to define the signature for calculating costs between nodes. We have two types of costs: HeuristicCost, which estimates the cost from a node to the goal, and NodeTraversalCost, which calculates the cost between two neighbouring nodes.

public delegate float CostFunction(T a, T b);
public CostFunction HeuristicCost { get; set; }
public CostFunction NodeTraversalCost { get; set; }

After that, we end the region.

#endregion

The Path Finder Node Class

We then start with another region and define a nested class called PathFinderNode. Nested classes are classes defined within another class. We have implemented this class as a nested class here as it will mostly be used by our PathFinder class.

public class PathFinderNode : System.IComparable<PathFinderNode>

The class implements the IComparable interface, which means instances of this class can be compared to each other.

This class is crucial because it represents nodes within the search tree generated by the pathfinding algorithm. Unlike the Node class we saw earlier, which was abstract and served as a template for various types of nodes, this class encapsulates a specific node in the search process. 

Inside the class, we define various properties and methods that will help us manage these nodes during the search process. 

// The parent of this node.
public PathFinderNode Parent { get; set; }

We start with the property named Parent. This property represents the parent node of the current node in the search tree. In other words, it points to the node from which the current node was reached.

// The Node that this PathFinderNode is pointing to.
public Node<T> Location { get; private set; }

We then add a property called Location, which represents the actual Node that this PathFinderNode is associated with. It stores the reference to the Node in the graph.

// The various costs.
public float Fcost { get; private set; }
public float GCost { get; private set; }
public float Hcost { get; private set; }

We then add a few new properties that represent different costs associated with the node. GCost is the cost from the start node to this node, Hcost is the heuristic cost from this node to the destination node, and Fcost is the total cost of reaching this node, which is the sum of GCost and HCost.

// The constructor.
// It takes in the Node, the parent, the gcost, and the hcost.
public PathFinderNode(Node<T> location,
    PathFinderNode parent,
    float gCost,
    float hCost)
{
  Location = location;
  Parent = parent;
  Hcost = hCost;
  SetGCost(gCost);
}

After that, we add a constructor for this class. This constructor initialises a PathFinderNode with the given Node as its location, the provided parent node, and the specified GCost and HCost. It then calls the SetGCost method to set the GCost and update the Fcost accordingly.

// Set the gcost.
public void SetGCost(float c)
{
  GCost = c;
  Fcost = GCost + Hcost;
}

Then, we implement the SetGCost method. This method updates the node’s GCost and recalculates the FCost based on the new GCost and the existing HCost.

public int CompareTo(PathFinderNode other)
{
  if (other == null) return 1;
  return Fcost.CompareTo(other.Fcost);
}

We will now implement the IComparable interface. This method allows instances of PathFinderNode to be compared based on their Fcost. It returns a negative value if the current node’s Fcost is less than the other node’s Fcost, zero if they are equal, and a positive value if it’s greater.

We finish off by calling the endregion. 

#endregion

And that wraps up the PathFinderNode class!

Some More Properties

We will now continue with the PathFinder class by defining another region called Properties. Remember that putting sections of code between a region is just a way to organise our code visually, making it easier to understand and navigate.

#region Properties

Then, we will define a property called Status. This property represents the current status of the Pathfinder. It can have values like NOT_INITIALISED, RUNNING, SUCCESS, or FAILURE. By default, it’s set to NOT_INITIALISED. The get accessor allows us to read the value of Status, while the private set accessor means that only methods within this class can change the value of Status.

// Add a property that holds the current status of the
// pathfinder. By default, it is set to NOT_INITIALISED.
// Also note that we have made the set to private to
// ensure that only this class can change and set
// the status.
public PathFinderStatus Status
{
  get;
  private set;
} = PathFinderStatus.NOT_INITIALISED;

After that, we define properties for the start and goal nodes of the pathfinder. These properties allow us to access the start and goal nodes from outside the class, but they can only be set internally (hence the private set modifier). This encapsulation ensures that only the PathFinder class can modify these nodes.

// Add properties for the start and goal nodes.
public Node<T> Start { get; private set; }
public Node<T> Goal { get; private set; }

Lastly, we add another property called CurrentNode, which represents the current node that the pathfinder is exploring. This property allows external classes to access the current node, but it can only be set internally by the PathFinder class.

// The property to access the CurrentNode that the
// pathfinder is now at.
public PathFinderNode CurrentNode { get; private set; }

We end this section of code by adding the endregion.

#endregion

The Open and Closed List 

We start once again with a region to organise our code.

#region Open and Closed lists and associated functions

To manage the open and closed lists in the pathfinding algorithm, we will define two lists: openList and closedList. openList will keep track of nodes that have been discovered but not yet explored, while closedList will store nodes that have already been explored. 

// The open list for the pathfinder.
protected List<PathFinderNode> openList = new List<PathFinderNode>();

// The closed list
protected List<PathFinderNode> closedList = new List<PathFinderNode>();

We will then create a helper method called GetLeastCostNode. This method will take a list of PathFinderNode instances as input and return the node with the lowest FCost. It will iterate through the list, comparing the FCost of each node and keeping track of the index of the node with the lowest cost.

// A helper method to find the least cost node from a list
protected PathFinderNode GetLeastCostNode(List<PathFinderNode> myList)
{
  // Implementation of the helper method…
}

We will also define another helper method called Is In List. This method will check if a specific value of type T is present in the list of PathFinderNode instances. It will iterate through the list and compare the value of each node’s location with the given value cell. If a match is found, it will return the index of the item in the list; otherwise, it will return -1.

// A helper method to check if a value of T is in a list.
// If it is then return the index of the item where the
// value is. Otherwise return -1.
protected int IsInList(List<PathFinderNode> myList, T cell)
{
  // Implementation of the helper method…
}

Finally, we’ll end the region. 

#endregion

Delegates for Action Callbacks

We will now define another region titled “Delegates for action callbacks”, where we will declare delegates to handle changes to internal values. The game will utilise these delegates to represent alterations to the cells and lists visually. These delegates will facilitate triggering specific actions or behaviours in response to various events during the pathfinding process, allowing for visual representation and interaction within the game environment.

#region Delegates for action callbacks

We start by declaring a delegate type DelegatePathFinderNode, intended to handle methods that take a PathFinderNode as a parameter.

public delegate void DelegatePathFinderNode(PathFinderNode node);

Following this, we declare instances of the DelegatePathFinderNode delegate type called the onChangeCurrentNode, onAddToOpenList, onAddToClosedList, and onDestinationFound. 

These delegates will be assigned methods that take a PathFinderNode as a parameter and will be invoked when certain events occur, such as changes to the current node, addition of a node to the open list, addition of a node to the closed list, and discovery of the destination node.

public DelegatePathFinderNode onChangeCurrentNode;
public DelegatePathFinderNode onAddToOpenList;
public DelegatePathFinderNode onAddToClosedList;
public DelegatePathFinderNode onDestinationFound;

Next, we define another delegate type DelegateNoArgument, which will handle methods with no parameters.

public delegate void DelegateNoArgument();

We proceed by creating instances of the DelegateNoArgument delegate type called onStarted, onRunning, onFailure, and onSuccess. 

These delegates will be assigned methods with no parameters. They will be invoked when certain events occur, such as the start of the pathfinding algorithm, when the algorithm is running, when the algorithm fails to find a path, and when the algorithm successfully finds a path.

public DelegateNoArgument onStarted;
public DelegateNoArgument onRunning;
public DelegateNoArgument onFailure;
public DelegateNoArgument onSuccess;

Finally, we end the region. 

#endregion

The Reset Method

Next, we will define a method called Reset, which will reset the internal variables for a new search.

// Reset the internal variables for a new search.
protected void Reset()
{

Within the method, we will first check if the status of the pathfinder is set to RUNNING. If it is, we will not perform the reset and simply return from the method.

  if (Status == PathFinderStatus.RUNNING)
  {
    // Cannot reset path finder.     // Pathfinding is in progress.
    return;
  }

Next, if the pathfinder is not currently running, we will set the CurrentNode to null, clear both the open and closed lists (openList and closedList), and reset the status of the pathfinder to NOT INITIALISED.

  CurrentNode = null;

  openList.Clear();
  closedList.Clear();

  Status = PathFinderStatus.NOT_INITIALISED;

This Reset method will ensure that the pathfinder is ready for a new search by clearing all previous data and resetting its status. It’s an essential step before starting a new pathfinding operation.

}

The Search Step

We will now define a method named Step, which will handle the progression of the pathfinding algorithm until it either succeeds or fails.

// Step until success or failure
// Take a search step. The user must continue to call this method
// until the Status is either SUCCESS or FAILURE.
public PathFinderStatus Step()
{

Within this method, we’ll begin by adding the current node to the closed list.

  // Add the current node to the closed list.
  closedList.Add(CurrentNode);

  // Call the delegate to inform any subscribers.
  onAddToClosedList?.Invoke(CurrentNode);

Next, we’ll check if the open list is empty. If it is, we’ll set the status to FAILURE, invoke the onFailure delegate if it’s not null, and return the status.

if (openList.Count == 0)
{
  // we have exhausted our search. No solution is found.
  Status = PathFinderStatus.FAILURE;
  onFailure?.Invoke();
  return Status;
}

Then, we’ll get the least costly element from the open list and make it the new current node.

CurrentNode = GetLeastCostNode(openList);

// Call the delegate to inform any subscribers.
onChangeCurrentNode?.Invoke(CurrentNode);

After that, we’ll remove the current node from the open list.

openList.Remove(CurrentNode);

Now, we’ll check if the current node contains the goal cell. If it does, we’ll set the status to SUCCESS, invoke the onDestinationFound delegate if it’s not null, invoke the onSuccess delegate, and return the status.

if (EqualityComparer<T>.Default.Equals(
    CurrentNode.Location.Value, Goal.Value))
{
  Status = PathFinderStatus.SUCCESS;
  onDestinationFound?.Invoke(CurrentNode);
  onSuccess?.Invoke();
  return Status;
}

Following that, we’ll find the neighbours of the current node and traverse each of these neighbours for possible expansion.

// Find the neighbours.
List<Node<T>> neighbours = CurrentNode.Location.GetNeighbours();

// Traverse each of these neighbours for possible expansion.
foreach (Node<T> cell in neighbours)
{
  AlgorithmSpecificImplementation(cell);
}

Within each iteration of the loop, the method Algorithm Specific Implementation is called with the current neighbour node cell as an input parameter. This method is abstract and must be implemented by subclasses of the pathfinder. It’s meant to handle specific implementation details or operations related to the pathfinding algorithm, such as evaluating the cost of moving to the neighbour or updating the path based on the neighbour’s properties.

Lastly, we’ll set the status to RUNNING, invoke the onRunning delegate if it’s not null, and return the status.

Status = PathFinderStatus.RUNNING;
onRunning?.Invoke();
return Status;

Finally, we define the abstract method Algorithm Specific Implementation that is not directly implemented here. This method is expected to be implemented by subclasses and will handle specific implementations required by the pathfinding algorithm.

abstract protected void AlgorithmSpecificImplementation(Node<T> cell);

Initialising Path Finding

We will now define a method called Initialise, which will initialise a new search in the pathfinding algorithm. 

public bool Initialise(Node<T> start, Node<T> goal)
{

First, we’ll check if the status of the pathfinder is set to RUNNING. If it is, we’ll return false because pathfinding is already in progress.

if (Status == PathFinderStatus.RUNNING)
{
  // Path finding is already in progress.
  return false;
}

Next, we’ll reset the variables to prepare for the new search operation.

// Reset the variables.
Reset();

Then, we’ll set the start and goal nodes for this search.

Start = start;
Goal = goal;

After that, we’ll calculate the heuristic cost for the start node using the provided heuristic function HeuristicCost.

// Calculate the H cost for the start.
float H = HeuristicCost(Start.Value, Goal.Value);

Now, we’ll create a root node with its parent as null and initialise its GCost to 0 and HCost to the calculated heuristic cost.

// Create a root node with its parent as null.
PathFinderNode root = new PathFinderNode(Start, null, 0f, H);

Subsequently, we will add this root node to the open list.

openList.Add(root);

And then we will set the current node to the root node.

//Set the current node to the root node.
CurrentNode = root;

Then, we’ll invoke delegates to inform the caller if they are not null. This includes the onChangeCurrentNode delegate to notify of the change in the current node, and the onStarted delegate to signify the start of the pathfinding operation.

// Invoke the delegates to inform the caller if the delegates are not null.
onChangeCurrentNode?.Invoke(CurrentNode);
onStarted?.Invoke();

Finally, we’ll set the status of the pathfinder to RUNNING and return true to indicate successful initialisation of the search operation.

// Set the status of the Pathfinder to RUNNING.
Status = PathFinderStatus.RUNNING;

return true;

We then bound these three methods within a region for better code organisation and clarity.

We have now implemented the basic structure of the PathFinder. However, it is not yet able to do the path findings as we have not implemented any algorithm-specific implementation. We shall now proceed to implement the three well-known types of algorithms for pathfinding. 

The Dijkstra’s Algorithm

We will start with the first algorithm, known as the Dijkstra’s algorithm. Dijkstra’s algorithm explores paths uniformly, considering all neighbouring nodes without any heuristic guidance towards the goal. It guarantees finding the shortest path. But it can be computationally expensive, especially in large graphs.

Since Dijkstra’s algorithm does not use any heuristic function and relies solely on the accumulated cost from the start node to each node being considered, the Hcost is always 0.

We start by defining a subclass of PathFinder called DijkstraPathFinder, which implements Dijkstra’s algorithm for pathfinding.

public class DijkstraPathFinder<T> : PathFinder<T>

Within the Dijkstra PathFinder class, we will implement the abstract method Algorithm Specific Implementation. It is an override of a method in the superclass. This method is responsible for implementing the specific logic of Dijkstra’s algorithm for each cell.

protected override void AlgorithmSpecificImplementation(Node<T> cell)

In this method, we check if the current cell is not in the closed list, meaning it has not been visited yet.

if (IsInList(closedList, cell.Value) == -1)

Next, we calculate the tentative cost, Gcost, to reach the current cell from the starting node. Since this is Dijkstra’s algorithm, we don’t consider the heuristic cost (or the Hcost).

float G = CurrentNode.GCost + NodeTraversalCost(CurrentNode.Location.Value, cell.Value);
float H = 0.0f; // Dijkstra doesn’t include the Heuristic cost

Then, we check if the cell is already in the open list. If not, we add it to the open list with the calculated costs.

int idOList = IsInList(openList, cell.Value);
if (idOList == -1)
{
    // The cell does not exist in the open list.
    // We will add the cell to the open list.

    PathFinderNode n = new PathFinderNode(cell, CurrentNode, G, H);
    openList.Add(n);
    onAddToOpenList?.Invoke(n);
}

If the cell is already in the open list, we check if the newly calculated cost is less than the existing cost for that cell in the open list. If it is, we update the cost and parent of the cell in the open list.

else
{
    float oldG = openList[idOList].GCost;
    if (G < oldG)
    {
        // change the parent and update the cost to the new G
        openList[idOList].Parent = CurrentNode;
        openList[idOList].SetGCost(G);
        onAddToOpenList?.Invoke(openList[idOList]);
    }
}

This process ensures that Dijkstra’s algorithm explores nodes based on their distance from the start node, updating costs as it discovers shorter paths.

The A* Algorithm

Next, we will implement the “A-star” algorithm. The “A-star” algorithm uses a heuristic function to guide the search towards the goal, prioritising paths that are more likely to lead to the goal. It combines the cost to reach a node from the start (which is the GCost) and an estimated cost to reach the goal from that node (which is the HCost). “A-star” is generally more efficient than Dijkstra’s algorithm because it tends to explore fewer nodes while still guaranteeing an optimal solution if an admissible heuristic is used.

The “A-star” algorithm’s performance heavily depends on the quality of the heuristic function. In the worst case, “A-star” may behave similarly to Dijkstra’s algorithm, but with a good heuristic, “A-star” can significantly reduce the search space and achieve better performance.

We continue by defining a subclass of PathFinder called A-StarPathFinder which implements the “A-star” algorithm for pathfinding.

// The AstarPathFinder.
public class AStarPathFinder<T> : PathFinder<T>

Within the A-StarPathFinder class, we implement the Algorithm Specific Implementation function, which is an override of a method in the superclass. This method is responsible for implementing the specific logic of the “A-star” algorithm for each cell.

protected override void AlgorithmSpecificImplementation(Node<T> cell)

In this method, we first check if the current cell is not in the closed list, meaning it has not been visited yet.

if (IsInList(closedList, cell.Value) == -1)

Next, we calculate the cost (G) to reach the current cell from the start node. This is the cost of the path from the start node to the current cell.

float G = CurrentNode.GCost + NodeTraversalCost(CurrentNode.Location.Value, cell.Value);

We also calculate the heuristic cost (Hcost) from the current cell to the goal node.

float H = HeuristicCost(cell.Value, Goal.Value);

Then, we check if the cell is already in the open list. If not, we add it to the open list with the calculated costs.

int idOList = IsInList(openList, cell.Value);
if (idOList == -1)
{
    // The cell does not exist in the open list.
    // We will add the cell to the open list.

    PathFinderNode n = new PathFinderNode(cell, CurrentNode, G, H);
    openList.Add(n);
    onAddToOpenList?.Invoke(n);
}

If the cell is already in the open list, we check if the newly calculated cost (the GCost) is less than the existing cost for that cell in the open list. If it is, we update the cost and the parent of the cell in the open list.

else
{
    float oldG = openList[idOList].GCost;
    if (G < oldG)
    {
        // change the parent and update the cost to the new G
        openList[idOList].Parent = CurrentNode;
        openList[idOList].SetGCost(G);
        onAddToOpenList?.Invoke(openList[idOList]);
    }
}

This process ensures that the “A-star” algorithm explores nodes based on their combined cost (which is G + H), where G is the actual cost from the start node, and H is the heuristic estimate of the cost to the goal node.

The Greedy Best-first Search

Next, we will implement our final algorithm for pathfinding, called the greedy best-first search algorithm. GreedyBestFirstSearch is an uninformed search algorithm that explores a graph by prioritising nodes based on their heuristic value. It selects the node that appears to be closest to the goal according to a heuristic function without considering the actual cost of reaching that node from the start.

In contrast to the Dijkstra algorithm, the greedy best-first search algorithm does not use the cost to reach a node from the start. Instead, it purely relies on the heuristic cost to the goal node.

Greedy Best First Search is fast and can quickly find a solution if the heuristic function is well-designed. However, it does not guarantee optimality, meaning it may not always find the shortest path to the goal. Due to its greedy nature, it can get stuck in local optima or loops, especially if the heuristic function overestimates the actual cost to reach the goal. Therefore, while Greedy Best First Search is efficient, it may not always produce the most optimal solution.

Similar to other algorithm implementations, we will start by defining a subclass of PathFinder called GreedyPathFinder, which implements the Greedy Best First Search algorithm for pathfinding.

public class GreedyPathFinder<T> : PathFinder<T>

Within the GreedyPathFinder class, we implement the AlgorithmSpecificImplementation, which is an override of a method in the superclass. This method is responsible for implementing the specific logic of the Greedy Best First Search algorithm for each cell.

protected override void AlgorithmSpecificImplementation(Node<T> cell)

In this method, we first check if the current cell is not in the closed list, meaning it has not been visited yet.

if (IsInList(closedList, cell.Value) == -1)

Next, we calculate the heuristic cost (or HCost) from the current cell to the goal node. Greedy Best First Search doesn’t consider the actual cost (or GCost) from the start node.

float G = 0.0f; // Greedy best-first doesn’t include the G cost
float H = HeuristicCost(cell.Value, Goal.Value);

Then, we check if the cell is already in the open list. If not, we add it to the open list with the calculated heuristic cost (or HCost).

int idOList = IsInList(openList, cell.Value);
if (idOList == -1)
{
    // The cell does not exist in the open list.
    // We will add the cell to the open list.

    PathFinderNode n = new PathFinderNode(cell, CurrentNode, G, H);
    openList.Add(n);
    onAddToOpenList?.Invoke(n);
}

If the cell is already in the open list, we check if the newly calculated heuristic cost is less than the existing cost for that cell in the open list. If it is, we update the cost and parent of the cell in the open list.

else
{
    float oldG = openList[idOList].GCost;
    if (G < oldG)
    {
        // change the parent and update the cost to the new G
        openList[idOList].Parent = CurrentNode;
        openList[idOList].SetGCost(G);
        onAddToOpenList?.Invoke(openList[idOList]);
    }
}

This process ensures that the Greedy Best First Search algorithm explores nodes based solely on their heuristic values without considering the actual cost from the start node.

We have completed implementing the PathFinder. We shall now apply the AStarPathFinder to solve our 8-Puzzle.

In the next page we will apply our A* path finder and solve the 8-Puzzle game.

Pages: 1 2 3 4 5

2 thoughts on “8-Puzzle Problem Using A* in C# and Unity”

    1. Hi Bladin,

      The codes are all there. You should be able to see in the PuzzleMap section. Below extracted from the post.
      public List> GetNeighbours(PuzzleNode loc)
      {
      List> neighbours = new List>();
      int zero = loc.Value.GetEmptyTileIndex();
      List intArray = GetNeighbors(zero);
      for (int i = 0; i < intArray.Count; ++i) { PuzzleNode state = new PuzzleNode(this, new PuzzleState(loc.Value)); state.Value.SwapWithEmpty(intArray[i]); neighbours.Add(state); } return neighbours; }

Leave a Reply

Your email address will not be published. Required fields are marked *