Хранение и поиск в графе

Имеется некая игра. Необходимо оптимально быстро найти кратчайшую последовательность ходов для достижения перехода из одного игрового состояния в другое. (или всевозможные последовательности определённой длины). При чём нужна будет функция возможности ограничения возможных ходов. Например, если возможных ходов 4 (влево, вправо, вверх, вниз), то мы моглы бы запросить путь, который, допустим, не использует ходы влево и вниз. Как всё это дело лучше хранить и какие алгоритмы использовать для поиска?

[Размышления] Представляю себе принцип примерно следующим образом... При каждом ходе строится граф, где ребро это ход, а узел это состояние игры после данного хода (т.е. можно будет как анализировать существующую игру, так и сгенерировать до определённой глубины всевозможные 'виртуальные' комбинации для поиска по ним). Направление хода это вес, видимо. Но я не припомню ни одного стандартного алгоритма, который исключал бы из поиска определённые веса... Т.е. нужно пробежаться по графу и проставить исключаемым ходам неприлично высокий вес? (что тоже не исключает его участие на 100%) Или лучше подправить алгоритм, чтобы он по списку игнорировал определённые веса, а сам граф воспринимал, как невзвешенный?

На входе алгоритма - некие состояния игры, т.е. для каждого узла нужно хранить какой-то хеш (т.к. хранить все состояния довольно накладно), чтобы входные данные сразу можно было ассоциировать с нужными узлами графа. А потом поиском кратчайшего пути (A* наверное будет в данном случае оптимально?) можно будет найти кратчайший, а поиском вглубину(?) с ограничением по глубине для определённой длины.