Начнем с того, что меркаторская карта не определяет направления пути - она сохраняет только углы (а значит, и форму малых объектов). Это весьма удобно, что известно всякому пользователю Google Earth, но при реализации проблем не оберешься. Хотя... формула для расстояния может оказаться не слишком ужасной. Но экспоненты, косинусы и квадратные корни в ней точно будут.
Что до направления - прямые на ней выглядят дугами (не знаю, дугами чего, но это не окружности. Синусоиды?), которые отклоняются от отрезка к полюсу (кратчайший путь из Сиэтла в Москву пересекает Полярный круг).
Модель хочется дискретной? Самое круглое, что можно собрать из шестиугольников - нечто вроде футбольного мяча, с 12 пятиугольными "дырками" (недоступными клетками?). Из квадратов ничего круглее куба (с 8 недоступными вершинами, где сходятся 3 квадрата вместо четырех), скорее всего, не получится. Можно покрыть куб косыми квадратами, тогда недоступны будут 8 треугольных клеток.