This project showcases the implementation of the A* (A-Star) search algorithm, developed as part of my ITCS 3153 (Introduction to Artificial Intelligence) coursework at UNC Charlotte. The assignment successfully demonstrates all required objectives including grid creation, user-interactive node selection, A* algorithm implementation, and real-time pathfinding visualization.
Demo
Project Overview
The A* search algorithm is a graph traversal and pathfinding algorithm that is used to find the shortest path between two nodes. This implementation creates a visual representation of the algorithm in action, each step is displayed in the console with color-coded cells:
- White cells: Empty, traversable spaces
- Gray cells: Obstacles (blocked)
- Green cell: Start position
- Red cell: Goal position
- Blue cells: Explored Nodes
- Green path: The final optimal route
Technologies Used: Java, Pathfinding Algorithms, ANSI Escape Codes for console colorization
How to Run the Project
Prerequisites
To run this project, ensure you have the following installed on your machine:
- Java Development Kit (JDK) 8 or higher, you can download it from here.
- Git, you can download it from here.
Installation/Execution Steps
- Clone the repository:
git clone https://github.com/jcmecham/Intro_To_AI_ITCS_3153.git - Navigate to the project directory:
cd "Intro_To_AI_ITCS_3153/Assignment 2 - A Star Search" - Compile the Java files:
javac Main.java Node.java ConsoleColors.java - Execute the compiled program:
java Main
How A* Search Works
A* (pronounced "A-star") is an intelligent pathfinding algorithm that efficiently finds the shortest path between two points. Unlike simpler algorithms that blindly explore in all directions, A* uses a heuristic function to guide its search toward the goal, making it much more efficient.
A* works by assigning each position a total cost value using the cost function f(n) = g(n) + h(n), which combines two components:
- g(n): The actual distance traveled from the start to this position
- h(n): The estimated distance from this position to the goal (the "heuristic")
The algorithm always explores the position with the lowest f(n) value first, prioritizing paths that are both short so far AND look promising.
For a more comprehensive mathematical explanation of A* and other pathfinding algorithms, check out this guide to the A* algorithm.