Как бы лучше оптимизировать алгоритм поиска, если нужно не просто найти путь из А в Б, а путь шириной, например, 2 клетки? Юзаю алгоритм Дейкстры. Что-то идей совсем нету :(

увеличить препятствия и искать узкий путь?

> Как бы лучше оптимизировать алгоритм поиска, если нужно
> не просто найти путь из А в Б, а путь шириной, например,
>  2 клетки?


А чем поиск пути путь шириной в 2 клетки отличается от поиска обычного?
Чуть-чуть изменить алгоритм стандартного поиска:
Если при следующем шаге ширина стала равной 1, считаем данное направление тупиком.

отличие в необходимости проверять ширину

Получилось) Просто проверять ширину недостаточно, нужно еще и диагонали, чтобы понять что "куб" 2х2 туда пролезет