База поиска путей - BFS

Расшифровка на секунду: BFS — breadth-first search, поиск в ширину. Не вглубь, а именно вширь: сначала обходишь всех соседей, потом соседей соседей, слоями, как круги на воде от камня. В визуализации на открытых плоскостях сложных это выглядит очень красиво.

Придумал, кстати, не один человек. Эдвард Мур в 1959 искал кратчайший путь из лабиринта для подопытных крыс, а через два года (не Брюс) Ли независимо описал то же самое — уже для трассировки проводников на платах. Друг о друге они даже не знали. В учебники алгоритм попал только в 70-х, когда его формализовали как общий обход графа, а до этого он существовал отдельно в каждой прикладной области - своё имя, своя статья.

Идея проще, чем звучит: берёшь стартовую точку, кладёшь в очередь, и на каждом шаге забираешь первого из очереди, смотришь его соседей, новых добавляешь в конец. Пока очередь не опустеет. Что зашло первым - то первым и обработалось, поэтому он слоеный. Как лук.

В реальном мире BFS почти везде, где нужен кратчайший путь без весов. LinkedIn считает степень связи между людьми именно так, второй круг, третий круг. Роутеры распространяют информацию о сети похожим образом, слой за слоем. Солвер для кубика Рубика перебирает состояния в ширину, чтобы гарантированно найти кратчайшее решение. Ну и кубер, конечно же, с NPC в играх туда же: обход зависимостей подов слой за слоем, поиск пути для NPC на клетчатой карте - все, что нужно. Для остального есть Дейкстра и Астар.

Лично я, наверное, одним из первых алгоритмов опробовал именно такой, когда трогал геймдев чуть серьезнее, чем маленькие демки. Забавно, что за 65 лет ничего лучше очереди не придумали.