Поиск пути и обход препятствий - алгоритм A* (AStar) и его модификации. При этом мир предполагается разбить на зоны.
Что касается карты, то однозначно ответить нельзя.
Для начала нужно определиться - процедурная генерация или левел-дизайн. И то, и другое имеет свои плюсы и минусы. Генерация делает игру разнообразнее, но сделать геймплей интересным сложнее, а сюжет впилить практически невозможно. Ручные карты, наоборот, могут быть очень продуманными и красивыми, содержать уникальные локации, города, героев, но требуют дополнительных человеко-часов.
Далее, можно взять какой-то готовый движок и допилить его до своих нужд, заодно тянуть с собой ненужный функционал, но может быть, что в нем не хватает чего-то важного и придется сильно допиливать, а может оказаться проще написать с нуля. Зависит от вашего геймплея и конкретных фич вашей игры.
В общем, я бы на вашем месте не искал готовое решение, а делал своё, и составлял бы функционал игры из более мелких кирпичиков - отдельно алгоритм генерации (плюс свои хотелки типа генерации координат городов), отдельно сделать зум карты (свой или нагуглить), отдельно сами города и т.д. Генерация карты, соответственно, тоже составляется чисто под вашу игру из еще более мелких кирпичиков. Алгоритмов генерации множество, с их поиском у вас не будет проблем.
Средний
