Как построить граф по матрице?

Question

[alexeysikora]

У меня есть матрица, которая представляет собой карту игры. Выглядит эта матрица примерно так:

[
        '.....',
        '..WW.',
        '.....'
]

суть элементов матрицы довольна проста:
'.' - доступное для посещения поле
'W' - недоступное для посещения поле

Мне нужно построить неориентированный граф этой карты, где вершинами будут являться доступные поля, соединённые рёбрами, а весом рёбер будет выступать расстояние между этими полями (X), для того чтобы после построения этого графа выбрать в нём 2 вершины и найти между ними кратчайший путь (игрок из точки А должен добраться до цели Б по кратчайшему пути). Двигаться по карте можно только по горизонтали и по вертикали.

Никак не могу понять какой принцип мне использовать для построения такого графа.

Answer 1

[Alexandroppolus]

Зачем строить граф? У каждой ячейки есть только соседи сверху-снизу-слева-справа.
А главное, какой может быть вес у ребер? Если соединены только смежные по стороне ячейки, то все ребра одинакового веса.
https://ru.wikipedia.org/wiki/A* - посмотри вот такую штуку

Answer 2

[Wataru]

а весом рёбер будет выступать расстояние между этими полями. для того чтобы после построения этого графа выбрать в нём 2 вершины и найти между ними кратчайший путь ... Двигаться по карте можно только по горизонтали и по вертикали.

Это какой-то бред. Начало фразы подразумевает, что ребра есть между всеми парами вершин, продолжение говорит, что все ребра длины 1 между соседними клетками. Я предполагаю что тут именно второй вариант.

Во-первых, занумеруйте все клетки. Подойдет простая формула вроде i+m*j

Вот у вас уже есть n*m вершин в графе. Теперь добавьте ребра. Для каждой клетки (два цикла) посмотрите 4 соседние клетки. Если обе клетки - ., то добавьте из текущей клетки ребро в соседнюю.

Соседей удобно перебирать, если завести константные массивы для смещений:

const int dx[4]= {1, 0, -1, 0};
const int dy[4]= {0, 1, 0, -1};

Тогда для клетки (i, j) можно перебрать всех соседей одним циклом на 4 итерации - (i+dx[k], j+dy[k]). Надо только не забыть проверить на выход за границы матрицы.

Ну и вам надо написать функцию типа AddEdge(int u, int v) которая будет в удобную для вас структуру данных добавлять ребра. Граф удобно хранить в виде списков смежности. На C++ это можно сделать просто std::vector<std::vector<int>> и добавлять соседей через vector::push_back. Это на практике работает быстрее всяких связных списков.

И у вас будет три вложенных цикла - внешние по всем клеткам, а внутренний по четырем направлениям. Внутри вы проверяете, что сосед по этому направлению есть и между клетками можно пройти. В этом случае вызывайте AddEdge.

А можно вообще граф не строить. Берете ваш алгоритм поиска кратчайшего пути (BFS, Dijkstra или A*) и там везде, где перебираются соседи одной вершины, вставляете код проверки четырех направлений через dx/dy. Вершины можно или нумеровать их координатами, и тогда все массивы пометок будут двумерными, или можно использовать формулу u = i+j*m, (i,j) = (u%m, u/m) для преобразования координат в номер вершины и назад.

А еще есть всякие алгоритмы, которые работают сильно быстрее за счет использования того факта, что у вас не произвольный граф, а сетка в матрице. Jump Point Search - один из таких алгоритмов. В нем граф умышленно не строится и работа идет непосредственно в матрице.