Tìm kiếm A*

1g[start] = 0;  // Chi phí từ điểm đầu = 02open.add(new int[]{h(start), start});  // Nạp tập mở với f = h3while (!open.isEmpty()) {  // Đến khi tập mở rỗng4  int node = open.poll()[1];  // Lấy ô có f nhỏ nhất5  if (settled[node]) continue;  // Bỏ qua bản trùng cũ6  settled[node] = true;  // Chốt ô này7  if (node == goal) return buildPath();  // Tới đích — truy vết đường8  for (int neighbor : neighbors(node)) {  // Duyệt các ô kề đi được9    int tentativeG = g[node] + cost(neighbor);  // Chi phí tới nơi qua node10    if (tentativeG < g[neighbor]) {  // Tìm được đường rẻ hơn11      g[neighbor] = tentativeG; parent[neighbor] = node;  // Cập nhật và lưu cha12      open.add(new int[]{tentativeG + h(neighbor), neighbor});  // Xếp theo f = g + h13    }14  }15}16 17int h(int cell) {  // Khoảng cách Manhattan tới đích18  int r = cell / COLS, c = cell % COLS;19  int gr = goal / COLS, gc = goal % COLS;20  return Math.abs(r - gr) + Math.abs(c - gc);21}22 23List<Integer> neighbors(int cell) {  // Các ô kề đi được24  int r = cell / COLS, c = cell % COLS;25  int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};26  List<Integer> out = new ArrayList<>();27  for (int[] d : dirs) {28    int nr = r + d[0], nc = c + d[1];29    if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;30    int nbr = nr * COLS + nc;31    if (!walls.contains(nbr)) out.add(nbr);32  }33  return out;34}35 36int cost(int cell) {  // Chi phí bước vào một ô37  return weights.contains(cell) ? WEIGHT_COST : 1;38}39 40List<Integer> buildPath() {  // Lần theo cha từ đích41  List<Integer> path = new ArrayList<>();42  for (int at = goal; at != -1; at = parent[at]) path.add(at);43  Collections.reverse(path);44  return path;45}