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


      1 #include <stdlib.h>
      2 #include "liblashgame/lash_game_path.h"
      3 #include "liblashgame/lash_game_standard.h"
      4 #include "liblash/lash_tree.h"
      5 #include "liblash/lash_tree_dump.h"
      6 #include "liblashgame/lash_game_map.h"
      7 
      8 unsigned int _liblashgame_unitsize = 1;
      9 unsigned int _path_simple_mem_increment_step = 0;
     10 unsigned int _path_simple_mem_increments_amount = 0;
     11 
     12 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) {
     13 	lash_game_coords_t offsetcoords;
     14 	lash_game_coords_t targetcoords;
     15 	lash_indexToCartesian(&offsetcoords, map->w, map->h, &_liblashgame_unitsize, &offsetindex);
     16 	lash_indexToCartesian(&targetcoords, map->w, map->h, &_liblashgame_unitsize, &targetindex);
     17 	_path_simple_mem_increment_step = (int)lash_getCartesianMagnitude(targetcoords.x, targetcoords.y, offsetcoords.x, offsetcoords.y) * 4;
     18 	path->w = map->w;
     19 	path->h = map->h;
     20 	path->target = targetindex;
     21 	path->source = offsetindex;
     22 	path->spaces_position = 0;
     23 	
     24 	path->spaces = (lash_path_simple_space_t*)malloc(sizeof(lash_path_simple_space_t) * (unsigned int)*(map->w) * *(map->h));
     25 	if (path->spaces == NULL)
     26 		return NULL;
     27 		
     28 	path->opentree = lash_treeInit(path->opentree, (unsigned int)*(map->w) * *(map->h)); // enough for the whole world if necessary, consider making a realloc routine for this one too
     29 	if (path->opentree == NULL)
     30 		return NULL;
     31 		
     32 	path->closedtree = lash_treeInit(path->closedtree, (unsigned int)*(map->w) * *(map->h)); // enough for the whole world if necessary, consider making a realloc routine for this one too
     33 	if (path->closedtree == NULL)
     34 		return NULL;
     35 	
     36 	path->spacestree =  lash_treeInit(path->spacestree, (unsigned int)*(map->w) * *(map->h));
     37 	if (path->spacestree == NULL)
     38 		return NULL;
     39 	
     40 	lash_treeDumpInit(3);
     41 	lash_treeDumpAdd(path->opentree, "open");
     42 	lash_treeDumpAdd(path->spacestree, "spaces");
     43 	lash_treeDumpAdd(path->closedtree, "closed");
     44 					
     45 	if (lash_pathSimpleUpdateSpace(path, NULL, NULL, offsetindex, 0) == NULL)
     46 		return NULL;
     47 	
     48 	lash_treePush(path->opentree, path->spaces->f, 0);
     49 	
     50 	return path;
     51 }
     52 
     53 int _lash_pathSimpleMemInc(lash_path_simple_t *path) {
     54 	lash_path_simple_space_t *tmp_spaces;
     55 	
     56 	tmp_spaces = realloc(path->spaces, sizeof(lash_path_simple_space_t) * _path_simple_mem_increment_step * (_path_simple_mem_increments_amount + 1));
     57 	
     58 	if (tmp_spaces == NULL)
     59 		return 1;
     60 	
     61 	path->spaces = tmp_spaces;
     62 	
     63 	return 0;
     64 }
     65 
     66 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) {
     67 	/// \todo check memory cap, increase if necessary
     68 	lash_path_simple_space_t *currentspace;
     69 	lash_game_coords_t targetcoords, currentcoords;
     70 	
     71 	if (editspace != NULL) {
     72 		currentspace = editspace;
     73 	} else {
     74 		currentspace = (path->spaces + path->spaces_position);
     75 		currentspace->index = currentindex;
     76 	}
     77 	
     78 	currentspace->g = g;
     79 	currentspace->parent = parent;
     80 	lash_indexToCartesian(&targetcoords, path->w, path->h, &_liblashgame_unitsize, &path->target);
     81 	lash_indexToCartesian(&currentcoords, path->w, path->h, &_liblashgame_unitsize, &currentindex);
     82 	currentspace->h = lash_getManhattanMagnitudeFromCartesian(targetcoords, currentcoords);
     83 	currentspace->f = (currentspace->h * 10) + currentspace->g;
     84 	//lash_treePush(path->opentree, currentspace->f, currentindex);
     85 	
     86 	if (editspace == NULL) {
     87 		lash_treePush(path->spacestree, currentindex, path->spaces_position);
     88 		path->spaces_position++;
     89 	}
     90 	
     91 	return currentspace;
     92 }
     93 
     94 //int lash_pathSimpleStep(lash_path_simple_space_t *parent) {
     95 lash_path_simple_space_t * lash_pathSimpleStepProcess(lash_path_simple_t *path, lash_map_simple_t *map, lash_path_simple_space_t *center, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount) {
     96 	int i;
     97 	int newx;
     98 	int newy;
     99 	lash_game_coords_t centercoords, newcoords;
    100 	//lash_indexToCartesian(&centercoords, lash_path_simple_map->w, lash_path_simple_map->h, 1, &center->index);
    101 	lash_indexToCartesian(&centercoords, map->w, map->h, &_liblashgame_unitsize, (lash_game_map_index_t*)&center->index);
    102 	
    103 	// close the current index
    104 	lash_pathSimpleClose(path, center);
    105 	
    106 	//for (newcoords.y = centercoords.y - 1; newcoords.y <= centercoords.y + 1; newcoords.y++) {
    107 	for (newy = centercoords.y - 1; newy <= centercoords.y + 1; newy++) {
    108 		//for (newcoords.x = centercoords.x - 1; newcoords.x <= centercoords.x + 1; newcoords.x++) {
    109 		for (newx = centercoords.x - 1; newx <= centercoords.x + 1; newx++) {
    110 			lash_game_map_index_t newindex = -1;
    111 			unsigned char newscore = center->g + LASH_GAME_PATH_SIMPLE_SCORE_DIAGONAL;
    112 			float modifier;
    113 			
    114 			// if out of bounds
    115 			//if (newcoords.x < 0 || newcoords.x > *(map->w) - 1 || newcoords.y < 0 || newcoords.y > *(map->h) -1)
    116 			if (newx < 0 || newx > *(map->w) - 1 || newy < 0 || newy > *(map->h) -1)
    117 				continue;
    118 				
    119 			// coords handle only unsigned values, so the negatives must be handled with local ints
    120 			newcoords.x = newx;
    121 			newcoords.y = newy;
    122 			
    123 			lash_cartesianToIndex(&newindex, map->w, map->h, &_liblashgame_unitsize, &newcoords);
    124 			
    125 			// modifier related
    126 			modifier = lash_pathSimpleCheckModifier(&(map->layer_path + newindex)->val, obstacleslist, obstaclescount);
    127 			// if not passable
    128 			if (modifier == 0.f)
    129 				continue;
    130 			
    131 			// if the space already is created in memory, retrieve the index of it from the spaces index tree
    132 			int existingspacespos = -1;
    133 			int existingspacestreepos = lash_treeFindBySort(path->spacestree, newindex);
    134 			//int existingspacestreepos = lash_treeFindByLocal(path->spacestree, newindex);
    135 
    136 			if (existingspacestreepos != -1) {
    137 				existingspacespos = *(path->spacestree->local + existingspacestreepos);
    138 			
    139 				// if the space already is on the closed list...
    140 				if (existingspacespos != -1) {	
    141 					int existingclosedspacespos = lash_treeFindByLocal(path->closedtree, existingspacespos);
    142 					if (existingclosedspacespos != -1)
    143 						continue;
    144 				}
    145 			}
    146 				
    147 			if (newcoords.y == centercoords.y) {
    148 				// if same square as center
    149 				// this should never be evaluated, as the current square should be on the closed list
    150 				if (newcoords.x == centercoords.x) {
    151 					continue;
    152 				}
    153 				// if straight right of left
    154 				newscore = center->g + LASH_GAME_PATH_SIMPLE_SCORE_STRAIGHT;
    155 			} else if (newcoords.x == centercoords.x) {
    156 				// if straight up or down
    157 				newscore = center->g + LASH_GAME_PATH_SIMPLE_SCORE_STRAIGHT;
    158 			}
    159 			
    160 			if (existingspacespos != -1) {
    161 				unsigned int existingopenpos = lash_treeFindByLocal(path->opentree, existingspacespos);
    162 			
    163 			// if this index is NOT already in the openlist... (and space is not added either)
    164 				if (existingopenpos == -1) {
    165 					// add it to the openlist
    166 					lash_pathSimpleUpdateSpace(path, NULL, center, newindex, newscore);
    167 					//lash_treePush(path->opentree, newscore, path->spaces_position - 1);
    168 					lash_treePush(path->opentree, (path->spaces + path->spaces_position - 1)->f, path->spaces_position - 1);
    169 				} else {
    170 					if ((path->spaces + existingspacespos)->g > newscore) {
    171 						lash_pathSimpleUpdateSpace(path, (path->spaces + existingspacespos), center, 0, newscore);
    172 						lash_treeRemove(path->opentree, existingspacestreepos, NULL, NULL);
    173 						//lash_treePush(path->opentree, newscore, existingspacespos);
    174 						lash_treePush(path->opentree, (path->spaces + existingspacespos)->f, path->spaces_position - 1);
    175 					}
    176 				}
    177 			// if the space doesn't exist at all in the space list, it can't have been added to the openlist
    178 			} else {
    179 				lash_pathSimpleUpdateSpace(path, NULL, center, newindex, newscore);
    180 				//lash_treePush(path->opentree, newscore, path->spaces_position - 1);
    181 				
    182 				lash_treePush(path->opentree, (path->spaces + path->spaces_position - 1)->f, path->spaces_position - 1);
    183 				
    184 			}
    185 		}
    186 	}
    187 	
    188 	// remove the next step from the openlist and return it
    189 	// this is the position with the lowest f value
    190 	return lash_pathSimpleNext(path);
    191 }
    192 
    193 int lash_pathSimpleClose(lash_path_simple_t *path, lash_path_simple_space_t *space) {
    194 	unsigned int spacepos = lash_treeFindBySort(path->spacestree, space->index);
    195 	return lash_treePush(path->closedtree, (long int)path->closedtree->position, (unsigned int)(space - path->spaces));
    196 }
    197 
    198 lash_path_simple_space_t * lash_pathSimpleNext(lash_path_simple_t *path) {
    199 	unsigned int nextstepindex;
    200 	long int nextstepf;
    201 	int i;
    202 	
    203 	if (lash_treeShift(path->opentree, &nextstepf, &nextstepindex) == -1)
    204 		return NULL;
    205 		
    206 	return path->spaces + nextstepindex;
    207 }
    208 
    209 // 1.0 = full movement, 0.0 = impassable
    210 float lash_pathSimpleCheckModifier(const lash_map_simple_layer_item_t *layeritem, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount) {
    211 	if (layeritem == NULL || obstacleslist == NULL || obstaclescount == 0)
    212 		return 1;
    213 		
    214 	int i;
    215 	for (i = 0; i < obstaclescount; i++) {
    216 		if (*layeritem == (obstacleslist+i)->val)
    217 			// should be done directly with the bits for speed
    218 			return (obstacleslist+i)->modifier / (float)LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE;
    219 	}
    220 	return 1;
    221 }
    222 
    223 void lash_pathSimpleFree(lash_path_simple_t *path) {
    224 	free(path->opentree);
    225 	free(path->closedtree);
    226 	free(path->spacestree);
    227 	free(path->spaces);
    228 }