Общая анимация поиска пути

От: Из: Общие

Это часть проекта, который я построил для визуализации алгоритмов поиска пути. Эти файлы запускают алгоритмы и собирают список кадров, которые используются для отображения анимации.

алгоритмы.ts

export type Algorithm = (start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) => GridFrame[];

export function breadthFirstSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
    const queue = new Queue<Coord>();
    const distances = new HashMap<Coord, number>();

    return genericUnidirectionalSearch(start, goal, queue, distances, weights, walls);
}

export function depthFirstSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
    const stack = new Stack<Coord>();
    const distances = new HashMap<Coord, number>();

    return genericUnidirectionalSearch(start, goal, stack, distances, weights, walls);
}

export function bestFirstSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
    const heuristicComparator = stringToHeuristic.get(heuristic)(goal);
    const priorityQueue = new PriorityQueue(heuristicComparator);
    const distances = new HashMap<Coord, number>();

    return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function dijkstra(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
    const distances = new HashMap<Coord, number>();
    const distanceComparator = generateDijkstraComparator(distances);
    const priorityQueue = new PriorityQueue(distanceComparator);

    return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function aStar(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
    const distances = new HashMap<Coord, number>();
    const comparator = generateAStarComparator(goal, distances, heuristic);
    const priorityQueue = new PriorityQueue(comparator);

    return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function randomSearch(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
    const distances = new HashMap<Coord, number>();
    const comparator = generateRandomComparator();
    const priorityQueue = new PriorityQueue(comparator);

    return genericUnidirectionalSearch(start, goal, priorityQueue, distances, weights, walls);
}

export function bidirectionalBFS(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
    const forwardsDistances = new HashMap<Coord, number>();
    const backwardsDistances = new HashMap<Coord, number>();
    const forwardQueue = new Queue<Coord>();
    const backwardQueue = new Queue<Coord>();

    return genericBidirectionalSearch(forwardQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalDFS(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], _: string) {
    const forwardsDistances = new HashMap<Coord, number>();
    const backwardsDistances = new HashMap<Coord, number>();
    const forwardsStack = new Stack<Coord>();
    const backwardStack = new Stack<Coord>();

    return genericBidirectionalSearch(forwardsStack, backwardStack, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalGBFS(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
    const forwardsDistances = new HashMap<Coord, number>();
    const backwardsDistances = new HashMap<Coord, number>();
    const forwardsComparator = stringToHeuristic.get(heuristic)(goal);
    const backwardsComparator = stringToHeuristic.get(heuristic)(start);
    const forwardsQueue = new PriorityQueue<Coord>(forwardsComparator);
    const backwardQueue = new PriorityQueue<Coord>(backwardsComparator);

    return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalDijkstra(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
    const forwardsDistances = new HashMap<Coord, number>();
    const backwardsDistances = new HashMap<Coord, number>();
    const forwardsComparator = generateDijkstraComparator(forwardsDistances);
    const backwardsComparator = generateDijkstraComparator(backwardsDistances);
    const forwardsQueue = new PriorityQueue<Coord>(forwardsComparator);
    const backwardQueue = new PriorityQueue<Coord>(backwardsComparator);

    return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalAStar(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
    const forwardsDistances = new HashMap<Coord, number>();
    const backwardsDistances = new HashMap<Coord, number>();
    const forwardsComparator = generateAStarComparator(goal, forwardsDistances, heuristic);
    const backwardsComparator = generateAStarComparator(start, backwardsDistances, heuristic);
    const forwardsQueue = new PriorityQueue<Coord>(forwardsComparator);
    const backwardQueue = new PriorityQueue<Coord>(backwardsComparator);

    return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

export function bidirectionalRandom(start: Coord, goal: Coord, walls: boolean[][], weights: number[][], heuristic: string) {
    const forwardsDistances = new HashMap<Coord, number>();
    const backwardsDistances = new HashMap<Coord, number>();
    const comparator = generateRandomComparator();
    const forwardsQueue = new PriorityQueue<Coord>(comparator);
    const backwardQueue = new PriorityQueue<Coord>(comparator);

    return genericBidirectionalSearch(forwardsQueue, backwardQueue, forwardsDistances, backwardsDistances, start, goal, weights, walls);
}

genericPathfinding.ts


// Generic pathfinding algo for searching from a source. Parameterized with the data structure used to make it generic
export function genericUnidirectionalSearch(
    start: Coord,
    goal: Coord,
    agenda: Collection<Coord>,
    distances: HashMap<Coord, number>,
    weights: number[][],
    walls: boolean[][]) {

    const path = new HashMap<Coord, Coord>();
    const visited = initialseGridWith(false);
    const considered = initialseGridWith(false);
    const frames: GridFrame[] = [];

    agenda.add(start);
    visited[start.row][start.col] = true;
    distances.add(start, 0);

    while (!agenda.isEmpty()) {
        const isFound = considerNextNode(path, visited, agenda, goal, weights, considered, walls, distances, frames);

        if (isFound) {
            const finalPath = pathMapToGrid(path, goal);

            createFinalPathFrame(finalPath, visited, considered, frames);
            break;
        }
    }

    return frames;
}

// Generic pathfinding algo for searching from both the source and goal concurrently
export function genericBidirectionalSearch(
    forwardAgenda: Collection<Coord>,
    backwardAgenda: Collection<Coord>,
    forwardDistances: HashMap<Coord, number>,
    backwardDistances: HashMap<Coord, number>,
    start: Coord,
    goal: Coord,
    weights: number[][],
    walls: boolean[][]) {

    const forwardPath = new HashMap<Coord, Coord>();
    const backwardPath = new HashMap<Coord, Coord>();

    const forwardVisited = initialseGridWith(false);
    const backwardVisited = initialseGridWith(false);

    const forwardConsidered = initialseGridWith(false);
    const backwardConsidered = initialseGridWith(false);

    const frames: GridFrame[] = [];

    forwardDistances.add(start, 0);
    backwardDistances.add(goal, 0);

    forwardAgenda.add(start);
    backwardAgenda.add(goal);

    forwardVisited[start.row][start.col] = true;
    backwardVisited[goal.row][goal.col] = true;

    while (!forwardAgenda.isEmpty() && !backwardAgenda.isEmpty()) {
        const foundForwards = considerNextNode(forwardPath, forwardVisited, forwardAgenda, goal, weights, forwardConsidered, walls, forwardDistances, frames);
        const foundBackwards = considerNextNode(backwardPath, backwardVisited, backwardAgenda, start, weights, backwardConsidered, walls, backwardDistances, frames);

        mergeFrames(frames);

        if (foundForwards) {
            const finalPath = pathMapToGrid(forwardPath, goal);
            const mergedVisited = mergeGrids(forwardVisited, backwardVisited);
            const mergedConsidered = mergeGrids(forwardConsidered, backwardConsidered);

            createFinalPathFrame(finalPath, mergedVisited, mergedConsidered, frames);
            break;
        } else if (foundBackwards) {
            const finalPath = pathMapToGrid(backwardPath, start);
            const mergedVisited = mergeGrids(forwardVisited, backwardVisited);
            const mergedConsidered = mergeGrids(forwardConsidered, backwardConsidered);

            createFinalPathFrame(finalPath, mergedVisited, mergedConsidered, frames);
            break;
        } else if (hasIntersection(forwardConsidered, backwardConsidered)) {
            const intersection = getIntersection(forwardConsidered, backwardConsidered);
            const finalPath = mergeGrids(pathMapToGrid(forwardPath, intersection), pathMapToGrid(backwardPath, intersection));
            const mergedVisited = mergeGrids(forwardVisited, backwardVisited);
            const mergedConsidered = mergeGrids(forwardConsidered, backwardConsidered);

            createFinalPathFrame(finalPath, mergedVisited, mergedConsidered, frames);
            break;
        }
    }

    return frames;
}

// Generic function for making one step in a pathfinding algorithm
function considerNextNode(
    path: HashMap<Coord, Coord>,
    visited: boolean[][],
    agenda: Collection<Coord>,
    goal: Coord,
    weights: number[][],
    considered: boolean[][],
    walls: boolean[][],
    distances: HashMap<Coord, number>,
    frames: GridFrame[]) {

    const currentPos = agenda.remove();
    const currentNeighbours = generateNeighbours(currentPos);

    considered[currentPos.row][currentPos.col] = true;
    frames.push(generateGridFrame(visited, considered, []));

    if (isSameCoord(currentPos, goal)) {
        return true;
    }

    currentNeighbours.forEach(neighbour => {
        if (!isOutOfBounds(neighbour) && !walls[neighbour.row][neighbour.col]) {
            const neighbourDistance = distances.get(currentPos) + weights[neighbour.row][neighbour.col];

            if (!visited[neighbour.row][neighbour.col]) {
                distances.add(neighbour, neighbourDistance);
                agenda.add(neighbour);
                visited[neighbour.row][neighbour.col] = true;
                path.add(neighbour, currentPos);
            }
        }
    });

    return false;
}

// Given two boolean grids, for all tiles, take the logical OR and return a new grid
function mergeGrids(grid: boolean[][], matrix: boolean[][]) {
    const mergedGrid = initialseGridWith(false);

    for (let row = 0; row < HEIGHT; row++) {
        for (let col = 0; col < WIDTH; col++) {
            mergedGrid[row][col] = grid[row][col] || matrix[row][col];
        }
    }

    return mergedGrid;
}

// Merge two animation frames to produce a frame that contains the information encoded in both
function mergeFrames(frames: GridFrame[]) {
    const backwardsFrame = frames.pop();
    const forwardsFrame = frames.pop();
    const mergedFrame = initialseGridWith(TileFrame.Blank);

    for (let row = 0; row < HEIGHT; row++) {
        for (let col = 0; col < WIDTH; col++) {
            if (forwardsFrame[row][col] === TileFrame.Searching || backwardsFrame[row][col] === TileFrame.Searching) {
                mergedFrame[row][col] = TileFrame.Searching;
            } else if (forwardsFrame[row][col] === TileFrame.Frontier || backwardsFrame[row][col] === TileFrame.Frontier) {
                mergedFrame[row][col] = TileFrame.Frontier;
            }
        }
    }

    frames.push(mergedFrame);
}

// Add a frame containing the final path to the list
function createFinalPathFrame(path: boolean[][], visited: boolean[][], considered: boolean[][], frames: GridFrame[]) {
    frames.push(generateGridFrame(visited, considered, path));
}

// Convert the hashmap pointer based path to a boolean grid based path
function pathMapToGrid(pathMap: HashMap<Coord, Coord>, goal: Coord) {
    const path = initialseGridWith(false);
    let pos = goal;

    while (pathMap.get(pos) !== undefined) {
        path[pos.row][pos.col] = true;

        pos = pathMap.get(pos);
    }

    return path;
}

// Encode the state of a pathfinding algorithm into a frame 
function generateGridFrame(visited: boolean[][], considered: boolean[][], path: boolean[][]) {
    const grid = initialseGridWith(TileFrame.Blank);

    for (let row = 0; row < HEIGHT; row++) {
        for (let col = 0; col < WIDTH; col++) {
            if (path.length > 0 && path[row][col]) {
                grid[row][col] = TileFrame.Path;
            } else if (considered[row][col]) {
                grid[row][col] = TileFrame.Searching;
            } else if (visited[row][col]) {
                grid[row][col] = TileFrame.Frontier;
            }
        }
    }

    return grid;
}

Comparators.ts


type Heuristic = (goal: Coord) => (c1: Coord, c2: Coord) => number;

// Map a heuristics JSX representation onto its implementation 
export const stringToHeuristic = new Map<string, Heuristic>([
    ["manhattan", generateManhattanComparator],
    ["euclidean", generateEuclideanComparator],
    ["chebyshev", generateChebyshevComparator]
]);

// Return a comparator that compares by adding the distance from the starting tile and estimated distance from the goal
export function generateAStarComparator(goal: Coord, distances: HashMap<Coord, number>, heuristic: string) {
    return (c1: Coord, c2: Coord) => {
        const heuristicGenerator = stringToHeuristic.get(heuristic);
        const dijkstraComparison = generateDijkstraComparator(distances)(c1, c2);
        const heuristicComparison = heuristicGenerator(goal)(c1, c2);

        return dijkstraComparison + heuristicComparison;
    }
}

// Returns a comparator that compares using the distance from the starting tile
export function generateDijkstraComparator(distances: HashMap<Coord, number>) {
    return (c1: Coord, c2: Coord) =>
        distances.get(c2) - distances.get(c1);
}

// Returns a comparator that selects an item randomly
export function generateRandomComparator() {
    return (c1: Coord, c2: Coord) => Math.random() - 0.6;
}

// Given two coordinates (p1, p2) and (g1, g2), return comparator that compares using formula max(abs(p1 - g1), abs(p2 - g2))
function generateChebyshevComparator({ row: goalRow, col: goalCol }: Coord) {
    return ({ row: r1, col: c1 }: Coord, { row: r2, col: c2 }: Coord) =>
        Math.max(Math.abs(r2 - goalRow), Math.abs(c2 - goalCol)) - Math.max(Math.abs(r1 - goalRow), Math.abs(c1 - goalCol));

}

// Given two coordinates (p1, p2) and (g1, g2), return comparator that compares using formula sqrt((p1 - g1)^2 + abs(p2 - g2)^2)
function generateEuclideanComparator({ row: goalRow, col: goalCol }: Coord) {
    return ({ row: r1, col: c1 }: Coord, { row: r2, col: c2 }: Coord) => {
        const r1Dist = Math.sqrt(Math.pow(r1 - goalRow, 2) + Math.pow(c1 - goalCol, 2));
        const r2Dist = Math.sqrt(Math.pow(r2 - goalRow, 2) + Math.pow(c2 - goalCol, 2));

        return r2Dist - r1Dist;
    }
}

// Given two coordinates (p1, p2) and (g1, g2), return comparator that compares using formula abs(p1 - g1) + abs(p2 - g2) 
function generateManhattanComparator({ row: goalRow, col: goalCol }: Coord) {
    return ({ row: r1, col: c1 }: Coord, { row: r2, col: c2 }: Coord) =>
        (Math.abs(r2 - goalRow) + Math.abs(c2 - goalCol)) - (Math.abs(r1 - goalRow) + Math.abs(c1 - goalCol));

}

0

Похожие записи:

  1. N-Queens без рекурсии (но с одним goto)
  2. Как я могу ускорить мой алгоритм IDA * для N-puzzle?
  3. Нахождение минимального количества шагов, необходимых для перехода от источника к терминалу
  4. Игра Connect Four, созданная на основе игры Tic Tac Toe [closed]
  5. Программа расчета небоскребов для размера NxN, версия 2 (с использованием функции отслеживания с возвратом)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *