Телефонный навигатор для Forza Horizon 6. Как это было сделано - часть 2
В прошлой серии телефон научился понимать, где находится машина: Forza шлет телеметрию, Python ее принимает, координаты переводятся на карту, браузер на телефоне получает JSON.
Но точка на карте - это еще не навигатор. Это максимум режим “я знаю, где я заблудился”. Настоящий навигатор начинается в тот момент, когда ты нажимаешь на цель, а он строит дорогу, а не рисует палку через гору, реку и чувство собственного достоинства.
Почему нельзя просто нарисовать линию до цели
Самый быстрый способ сделать “маршрут” - взять координаты машины, координаты цели и провести между ними прямую. Для демо на 10 секунд выглядит отлично. Для реальной езды - стыд.
Проблема очевидная: машина не летает по любому пикселю карты. Ей нужны дороги. Значит, карту надо превратить в дорожный граф: узлы, ребра, длины, веса, классы дорог. По сути, сделать маленькую навигационную систему поверх игровой карты.
Сначала была просто большая карта
В проекте карта живет как мир 20000 на 20000 условных пикселей. Есть тайлы, метаданные, слой POI и координаты маркеров. Фронтенд показывает нужный кусок карты, сервер знает базовые параметры.
Параметры карты в сервере
MAP_ID = 481
DEFAULT_LAYER_ID = 760
MIN_ZOOM, MAX_ZOOM = 12, 18
TILE_SIZE = 256
MAP_WIDTH, MAP_HEIGHT = 20000, 20000
POI - отдельная приятная часть. markers.json хранит точки интереса, а поиск работает по названию, категории и описанию. Если уже есть координаты машины, результаты можно отсортировать по расстоянию. Не нейросеть, не магия, просто нормальная инженерная польза.
Поиск POI с учетом расстояния от машины
def search_markers(query: str, limit: int = 25):
terms = [t for t in query.strip().lower().split() if t]
snap = STATE.get_snapshot()
px, py = snap.get("map_x"), snap.get("map_y")
results = []
for marker in load_markers_data():
hay = " ".join(str(marker.get(k, "")) for k in (
"title", "category", "parent_category", "description", "desc"
)).lower()
if not all(term in hay for term in terms):
continue
item = dict(marker)
if px is not None and py is not None:
item["distance_px"] = round(math.hypot(
float(marker.get("map_x", 0)) - float(px),
float(marker.get("map_y", 0)) - float(py),
), 2)
results.append(item)
return results[:limit]
Дороги пришлось добывать из картинки
Вот тут началась та часть, которую нормальный человек, вероятно, назвал бы “а может, ну его”.
У меня была красивая карта. Но для маршрута нужна не красивая карта, а данные о дорогах. То есть надо было понять, где на изображении дорога, вычистить мусор, убрать ложные пятна, восстановить разрывы, превратить толстые дорожные линии в тонкий скелет и потом уже собрать граф.
На словах это звучит как компьютерное зрение. На практике - как спор с картинкой, которая очень не хочет становиться JSON.
Первый заход был через OpenCV. Я не пытался “понять” карту как человек - я пытался вытащить из изображения схему дорог: белые линии, оранжевые магистрали, пунктир, разрывы. OpenCV делал черновую маску: фильтр по цвету, морфологическая очистка, склейка близких участков, потом скелетизация. Звучит умно, но на практике алгоритм с одинаковой уверенностью находил дорогу, подпись на карте и какой-нибудь декоративный пиксель, которому просто повезло быть нужного цвета.
Поэтому после распознавания пришлось сделать отдельный HTML-редактор карты. Не красивый “редактор уровней”, а рабочую утилиту для ремонта: открыть маску, стереть мусор распознавания, дорисовать недостающие проезды, заштриховать разрывы, сохранить ручные штрихи в JSON и заново собрать road_graph. В этот момент проект окончательно перестал быть “сейчас OpenCV все сам поймет” и стал нормальной инженеркой: автомат нашел основу, человек добил то, что без глаза и здравого смысла не чинится.
Фрагмент из build_road_graph_from_manual_mask.py - выделение дорожного цвета
def classify_pixels(base_rgb: np.ndarray) -> np.ndarray:
hsv = cv2.cvtColor(base_rgb, cv2.COLOR_RGB2HSV)
h, s, v = hsv[..., 0], hsv[..., 1], hsv[..., 2]
r, g, b = base_rgb[..., 0], base_rgb[..., 1], base_rgb[..., 2]
orange = (
(h >= 2) & (h <= 28) & (s >= 35) & (v >= 70) &
(r.astype("int16") - b.astype("int16") >= 35) &
(r.astype("int16") >= g.astype("int16") - 12)
)
return cv2.dilate(
orange.astype("uint8"), np.ones((5, 5), np.uint8), iterations=1
).astype(bool)
Автоматом это сделать полностью красиво не получилось. Карта содержит подписи, иконки, швы, разные цвета, декоративные элементы. Поэтому появился ручной слой правок: где-то стереть мусор, где-то дорисовать разрыв, где-то поправить место, где алгоритм слишком самоуверенно увидел дорогу.
В итоговом графе в метаданных остался след этой возни: 1387 ручных штрихов, из них 1153 draw, 155 erase, 79 erasePatch. Это не “я нажал одну кнопку и получил навигацию”. Это скорее “я убедил карту сотрудничать”.
Маска дороги -> скелет -> граф
После очистки маска превращается в скелет. Толстая линия дороги становится тонкой ниткой по центру. Потом эта нитка режется на узлы и ребра. Узел - точка на дороге. Ребро - проезд между двумя точками. У ребра есть длина и класс дороги.
Очистка маски и skeletonize
raw_mask = np.asarray(Image.open(args.mask).convert("L")) > 127
count, labels, stats, _ = cv2.connectedComponentsWithStats(
raw_mask.astype("uint8"), 8
)
mask = np.zeros_like(raw_mask, dtype=bool)
for label in range(1, count):
area = int(stats[label, cv2.CC_STAT_AREA])
if area >= args.min_component_area:
mask[labels == label] = True
skeleton = skeletonize(mask)
paths, skeleton_points, key_points = build_skeleton_paths(skeleton)
Узел и ребро - уже не картинка, а данные для навигации
COST = {
"white": 1.00,
"orange": 1.08,
"orange_dashed": 2.60,
"unknown": 9.50,
}
def add_edge(a: int, b: int, length: float, cls: str) -> None:
edges.append({
"from": nodes[a]["id"],
"to": nodes[b]["id"],
"length": round(length, 3),
"cost": round(length * COST.get(cls, COST["unknown"]), 3),
"road_class": cls,
})
Итоговый road_graph.json получился вполне взрослый: 14561 узел, 18612 ребер, шаг сжатия скелета около 6.595 px. Внутри есть классы дорог: white и orange, есть веса, компоненты связности и данные для runtime-достройки разрывов.
То есть когда на телефоне появляется синяя линия маршрута, за ней не CSS и не SVG-фокус. За ней лежит нормальный граф.
A*: потому что маршрут должен думать
Когда граф появился, понадобился поиск пути. Здесь используется A*. Алгоритм не просто ползает по всем дорогам, а идет по графу с учетом уже накопленной стоимости и примерного расстояния до цели.
На бытовом языке: “я еду по реальным дорогам, но не делаю вид, что вся карта одинаково интересна”.
Укороченный A* по дорожному графу
def shortest_graph_path(graph, start_idx, goal_idx, profile=None):
coords = graph["coords"]
adjacency = graph["adjacency"]
gx, gy = coords[goal_idx]
def heuristic(node_idx: int) -> float:
ax, ay = coords[node_idx]
return math.hypot(ax - gx, ay - gy)
heuristic_weight = float((profile or {}).get("heuristic_weight", 1.0))
open_heap = [(heuristic(start_idx) * heuristic_weight, 0.0, start_idx)]
came_from = {start_idx: None}
best_cost = {start_idx: 0.0}
while open_heap:
_priority, cost_so_far, current = heapq.heappop(open_heap)
if current == goal_idx:
path = [current]
while came_from[path[-1]] is not None:
path.append(came_from[path[-1]])
path.reverse()
return path, cost_so_far
for neighbor, _stored_edge_cost in adjacency[current]:
edge_cost = _route_edge_cost(graph, current, neighbor, profile)
new_cost = cost_so_far + edge_cost
if new_cost < best_cost.get(neighbor, float("inf")):
best_cost[neighbor] = new_cost
came_from[neighbor] = current
heapq.heappush(open_heap, (
new_cost + heuristic(neighbor) * heuristic_weight,
new_cost,
neighbor,
))
Почему веса важнее, чем кажется
Если искать просто кратчайший путь, навигатор быстро начинает вести себя как человек, который “знает короткую дорогу”, а потом ты уже едешь через кусты, канаву и психологическую травму.
Поэтому у разных дорог разные множители. Белая дорога - базовая. Оранжевая почти нормальная. Пунктир и неизвестные участки дороже. Синтетические мостики для ремонта разрывов тоже не бесплатные, иначе алгоритм полюбит заплатки больше настоящих дорог.
Стоимость разных типов дорог
ROAD_CLASS_MULTIPLIERS = {
"white": 1.00,
"orange": 1.08,
"orange_dashed": 2.60,
"synthetic_short": 2.40,
"synthetic_medium": 7.00,
"synthetic_bridge": 34.00,
"unknown": 9.50,
}
Итог серии
На этом этапе проект перестал быть “картой с живой точкой” и стал навигатором. Он умеет искать POI, понимать позицию машины, приклеивать старт и цель к дорожной сети и строить маршрут по графу.
Но дальше вскрылся главный враг. Не UDP, не JavaScript, не телефон. Развязки.
Потому что в 2D две дороги могут пересекаться, а в игре одна идет сверху, другая снизу, третья уходит рампой, и граф такой: “ну вроде все рядом, поехали”.
В следующей серии - почему развязки это маленький филиал ада и почему ближайшая дорога не всегда та, по которой ты едешь.
