Algoritmy v praxi: Knights Travails

Feb 1, 2026

Únor 2026

Poslední projekt tohoto týdne spojil všechno dohromady do reálného problému. Zadání znělo jednoduše: Najdi nejkratší cestu šachového koně z bodu A do bodu B.

Šachovnice je vlastně Graf. Každé políčko je uzel a každý možný skok koně je hrana, která uzly spojuje.

Proč BFS (Breadth-First Search)?

Měl jsem na výběr mezi DFS (do hloubky) a BFS (do šířky). Protože hledáme nejkratší cestu, BFS je jasná volba. Funguje jako vlnky na vodě – prohledává všechny sousedy v 1. kroku, pak ve 2. kroku atd. Jakmile narazí na cíl, máme jistotu, že je to nejrychlejší cesta.

Klíčem k řešení byla Fronta (Queue) a sledování již navštívených políček, abychom se nezacyklili.

Tady je srdce mého algoritmu:

findShortestPath() {
    const queue = []; // Fronta pro BFS
    const visited = new Set(); // Abychom nechodili v kruhu

    // Do fronty ukládám nejen pozici, ale i celou historii cesty
    queue.push({ position: this.start, path: [this.start] });
    visited.add(this.start.toString());

    while (queue.length) {
        const { position, path } = queue.shift(); // FIFO - vezmi prvního

        // Jsme v cíli? Vrať cestu!
        if (position.toString() === this.end.toString()) return path;

        // Generuj možné tahy koně
        new GameBoard()
            .getKnightMoves(position)
            .filter((move) => !visited.has(move.toString()))
            .forEach((move) => {
                queue.push({ position: move, path: [...path, move] });
                visited.add(move.toString());
            });
    }
}

Tento projekt mi ukázal, že “nudné” datové struktury jako Grafy a Fronty jsou přesně to, co pohání věci jako GPS navigace nebo AI ve hrách.

GitHub: projekt BST