А почему вдруг AStar не подходит? Даже если у тебя шахматная доска, это все-равно граф. Область из ячеек - тем более граф. А для обхода графов очень мало алгоритмов и AStar один из лучших. AStar'ом анализируют кратчайшие пути на геокартах. Не думаю, что твой граф сложнее геокарт.

И что еще не совсем понятно. Какие точки должны быть соеденины? Это должны быть только прямые или ломаные отрезки?

Вообще, задача описана очень плохо. Приципи картинку со своими точками.

У каждого твоего блока есть центр с определенными координатами. Нужно создать структуру данных описывающую граф соостоящий из координат *(пары x,y) этих блоков. Таким образом отпадет необходимость разбивать все на клетки. Геокарты тоже не на клетки разбиты, а используют градусы, минуты и секунды для определения положения. Правда это уже тоже не самая актуальная фишка.
Таким образом при перемещении блоков, сам граф меняться не будет, так как количество узлов в графе будет оставаться постоянным (или пусть даже будет меняться - все равно), а значения координат для узлов будут менятья.
Обходя граф алгоритмом можно находить кратчайший путь от входа к выходу. Хотя, скажу честно, я  так и не понял - нужно искать кратчайший путь от заданного выхода до ближайшего входа? Если да, то при инициализации графа можно сразу сделать его взвешеным и потом алгоритм будет пролетать пару миллионов узлов за доли секунды. (в зависимости от процессора и серды исполнения, конечно). При этом только важно учитывать динамическое изменине положения узлов и оптимально реинициализировать веса графа во врмея смены положения узлов.

Да, графы без пересечений могут только в трехмерности существовать, да и то не все.