Алгоритм генерации случайного пути с заданным размером пути

Question

Я пытаюсь сгенерировать путь внутри матрицы с определенным количеством элементов внутри выбранного пути.

Я могу создать из точки A в точку B без проблем, используя:

step(int[] s, int[] e) //start - end
{
   int d = delta(s, e);
   if (d > 1)
   {
      //spread around
      List<int[]> pts = new List<int[]>();
      pts.Add(new int[2] { s[0] -1, s[1]    }); //left
      pts.Add(new int[2] { s[0] +1, s[1]    }); //right
      pts.Add(new int[2] { s[0]   , s[1] +1 }); //top
      pts.Add(new int[2] { s[0]   , s[1] -1 }); //bot

      //remove out of bounds points
      List<int[]> goodPoints = new List<int[]>();
      foreach (var p in pts)
      {
         if (checkValidBoundries(p))
         {
            goodPoints.Add(p);
         }
      }

      //calculate lowest deltas
      int lowestDelta = int.MaxValue;
      int[] bestFit = new int[2];
      foreach (var p in goodPoints)
      {
         int localDelta = delta(p, e);
         if (localDelta == lowestDelta) //local shuffle
         {
            if (await coinFlip())
            {
               bestFit = p;
            }
         }
         else if (localDelta < lowestDelta)
         {
            lowestDelta = localDelta;
            bestFit = p;
         }
      }

      matrix.setValue(bestFit[0], bestFit[1]);
      step(bestFit, e);
   }
}

Этот код будет рекурсивно повторяться до тех пор, пока путь не закончится. Вот так я получаю кратчайший путь.

Итак, мой вопрос: как я могу определить количество элементов в пути?

Например: от A до B этот алгоритм дает мне6 элементов, независимо от пути, он всегда будет использовать самую низкую дельту между точками. Но если я хочу, чтобы этот путь был длиной 7, 8 элементов?

Я попытался выбрать один элемент за раз из пути и заблокировать его, чтобы при следующем запуске он не считал его действительным, но он продолжает работатьневерно.

Новый путь может быть случайным, нет проблем. Я просто хочу контролировать количество элементов в «лучшем пути».

Любая помощь? Заранее спасибо

Answer 1

Кажется, вы хотите найти ближайший путь между двумя точками A и B в сетке без каких-либо препятствий. Движение должно быть в одном из четырех основных направлений. Затем вы хотите удлинить этот путь до определенной длины.

Во-первых, если нет препятствий, вам не нужно прощупывать все направления. Например, если B находится в 4 шагах к востоку и в двух шагах к северу от A, просто выбирайте шаги из {E, E, E, E, N, N} случайным образом (или перетасовывайте массив) до тех пор, пока не прибудете.

Наименьшее расстояние d * между A и B - это манхэттенское расстояние:

d * = | Ax - Bx |+ | Ay - By |

Если вы представляете, что сетка окрашена как шахматная доска, расстояние между A и B будет четным, если оба цвета имеют одинаковый цвет, а в другом случае - нечетное. Это относится не только к наименьшему расстоянию, но и к расстоянию любого действительного пути между A и B. Следовательно, вы можете получить только расстояния d * + 2 · k.

Вы можете сделать более длинные пути с помощьюдобавив небольшие «объезды» к вашему идеальному пути:

        · · · · · · · ·            · · · · · · · ·            · · · · · · · ·
        · · · · · · B ·            · · · · · · B ·            · · · · · · B ·
        · · · · ┌───┘ ·            · u · · ┌───┘ ·            · · · · ┌───┘ ·
        · · · · │ · · ·            · ╒═╕ · └─╖ · ·            · · · ╔═╡ · · ·
        · ┌─────┘ · · ·            · │ └─────╜ v ·            · ┌───╜ ╧ w · ·
        · A · · · · · ·            · A · · · · · ·            · A · · · · · ·
        · · · · · · · ·            · · · · · · · ·            · · · · · · · ·

Каждый из «вмятин» u и v добавляет два сегмента к вашему пути. Когда вы делаете вмятины, будьте осторожны, чтобы не сделать вмятину, где уже есть часть пути: у вмятины есть часть пути, свернутая на себя, так что есть тупик. Вы можете удалить тупик, но путь будет иметь ту же длину, что и раньше.

Как реализовать все это, оставлено в качестве упражнения для читателя. :)