a* поиск пути - стоимость преемника

Я переделываю старую кастомную игру Warcraft 3, в которую когда-то играл, и ставлю ее на iphone. По сути, у вас есть определенное количество времени, чтобы построить лабиринт из определенного количества блоков, и чем больше времени требуется крипу, чтобы пройти лабиринт, тем больше очков вы получите.

Я делаю все это в эфире с помощью cocos2d, и прямо сейчас я добавляю алгоритм поиска пути a*. Я использую реализацию Джастина Хейса-Джонса и работаю над класс узла прямо сейчас.

Однако меня смущает пара вещей. Класс выглядит так:

class MapSearchNode
{
public:
    unsigned int x;  // the (x,y) positions of the node
    unsigned int y; 


    MapSearchNode() { x = y = 0; }
    MapSearchNode( unsigned int px, unsigned int py ) { x=px; y=py; }

    bool IsGoal( MapSearchNode &nodeGoal ) { return (x == nodeGoal.x && y == nodeGoal.y); }
    bool IsSameState( MapSearchNode &rhs ) { return (x == rhs.x && y == rhs.y); }

    float GoalDistanceEstimate( MapSearchNode &nodeGoal );
    float GetCost( MapSearchNode &successor );
    bool GetSuccessors( AStarSearch<MapSearchNode> *astarsearch, MapSearchNode *parent_node );

    //void PrintNodeInfo();
};

Я просто не уверен, что означает GetCost. В этом примере лабиринта, где X — это стены, а _ — зоны, по которым можно пройти, будет ли стоимость перехода из (3, 1) в (3, 2) равна 0? И сколько будет стоить переход от (3, 1) к (4, 1), поскольку это невозможно?

X X _ X X
X _ _ X X
X _ X X X
X _ _ _ _
X X X X X

И тогда я думаю, что могу просто реализовать GoalDistanceEstimate, используя формулу расстояния, правильно?


path-finding a-star
person Caleb Jares    schedule 27.04.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Общий A* основан на взвешенном графике. В практических приложениях для решения лабиринтов все ребра имеют одинаковый конечный вес (обычно 1) для проходимой местности и бесконечный (записывается как очень большое число, просто используйте 100000 или что-то в этом роде) для непроходимой местности.

person Blindy    schedule 27.04.2011
comment
Если вы сделаете это так, вам придется придумать лучшую эвристику, чем просто евклидово расстояние, иначе A * не будет намного быстрее, чем у Дейкстры. - person Mike; 16.12.2013

arrow_upward
1
arrow_downward

Насколько я понимаю, стоимость была «совокупной суммой», которая определяла «самый быстрый путь». Стоимость добавляется к каждому квадрату или узлу, к которому они должны перейти. Это также может включать в себя такие вещи, как ограничения местности (например, замедление и т. д.).

person Freesnöw    schedule 27.04.2011
comment
Думаю, я нашел ответ. Для каждого из узлов стоимость будет равна единице (проход на одну плитку вперед), и в методе GetSuccessors я не буду добавлять преемников, по которым нельзя пройти. И получается, что стоимость - это стоимость одного узла для другого, общая стоимость хранится в узле, и когда создается новый узел, его общая стоимость устанавливается равной общей стоимости последнего узла плюс функция GetCost к новому узел. - person Caleb Jares; 27.04.2011