In this project, you will implement basic navigation for a game character using pathfinding algorithms. This will involve creating a grid-based map, implementing the A* algorithm, and enabling the character to navigate from a start point to a goal point while avoiding obstacles.

• Understand the basics of grid-based navigation.
• Implement the A* pathfinding algorithm.
• Enable a game character to navigate a map with obstacles.

Before starting this project, ensure you have completed the following modules:

• Pathfinding Algorithms
• A* Implementation
• Navigation with NavMesh

1. Create a New Project: Open your preferred game development environment (e.g., Unity, Unreal Engine) and create a new project.
2. Create a Grid-Based Map: Design a simple grid-based map where each cell can be either walkable or an obstacle.

1. Define the Grid: Create a class to represent the grid. Each cell in the grid should have properties such as isWalkable, gCost, hCost, and parent.

   public class Node
   {
       public bool isWalkable;
       public Vector2 position;
       public int gCost;
       public int hCost;
       public Node parent;
   
       public int fCost => gCost + hCost;
   }
   

2. Initialize the Grid: Initialize the grid with walkable and non-walkable cells.

   public class Grid
   {
       private Node[,] nodes;
       private int width;
       private int height;
   
       public Grid(int width, int height)
       {
           this.width = width;
           this.height = height;
           nodes = new Node[width, height];
           InitializeGrid();
       }
   
       private void InitializeGrid()
       {
           for (int x = 0; x < width; x++)
           {
               for (int y = 0; y < height; y++)
               {
                   nodes[x, y] = new Node
                   {
                       isWalkable = true,
                       position = new Vector2(x, y)
                   };
               }
           }
       }
   }
   

3. Implement the A Algorithm*: Implement the A* algorithm to find the shortest path from the start node to the goal node.

   public List<Node> FindPath(Node startNode, Node goalNode)
   {
       List<Node> openList = new List<Node>();
       HashSet<Node> closedList = new HashSet<Node>();
   
       openList.Add(startNode);
   
       while (openList.Count > 0)
       {
           Node currentNode = openList[0];
           for (int i = 1; i < openList.Count; i++)
           {
               if (openList[i].fCost < currentNode.fCost || openList[i].fCost == currentNode.fCost && openList[i].hCost < currentNode.hCost)
               {
                   currentNode = openList[i];
               }
           }
   
           openList.Remove(currentNode);
           closedList.Add(currentNode);
   
           if (currentNode == goalNode)
           {
               return RetracePath(startNode, goalNode);
           }
   
           foreach (Node neighbor in GetNeighbors(currentNode))
           {
               if (!neighbor.isWalkable || closedList.Contains(neighbor))
               {
                   continue;
               }
   
               int newMovementCostToNeighbor = currentNode.gCost + GetDistance(currentNode, neighbor);
               if (newMovementCostToNeighbor < neighbor.gCost || !openList.Contains(neighbor))
               {
                   neighbor.gCost = newMovementCostToNeighbor;
                   neighbor.hCost = GetDistance(neighbor, goalNode);
                   neighbor.parent = currentNode;
   
                   if (!openList.Contains(neighbor))
                   {
                       openList.Add(neighbor);
                   }
               }
           }
       }
   
       return null;
   }
   
   private List<Node> RetracePath(Node startNode, Node endNode)
   {
       List<Node> path = new List<Node>();
       Node currentNode = endNode;
   
       while (currentNode != startNode)
       {
           path.Add(currentNode);
           currentNode = currentNode.parent;
       }
       path.Reverse();
       return path;
   }
   
   private int GetDistance(Node nodeA, Node nodeB)
   {
       int dstX = Mathf.Abs(nodeA.position.x - nodeB.position.x);
       int dstY = Mathf.Abs(nodeA.position.y - nodeB.position.y);
   
       if (dstX > dstY)
           return 14 * dstY + 10 * (dstX - dstY);
       return 14 * dstX + 10 * (dstY - dstX);
   }
   

1. Draw the Grid: Create a method to draw the grid and visualize the path.

   void OnDrawGizmos()
   {
       if (grid != null)
       {
           foreach (Node node in grid.nodes)
           {
               Gizmos.color = node.isWalkable ? Color.white : Color.red;
               Gizmos.DrawCube(new Vector3(node.position.x, 0, node.position.y), Vector3.one * 0.9f);
           }
       }
   }
   

2. Draw the Path: Visualize the path found by the A* algorithm.

   void OnDrawGizmos()
   {
       if (grid != null)
       {
           foreach (Node node in grid.nodes)
           {
               Gizmos.color = node.isWalkable ? Color.white : Color.red;
               Gizmos.DrawCube(new Vector3(node.position.x, 0, node.position.y), Vector3.one * 0.9f);
           }
   
           if (path != null)
           {
               foreach (Node node in path)
               {
                   Gizmos.color = Color.black;
                   Gizmos.DrawCube(new Vector3(node.position.x, 0, node.position.y), Vector3.one * 0.9f);
               }
           }
       }
   }
   

1. Create a Character: Add a character to the scene and create a script to move it along the path.

   public class Character : MonoBehaviour
   {
       public float speed = 5f;
       private List<Node> path;
       private int targetIndex;
   
       public void SetPath(List<Node> path)
       {
           this.path = path;
           targetIndex = 0;
           StopCoroutine("FollowPath");
           StartCoroutine("FollowPath");
       }
   
       private IEnumerator FollowPath()
       {
           Vector3 currentWaypoint = path[0].position;
           while (true)
           {
               if (transform.position == currentWaypoint)
               {
                   targetIndex++;
                   if (targetIndex >= path.Count)
                   {
                       yield break;
                   }
                   currentWaypoint = path[targetIndex].position;
               }
   
               transform.position = Vector3.MoveTowards(transform.position, currentWaypoint, speed * Time.deltaTime);
               yield return null;
           }
       }
   }
   

2. Assign the Path to the Character: Once the path is found, assign it to the character.

   void Update()
   {
       if (Input.GetMouseButtonDown(0))
       {
           Vector3 mousePosition = Camera.main.ScreenToWorldPoint(Input.mousePosition);
           Node startNode = grid.GetNodeFromWorldPoint(transform.position);
           Node goalNode = grid.GetNodeFromWorldPoint(mousePosition);
   
           List<Node> path = FindPath(startNode, goalNode);
           character.SetPath(path);
       }
   }
   

• Task: Modify the grid size to be larger or smaller and observe how the pathfinding algorithm performs.
• Solution: Change the width and height parameters in the Grid class constructor.

• Task: Add more obstacles to the grid and ensure the character can still find a path to the goal.
• Solution: Modify the InitializeGrid method to set more cells as non-walkable.

• Task: Optimize the A* algorithm to improve performance, especially for larger grids.
• Solution: Implement a priority queue for the open list to reduce the time complexity of finding the node with the lowest fCost.

In this project, you have implemented basic navigation for a game character using the A* pathfinding algorithm. You have learned how to create a grid-based map, implement the A* algorithm, visualize the path, and move a character along the path. These skills are fundamental for developing intelligent behaviors in game characters and will serve as a foundation for more advanced AI techniques in video games.