I came across this funky color-cycling Prim’s Algorithm Observable notebook and I’m trying to port it to Processing Java.
But surprise surprise it’s not working.
So I’ve annotated the ported code with my interpretation of the JavaScript and the Java equivalent (in case my interpretation of any part is wrong – I’m not superbly familiar with JavaScript).
The first bit (a port of cells = {...}) seems the work; the second bit distance = {...} doesn’t (it only sets a couple values of the array!)
Can anyone spot anything?
import java.util.PriorityQueue;
import java.util.Arrays;
// https://observablehq.com/@mbostock/prims-algorithm-v
static final int E = 1 << 3;
static final int W = 1 << 2;
static final int S = 1 << 1;
static final int N = 1 << 0;
void setup() {
size(800, 800);
int[] cells = new int[width*height];
PriorityQueue<Entry> heap = new PriorityQueue<Entry>(); // I *think* this should be equivalent to js FlatQueue()
heap.add(new Entry(0, N, random(1)));
heap.add(new Entry(0, E, random(1)));
while (!heap.isEmpty()) {
Entry edge = heap.poll(); // pop here, not in while() check -- equivalent, right?
int i0 = edge.index;
int i1;
int d0 = edge.direction;
int d1;
int x0 = i0 % width;
int x1;
int y0 = i0 / width | 0; // I think "| 0" is to get javascript integer divsion; retained here in Java for now
int y1;
if (d0 == N) {
i1 = i0 - width;
x1 = x0;
y1 = y0 - 1;
d1 = S;
} else if (d0 == S) {
i1 = i0 + width;
x1 = x0;
y1 = y0 + 1;
d1 = N;
} else if (d0 == W) {
i1 = i0 - 1;
x1 = x0 - 1;
y1 = y0;
d1 = E;
} else {
i1 = i0 + 1;
x1 = x0 + 1;
y1 = y0;
d1 = W;
}
try {
if (cells[i1] == 0) {
cells[i0] |= d0;
cells[i1] |= d1;
if (y1 > 0 && cells[i1 - width] == 0) {
heap.add(new Entry(i1, N, random(1)));
}
if (y1 < height - 1 && cells[i1 + width] == 0) {
heap.add(new Entry(i1, S, random(1)));
}
if (x1 > 0 && cells[i1 - 1] == 0) {
heap.add(new Entry(i1, W, random(1)));
}
if (x1 < width - 1 && cells[i1 + 1] == 0) {
heap.add(new Entry(i1, E, random(1)));
}
}
}
catch (Exception e) {
e.printStackTrace(); // catch out of bounds error -- it goes out of bounds for just 1 cell (the last one?) (for some reason)
}
}
// SOMETHING IN THIS BIT ISN'T WORKING (almost everything in distance s null)
Integer[] distance = new Integer[width*height]; // Use Integer (rather than int) array so initial values are null
ArrayList<Integer> frontier = new ArrayList<Integer>();
frontier.add((height - 1) * width);
distance[frontier.get(0)] = 0;
for (int d = 0; d < frontier.size(); ++d) {
ArrayList<Integer> frontier1 = new ArrayList<Integer>();
for (int i = 0, n0 = frontier.size(); i < n0; ++i) {
int i0 = frontier.get(i);
int i1;
/**
the following is my interpretation of "if (cells[i0] & E && distance[i1 = i0 + 1] === undefined)" to Java.
"cells[i0] & E" is bitwise ANDing I think
therefore the "&&" between each clause is casting the first clause to a boolean,
this is only true when the answer of the AND is 1 (1 is the only numerical truthy I believe)
**/
//int i1 = i0 + 1; // assign here rather than inline
if (((cells[i0] & E)==1) && distance[i1 = i0 + 1] == null) {
distance[i1] = d;
frontier1.add(i1);
}
if (((cells[i0] & W)==1) && distance[i1 = i0-1] == null) {
distance[i1] = d;
frontier1.add(i1);
}
if (((cells[i0] & S)==1) && distance[i1 = i0+width] == null) {
distance[i1] = d;
frontier1.add(i1);
}
if (((cells[i0] & N)==1) && distance[i1 = i0-width] == null) {
distance[i1] = d;
frontier1.add(i1);
}
}
frontier = new ArrayList<Integer>(frontier1);
}
loadPixels();
for (int i = 0; i < pixels.length; i++) {
if (distance[i] != null) {
println(distance[i].intValue()); // only 2 values are not null!
}
}
updatePixels();
}
void draw() {
background(250, 0, 0); // not bothering with color mapping (the last part) yet
}
class Entry implements Comparable<Entry> {
int index; // value
int direction; // value
float value; // location in heap
public Entry(int index, int direction, float value) {
this.index = index;
this.direction = direction;
this.value = value;
}
public int compareTo(Entry other) {
return Float.compare(value, other.value);
}
}
I remembered this today and asked ChatGPT to reimplement the problematic distance() function in Java. It did so marvellously, so I was able to complete the port😁.
