Блог

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

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

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

 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 amp;nodeGoal ) { return (x == nodeGoal.x amp;amp; y == nodeGoal.y); }
    bool IsSameState( MapSearchNode amp;rhs ) { return (x == rhs.x amp;amp; y == rhs.y); }

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

    //void PrintNodeInfo();
};
  

Я просто не уверен, что означает getCost. В этом примере лабиринта, где X — стены, а _ ‘s — проходимые области, будет ли стоимость перехода от (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, используя формулу расстояния, правильно?

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

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