Путь с наименьшими оборотами в алгоритме прямоугольной сетки

Question

Я застрял в течение последних 4 дней в алгоритме. Я работаю над игрой типа Mahjong Safari (http://www.pogo.com/games/mahjongsafari), и я хочу разработать путь между двумя плитами с наименьшим количеством фрагментов.

Я уже применил алгоритм A * с Manhattan Hueristic, но это порождает кратчайший путь с большим количеством поворотов. Нет необходимости в кратчайшем пути, мне нужен только путь с минимальными оборотами (желательно 2). Ниже приведена картинка из игры Mahjong Safari, которая генерирует путь между двумя плитами. Вы заметите, что путь от A до B и путь от B до A различны.

Пожалуйста, помогите мне, в любом коде или любого имени алгоритма или любой логики вы думаете, могли бы работать.

EDIT: Решение я применил для этого:

Я использовал подлинный A * алгоритм первой, чтобы найти кратчайший путь, и я использовал Манхэттен расстояние в качестве оценки эвристической цели. Для того, чтобы выправить путь больше, и выбирать путь с наименьшим числом витков, я использовал следующие тактику в каждой итерации:

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

Решение я применил для этого:

Сначала я использовал оригинальный алгоритм A *, чтобы найти кратчайший путь, и я использовал расстояние Манхэттена как эвристическую оценку цели. Чтобы выпрямить путь больше и выбрать путь с наименьшим числом оборотов, я использовал следующую тактику на каждой итерации:

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(); 
    } 

} 

Answer 2

Вы можете использовать Dijkstra's shortest path algorithm, но в каждом узле вы должны не только хранить кратчайший путь, но также направление этого пути, так что вы знаете, нужно ли увеличить счет.

Думая немного больше, я думаю, вам нужно будет хранить все кратчайшие пути со своим направлением в каждом узле, чтобы выбрать лучший.

Answer 3

Ваша проблема более простая, чем использование эвристики, поскольку вам не нужны ожидания, но она может повысить скорость поиска оптимального, если ваш поиск не «завершен» .. но вам просто нужен путь с минимальными поворотами, следовательно, вы можете пойти с Жадным Поиском где:

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 

Вот простой код в Java, которые иллюстрируют:

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; 
    } 
}