Following a trail of pixels

Programming Questions

conorzoho

in Programming Questions • 1 year ago

I load an image that is a simple 3 colour one:

color 0 (black) represents an empty space, 255 (white) represents a starting point for a trail and 149 (grey) represents a trail.

I scan the image at the start to find any white pixels and make an array of this amount called crayonPoints. This is a PVector that holds the position of 'crayons' and they begin on these starting points. White pixels are isolated one offs.

The image is drawn in such a way that there is always a grey pixel line leading off from these initial white pixels that makes a path. It can change direction in any of the 8 directions around the current position but never junctions. My code searches the 8 pixels around the current location (crayonPoints) and finds the next touching grey pixel. Ruling out that it is one we were already came from, or the current location, it changes the coordinates of crayonPoints to this new location. Repeating this should follow a trail.

However, what I'm experiencing is the pixels moving diagonally around the black space and then bouncing off any grey pixels they encounter:

void searchPixelNeighbours(int i) {
// The trail in the image is pixels of grey of value 149.
// Search in a circle (neighbourhood) around the currentLocation
PVector nextPoint = new PVector(0,0);
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
int xCoord = int(crayonPoints[i].x - 1 + x);
int yCoord = int(crayonPoints[i].y - 1 + y);
if (previousPoints[i].x != xCoord && previousPoints[i].y != yCoord) {
// Confirms this was not our last point. We don't want to backtrack
if (crayonPoints[i].x != xCoord && crayonPoints[i].y != yCoord) {
// Confirms this is not our current point.
if (red(lightMap.pixels[(yCoord * lightMapWidth) + xCoord]) == red(149)) {
// Next trail pixel found!
nextPoint = new PVector(xCoord, yCoord);
}
}
}
}
}
previousPoints[i] = crayonPoints[i].get();
crayonPoints[i].set(nextPoint);
}

I'm completely stumped. I've rearranged this several times with different results but nothing close to success.

Replies(10)

amnon.owed

Re: Following a trail of pixels

1 year ago

The problem is probably line 16:

if (red(lightMap.pixels[(yCoord * lightMapWidth) + xCoord]) == red(149)) {

should be

if (red(lightMap.pixels[(yCoord * lightMapWidth) + xCoord]) == 149) {

In general, using println() often helps a lot when debugging code.

conorzoho

Re: Following a trail of pixels

1 year ago

Aha. That's a start. Thanks amnon.owed. I probably did that after hours of rephrasing everything I could think of. Also, I just realised my conditions were too stringent and I need to replace a lot of ANDs with ORs. I'm finally making progress.

I've a huge amount of printlns that I ommited. There were just too many to know what was useful for clarity to a stranger.

conorzoho

Re: Following a trail of pixels

1 year ago

This is my progress. Right now, I am getting some tracing of the trails going on but am having hit and miss luck with turning corners. I have four test trails all with 90 degree turns (no 45 degree tested yet) and sometimes the trace is turning the corner fine and other times it is getting stuck on corners and not progressing.

void searchPixelNeighbours(int i) {
// The trail is pixels of grey at (149).
// Search in a circle around the currentLocation
PVector nextPoint = new PVector(0,0);
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
int xCoord = int(crayonPoints[i].x - 1 + x);
int yCoord = int(crayonPoints[i].y - 1 + y);
if (previousPoints[i].x != xCoord || previousPoints[i].y != yCoord) {
// Confirms this was not our last point. We don't want to backtrack
// This will also double up as referring to the starting point as our previous point and current point
if (crayonPoints[i].x != xCoord || crayonPoints[i].y != yCoord) {
// Confirms this is not our current point.
if (red(lightMap.pixels[(yCoord * lightMapWidth) + xCoord]) == 149) {
// Next trail pixel found!
nextPoint = new PVector(xCoord, yCoord);
}
}
}
}
}
previousPoints[i] = crayonPoints[i].get();
if (nextPoint.x != 0) {
crayonPoints[i].set(nextPoint);
}
}

conorzoho

Re: Following a trail of pixels

1 year ago

Narrowing it down, the above code seems to work everything other than a trail turning 90 degrees left. It traces fine if the trail is down, right or up, but if it goes left it gets stuck. Turning left is x - 1 so I'm trying to see if that's somehow significant.

conorzoho

Re: Following a trail of pixels

1 year ago

teddyboy - I was just about to acknowledge that I knew about :

After it finds the point the loop still continues so if there is more than one point it will respond to the last one it crossed.

... and that I had ruled out any points that were the direction we came from or the current pixel, so the only remaining possibility is the next one we need to go to. Then it dawned on me that it isn't the simple when turning 90 degree corners. So thankyou for making me think about that one again. To clarify: when approaching a 90 degree turn, there's a moment when there are 2 possible pixels that can be the next pixel. I need to do some code that checks for trail pixel at x=1 if x=0 or x=2. If tit finds one, it means we're at a corner and to choose x=1 as the next pixel.

While doing that, I'm having no luck with 'continue'. That was a nice suggestion in the code but if I replace {} with it, the code does nothing. I had an idea that the conditions would need to be inverted to make continue work but I still got nothing. Perhaps it's showing some flaw in my code.

teddybot

Re: Following a trail of pixels

1 year ago

if (previousPoints[i].x != xCoord || previousPoints[i].y == yCoord) continue;
if (crayonPoints[i].x != xCoord || crayonPoints[i].y == yCoord) continue;

should be

