CODEWITHSUNDEEP
algorithmpath-findinga-star
Greyshack
Greyshack

Reputation: 1971

Find shortest path using A Star with difficult restriction

I need to solve the following problem: I have a grid in which you can move in 8 directions, N,S,E,W,NE,NW,SE,SW.

Moving orthogonally costs always 1. Moving diagonally costs 1 if the previous move was orthogonal or if the previous move was diagonal and cost 2, else it costs 2.

So a few examples to explain better:

  1. moving NE,NE will cost 1+2 = 3

  2. moving NE,E,NE will cost 1+1+1 = 3

  3. moving NE,NE,NE will cost 1+2+1 = 4

I think that's enough to get the gist of it.

I don't know how to implement an A* algorithm that would achieve this. My heurestic function:

private double heuresticDistance(Node p1, Node p2){
        double dx = Math.abs(p1.x - p2.x);
        double dy = Math.abs(p1.y - p2.y);
        // D = 1d, D2 = 1.5d;
        return D * (dx + dy) + (D2 - 2 * D) * Math.min(dx, dy);
    }

Obviously it's not good in this case and there are some cases where it will not go the shortest path(cost-wise), meaning that it could have gone a different way that would result in a lower cost.

It is really important that it will always find the cheapest or one of the cheapest if there are more than one.

Could you give me some hints? My A* implementation is pretty straightforward I guess I wrote it according to the wikipedia pseudocode.

EDIT:

public class Node{
    public int x,y;
}

Upvotes: 2

Views: 487

Answers (2)

David
David

Reputation: 953

Referencing the wikipedia article A* search algorithm. Your heuristic is not "monotonic", because the cost of a given path depends on past choices. Here's my attempt.

Any path can be split into a series of orthagonal movements and a series of diagonal movements. In the heuristic, let's move diagonal until we are orthagonal to the target. That ensures the maximum number of extra costs. NE-NE-E-E.

On the other hand, the best case occurs when we mix orthagonal and diagonal movement evenly: E-NE-E-NE. So for each orthagonal movement, we can treat one diagonal movement as orthagonal.

private double heuresticDistance(Node p1, Node p2, bool lastWasDiagonal) {
    int dx = Math.abs(p1.x - p2.x);
    int dy = Math.abs(p1.x - p2.x);
    int diagonals = Math.min(dx, dy);
    int orthagonals = Math.max(dx, dy) - diagonals;
    // example: dx=3, dy=5. Move diagonally 3 times and orthagonally 2 times.

    int temp = diagonals + orthagonals;
    diagonals = Math.max(diagonals - orthagonals, 0);
    orthagonals = temp - diagonals;

    int lastDiagonalBonus = 0;
    if( lastWasDiagonal && orthagonals < 1 )
        lastDiagonalBonus = 1;  // the special case that last move was diagonal and we have no orthagonal moves available to compensate

    if( diagonals % 2 == 1 ) {
        diagonals--; orthagonals++;
    }
    return diagonals * 3 / 2 + orthagonals * 1 + lastDiagonalBonus;
}

Upvotes: 0

Salvador Dali
Salvador Dali

Reputation: 222481

Your heuristic function is not admissible.

Look at the path from (0, 0) to (1, 1). Your heuristics tells you that it is equal to 1 * (1 + 1) + (1.5 - 2) * 1 = 1.5. But the path is 1. So you overestimate your goal, thus make your heuristic in-admissible and this cause A* to find the wrong path.

Take a closer look at A* and you will see that it requires admissibility (also I do not remember whether the consistency is important for your case).

Upvotes: 2

Related Questions