Кратчайший путь Java - PullRequest
Новая
       2

Кратчайший путь Java

0 голосов
/ 23 февраля 2012

Я пытаюсь сделать небольшую игру Tower Defender на Java. У меня есть сетка, состоящая из Point2D.Double массива с именем:

FieldArr [ч] [v]

h представляет горизонтальные поля, v вертикальные вертикальные поля

это делает сетку вот такой 

+ + + + + + +
S + X + + + +
+ + + X + + +
+ X + + + + F
+ + X + + + +

S обозначает начало, F обозначает конец, X обозначает башни

сейчас я хочу рассчитать кратчайший маршрут, но я не знаю, как начать этот маршрут

Башни имеют следующие переменные для местоположения: HorizontalNr и VerticalNr.

для краски я делаю тогда: 

public void paint(Graphics2D g2) {
    int Xpos = HorizontalNr * playfield.getSquarewidth() + playfield.GetinitialXPos();
    int Ypos = VerticalNr * playfield.getSquarewidth() + playfield.GetinitialYPos();
    g2.fillRect(Xpos, Ypos, 50, 50);
}

У кого-нибудь есть какие-нибудь советы, как мне сделать класс противника, чтобы не было проблем с алгоритмом? и / или есть советы о том, как рассчитать кратчайший путь?

уже спасибо гр киви

Ответы [ 3 ]

4 голосов
/ 23 февраля 2012

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

Например, простой и эффективный алгоритм - это алгоритм Дейкстры . Из Википедии:

  1. Пусть узел, с которого мы начинаем, называется начальным узлом. Пусть расстояние узла Y будет расстоянием от начального узла до Y. Алгоритм Дейкстры назначит некоторые начальные значения расстояния и постарается улучшить их шаг за шагом. Присвойте каждому узлу предварительное значение расстояния: установите его равным нулю для нашего начального узла и равным бесконечности для всех остальных узлов.
  2. Пометить все узлы как непосещенные. Установите начальный узел как текущий. Создайте набор не посещенных узлов, называемый не посещенным набором, состоящий из всех узлов, кроме начального узла.
  3. Для текущего узла рассмотрите все его не посещенные соседи и вычислите их предварительные расстояния. Например, если текущий узел A помечен с предварительным расстоянием 6, а ребро, соединяющее его с соседом B, имеет длину 2, то расстояние до B (через A) будет 6 + 2 = 8. Если это расстояние меньше, чем ранее записанное предварительное расстояние B, перезапишите это расстояние. Несмотря на то, что сосед был осмотрен, он не помечен как посещенный в настоящее время и остается в непосещенном наборе.
  4. Когда мы закончим, рассматривая всех соседей текущего узла, отметим текущий узел как посещенный и удалим его из невидимого набора. Посещенный узел никогда не будет проверен снова; записанное в настоящее время расстояние является окончательным и минимальным.
  5. Если узел назначения был отмечен как посещенный (при планировании маршрута между двумя конкретными узлами) или если наименьшее предварительное расстояние среди узлов в невидимом наборе равно бесконечности (при планировании полного обхода), остановитесь. Алгоритм завершен.
  6. Установите не посещаемый узел, помеченный наименьшим предварительным расстоянием, как следующий «текущий узел» и вернитесь к шагу 3.
2 голосов
/ 09 октября 2012

если вы хотите избежать башен, то вы ищете евклидову дорожку от начала до конца, которая разрешима с кратчайшим путем ала djkstra.

1 голос
/ 23 февраля 2012

Как сказал Марк, это проблема кратчайшего пути, которую можно легко и эффективно решить.

Обратите внимание, что поскольку ваша задача не взвешена, вы можете использовать здесь BFS , что довольно легко реализовать, а также гарантирует поиск кратчайшего пути для невзвешенных графиков.

Псевдокод для BFS: 

findShortestPath(source,target):
  queue<- new queue
  visited <- {}
  Map<point,point> parents <- empty map
  queue.push(source)
  while (queue.empty() == false): 
     current <- queue.takeFirst()
     if (current.equals(target)):
         extract the path from source to destination using the map parents(*)
         return
     visited.add(current)
     for each p such that p and current are neighbors: //insert neighbors to queue
          if p is not in visited: 
                if (p is not an obstacle):
                   queue.push(p)
                   parents.put(p,current) //current is the parent of p

(*) Извлечь путь из карты просто: просто следуйте current <- parent.get(current), пока не получите null, таким образом вы извлечете точный путь, который будете использовать.

Обратите внимание, что даже более быстрое решение [в большинстве случаев] будет A * с эвристикой манхэттенского расстояния , но реализовать его гораздо сложнее.

...