liblashgame

lash_game_path.c (9301B)

---

 #include <stdlib.h>
 #include "liblashgame/lash_game_path.h"
 #include "liblashgame/lash_game_standard.h"
 #include "liblash/lash_tree.h"
 #include "liblash/lash_tree_dump.h"
 #include "liblashgame/lash_game_map.h"
 
 unsigned int _liblashgame_unitsize = 1;
 unsigned int _path_simple_mem_increment_step = 0;
 unsigned int _path_simple_mem_increments_amount = 0;
 
 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) {
 	lash_game_coords_t offsetcoords;
 	lash_game_coords_t targetcoords;
 	lash_indexToCartesian(&offsetcoords, map->w, map->h, &_liblashgame_unitsize, &offsetindex);
 	lash_indexToCartesian(&targetcoords, map->w, map->h, &_liblashgame_unitsize, &targetindex);
 	_path_simple_mem_increment_step = (int)lash_getCartesianMagnitude(targetcoords.x, targetcoords.y, offsetcoords.x, offsetcoords.y) * 4;
 	path->w = map->w;
 	path->h = map->h;
 	path->target = targetindex;
 	path->source = offsetindex;
 	path->spaces_position = 0;
 	
 	path->spaces = (lash_path_simple_space_t*)malloc(sizeof(lash_path_simple_space_t) * (unsigned int)*(map->w) * *(map->h));
 	if (path->spaces == NULL)
 		return NULL;
 		
 	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
 	if (path->opentree == NULL)
 		return NULL;
 		
 	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
 	if (path->closedtree == NULL)
 		return NULL;
 	
 	path->spacestree =  lash_treeInit(path->spacestree, (unsigned int)*(map->w) * *(map->h));
 	if (path->spacestree == NULL)
 		return NULL;
 	
 	lash_treeDumpInit(3);
 	lash_treeDumpAdd(path->opentree, "open");
 	lash_treeDumpAdd(path->spacestree, "spaces");
 	lash_treeDumpAdd(path->closedtree, "closed");
 					
 	if (lash_pathSimpleUpdateSpace(path, NULL, NULL, offsetindex, 0) == NULL)
 		return NULL;
 	
 	lash_treePush(path->opentree, path->spaces->f, 0);
 	
 	return path;
 }
 
 int _lash_pathSimpleMemInc(lash_path_simple_t *path) {
 	lash_path_simple_space_t *tmp_spaces;
 	
 	tmp_spaces = realloc(path->spaces, sizeof(lash_path_simple_space_t) * _path_simple_mem_increment_step * (_path_simple_mem_increments_amount + 1));
 	
 	if (tmp_spaces == NULL)
 		return 1;
 	
 	path->spaces = tmp_spaces;
 	
 	return 0;
 }
 
 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) {
 	/// \todo check memory cap, increase if necessary
 	lash_path_simple_space_t *currentspace;
 	lash_game_coords_t targetcoords, currentcoords;
 	
 	if (editspace != NULL) {
 		currentspace = editspace;
 	} else {
 		currentspace = (path->spaces + path->spaces_position);
 		currentspace->index = currentindex;
 	}
 	
 	currentspace->g = g;
 	currentspace->parent = parent;
 	lash_indexToCartesian(&targetcoords, path->w, path->h, &_liblashgame_unitsize, &path->target);
 	lash_indexToCartesian(&currentcoords, path->w, path->h, &_liblashgame_unitsize, &currentindex);
 	currentspace->h = lash_getManhattanMagnitudeFromCartesian(targetcoords, currentcoords);
 	currentspace->f = (currentspace->h * 10) + currentspace->g;
 	//lash_treePush(path->opentree, currentspace->f, currentindex);
 	
 	if (editspace == NULL) {
 		lash_treePush(path->spacestree, currentindex, path->spaces_position);
 		path->spaces_position++;
 	}
 	
 	return currentspace;
 }
 
 //int lash_pathSimpleStep(lash_path_simple_space_t *parent) {
 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) {
 	int i;
 	int newx;
 	int newy;
 	lash_game_coords_t centercoords, newcoords;
 	//lash_indexToCartesian(&centercoords, lash_path_simple_map->w, lash_path_simple_map->h, 1, &center->index);
 	lash_indexToCartesian(&centercoords, map->w, map->h, &_liblashgame_unitsize, (lash_game_map_index_t*)&center->index);
 	
 	// close the current index
 	lash_pathSimpleClose(path, center);
 	
 	//for (newcoords.y = centercoords.y - 1; newcoords.y <= centercoords.y + 1; newcoords.y++) {
 	for (newy = centercoords.y - 1; newy <= centercoords.y + 1; newy++) {
 		//for (newcoords.x = centercoords.x - 1; newcoords.x <= centercoords.x + 1; newcoords.x++) {
 		for (newx = centercoords.x - 1; newx <= centercoords.x + 1; newx++) {
 			lash_game_map_index_t newindex = -1;
 			unsigned char newscore = center->g + LASH_GAME_PATH_SIMPLE_SCORE_DIAGONAL;
 			float modifier;
 			
 			// if out of bounds
 			//if (newcoords.x < 0 || newcoords.x > *(map->w) - 1 || newcoords.y < 0 || newcoords.y > *(map->h) -1)
 			if (newx < 0 || newx > *(map->w) - 1 || newy < 0 || newy > *(map->h) -1)
 				continue;
 				
 			// coords handle only unsigned values, so the negatives must be handled with local ints
 			newcoords.x = newx;
 			newcoords.y = newy;
 			
 			lash_cartesianToIndex(&newindex, map->w, map->h, &_liblashgame_unitsize, &newcoords);
 			
 			// modifier related
 			modifier = lash_pathSimpleCheckModifier(&(map->layer_path + newindex)->val, obstacleslist, obstaclescount);
 			// if not passable
 			if (modifier == 0.f)
 				continue;
 			
 			// if the space already is created in memory, retrieve the index of it from the spaces index tree
 			int existingspacespos = -1;
 			int existingspacestreepos = lash_treeFindBySort(path->spacestree, newindex);
 			//int existingspacestreepos = lash_treeFindByLocal(path->spacestree, newindex);
 
 			if (existingspacestreepos != -1) {
 				existingspacespos = *(path->spacestree->local + existingspacestreepos);
 			
 				// if the space already is on the closed list...
 				if (existingspacespos != -1) {	
 					int existingclosedspacespos = lash_treeFindByLocal(path->closedtree, existingspacespos);
 					if (existingclosedspacespos != -1)
 						continue;
 				}
 			}
 				
 			if (newcoords.y == centercoords.y) {
 				// if same square as center
 				// this should never be evaluated, as the current square should be on the closed list
 				if (newcoords.x == centercoords.x) {
 					continue;
 				}
 				// if straight right of left
 				newscore = center->g + LASH_GAME_PATH_SIMPLE_SCORE_STRAIGHT;
 			} else if (newcoords.x == centercoords.x) {
 				// if straight up or down
 				newscore = center->g + LASH_GAME_PATH_SIMPLE_SCORE_STRAIGHT;
 			}
 			
 			if (existingspacespos != -1) {
 				unsigned int existingopenpos = lash_treeFindByLocal(path->opentree, existingspacespos);
 			
 			// if this index is NOT already in the openlist... (and space is not added either)
 				if (existingopenpos == -1) {
 					// add it to the openlist
 					lash_pathSimpleUpdateSpace(path, NULL, center, newindex, newscore);
 					//lash_treePush(path->opentree, newscore, path->spaces_position - 1);
 					lash_treePush(path->opentree, (path->spaces + path->spaces_position - 1)->f, path->spaces_position - 1);
 				} else {
 					if ((path->spaces + existingspacespos)->g > newscore) {
 						lash_pathSimpleUpdateSpace(path, (path->spaces + existingspacespos), center, 0, newscore);
 						lash_treeRemove(path->opentree, existingspacestreepos, NULL, NULL);
 						//lash_treePush(path->opentree, newscore, existingspacespos);
 						lash_treePush(path->opentree, (path->spaces + existingspacespos)->f, path->spaces_position - 1);
 					}
 				}
 			// if the space doesn't exist at all in the space list, it can't have been added to the openlist
 			} else {
 				lash_pathSimpleUpdateSpace(path, NULL, center, newindex, newscore);
 				//lash_treePush(path->opentree, newscore, path->spaces_position - 1);
 				
 				lash_treePush(path->opentree, (path->spaces + path->spaces_position - 1)->f, path->spaces_position - 1);
 				
 			}
 		}
 	}
 	
 	// remove the next step from the openlist and return it
 	// this is the position with the lowest f value
 	return lash_pathSimpleNext(path);
 }
 
 int lash_pathSimpleClose(lash_path_simple_t *path, lash_path_simple_space_t *space) {
 	unsigned int spacepos = lash_treeFindBySort(path->spacestree, space->index);
 	return lash_treePush(path->closedtree, (long int)path->closedtree->position, (unsigned int)(space - path->spaces));
 }
 
 lash_path_simple_space_t * lash_pathSimpleNext(lash_path_simple_t *path) {
 	unsigned int nextstepindex;
 	long int nextstepf;
 	int i;
 	
 	if (lash_treeShift(path->opentree, &nextstepf, &nextstepindex) == -1)
 		return NULL;
 		
 	return path->spaces + nextstepindex;
 }
 
 // 1.0 = full movement, 0.0 = impassable
 float lash_pathSimpleCheckModifier(const lash_map_simple_layer_item_t *layeritem, const lash_path_simple_obstacle_t *obstacleslist, const unsigned char obstaclescount) {
 	if (layeritem == NULL || obstacleslist == NULL || obstaclescount == 0)
 		return 1;
 		
 	int i;
 	for (i = 0; i < obstaclescount; i++) {
 		if (*layeritem == (obstacleslist+i)->val)
 			// should be done directly with the bits for speed
 			return (obstacleslist+i)->modifier / (float)LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE;
 	}
 	return 1;
 }
 
 void lash_pathSimpleFree(lash_path_simple_t *path) {
 	free(path->opentree);
 	free(path->closedtree);
 	free(path->spacestree);
 	free(path->spaces);
 }