lash_game_path.h (8326B)
1 #ifndef LASH_GAME_PATH_SIMPLE_H_ 2 #define LASH_GAME_PATH_SIMPLE_H_ 3 4 #include "liblashgame/lash_game_standard.h" 5 #include "liblashgame/lash_game_map.h" 6 #include "liblash/lash_tree.h" 7 8 #define LASH_GAME_PATH_SIMPLE_SCORE_STRAIGHT 10 9 #define LASH_GAME_PATH_SIMPLE_SCORE_DIAGONAL 14 10 11 // Defines amount of resistance, not amount of movement 12 #define LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE 192 13 #define LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_QUARTER 144 14 #define LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_THIRD 128 15 #define LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_HALF 96 16 #define LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_TWOTHIRDS 64 17 #define LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_THREEQUARTER 48 18 #define LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_FULL 0 19 20 typedef struct lash_path_simple_obstacle_t lash_path_simple_obstacle_t; 21 22 struct lash_path_simple_obstacle_t { 23 lash_map_simple_layer_item_t val; 24 unsigned char modifier; 25 }; 26 27 typedef struct lash_path_simple_space_t lash_path_simple_space_t; 28 29 struct lash_path_simple_space_t { 30 unsigned char g; 31 unsigned int h; 32 unsigned int f; 33 lash_path_simple_space_t *parent; 34 lash_game_map_index_t index; 35 }; 36 37 typedef struct lash_path_simple_t lash_path_simple_t; 38 39 struct lash_path_simple_t { 40 unsigned int *w; 41 unsigned int *h; 42 //lash_path_simple_space_t *openlist; 43 //lash_path_simple_space_t *closedlist; 44 lash_path_simple_space_t *spaces; 45 lash_tree_t *opentree; 46 lash_tree_t *closedtree; 47 lash_tree_t *spacestree; 48 //unsigned int openlist_idx; 49 //unsigned int closedlist_idx; 50 unsigned int spaces_position; 51 lash_game_map_index_t source; 52 lash_game_map_index_t target; 53 }; 54 55 //int lash_pathSimpleInit(const unsigned int *w, const unsigned int *h, const lash_game_map_index_t index_offset, const lash_game_map_index_t index_target); 56 lash_path_simple_t * lash_pathSimpleInit(lash_path_simple_t *path, lash_map_simple_t *map, const lash_game_map_index_t offsetindex, const lash_game_map_index_t targetindex); 57 int _lash_pathSimpleMemInc(lash_path_simple_t *path); 58 lash_path_simple_space_t * lash_pathSimpleUpdateSpace(lash_path_simple_t *path, lash_path_simple_space_t *editspace, lash_path_simple_space_t *parent, const lash_game_map_index_t currentindex, const unsigned int g); 59 //int lash_pathSimpleStep(lash_path_simple_space_t *parent); 60 lash_path_simple_space_t * lash_pathSimpleStepProcess(lash_path_simple_t *path, lash_map_simple_t *map, lash_path_simple_space_t *parent, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount); 61 lash_path_simple_space_t * lash_pathSimpleNext(lash_path_simple_t *path); 62 int lash_pathSimpleClose(lash_path_simple_t *path, lash_path_simple_space_t *space); 63 float lash_pathSimpleCheckModifier(const lash_map_simple_layer_item_t *layeritem, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount); 64 void lash_pathSimpleFree(lash_path_simple_t *path); 65 66 #endif //LASH_GAME_PATH_SIMPLE_H_ 67 68 /** 69 * \file lash_game_path.h 70 * \brief A* Pathfinder routine for tiled maps 71 * \todo Consider putting map and obstacles directly in path struct 72 * \todo Internal handling of target reached 73 * \todo Consider changing defines into enums 74 */ 75 76 /** 77 * \struct lash_path_simple_t 78 * \brief The path object 79 * \var lash_path_simple_t::w 80 * World width 81 * \var lash_path_simple_t::h 82 * World height 83 * \var lash_path_simple_t::spaces 84 * Array of \ref lash_path_simple_space_t objects comprising the spaces used for path checking 85 * \var lash_path_simple_t::opentree 86 * Array of spaces adjacent to the spaces along the current path. Points to indices in the \ref lash_path_simple_t::spacestree array 87 * \var lash_path_simple_t::closedtree 88 * Array of chosen spaces. Points to indices in the \ref lash_path_simple_t::spacestree array 89 * \var lash_path_simple_t::spacestree 90 * Array of spaces used by the path processor 91 * \var lash_path_simple_t::spaces_position 92 * The current end position of the \ref lash_path_simple_t::spacestree array 93 * \var lash_path_simple_t::source 94 * Map index value of the start position 95 * \var lash_path_simple_t::target 96 * Map index value of the target position 97 */ 98 99 /** 100 * \struct lash_path_simple_space_t 101 * \brief Path space 102 * \var lash_path_simple_space_t::g 103 * The score of reaching this space from offset 104 * \var lash_path_simple_space_t::g 105 * The score of reaching the target through this offset 106 * \var lash_path_simple_space_t::g 107 * The heuristic score from this space to the target 108 * \var lash_path_simple_space_t::parent 109 * The parent space; The space that was stepped through on the path's current route to reach this space 110 * \var lash_path_simple_space_t::index 111 * The map position of the space 112 */ 113 114 /** 115 * \struct lash_path_simple_obstacle_t 116 * \brief Dictionary from map layer values to modifier factors 117 * \var lash_path_simple_obstacle_t::val 118 * The key value 119 * \var lash_path_simple_obstacle_t::modifier 120 * The modifier factor, in x / 192 121 */ 122 123 /** 124 * \fn int lash_pathSimpleClose(lash_path_simple_t *path, lash_path_simple_space_t *space) 125 * \brief Adds the specified space to the closedtree 126 * \param path The path to operate on 127 * \param space The space to add 128 * 129 * Returns the value of lashTreePush 130 * 131 * \todo Verify that space cannot be added if it already exists, and that return value is 1 if space cannot be added 132 * 133 */ 134 135 /** 136 * \fn float lash_pathSimpleCheckModifier(const lash_map_simple_layer_item_t *layeritem, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount) 137 * \brief Returns the modifier factor for the specified map value 138 * \param layeritem Map value to check 139 * \param obstacleslist The list of modifier values to check against 140 * \param obstaclescount The size of the obstacles list 141 * 142 * \todo This routine currently only returns impassable for all map values that exist in the obstacles list 143 */ 144 145 /** 146 * \fn lash_path_simple_space_t * lash_pathSimpleNext(lash_path_simple_t *path) 147 * \brief Returns the space with the lowest f value 148 * \param path The path to operate on 149 */ 150 151 /** 152 * \fn lash_path_simple_space_t * lash_pathSimpleStepProcess(lash_path_simple_t *path, lash_map_simple_t *map, lash_path_simple_space_t *parent, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount) 153 * \brief Retrieves the next step towards the target 154 * \param path The path to operate on 155 * \param map The map data to use 156 * \param parent The current space 157 * \param obstacleslist Array of map values that modify movement 158 * \param obstaclescount Amount of values in obstacleslist 159 * 160 * Adds all passable, unclosed adjacent squares that are not already added to the openlist. 161 * Checks if the the current space is a faster step to reach each adjacent space, and updates the spaces accordingly. 162 * Retrieves the resulting space with the lowest f value, and returns a pointer to it. 163 * If NULL is returned, path cannot be found 164 * 165 * \sa lashPathSimpleNext 166 * \todo Implement movement modifiers 167 * \todo Verify return values for found target and no paths 168 */ 169 170 171 /** 172 * \fn lash_path_simple_t * lash_pathSimpleInit(lash_path_simple_t *path, lash_map_simple_t *map, const lash_game_map_index_t offsetindex, const lash_game_map_index_t targetindex) 173 * \brief Allocate memory and initialize members 174 * \param path The path to initialize 175 * \param map The map data to use 176 * \param offsetindex Where on the map to start 177 * \param targetindex Where on the map to end 178 * 179 * Initializes the path struct. 180 * Also sets a memory increase interval equal to 4 times the magnitude of the vector between offset and target. 181 * The binary tree sizes are initially set to this increase interval, and if will be expanded by the same amount if the capacity is exceeded. 182 * 183 */ 184 185 /** 186 * \fn lash_path_simple_space_t * lash_pathSimpleUpdateSpace(lash_path_simple_t *path, lash_path_simple_space_t *editspace, lash_path_simple_space_t *parent, const lash_game_map_index_t currentindex, const unsigned int g) 187 * \brief Updates or adds a space to be checked 188 * \param path The path struct to operate on 189 * \param editspace If specified, a new space will not be added, but the values of the specified spaee will be updated instead 190 * \param parent The parent space of the current space 191 * \param currentindex The map position of the current space 192 * \param g The g value to set for the space 193 * 194 * 195 */ 196