function a_star(grid, start, goal) {
    let openList = [];
    let closedList = new Set();
    let cameFrom = {};
    let gScore = {};
    let fScore = {};
    
    // Initialize start node
    openList.push(start);
    gScore[start] = 0;
    fScore[start] = heuristic(start, goal);
    
    while (openList.length > 0) {
        let current = lowestFScore(openList, fScore);
        
        if (current === goal) {
            return reconstructPath(cameFrom, current);
        }
        
        openList = openList.filter(n => n !== current);
        closedList.add(current);
        
        let neighbors = getNeighbors(grid, current);
        for (let neighbor of neighbors) {
            if (closedList.has(neighbor)) continue;
            
            let tentativeGScore = gScore[current] + 1;
            
            if (!openList.includes(neighbor)) {
                openList.push(neighbor);
            }
            if (tentativeGScore >= gScore[neighbor]) continue;
            
            cameFrom[neighbor] = current;
            gScore[neighbor] = tentativeGScore;
            fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal);
        }
    }
    
    return null;  // No path found
}

function lowestFScore(openList, fScore) {
    let lowest = openList[0];
    for (let node of openList) {
        if (fScore[node] < fScore[lowest]) {
            lowest = node;
        }
    }
    return lowest;
}

function heuristic(a, b) {
    return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);  // Manhattan distance
}

function getNeighbors(grid, node) {
    let neighbors = [];
    let [row, col] = node;
    
    let moves = [
        [0, 1], [1, 0], [0, -1], [-1, 0]  // Right, Down, Left, Up
    ];
    
    for (let move of moves) {
        let newRow = row + move[0];
        let newCol = col + move[1];
        if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length && grid[newRow][newCol] === 0) {
            neighbors.push([newRow, newCol]);
        }
    }
    
    return neighbors;
}

function reconstructPath(cameFrom, current) {
    let path = [current];
    while (current in cameFrom) {
        current = cameFrom[current];
        path.push(current);
    }
    return path.reverse();
}
class Car {
    constructor(start, goal, grid) {
        this.position = start;
        this.goal = goal;
        this.grid = grid;
        this.path = a_star(grid, start, goal);
        this.index = 0;
    }
    
    move() {
        if (this.path && this.index < this.path.length) {
            this.position = this.path[this.index];
            this.index++;
        }
    }
    
    render() {
        // Render the car on the canvas
        let [x, y] = this.position;
        drawCar(x, y);  // Replace with actual Ancient Brain rendering logic
    }
}
// Define the grid (0 = road, 1 = obstacle)
let grid = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
];

// Initialize cars with start and goal positions
let car1 = new Car([0, 0], [4, 4], grid);
let car2 = new Car([4, 0], [0, 4], grid);
let cars = [car1, car2];

// Render function for Ancient Brain
function startBrain() {
    // Render grid and cars
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            drawCell(row, col, grid[row][col]);
        }
    }
    
    for (let car of cars) {
        car.render();
        car.move();
    }
}

// Custom draw functions
function drawCell(row, col, type) {
    if (type === 1) {
        // Draw obstacle
        ctx.fillStyle = 'black';
    } else {
        // Draw road
        ctx.fillStyle = 'gray';
    }
    ctx.fillRect(col * cellSize, row * cellSize, cellSize, cellSize);
}

function drawCar(x, y) {
    ctx.fillStyle = 'blue';
    ctx.fillRect(y * cellSize + 5, x * cellSize + 5, cellSize - 10, cellSize - 10);
}
function checkCollision(car, cars) {
    for (let otherCar of cars) {
        if (car !== otherCar && car.position.toString() === otherCar.position.toString()) {
            return true;
        }
    }
    return false;
}

function updateCars() {
    for (let car of cars) {
        if (!checkCollision(car, cars)) {
            car.move();
        }
    }
}