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_simple.c (10832B)


      1 #include <stdlib.h>
      2 #include <stdio.h>
      3 #include <string.h>
      4 
      5 #include "liblash/lash_tree3.h"
      6 #include "liblashgame/lash_game_path_simple.h"
      7 #include "liblashgame/lash_game_standard.h"
      8 
      9 /**
     10  * \todo unitsize should be defined somewhere centrally. Map can be candidate
     11  * \todo set obstaclelist on path init
     12  * \warning the process step only checks for existence of existing spaces in the openlist, while theoretically a space can be shifted from openlist with nextstep without being added to the closedlist
     13  * 
     14  */
     15 
     16 int lash_pathSimpleInit() {
     17 	/*_lash_path_default_obstacles[0].val = 0;
     18 	_lash_path_default_obstacles[0].modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE;
     19 	_lash_path_default_obstacles[1].val = 1;
     20 	_lash_path_default_obstacles[1].modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_FULL;*/
     21 	_lash_path_default_obstacles = (lash_path_simple_obstacle_t *)malloc(sizeof(lash_path_simple_obstacle_t) * 2);
     22 	if (_lash_path_default_obstacles == NULL)
     23 		return 1;
     24 	
     25 	_lash_path_default_obstacles->val = 0;
     26 	_lash_path_default_obstacles->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE;
     27 	(_lash_path_default_obstacles + 1)->val = 1;
     28 	(_lash_path_default_obstacles + 1)->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_FULL;
     29 	
     30 	return 0;
     31 }	
     32 
     33 lash_path_simple_t * lash_pathSimpleNew(lash_path_simple_t *path, lash_map_simple_t *map, const lash_game_map_index_t offsetindex, const lash_game_map_index_t targetindex) {
     34 	unsigned int unitsize = 1;
     35 	unsigned int treecapacity = (unsigned int)*(map->w) * *(map->h) * 2;
     36 	
     37 	lash_game_coords_t offsetcoords;
     38 	lash_game_coords_t targetcoords;
     39 	
     40 	lash_indexToCartesian(&offsetcoords, map->w, map->h, &unitsize, &offsetindex);
     41 	lash_indexToCartesian(&targetcoords, map->w, map->h, &unitsize, &targetindex);
     42 	
     43 	path->w = map->w;
     44 	path->h = map->h;
     45 	path->target = targetindex;
     46 	path->source = offsetindex;
     47 
     48 	// enough for the whole world if necessary, consider making a realloc routine for these
     49 	path->opentree = lash_treeInit(path->opentree, treecapacity); 
     50 	if (path->opentree == NULL)
     51 		return NULL;
     52 		
     53 	path->closedtree = lash_treeInit(path->closedtree, treecapacity);
     54 	if (path->closedtree == NULL)
     55 		return NULL;
     56 		
     57 	path->spaces = (lash_path_simple_space_t*)malloc(sizeof(lash_path_simple_space_t) * treecapacity);
     58 	if (path->spaces == NULL)
     59 		return NULL;
     60 	
     61 	path->space_capacity = treecapacity;
     62 	path->space_count = 0;
     63 	
     64 	if (_lash_pathSimpleUpdateSpace(path, path->spaces, NULL, offsetindex, 0) == NULL)
     65 		return NULL;
     66 		
     67 	path->space_count = 1;
     68 	
     69 	lash_treePush(path->opentree, path->spaces, NULL);
     70 
     71 	return path;
     72 }
     73 
     74 lash_path_simple_space_t * _lash_pathSimpleAddSpace(lash_path_simple_t *path) {
     75 	
     76 
     77 	if (path->space_count == path->space_capacity) {
     78 		printf("SPACE COUNT is not  %d / %d", path->space_count, path->space_capacity);
     79 		return NULL;
     80 	}
     81 	
     82 	path->space_count++;
     83 
     84 	return (path->spaces + path->space_count - 1);
     85 }
     86 
     87 lash_path_simple_t * _lash_pathSimpleUpdateSpace(lash_path_simple_t *path, lash_path_simple_space_t *currentspace, lash_path_simple_space_t *parent, const lash_game_map_index_t currentindex, const unsigned int g) {
     88 	/// \todo check memory cap, increase if necessary
     89 	unsigned int unitsize = 1;
     90 	lash_game_coords_t targetcoords, currentcoords;
     91 	currentspace->g = g;
     92 	currentspace->parent = parent;
     93 	lash_indexToCartesian(&targetcoords, path->w, path->h, &unitsize, &path->target);
     94 	lash_indexToCartesian(&currentcoords, path->w, path->h, &unitsize, &currentindex);
     95 	currentspace->h = lash_getManhattanMagnitudeFromCartesian(targetcoords, currentcoords);
     96 	currentspace->f = (currentspace->h * 10) + currentspace->g; // f score
     97 	currentspace->index = currentindex;
     98 	return path;
     99 }
    100 
    101 int _lash_pathSimpleClose(lash_path_simple_t *path, lash_path_simple_space_t *space) {
    102 	return lash_treePush(path->closedtree, space, NULL);
    103 }
    104 
    105 /**
    106  * \todo weighted movement calculations for semi-passable spaces
    107  */
    108 unsigned int lash_pathSimpleStepProcess(lash_path_simple_t *path, lash_map_simple_t *map, lash_path_simple_space_t *centerspace, lash_path_simple_obstacle_t *obstacleslist, unsigned char obstaclescount) {
    109 	int newx;
    110 	int newy;
    111 	unsigned int unitsize = 1;
    112 	unsigned int freespaces = 0;
    113 	lash_game_coords_t centercoords, newcoords;
    114 	
    115 	if (obstacleslist == NULL || obstaclescount == 0) {
    116 		obstacleslist = _lash_path_default_obstacles;
    117 		obstaclescount = LASH_GAME_PATH_SIMPLE_OBSTACLE_DEFAULT_COUNT;
    118 	}
    119 	
    120 	lash_indexToCartesian(&centercoords, map->w, map->h, &unitsize, (lash_game_map_index_t*)&centerspace->index);
    121 	
    122 	// close the current index
    123 	_lash_pathSimpleClose(path, centerspace);
    124 	
    125 	//printf("Processing index %u\n", centerspace->index);
    126 	
    127 	// loop through adjacent vertical spaces
    128 	for (newy = centercoords.y - 1; newy <= (int)(centercoords.y + 1); newy++) {
    129 	
    130 		// loop through adjacent horizontal spaces
    131 		for (newx = centercoords.x - 1; newx <= (int)(centercoords.x + 1); newx++) {
    132 			
    133 			//printf("x %u y %u ", newx, newy);
    134 			
    135 			// store the movement modifier
    136 			// this is currently only binary - passable or non passable
    137 			float modifier;
    138 			
    139 			// store the new space for editing
    140 			lash_path_simple_space_t *newspace;
    141 			
    142 			// newindex -1 means invalid index
    143 			lash_game_map_index_t newindex = -1;
    144 			
    145 			// initialize the score with diagonal movement
    146 			// change it further down if movement is straight
    147 			// the score is the weight of the movement from the path's startindex to current centerspace, plus this new movement
    148 			unsigned char newscore = centerspace->g + LASH_GAME_PATH_SIMPLE_SCORE_DIAGONAL;
    149 			
    150 			// if out of bounds then do nothing
    151 			if (newx < 0 || newx > *(map->w) - 1 || newy < 0 || newy > *(map->h) -1) {
    152 				//printf("(out of bounds)\n");
    153 				continue;
    154 			}
    155 				
    156 			// lash_game_coords_t handle only unsigned values, so the negatives must be handled with local ints
    157 			newcoords.x = newx;
    158 			newcoords.y = newy;
    159 			
    160 			// find the index of the current adjacent space
    161 			lash_cartesianToIndex(&newindex, map->w, map->h, &unitsize, &newcoords);
    162 			//printf("i %u: ", (unsigned int)newindex);
    163 			
    164 			// modifier related
    165 			modifier = lash_pathSimpleCheckModifier(&(map->layer_path + newindex)->val, obstacleslist, obstaclescount);
    166 			// if not passable, do nothing with this space
    167 			if (modifier == 0.f) {
    168 				//printf("impassable\n");
    169 				continue;
    170 			}
    171 			
    172 			// if the space is already in the closedlist, do nothing with this space
    173 			if (_lash_pathSimpleFindIndexInTree(path->closedtree, newindex)) {
    174 				//printf("closed\n");
    175 				continue;
    176 			}
    177 			
    178 			// update the newscore if movement is straight	
    179 			if (newcoords.y == centercoords.y) {
    180 				// if same square as center
    181 				// this should never be evaluated, as the current square should be on the closed list
    182 				if (newcoords.x == centercoords.x) {
    183 					continue;
    184 				}
    185 				// right of left
    186 				newscore = centerspace->g + LASH_GAME_PATH_SIMPLE_SCORE_STRAIGHT;
    187 			} else if (newcoords.x == centercoords.x) {
    188 				// up or down
    189 				newscore = centerspace->g + LASH_GAME_PATH_SIMPLE_SCORE_STRAIGHT;
    190 			}
    191 			 
    192 			// if we made it this far, it means that the space should be evaluated
    193 			// that means process it for the openlist
    194 			newspace = _lash_pathSimpleFindIndexInTree(path->opentree, newindex);
    195 			
    196 			// if the space is not already in the openlist, add it and update it
    197 			if (newspace == NULL) {
    198 				newspace = _lash_pathSimpleAddSpace(path);
    199 				_lash_pathSimpleUpdateSpace(path, newspace, centerspace, newindex, newscore);
    200 				lash_treePush(path->opentree, newspace, NULL);
    201 			// if not update the existing space
    202 			// compare to the old score
    203 			// if old score is lower change back
    204 			} else {
    205 				lash_path_simple_space_t oldspace;
    206 				memcpy(&oldspace, newspace, sizeof(lash_path_simple_space_t));
    207 				_lash_pathSimpleUpdateSpace(path, newspace, centerspace, newindex, newscore);
    208 				if (newspace->f > oldspace.f)
    209 					memcpy(newspace, &oldspace, sizeof(lash_path_simple_space_t));
    210 			}
    211 			
    212 			//printf("score %u\n", newspace->f);
    213 			
    214 			freespaces++;
    215 		}
    216 	}
    217 	
    218 	return freespaces;
    219 }
    220 
    221 
    222 lash_path_simple_space_t * lash_pathSimpleNext(lash_path_simple_t *path, lash_path_simple_space_t **space) {
    223 	
    224 	if (path->opentree->count == 0) {
    225 		*space = NULL;
    226 	}
    227 
    228 	lash_treeShift(path->opentree, (void*)space);
    229 		
    230 	return (lash_path_simple_space_t*)space;
    231 }
    232 
    233 // 1.0 = full movement, 0.0 = impassable
    234 float lash_pathSimpleCheckModifier(const lash_map_simple_layer_item_t *layeritem, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount) {
    235 	if (layeritem == NULL || obstacleslist == NULL || obstaclescount == 0)
    236 		return -1.0;
    237 		
    238 	int i;
    239 	for (i = 0; i < obstaclescount; i++) {
    240 		if (*layeritem == (obstacleslist+i)->val)
    241 			return (obstacleslist+i)->modifier / (float)LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE;
    242 	}
    243 	return -1.0;
    244 }
    245 
    246 void lash_pathSimpleFree(lash_path_simple_t *path) {
    247 	
    248 	if (path->spaces != NULL)
    249 		free(path->spaces);
    250 
    251 	if (path->opentree != NULL)
    252 		lash_treeFree(path->opentree);
    253 	
    254 	if (path->closedtree != NULL)
    255 		lash_treeFree(path->closedtree);	
    256 
    257 }
    258 
    259 void lash_pathSimpleFinish() {
    260 	if (_lash_path_default_obstacles != NULL)
    261 		free(_lash_path_default_obstacles);
    262 }
    263 
    264 
    265 lash_path_simple_space_t * _lash_pathSimpleFindIndexInTree(lash_tree_t *tree, lash_game_map_index_t index) {
    266 	int i;
    267 	lash_path_simple_space_t *checkspace = NULL;
    268 	
    269 	if (tree == NULL)
    270 		return NULL;
    271 		
    272 	for (i = 0; i < tree->count; i++) {
    273 		checkspace = (lash_path_simple_space_t*)*(tree->item + i);
    274 		if (checkspace->index == index)
    275 			return checkspace;
    276 	}
    277 	
    278 	return NULL;
    279 }
    280 
    281 int lash_pathSimpleCompileFreeSpaces(unsigned int **freeindices, const unsigned int freeindices_capacity, lash_map_simple_layer_t *sourcelayer, const unsigned int sourcelayer_count, lash_path_simple_obstacle_t *obstacleslist, unsigned char obstaclescount) {
    282 	return lash_pathSimpleCompileMaxObstructedSpaces(freeindices, freeindices_capacity, sourcelayer, sourcelayer_count, obstacleslist, obstaclescount, 0.0);
    283 }	
    284 
    285 int lash_pathSimpleCompileMaxObstructedSpaces(unsigned int **freeindices, const unsigned int freeindices_capacity, lash_map_simple_layer_t *sourcelayer, const unsigned int sourcelayer_count, lash_path_simple_obstacle_t *obstacleslist, unsigned char obstaclescount, float modifier_threshold) {
    286 	int i;
    287 	int freeindices_count = 0;
    288 	
    289 	
    290 	if (sourcelayer == NULL || freeindices == NULL)
    291 		return -1;
    292 	
    293 	if (obstacleslist == NULL || obstaclescount == 0) {
    294 		obstacleslist = _lash_path_default_obstacles;
    295 		obstaclescount = LASH_GAME_PATH_SIMPLE_OBSTACLE_DEFAULT_COUNT;
    296 	}
    297 	
    298 	
    299 	for (i = 0; i < sourcelayer_count; i++) {
    300 		if (freeindices_count == freeindices_capacity)
    301 			return freeindices_count;
    302 		
    303 		if (lash_pathSimpleCheckModifier(&(sourcelayer + i)->val, obstacleslist, obstaclescount) > modifier_threshold) {
    304 			*(*freeindices + freeindices_count) = i;
    305 			freeindices_count++;
    306 		}
    307 		
    308 		
    309 	}
    310 	
    311 	return freeindices_count;
    312 }