if ( (previousPoints[i].x == xCoord) && (previousPoints[i].y == yCoord) ) continue;
if ( (crayonPoints[i].x == xCoord) && (crayonPoints[i].y == yCoord) ) continue;

conorzoho

Re: Following a trail of pixels

1 year ago

That fixed the continue problem nicely, thanks. Also, many thanks teddybot for having a go at this. It's working now and I'd still be several more days at it without your help. Genuinely appreciated.

I couldn't quite get my head around your code in parts but fed parts of it into what I was doing and this is now what's working (if a little less pretty):

void searchPixelNeighbours(int i) {
// The trail is pixels of grey at (149).
// Search in a circle around the currentLocation
int gotpoint=0;
PVector nextPoint = new PVector(0,0);
for (int z = 0; z < 2; z++) { // z runs through all 9 pixels twice. Once for up/down. Once for diagonals.
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (gotpoint == 0) {
int xCoord = int(crayonPoints[i].x - 1 + x);
int yCoord = int(crayonPoints[i].y - 1 + y);
if ( (previousPoints[i].x == xCoord) && (previousPoints[i].y == yCoord) ) continue; // Confirms this is not our last point.
if ( (crayonPoints[i].x == xCoord) && (crayonPoints[i].y == yCoord) ) continue; // Confirms this is not our current point.
if (red(lightMap.pixels[(yCoord * lightMapWidth) + xCoord]) == 149) { // tells us the pixel is a trail (grey) pixel
if (x==1 && y==0) {gotpoint=1;}
if (x==0 && y==1 && gotpoint==0) {gotpoint=1;}
if (x==2 && y==1 && gotpoint==0) {gotpoint=1;}
if (x==1 && y==2 && gotpoint==0) {gotpoint=1;}
// No up/down/sideways point found, so find diagonal point
if (z==1 && gotpoint == 0) {
if (x==0 && y==0 && gotpoint==0) {gotpoint=1;}
if (x==2 && y==0 && gotpoint==0) {gotpoint=1;}
if (x==0 && y==2 && gotpoint==0) {gotpoint=1;}
if (x==2 && y==2 && gotpoint==0) {gotpoint=1;}
}
if (gotpoint==1) {
nextPoint = new PVector(xCoord, yCoord);
}
}
}
}
}
}
previousPoints[i] = crayonPoints[i].get();
if (nextPoint.x != 0) {
crayonPoints[i].set(nextPoint);
journeyState[i] = 0;
} else {
journeyState[i] = 1;
}
}

Also, just to note: I'm aware that running through the 9 neighbour pixels twice isn't the most efficient way of doing things speed-wise as you can define which of the pixels are diagonal already. However, it hasn't cost a visible speed difference in what I'm doing and is the first thing I've gotten to work so far that only attempts to see if a neighbour is a diagonal pixel after fully exhausting the fact that any given pixel, of nine, is not diagonally connected.

teddybot

Re: Following a trail of pixels

1 year ago

In the following case it may be necessary to store the last two locations you have been.
Where # is your path and _ is your current location.
#XX
#_X
XX#

Here is one that checks the last two points, has a line that brings it back and will repeat:
float c=0;
int x=100, y=100;
int lastx1=0, lasty1=0;
int lastx2=0, lasty2=0;
int gotpoint=0;
int checkx, checky;

void setup()
{
size(640, 480);
stroke(0, 0, 0);
strokeWeight(1);
}

void draw()
{
fill(255, 255, 255);
rect(0, 0, 640, 480);
fill(100, 255, 100);
line(100, 100, 150, 100);
line(150, 100, 150, 150);
line(150, 150, 100, 150);
line(100, 150, 100, 200);
line(100, 200, 220, 250);
line(220, 250, 300, 300);
line(300, 300, 320, 350);
line(300, 300, 280, 350);
line(280, 350, 320, 360);
rect(320, 350, 100, 100);
loadPixels();

gotpoint=0;
setpoint(1, 0);
setpoint(-1, 0);
setpoint(0, 1);
setpoint(0, -1);
setpoint(-1, -1);
setpoint(1, 1);
setpoint(1, -1);
setpoint(-1, 1);

if (gotpoint==0) {
    lastx1=lasty1=0;
    fill(200, 0, 0);
}
else fill(0, 0, 200);

ellipse(x, y, 20, 20);
}

void setpoint(int offsetx, int offsety)
{
if (gotpoint == 1) return;
checkx = x+offsetx;
checky = y+offsety;
if ((checkx==lastx1) && (checky==lasty1)) return;
if ((checkx==lastx2) && (checky==lasty2)) return;

//c=green(pixels[checkx+(checky*width)]);
//if (c==0) {

//Reference states this method is faster than red,blue,green functions
if ((pixels[checkx+(checky*width)] & 0xFF)==0) {
    lastx2=lastx1;
    lasty2=lasty1;
    lastx1=x;
    lasty1=y;
    x=checkx;
    y=checky;
    gotpoint=1;
}
}

conorzoho

Re: Following a trail of pixels

1 year ago

Nicely done. I've a lot to learn yet.

teddybot

Re: Following a trail of pixels

1 year ago

Thanks it is updated so now the object returns back to the start and repeats by clearing the last saved position. A line intersecting at a certain angle or a group of vertexes controls where the object goes. If the object has info for which order it is processing the rules you are able to make a game where you click on the object and that affects which path it will take.
For example your goal would be to draw a line somewhere to try to get the objects back or you send them off to gather, return and build something.

Top Reply