liblashgame

Pathfinder and path decision making library for 2D tile game
git clone git://holbrook.no/liblashgame.git
Info | Log | Files | Refs

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