src/pathfinder/aystar.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file aystar.cpp Implementation of A*.
   9  *
  10  * This file has the core function for %AyStar.
  11  * %AyStar is a fast path finding routine and is used for things like AI path finding and Train path finding.
  12  * For more information about %AyStar (A* Algorithm), you can look at
  13  * <A HREF='http://en.wikipedia.org/wiki/A-star_search_algorithm'>http://en.wikipedia.org/wiki/A-star_search_algorithm</A>.
  14  */
  15
  16 #include "../../stdafx.h"
  17 #include "aystar.h"
  18
  19 #include "../../safeguards.h"
  20
  21 /**
  22  * Adds a node to the open list.
  23  * It makes a copy of node, and puts the pointer of parent in the struct.
  24  */
  25 void AyStar::OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
  26 {
  27         /* Add a new Node to the OpenList */
  28         PathNode &new_node = this->nodes.CreateNewNode();
  29         new_node.Set(parent, node->tile, node->td, true);
  30         new_node.estimate = f;
  31         new_node.cost = g;
  32         this->nodes.InsertOpenNode(new_node);
  33 }
  34
  35 /**
  36  * Checks one tile and calculate its f-value
  37  */
  38 void AyStar::CheckTile(AyStarNode *current, PathNode *parent)
  39 {
  40         /* Check the new node against the ClosedList */
  41         if (this->nodes.FindClosedNode(*current) != nullptr) return;
  42
  43         /* Calculate the G-value for this node */
  44         int new_g = this->CalculateG(this, current, parent);
  45         /* If the value was INVALID_NODE, we don't do anything with this node */
  46         if (new_g == AYSTAR_INVALID_NODE) return;
  47
  48         /* There should not be given any other error-code.. */
  49         assert(new_g >= 0);
  50         /* Add the parent g-value to the new g-value */
  51         new_g += parent->cost;
  52         if (this->max_path_cost != 0 && new_g > this->max_path_cost) return;
  53
  54         /* Calculate the h-value */
  55         int new_h = this->CalculateH(this, current, parent);
  56         /* There should not be given any error-code.. */
  57         assert(new_h >= 0);
  58
  59         /* The f-value if g + h */
  60         int new_f = new_g + new_h;
  61
  62         /* Get the pointer to the parent in the ClosedList (the current one is to a copy of the one in the OpenList) */
  63         PathNode *closedlist_parent = this->nodes.FindClosedNode(parent->key);
  64
  65         /* Check if this item is already in the OpenList */
  66         PathNode *check = this->nodes.FindOpenNode(*current);
  67         if (check != nullptr) {
  68                 /* Yes, check if this g value is lower.. */
  69                 if (new_g > check->cost) return;
  70                 this->nodes.PopOpenNode(check->key);
  71                 /* It is lower, so change it to this item */
  72                 check->estimate = new_f;
  73                 check->cost = new_g;
  74                 check->parent = closedlist_parent;
  75                 /* Re-add it in the openlist_queue. */
  76                 this->nodes.InsertOpenNode(*check);
  77         } else {
  78                 /* A new node, add it to the OpenList */
  79                 this->OpenListAdd(closedlist_parent, current, new_f, new_g);
  80         }
  81 }
  82
  83 /**
  84  * This function is the core of %AyStar. It handles one item and checks
  85  * its neighbour items. If they are valid, they are added to be checked too.
  86  * @return Possible values:
  87  *  - #AyStarStatus::EmptyOpenList
  88  *  - #AyStarStatus::LimitReached
  89  *  - #AyStarStatus::FoundEndNode
  90  *  - #AyStarStatus::StillBusy
  91  */
  92 AyStarStatus AyStar::Loop()
  93 {
  94         /* Get the best node from OpenList */
  95         PathNode *current = this->nodes.PopBestOpenNode();
  96         /* If empty, drop an error */
  97         if (current == nullptr) return AyStarStatus::EmptyOpenList;
  98
  99         /* Check for end node and if found, return that code */
 100         if (this->EndNodeCheck(this, current) == AyStarStatus::FoundEndNode && current->parent != nullptr) {
 101                 if (this->FoundEndNode != nullptr) {
 102                         this->FoundEndNode(this, current);
 103                 }
 104                 return AyStarStatus::FoundEndNode;
 105         }
 106
 107         /* Add the node to the ClosedList */
 108         this->nodes.InsertClosedNode(*current);
 109
 110         /* Load the neighbours */
 111         this->GetNeighbours(this, current);
 112
 113         /* Go through all neighbours */
 114         for (auto &neighbour : this->neighbours) {
 115                 /* Check and add them to the OpenList if needed */
 116                 this->CheckTile(&neighbour, current);
 117         }
 118
 119         if (this->max_search_nodes != 0 && this->nodes.ClosedCount() >= this->max_search_nodes) {
 120                 /* We've expanded enough nodes */
 121                 return AyStarStatus::LimitReached;
 122         } else {
 123                 /* Return that we are still busy */
 124                 return AyStarStatus::StillBusy;
 125         }
 126 }
 127
 128 /**
 129  * This is the function you call to run AyStar.
 130  * @return Possible values:
 131  *  - #AyStarStatus::FoundEndNode
 132  *  - #AyStarStatus::NoPath
 133  *  - #AyStarStatus::StillBusy
 134  * @note When the algorithm is done (when the return value is not #AyStarStatus::StillBusy) #Clear() is called automatically.
 135  *       When you stop the algorithm halfway, you should call #Clear() yourself!
 136  */
 137 AyStarStatus AyStar::Main()
 138 {
 139         AyStarStatus r = AyStarStatus::FoundEndNode;
 140         int i = 0;
 141         /* Loop through the OpenList
 142          *  Quit if result is no AyStarStatus::StillBusy or is more than loops_per_tick */
 143         while ((r = this->Loop()) == AyStarStatus::StillBusy && (this->loops_per_tick == 0 || ++i < this->loops_per_tick)) { }
 144 #ifdef AYSTAR_DEBUG
 145         switch (r) {
 146                 case AyStarStatus::FoundEndNode: Debug(misc, 0, "[AyStar] Found path!"); break;
 147                 case AyStarStatus::EmptyOpenList: Debug(misc, 0, "[AyStar] OpenList run dry, no path found"); break;
 148                 case AyStarStatus::LimitReached: Debug(misc, 0, "[AyStar] Exceeded search_nodes, no path found"); break;
 149                 default: break;
 150         }
 151 #endif
 152
 153         switch (r) {
 154                 case AyStarStatus::FoundEndNode: return AyStarStatus::FoundEndNode;
 155                 case AyStarStatus::EmptyOpenList:
 156                 case AyStarStatus::LimitReached: return AyStarStatus::NoPath;
 157                 default: return AyStarStatus::StillBusy;
 158         }
 159 }
 160
 161 /**
 162  * Adds a node from where to start an algorithm. Multiple nodes can be added
 163  * if wanted. You should make sure that #Clear() is called before adding nodes
 164  * if the #AyStar has been used before (though the normal main loop calls
 165  * #Clear() automatically when the algorithm finishes.
 166  * @param start_node Node to start with.
 167  * @param g the cost for starting with this node.
 168  */
 169 void AyStar::AddStartNode(AyStarNode *start_node, int g)
 170 {
 171 #ifdef AYSTAR_DEBUG
 172         Debug(misc, 0, "[AyStar] Starting A* Algorithm from node ({}, {}, {})\n",
 173                 TileX(start_node->tile), TileY(start_node->tile), start_node->direction);
 174 #endif
 175         this->OpenListAdd(nullptr, start_node, 0, g);
 176 }