Поиск пути в Java

Question

Допустим, я использую массивы для построения моей игровой карты, используя это:

{ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1 },
{ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 1 }

У меня есть ArrayList<> номеров плиток, которые ЗАБЛОКИРОВАНЫ, а другие НЕ ЗАБЛОКИРОВАНЫ. Я могу проверить, выполнив blocked(X,Y), и он вернет true или false, проверив X и Y этой плитки на currentMap, а затем он увидит, находится ли эта плитка в BLOCKED ArrayList<>. В любом случае, каков лучший способ поиска пути здесь?

Answer 1

Вы можете использовать алгоритмы поиска по графику, например Поиск в ширину .Реализации вы можете найти в Google, есть много примеров.

Answer 2

Я думаю, под поиском пути вы подразумеваете, что хотите найти кратчайший путь от ячейки (x1, y1) к ячейке (x2, y2). Здесь нужна дополнительная информация. Как определить соседние ячейки - то есть я могу перейти от одной ячейки к ее 4 соседям или 6 соседям, включая диагональное движение? Одинакова ли стоимость перемещения в какую-либо ячейку или она варьируется в зависимости от типа ячейки, или это перемещение строки / столбца или диагональное перемещение?

Предполагая, что стоимость перемещения одинакова для всех ячеек, и каждая ячейка смежна с 4 ячейками, с которыми она разделяет ребро, это в основном простая задача поиска кратчайшего пути в простом невзвешенном графике. Для этого вы можете использовать поиск в ширину . Узлами графа являются ячейки, и каждая ячейка (за исключением тех, которые находятся в верхнем и нижнем ряду и левом и крайнем правом столбцах) имеет четыре ребра (по одному для каждой соседней ячейки). Когда мы посещаем каждый узел, мы просто пропускаем заблокированные узлы.

псевдокод:

shortest path(start,end, blocked):
   cost=map of node:int
   visited=set of nodes
   dx=array {0,1,0,-1}
   dy=array {1,0,-1,0}
   Q=queue of nodes
   cost[start]=0
   add start to Q
   while Q is not empty:
       node=remove top from Q
       for i=0 until 4:
           next=new node with next.x=node.x+dx[i], next.y=node.y+dy[i]
           if (next is a valid node) and (next is not in visited) and (next is not in blocked):
              cost[next]=cost[node]+1
              add next to visited
              add next to Q
    if end is in visited:
       return cost[end]
    else:
       return -1