Часть 1(скорость перемещения героев и типы местности и дорог):
Возьмем, что каждый герой перемещается на одну клетку за время Х, но его придется немного увеличить чем в данный момент в игре наверное.
Теперь в зависимости от того какой тип местности (к сожалению не знаю всех типов местности беру по гео уголку) к Х добавляется некий множитель

также
в зависимости от типа дороги тоже идет множитель
Бездорожье = 1.5
Тропинка = 1.25
тропа = 1
Тракт = 0.75
мощенная дорога = 0.5

Часть 2(перки):
а) Бродяга
В зависимости от уровня перка Бродяга герой будет выбирать более или менее оптимальный маршрут от города А к городу Б
примерно схема такая:
от города А к городу Б если города не на прямой, то нам оптимально будет идти либо по горизонтали в сторону города либо по вертикали, тогда шанс того в какую сторону герой пойдет считается так
уровень перка бродяга %оптимального направления(делится на 2 направления) % неоптимального направления(делится на 2 направления) стоит на месте
0 40 50 10
1 40 40 20
2 50 30 20
3 50 20 30
4 70 10 20
5 80 10 10
если точка отправления с конечной находятся на одной прямой:
уровень перка бродяга %оптимального направления(делится на 1 направление) % неоптимального направления(делится на 3 направления) стоит на месте
0 40 45 15
1 40 42 18
2 50 30 20
3 50 24 26
4 70 15 25
5 80 12 8
б) Знание троп
При выборе оптимального пути учитывается вес каждой клетки, т.е. тип местности и тип дороги(если надо могу подробнее расписать)
на нулевом уровне перка оптимальный путь вычисляется всегда по прямой
на 1 уровне - 15% шанс что будут учитыватсья веса клеток
2 - 30%
3 - 45%
4 - 60%
5 - 70%
в) Зоркий глаз
каждый уровень перка определяет с какого расстояния герой видит город, что позволяет ему идти к городу начиная с этого расстояния всегда оптимальным путем с учетом весов клеток
0 уровень - 0 клеток
1 - 2 клетки
2 - 3
3 - 4
4 - 5
5 - 6

Часть 3(механизм появления троп):
Для каждой клетки считается количество наступаний героев за последнии 2 недели
и первые 5% (в нынешних условиях это примерно 44 клетки) клеток по абсолютному показателю становятся мощенной дорогой
следующие 5% - трактом
следующие 5% - тропой
и еще 5% - тропинкой