th_pathfind.h

Go to the documentation of this file.

/*
Copyright (c) 2009 Peter "Corsix" Cawley
 
Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
 
#ifndef CORSIX_TH_TH_PATHFIND_H_
#define CORSIX_TH_TH_PATHFIND_H_
 
#include "config.h"
 
#include <cstdint>
#include <vector>
 
#include "lua.hpp"
 
class level_map;
class lua_persist_reader;
class lua_persist_writer;
class pathfinder;
enum class object_type : uint8_t;
struct map_tile_flags;
 
enum class travel_direction {
  north = 0,  
  east = 1,   
  south = 2,  
  west = 3    
};
 
struct path_node {
 
  const path_node* prev;
 
  int x;
 
  int y;
 
 
  int distance;
 
 
  int guess;
 
 
  size_t open_idx;
 
  bool visited;
 
 
  inline int value() const { return distance + guess; }
};
 
class abstract_pathfinder {
 public:
  abstract_pathfinder(pathfinder* pf);
  virtual ~abstract_pathfinder() = default;
 
 
  path_node* init(const level_map* pMap, int iStartX, int iStarty);
 
 
  bool search_neighbours(path_node* pNode, map_tile_flags flags, int iWidth);
 
  void record_neighbour_if_passable(path_node* pNode,
                                    map_tile_flags neighbour_flags,
                                    bool passable, path_node* pNeighbour);
 
 
  virtual int guess_distance(path_node* pNode) = 0;
 
 
  virtual bool try_node(path_node* pNode, map_tile_flags flags,
                        path_node* pNeighbour, travel_direction direction) = 0;
 
 protected:
  pathfinder* parent;    
  const level_map* map;  
};
 
class basic_pathfinder : public abstract_pathfinder {
 public:
  explicit basic_pathfinder(pathfinder* pf)
      : abstract_pathfinder(pf), destination_x(0), destination_y(0) {}
 
  int guess_distance(path_node* pNode) override;
  bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
                travel_direction direction) override;
 
  bool find_path(const level_map* pMap, int iStartX, int iStartY, int iEndX,
                 int iEndY);
 
  int destination_x;  
  int destination_y;  
};
 
class hospital_finder : public abstract_pathfinder {
 public:
  explicit hospital_finder(pathfinder* pf) : abstract_pathfinder(pf) {}
 
  int guess_distance(path_node* pNode) override;
  bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
                travel_direction direction) override;
 
  bool find_path_to_hospital(const level_map* pMap, int iStartX, int iStartY);
};
 
class idle_tile_finder : public abstract_pathfinder {
 public:
  explicit idle_tile_finder(pathfinder* pf)
      : abstract_pathfinder(pf),
        best_next_node(nullptr),
        best_distance(0),
        start_x(0),
        start_y(0) {}
 
  int guess_distance(path_node* pNode) override;
  bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
                travel_direction direction) override;
 
  //| Find a tile for idling.
  bool find_idle_tile(const level_map* pMap, int iStartX, int iStartY, int iN,
                      int parcelId);
 
  path_node* best_next_node;
  double best_distance;
  int start_x;  
  int start_y;  
};
 
class object_visitor : public abstract_pathfinder {
 public:
  explicit object_visitor(pathfinder* pf)
      : abstract_pathfinder(pf),
        L(nullptr),
        visit_function_index{},
        max_distance{},
        target_any_object_type{},
        target{} {}
 
  int guess_distance(path_node* pNode) override;
  bool try_node(path_node* pNode, map_tile_flags flags, path_node* pNeighbour,
                travel_direction direction) override;
 
  bool visit_objects(const level_map* pMap, int iStartX, int iStartY,
                     object_type eTHOB, int iMaxDistance, lua_State* L,
                     int iVisitFunction, bool anyObjectType);
 
  lua_State* L;
  int visit_function_index;
  int max_distance;
  bool target_any_object_type;
  object_type target;
};
 
 
class pathfinder {
 public:
  pathfinder();
  ~pathfinder();
 
  void set_default_map(const level_map* pMap);
 
  inline bool find_path(const level_map* pMap, int iStartX, int iStartY,
                        int iEndX, int iEndY) {
    return basic_pathfinder.find_path(pMap, iStartX, iStartY, iEndX, iEndY);
  }
 
  inline bool find_idle_tile(const level_map* pMap, int iStartX, int iStartY,
                             int iN, int parcelId) {
    return idle_tile_finder.find_idle_tile(pMap, iStartX, iStartY, iN,
                                           parcelId);
  }
 
  inline bool find_path_to_hospital(const level_map* pMap, int iStartX,
                                    int iStartY) {
    return hospital_finder.find_path_to_hospital(pMap, iStartX, iStartY);
  }
 
  inline bool visit_objects(const level_map* pMap, int iStartX, int iStartY,
                            object_type eTHOB, int iMaxDistance, lua_State* L,
                            int iVisitFunction, bool anyObjectType) {
    return object_visitor.visit_objects(pMap, iStartX, iStartY, eTHOB,
                                        iMaxDistance, L, iVisitFunction,
                                        anyObjectType);
  }
 
  int get_path_length() const;
  bool get_path_end(int* pX, int* pY) const;
  void push_result(lua_State* L) const;
 
  void persist(lua_persist_writer* pWriter) const;
  void depersist(lua_persist_reader* pReader);
 
 
  void allocate_node_cache(int iWidth, int iHeight);
 
  path_node* pop_from_open_heap();
  void push_to_open_heap(path_node* pNode);
  void open_heap_promote(path_node* pNode);
 
  const level_map* default_map;
 
  std::vector<path_node> nodes;
 
 
  path_node** dirty_node_list;
 
 
  std::vector<path_node*> open_heap;
 
  path_node* destination;
  int node_cache_width;
  int node_cache_height;
  int dirty_node_count;
 
 private:
  ::basic_pathfinder basic_pathfinder;
  ::hospital_finder hospital_finder;
  ::idle_tile_finder idle_tile_finder;
  ::object_visitor object_visitor;
};
 
#endif  // CORSIX_TH_TH_PATHFIND_H_