Последние пару дней я был простывшим и для успокоения занимался алгоритмом генерации лабиринтов и нахождении в нем путей. Графы и графовые алгоритмы база компутер саенс, но я как то эту тему пропустил, поэтому решил углубиться в ее изучение и наверстать.
На видео мышь находит цель, используя поиск в глубину. Находясь в текущей точке она выбирает направление и углубляется в него пока не найдет тупик, Затем она отступает пока не найдет клетку где есть доступный ход и снова углубляется в него, и так пока не найдет цель.
На втором видео визуализация того как этот алгоритм работает "под капотом", серым показаны клетки в которых мышь уже искала. Наглядно видна не эффективность алгоритма, т.к. мыши требуется обойти почти весь лабиринт прежде чем она наткнется на цель. хотя в некоторые моменты она была так близко к ней. Эту проблему решает поиск в ширину, или A* поиск, моя цель реализовать все эти алгоритмы в итоге.