👀 Views: 129 💬 Answers: 1 📅 Created: 2025-06-13

pathfinding algorithm a-star Java

I'm not sure how to approach I'm building a feature where I've spent hours debugging this and Quick question that's been bugging me - After trying multiple solutions online, I still can't figure this out... I'm relatively new to this, so bear with me... I'm currently working on an A* pathfinding algorithm implemented in Java, and I'm working with an unexpected scenario where the algorithm fails to find a path even when one exists. I’m using a simple grid-based approach with a heuristic based on the Manhattan distance. I initialize my open and closed lists and maintain a Node class that stores the required information (g-cost, h-cost, f-cost, parent, and position). However, despite having valid start and end nodes, it seems my open list isn’t being populated correctly, leading to a situation where the algorithm returns null instead of the expected path. Here's a simplified version of my Node class and the relevant parts of my A* implementation: ```java class Node { int x, y; Node parent; double gCost, hCost, fCost; public Node(int x, int y) { this.x = x; this.y = y; } } public List<Node> aStar(Node start, Node goal) { List<Node> openList = new ArrayList<>(); List<Node> closedList = new ArrayList<>(); openList.add(start); while (!openList.isEmpty()) { Node current = openList.get(0); for (Node node : openList) { if (node.fCost < current.fCost || (node.fCost == current.fCost && node.hCost < current.hCost)) { current = node; } } openList.remove(current); closedList.add(current); if (current.x == goal.x && current.y == goal.y) { return reconstructPath(current); } for (Node neighbor : getNeighbors(current)) { if (closedList.contains(neighbor)) { continue; } double tentativeGCost = current.gCost + 1; // Assuming equal cost for all movements if (!openList.contains(neighbor)) { openList.add(neighbor); } else if (tentativeGCost >= neighbor.gCost) { continue; } neighbor.parent = current; neighbor.gCost = tentativeGCost; neighbor.hCost = calculateHeuristic(neighbor, goal); neighbor.fCost = neighbor.gCost + neighbor.hCost; } } return null; // No path found } ``` I've verified that my `getNeighbors` method returns the correct neighboring nodes and that they are properly initialized. The `calculateHeuristic` function also seems to be working correctly. However, when I run the algorithm, the open list remains empty after the first iteration, causing it to skip checking valid neighbors. I’m not getting any exceptions or behavior messages, but I suspect it might be related to how I’m managing the open and closed lists. Any insights on what I might be doing wrong or suggestions for debugging this would be greatly appreciated! This is part of a larger web app I'm building. Any help would be greatly appreciated! I'm working on a API that needs to handle this. Any help would be greatly appreciated! Any suggestions would be helpful. My development environment is Windows 10. Am I missing something obvious? I've been using Java for about a year now. What would be the recommended way to handle this?