aystar.h

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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/>.
 */
 
#ifndef AYSTAR_H
#define AYSTAR_H
 
#include "../track_func.h"
 
#include "../misc/hashtable.hpp"
#include "../misc/binaryheap.hpp"
#include "../misc/dbg_helpers.h"
 
#include "yapf/nodelist.hpp"
#include "yapf/yapf_node.hpp"
 
static const int AYSTAR_DEF_MAX_SEARCH_NODES = 10000; 
 
enum AystarStatus {
  AYSTAR_FOUND_END_NODE, 
  AYSTAR_EMPTY_OPENLIST, 
  AYSTAR_STILL_BUSY,     
  AYSTAR_NO_PATH,        
  AYSTAR_LIMIT_REACHED,  
  AYSTAR_DONE,           
};
 
static const int AYSTAR_INVALID_NODE = -1; 
 
using AyStarNode = CYapfNodeKeyTrackDir;
 
struct PathNode : CYapfNodeT<AyStarNode, PathNode> {
};
 
bool CheckIgnoreFirstTile(const PathNode *node);
 
struct AyStar;
 
typedef int32_t AyStar_EndNodeCheck(const AyStar *aystar, const PathNode *current);
 
typedef int32_t AyStar_CalculateG(AyStar *aystar, AyStarNode *current, PathNode *parent);
 
typedef int32_t AyStar_CalculateH(AyStar *aystar, AyStarNode *current, PathNode *parent);
 
typedef void AyStar_GetNeighbours(AyStar *aystar, PathNode *current);
 
typedef void AyStar_FoundEndNode(AyStar *aystar, PathNode *current);
 
struct AyStar {
/* These fields should be filled before initing the AyStar, but not changed
 * afterwards (except for user_data)! (free and init again to change them) */
 
  /* These should point to the application specific routines that do the
   * actual work */
  AyStar_CalculateG *CalculateG;
  AyStar_CalculateH *CalculateH;
  AyStar_GetNeighbours *GetNeighbours;
  AyStar_EndNodeCheck *EndNodeCheck;
  AyStar_FoundEndNode *FoundEndNode;
 
  /* These are completely untouched by AyStar, they can be accessed by
   * the application specific routines to input and output data.
   * user_path should typically contain data about the resulting path
   * afterwards, user_target should typically contain information about
   * what you where looking for, and user_data can contain just about
   * everything */
  void *user_target;
  void *user_data;
 
  uint8_t loops_per_tick;   
  int max_path_cost;    
  int max_search_nodes = AYSTAR_DEF_MAX_SEARCH_NODES; 
 
  /* These should be filled with the neighbours of a tile by GetNeighbours */
  std::vector<AyStarNode> neighbours;
 
  /* These will contain the methods for manipulating the AyStar. Only
   * Main() should be called externally */
  void AddStartNode(AyStarNode *start_node, int g);
  int Main();
  int Loop();
  void CheckTile(AyStarNode *current, PathNode *parent);
 
protected:
  NodeList<PathNode, 8, 10> nodes;
 
  void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g);
};
 
#endif /* AYSTAR_H */