BFS: PriorityQueue не становится пустым

Question

Так что я хочу решить проблему, описанную в моем последнем посте: Terrain/Mountain algorithm not working as intended. Копия этой проблемы заключается в следующем:

Я хочу, чтобы создать рельеф местности с горы на него, используя очень простой принцип, показанный на этой высоте отображения:

0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 1 2 1 0 0 0 0 
0 0 0 1 2 3 2 1 0 0 0 
0 0 1 2 3 4 3 2 1 0 0 
0 0 0 1 2 3 2 1 0 0 0 
0 0 0 0 1 2 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 

Она начинается в случайной точке с height = 4, а затем постепенно уменьшает его соседей.

Рекурсивная идея проста, я начинаю точку, рекурсия в верхнюю/нижнюю/левую/правую сторону с помощью height - 1 (в этом примере), и только если не обнаружено, я устанавливаю их значения.

Так что я пошел вперед и реализовали его с BFS:

private void createMountain(final float[][] heightMapping, final float startHeight) { 
    boolean[][] traversed = new boolean[width][depth]; 
    boolean positive = (startHeight >= 0f); 
    int x = random.nextInt(width); 
    int z = random.nextInt(depth); 
    PriorityQueue<QueueElement> priorityQueue = new PriorityQueue<>((o1, o2) -> (int)Math.signum(o1.height - o2.height)); 
    priorityQueue.offer(new QueueElement(x, z, startHeight)); 
    while (!priorityQueue.isEmpty()) { 
     QueueElement current = priorityQueue.poll(); 
     if (current.x < 0 || current.x >= width || current.z < 0 || current.z >= depth) { 
      continue; 
     } 
     if (traversed[current.x][current.z]) { 
      continue; 
     } 
     if ((positive && current.height <= 0f) || (!positive && current.height >= 0f)) { 
      continue; 
     } 
     heightMapping[x][z] = current.height; 
     priorityQueue.offer(new QueueElement(x, z - 1, calculateNewHeight(current.height, positive))); 
     priorityQueue.offer(new QueueElement(x, z + 1, calculateNewHeight(current.height, positive))); 
     priorityQueue.offer(new QueueElement(x - 1, z, calculateNewHeight(current.height, positive))); 
     priorityQueue.offer(new QueueElement(x + 1, z, calculateNewHeight(current.height, positive))); 
    } 
} 

private class QueueElement { 
    public int x, z; 
    public float height; 

    public QueueElement(final int x, final int z, final float height) { 
     this.x = x; 
     this.z = z; 
     this.height = height; 
    } 
} 

private float calculateNewHeight(final float startHeight, final boolean positive) { 
    float delta = startHeight/maxDecayFactor; 
    return (positive) ? startHeight - delta : startHeight + delta; 
} 

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

Единственная реальная подсказка, которую я имею в настоящее время, состоит в том, что priorityQueue.size() продолжает увеличиваться на 3 все время.
Кто-нибудь имеет представление о том, что происходит?

Обновление: Даже после исправлений он по-прежнему не работает должным образом.

0.6 0.5 0.4 0.3 0.3 0.2 0.2 0.1 0.1 0.1 0.1 0.1 0.0 0.0 0.0 0.0 
0.8 1.0 1.2 1.6 1.9 2.4 3.0 3.8 4.7 5.9 7.4 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 

Что может быть неправильным? Является ли теперь PriorityQueue бесполезным?

Answer 1

Вы забыли установить traversed[x][z] = true; при опросе нового элемента.
Убедитесь, что вы делаете это после того как запрос if (traversed[current.x][current.z]) ...

Кроме того, в качестве примечания, для реализации - это Queue будет лучшей идеей, я думаю. (когда я написал PriorityQueue, будет лучше, если бы у меня было несколько пиков - что, похоже, не для вас, я думаю, что простая Queue будет лучше).