BFS: PriorityQueue not getting empty

Question

So I want to solve the problem described in my last post: Terrain/Mountain algorithm not working as intended. A copy of the problem is the following:

I want to create a terrain with a mountain on it, using a very basic principle, shown by this height mapping:

0 0 0 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

It starts at a random point with height = 4, and then gradually decreases it amonst the neighbours.

The recursive idea is simple, I start a point, recurse to the top/down/left/right with height - 1 (in this example), and only if not encountered yet, I set their values.

So I went ahead and implemented it with a 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;
}

Now the code never stops, I tried debugging it a few times, but either got no useful result, or a terrain that was completely flat.

The only real clue I have currently is that the priorityQueue.size() keeps increasing by 3 the whole time.
Does anyone have an idea of what is going on?

Update: Even after the fixes, it is still not working as intended.

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  

What could possibly be wrong? Is the PriorityQueue now messing things up?

Answer 1

You forgot to set traversed[x][z] = true; when you poll a new element.
Make sure you do it AFTER you query if (traversed[current.x][current.z]) ...

Also, as a side note, for your implementation - a Queue will be a better idea I think. (when I wrote a PriorityQueue will be better I had multiple peaks in mind - which seems not to be the case for you, I think a simple Queue will be best).