java - BFS: PriorityQueue not getting empty -
so want solve problem described in last post: terrain/mountain algorithm not working intended. copy of problem following:
i want create terrain mountain on it, using basic principle, shown 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 @ random point height = 4, , gradually decreases amonst neighbours.
the recursive idea simple, start point, recurse top/down/left/right height - 1 (in example), , if not encountered yet, set values.
so went ahead , implemented 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 code never stops, tried debugging few times, either got no useful result, or terrain flat.
the real clue have priorityqueue.size() keeps increasing 3 whole time.
have idea of going on?
update: after fixes, still not working 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 possibly wrong? priorityqueue messing things up?
you forgot set traversed[x][z] = true; when poll new element.
make sure after query if (traversed[current.x][current.z]) ...
also, side note, implementation - queue better idea think. (when wrote priorityqueue better had multiple peaks in mind - seems not case you, think simple queue best).
Comments
Post a Comment