Path with least turns in rectangular grid algorithm

Question

I am stuck for last 4 days in an algorithm. I am working on Mahjong Safari type game (http://www.pogo.com/games/mahjongsafari), and I want to develop path between two tiles with least number of tiles.

I already applied A* algorithm with Manhattan Hueristic, but that generates shortest path with lots of turns. There is no need of shortest path, I just need path with min turns (preferably 2). Below is image from Mahjong Safari game, which generates path between 2 tiles. You will notice that the path from A to B and path from B to A are different.

Please help me, in any code or any algorithm name or any logic you think could work.

EDIT: The Solution I applied for this:

I used genuine A* Algorithm first to find shortest path, and I used Manhattan distance as heuristic goal estimate. To straighten the path more, and choose path with least number of turns, i used following tactic in each iteration:

Tile first = currentNode.parent;
Tile curr  = currentNode;
Tile last  = successorOfCurrentNode;
if (first != null)
{
    if ((first.X == curr.X && first.Y != curr.Y) && (curr.Y == last.Y && curr.X != last.X))
    {
        // We got turn
    currentNode.Cost += 10;
    currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
    successorOfCurrentNode.calcuateTotalCost();
    }
    else if ((first.X != curr.X && first.Y == curr.Y) && (curr.X == last.X && curr.Y != last.Y))
    {
        // We got turn
    currentNode.Cost += 10;
    currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
    successorOfCurrentNode.calcuateTotalCost();
    }

}

Answer 1

You could use Dijkstra's shortest path algorithm, but in every node you should not only store the shortest path, but also the direction of that path, so you know whether you need to increase the count.

Thinking a little more, I guess you would need to store all shortest paths with their direction in every node, in order to pick the best one.

Answer 2

Your problem is more simple than using a heuristic, since you don't need expectation, but it can enhance the speed of finding the optimal in case your search is not "complete" .. but rather you just want the path with minimal turns, hence you can go with Greedy Search where:

h(A) > h(B) ~ turns(A) < turns(B)

h* = MIN(turns(x))

h(x): heuristic of path X

turns(x): number of turns in path X

h*: highest possible heuristic, path with minimum number of turns

Here is a simple code in Java that illustrate:

class TileGame
{
    // example of a game board
    int [][] matrix = new int [10][10];

    // return possible next-state
    public ArrayList<Path> next (Path p)
    {
        // based on your rules, you decide valid transitions
        ArrayList<Path> n = new ArrayList<Path>();
        ArrayList<Point> t = new ArrayList<Point>();

        // add up, down, right, and left
        t.add(new Point(p.current.x+1, p.current.y));
        t.add(new Point(p.current.x-1, p.current.y));
        t.add(new Point(p.current.x, p.current.y+1));
        t.add(new Point(p.current.x, p.current.y-1));

        // don't allow going back to previous tile, cause infinite loops
        t.remove(p.previous);

        for (Point i : t)
        {
            if (i.x == p.current.x == p.previous.x || i.y == p.current.y == p.previous.y)
                n.add(new Path(i, p.current, p.turns));
            else
                n.add(new Path(i, p.current, p.turns+1));
        }

        return n;
    }

    // ..

}

private class Path
{
    public Point current, previous;
    public int turns;

    public Path(Point curr, Point prev, int tur)
    {
        current = curr;
        previous = prev;
        turns = tur;
    }
}

Answer 3

The Solution I applied for this:

I used genuine A* Algorithm first to find shortest path, and I used Manhattan distance as heuristic goal estimate. To straighten the path more, and choose path with least number of turns, i used following tactic in each iteration:

enter code here

Tile first = currentNode.parent;
Tile curr  = currentNode;
Tile last  = successorOfCurrentNode;
if (first != null)
{
    if ((first.X == curr.X && first.Y != curr.Y) && (curr.Y == last.Y && curr.X != last.X))
    {
        // We got turn
        currentNode.Cost += 10;
        currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
        successorOfCurrentNode.calcuateTotalCost();
    }
    else if ((first.X != curr.X && first.Y == curr.Y) && (curr.X == last.X && curr.Y != last.Y))
    {
        // We got turn
        currentNode.Cost += 10;
        currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
        successorOfCurrentNode.calcuateTotalCost();
    }

}