A* Pathfinding - как изменить G и H, чтобы включить стоимость движения по пересеченной местности?
В моей 2D-игре реализован поиск путей A *, и он хорошо работает на простой карте с препятствиями. Теперь я пытаюсь понять, как изменить алгоритм, чтобы он считал пересеченную местность (холмы, лес и т. Д.) Как 2 хода вместо 1.
При стоимости перемещения 1 алгоритм использует целые числа 10 и 14 в функции стоимости перемещения. Меня интересует, как изменить эти значения, если одна ячейка фактически имеет стоимость перемещения 2? это будет 20:17?
Вот как мой текущий алгоритм в настоящее время вычисляет G и H ( принят от Ray Wenderleich):
// Compute the H score from a position to another (from the current position to the final desired position
- (int)computeHScoreFromCoord:(CGPoint)fromCoord toCoord:(CGPoint)toCoord
{
// Here we use the Manhattan method, which calculates the total number of step moved horizontally and vertically to reach the
// final desired step from the current step, ignoring any obstacles that may be in the way
return abs(toCoord.x - fromCoord.x) + abs(toCoord.y - fromCoord.y);
}
// Compute the cost of moving from a step to an adjecent one
- (int)costToMoveFromStep:(ShortestPathStep *)fromStep toAdjacentStep:(ShortestPathStep *)toStep
{
return ((fromStep.position.x != toStep.position.x)
&& (fromStep.position.y != toStep.position.y))
? 14 : 10;
}
3 ответа
Если некоторые ребра имеют стоимость перемещения 2, вы просто добавите 2 к G родительского узла, а не 1.
Что касается H: это не должно измениться. Получающаяся эвристика все еще будет допустимой / последовательной.
Я думаю, что получил, с этой строкой автор учебника проверяет, является ли ход 1 квадратом или 2 квадратами (диагональю) от хода, который в настоящее время рассматривается.
return ((fromStep.position.x != toStep.position.x)
&& (fromStep.position.y != toStep.position.y))
? 14 : 10;
К сожалению, это действительно простой случай, который не объясняет, что нужно делать. Число 10 используется для упрощения вычислений (10 = 1 стоимость перемещения), а (14 = 1 диагональное перемещение) является приближением к квадрату (10*10).
Я попытался ввести стоимость местности ниже, и это требует дополнительной информации - мне нужно знать, через какую ячейку я иду, чтобы добраться до места назначения. Это оказалось действительно раздражающим, и приведенный ниже код явно не самый лучший, но я попытался объяснить, что происходит на каждом этапе.
Если я делаю ход по диагонали, мне нужно знать, сколько это стоит, И как цена перемещения в 2 квадрата может быть использована для этого. Затем я могу выбрать самую низкую стоимость движения среди двух квадратов и вставить ее в уравнение формы:
moveCost = (int)sqrt(lowestMoveCost*lowestMoveCost + (stepNode.moveCost*10) * (stepNode.moveCost*10));
Вот весь цикл, который проверяет смежные шаги и создает из них новые шаги со стоимостью перемещения. Он находит плитку в массиве моей карты и возвращает ее стоимость местности.
NSArray *adjSteps = [self walkableAdjacentTilesCoordForTileCoord:currentStep.position];
for (NSValue *v in adjSteps) {
ShortestPathStep *step = [[ShortestPathStep alloc] initWithPosition:[v CGPointValue]];
// Check if the step isn't already in the closed set
if ([self.spClosedSteps containsObject:step]) {
continue; // Ignore it
}
tileIndex = [MapOfTiles tileIndexForCoordinate:step.position];
DLog(@"point (x%.0f y%.0f):%i",step.position.x,step.position.y,tileIndex);
stepNode = [[MapOfTiles sharedInstance] mapTiles] [tileIndex];
// int moveCost = [self costToMoveFromStep:currentStep toAdjacentStep:step];
//in my case 0,0 is bottom left, y points up x points right
if((currentStep.position.x != step.position.x) && (currentStep.position.y != step.position.y))
{
//move one step away - easy, multiply move cost by 10
moveCost = stepNode.moveCost*10;
}else
{
possibleMove1 = 0;
possibleMove2 = 0;
//we are moving diagonally, figure out in which direction
if(step.position.y > currentStep.position.y)
{
//moving up
possibleMove1 = tileIndex + 1;
if(step.position.x > currentStep.position.x)
{
//moving right and up
possibleMove2 = tileIndex + tileCountTall;
}else
{
//moving left and up
possibleMove2 = tileIndex - tileCountTall;
}
}else
{
//moving down
possibleMove1 = tileIndex - 1;
if(step.position.x > currentStep.position.x)
{
//moving right and down
possibleMove2 = tileIndex + tileCountTall;
}else
{
//moving left and down
possibleMove2 = tileIndex - tileCountTall;
}
}
moveNode1 = nil;
moveNode2 = nil;
CGPoint coordinate1 = [MapOfTiles tileCoordForIndex:possibleMove1];
CGPoint coordinate2 = [MapOfTiles tileCoordForIndex:possibleMove2];
if([adjSteps containsObject:[NSValue valueWithCGPoint:coordinate1]])
{
//we know that possible move to reach destination has been deemed walkable, get it's move cost from the map
moveNode1 = [[MapOfTiles sharedInstance] mapTiles] [possibleMove1];
}
if([adjSteps containsObject:[NSValue valueWithCGPoint:coordinate2]])
{
//we know that the second possible move is walkable
moveNode2 = [[MapOfTiles sharedInstance] mapTiles] [possibleMove2];
}
#warning not sure about this one if the algorithm has to backtrack really far back
//find out which square has the lowest move cost
lowestMoveCost = fminf(moveNode1.moveCost, moveNode2.moveCost) * 10;
moveCost = (int)sqrt(lowestMoveCost*lowestMoveCost + (stepNode.moveCost*10) * (stepNode.moveCost*10));
}
// Compute the cost form the current step to that step
// Check if the step is already in the open list
NSUInteger index = [self.spOpenSteps indexOfObject:step];
if (index == NSNotFound) { // Not on the open list, so add it
// Set the current step as the parent
step.parent = currentStep;
// The G score is equal to the parent G score + the cost to move from the parent to it
step.gScore = currentStep.gScore + moveCost;
// Compute the H score which is the estimated movement cost to move from that step to the desired tile coordinate
step.hScore = [self computeHScoreFromCoord:step.position toCoord:toTileCoord];
// Adding it with the function which is preserving the list ordered by F score
[self insertInOpenSteps:step];
}
else { // Already in the open list
step = (self.spOpenSteps)[index]; // To retrieve the old one (which has its scores already computed ;-)
// Check to see if the G score for that step is lower if we use the current step to get there
if ((currentStep.gScore + moveCost) < step.gScore) {
// The G score is equal to the parent G score + the cost to move from the parent to it
step.gScore = currentStep.gScore + moveCost;
// Because the G Score has changed, the F score may have changed too
// So to keep the open list ordered we have to remove the step, and re-insert it with
// the insert function which is preserving the list ordered by F score
// Now we can removing it from the list without be afraid that it can be released
[self.spOpenSteps removeObjectAtIndex:index];
// Re-insert it with the function which is preserving the list ordered by F score
[self insertInOpenSteps:step];
}
}
}
Эти типы проблем довольно распространены, скажем, в чип-маршрутизации и, да, в gamedev.
Стандартный подход состоит в том, чтобы иметь ваш граф (в C++ я бы сказал, что у вас есть Boost, "сеточный граф" или похожая структура). Если вы можете позволить себе иметь объект в каждой вершине, то решение довольно простое.
Вы соединяете две вершины (соседние или соседние по диагонали) ребром, если между ними нет препятствий. Вы назначаете этому краю вес, равный длине ребра (10 или 14), умноженной на стоимость местности. Иногда люди предпочитают не исключать края препятствий, а назначать им чрезвычайно большие веса (преимущество заключается в том, что при таком подходе вы гарантированно найдете хотя бы какой-нибудь путь, даже если объект застрял на острове).
Затем вы применяете алгоритм A*. Ваша эвристическая функция (H) может быть "пессимистичной" (равной евклидовому расстоянию, умноженному на максимальную стоимость перемещения) или "оптимистичной" (евклидовым расстоянием, умноженной на минимальную стоимость перемещения), или чем-то промежуточным. Различная эвристика приведет к немного разным "личностям" в вашем поиске, но обычно не имеет большого значения.