Hi! I’m currently tackling a challenge involving image path optimization and could use some assistance refining my algorithm. Picture an image represented as a 1D array of integers, with each pixel holding an “energy level” value. The top-left pixel of the image is indexed at (0,0).

My goal is to compute the shortest path, measured by energy, from the top to the bottom of the image. The path may start at any x-coordinate. Rather than resorting to brute force, I’m exploring a more algorithmic approach. I envision the path progressing downward (incrementing the y-coordinate), with options to move left, straight, or right-down at each step.

Here’s the outline of my algorithm:

Start at the top-left corner (0,0).

Determine the next best step by considering a lookahead distance denoted by “lookForward”.

Return -1, 0, or 1 for left, straight, or right directions.

Progressively find the optimal path by iteratively moving down the image.

I’ve already implemented most of the algorithm, but I’m currently stuck on refining the “lookForward” component. I’m seeking help with the “PathFinder.getBestStep(x, y, lookForward);” method. I know that recursion with methods is necessary to go through each step and find the best path, but despite my efforts, I haven’t been able to get it to work.

Here’s a snippet of my current code:

for (int x = 0; x < imageWidth; x++) {
    int xOffset = 0;
    for (int y = 0; y < imageHeight; y++) {
        final int bestStep = PathFinder.getBestStep(x + xOffset, y, 5); // "lookForward" distance is set to 5.

        if (bestStep == -1) {
            // Move one step left and one step down
            xOffset -= 1;
        }
        if (bestStep == 0) {
            // Move one step down
        }
        if (bestStep == 1) {
            // Move one step right and one step down
            xOffset += 1;
        }
    }
}

I kinda have this PathFinder class so far:

public class PathFinder {

    public final int[] energyMap; // energyMap is the image.
    public final int width; // Width of image (energyMap).
    public final int height; // Height of image (energyMap).
    public final int lookForward; // Amount of steps, it will lookForward.

    public PathFinder(int[] energyMap, int width, int height, int lookForward) {
        this.energyMap = energyMap;
        this.width = width;
        this.height = height;
        this.lookForward = lookForward;
    }

    // Return the -1, 0 or 1, for left, middle or right, step movement.
    public int getBestStep(final int x, final int y) {
        final List<Integer> bestPath = getBestPath(x + y * width, new ArrayList<>());
        return bestPath.getFirst();
    }

    // Get the shortest path, (based on shortest energy level)
    public List<Integer> getBestPath(final int index, List<Integer> currentPath) {
        // Don't really know what to do here.
        return null;
    }
}

An visualization of what I want:
”
Let’s consider an image that is 10×10, where each pixel represents either 1 or 0 for simplicity:

1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1

We can observe a clear path down the image where the “energy” is low. My objective is to identify and follow that path. However, the images I’ll be dealing with could be as large as 4000×4000, if not larger. Attempting to brute force the absolute best path would consume a significant amount of time. Hence, I aim to implement a method that only calculates a few steps ahead.

While processing a single 4000×4000 image wouldn’t be time-consuming, I might need to repeat this process multiple times, possibly up to 1000 times. It’s important to note that absolute precision is unnecessary; I’m primarily interested in identifying roughly the best path. I can adjust the “lookForward” variable to enhance the quality of the path determination.
“

Any help or guidance would be greatly appreciated!

At the post above! I’ve described a bunch of things I’ve tried and what I’m up to ????