Как построить наименьшую траекторию перемещения по клеткам, имея возможность переставлять препятствия?
Строим дерево ходов, строим целевую функцию, берем один из популярных алгоритмов оптимизации на графах (либо колония муравьев, либо имитация отжига), смешиваем, но не взбалтываем.
Ответ относится к стандартным алгоритмам поиска пути.
Литература:
algolist.manual.ru/games/wavealg.php
algolist.manual.ru/games/smartmove.php
www.gamedev.ru/code/articles/?id=4246
Любой алгоритм удачно усложняется за счет использования потенциальных полей.
https://habrahabr.ru/post/262181/