liblashgame

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

pathfindfreesquare.c (6343B)


      1 #include "../lash_game_path.h"
      2 #include "../lash_game_map.h"
      3 #include <stdio.h>
      4 #include <unistd.h>
      5 #include <stdlib.h>
      6 
      7 void dumpspaces (lash_path_simple_t *path) {
      8 	int i;
      9 	printf("Spaces dump:\n");
     10 	for (i = 0; i < path->spaces_position; i++) {
     11 		printf("%i=i%i,f%i ", i, (path->spaces+i)->index, (path->spaces+i)->f);
     12 	}
     13 	printf("\n");
     14 }
     15 
     16 
     17 int dumptree(lash_tree_t *tree, char *treename) {
     18 		printf("Tree %s is now size %d: ", treename, tree->position);
     19 		int j;
     20 		//long int lastn = 0;
     21 		int falsesort = 0;
     22 		long int nn, nc;
     23 		unsigned int nl;
     24 		for (j = 1; j <= tree->position; j++) {
     25 			int ti = *(tree->idx + j - 1);
     26 			nn = *(tree->heap + ti);
     27 			nl = *(tree->local + ti);
     28 			nc = *(tree->heap + *(tree->idx + (int)(j / 2) - 1));
     29 			printf("#%u:h%li,l%u ", j, nn, nl);
     30 			if (nn < nc && j > 1)
     31 				falsesort = 1;
     32 		}
     33 		if (falsesort == 1) {
     34 			printf("SORTERROR!\n");
     35 			return 1;
     36 		}
     37 		printf("\n");	
     38 		return 0;
     39 }
     40 
     41 void dumpmappathlayer(lash_map_simple_t *map, unsigned int unitsize, int position, int target, lash_path_simple_space_t *finalpath, unsigned int finalpathcount) {
     42 	lash_game_coords_t tmpcoords;
     43 	lash_game_map_index_t tmpidx;
     44 	for (tmpcoords.y = 0; tmpcoords.y < *map->h; tmpcoords.y++) {
     45 		for (tmpcoords.x = 0; tmpcoords.x < *map->w; tmpcoords.x++) {
     46 			lash_cartesianToIndex(&tmpidx, map->w, map->h, unitsize, &tmpcoords);
     47 			if (tmpidx == position) {
     48 				printf("XX ");
     49 			} else if (tmpidx == target) {
     50 				printf("-- ");
     51 			} else if (finalpath != NULL) {
     52 				int i = 0;
     53 				int onpath = 0;
     54 				for (i = 0; i <= finalpathcount; i++) {
     55 					if (tmpidx == (finalpath+i)->index && onpath == 0) {
     56 						printf(".. ");
     57 						onpath = 1;
     58 					}
     59 				}
     60 				if (onpath == 0) {
     61 					printf("%02i ", (int)lash_mapSimpleLayerPeek(map->layer_path, tmpidx));	
     62 				}
     63 			} else {
     64 				printf("%02i ", (int)lash_mapSimpleLayerPeek(map->layer_path, tmpidx));
     65 			}
     66 		}
     67 		printf("\n");
     68 	}
     69 	printf("\n");	
     70 }
     71 
     72 int main(int argc, char **argv) {
     73 	
     74 	lash_map_simple_t map;
     75 	lash_path_simple_t path;
     76 	lash_path_simple_space_t *space;
     77 	
     78 	int w = -1;
     79 	int h = -1;
     80 	int idx = -1;
     81 	int r = -1;
     82 	char arg = -1;
     83 	
     84 	int i = 0;
     85 	int xclip = 0;
     86 	int yclip = 0;
     87 	
     88 	unsigned int indexunit;
     89 	unsigned int dleft;
     90 	unsigned int dright;
     91 	unsigned int dtop;
     92 	unsigned int dbottom;
     93 	
     94 	unsigned int ctop;
     95 	unsigned int cbottom;
     96 	unsigned int cleft;
     97 	unsigned int cright;
     98 	
     99 	unsigned int spacestotal;
    100 	lash_game_map_index_t *spaces;
    101 	unsigned int spacescount;
    102 	
    103 	lash_game_map_index_t target;
    104 	
    105 	unsigned char obstaclestotal = 2;
    106 	
    107 	lash_path_simple_obstacle_t *obstacles = (lash_path_simple_obstacle_t*)malloc(sizeof(lash_path_simple_obstacle_t) * 3);
    108 	obstacles->val = 0;
    109 	obstacles->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE;
    110 	(obstacles+1)->val = 1;
    111 	(obstacles+1)->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_FULL;
    112 	(obstacles+2)->val = 2;
    113 	(obstacles+2)->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_HALF;
    114 	
    115 	lash_path_simple_space_t *finalpath;
    116 	
    117 	time_t t;
    118 	
    119 	srand((unsigned) time(&t));
    120 		
    121 	while ((arg = getopt(argc, argv, "w:h:i:r:")) != -1) {
    122 		switch(arg) {
    123 			case 'w':
    124 				w = atoi(optarg);
    125 				break;
    126 			case 'h':
    127 				h = atoi(optarg);
    128 				break;
    129 			case 'i':
    130 				idx = atoi(optarg);
    131 				break;
    132 			case 'r':
    133 				r = atoi(optarg);
    134 				break;
    135 		}
    136 	}
    137 	
    138 	if (w < 0 || h < 0 || idx < 0 || r < 0) {
    139 		fprintf(stderr, "All options not set, exiting ...\n");
    140 		return 1;
    141 	}
    142 	
    143 	printf("Width %d Height %d index %d radius %d\n", w, h, idx, r);
    144 		
    145 	lash_mapSimpleInit(&map, &w, &h);
    146 	
    147 	for (i = 0; i < w * h; i++) {
    148 		if (i != idx)
    149 			lash_mapSimpleLayerPoke(map.layer_path, i, rand() % 2);
    150 	}
    151 	
    152 	dumpmappathlayer(&map, 1, idx, -1, NULL, 0);
    153 	
    154 	dtop = (int)floor(idx / w);
    155 	dbottom = h - dtop - 1;
    156 	dleft = idx - dtop * w;
    157 	dright = ((dtop + 1) * w) - idx - 1;
    158 	
    159 	ctop = r > dtop ? dtop : r;
    160 	cbottom = r > dbottom ? dbottom : r;
    161 	cleft = r > dleft ? dleft : r;
    162 	cright = r > dright ? dright : r;
    163 	
    164 	spacestotal = (cright + cleft + 1) * (cbottom + ctop + 1);
    165 	
    166 	printf("Spaces to left edge %d clipping %d\n", dleft, cleft);
    167 	printf("Spaces to right edge %d clipping %d\n", dright, cright);
    168 	printf("Spaces to upper edge %d clipping %d\n", dtop, ctop);
    169 	printf("Spaces to lower edge %d clipping %d\n", dbottom, cbottom);
    170 	printf("Total spaces in clip %d\n", spacestotal);
    171 		
    172 	spaces = (lash_game_map_index_t*)malloc(sizeof(lash_game_map_index_t) * spacestotal);
    173 	spacescount = 0;
    174 	
    175 	for (yclip = idx - (ctop * w); yclip <= idx + (cbottom * w); yclip += w) {
    176 		for (xclip = yclip - cleft; xclip <= yclip + cright; xclip++) {
    177 			lash_map_simple_layer_item_t item = lash_mapSimpleLayerPeek(map.layer_path, xclip);
    178 			if (xclip == idx) {
    179 				printf("XX ");
    180 			} else {
    181 				printf("%.2d ", item);
    182 				
    183 				// here insert obstacleslist check
    184 				//if (item == 0) {
    185 				if (lash_pathSimpleCheckModifier(&item, obstacles, obstaclestotal) > 0.0) {
    186 					*(spaces + spacescount) = xclip;
    187 					spacescount++;
    188 				} else {
    189 					//fprintf(stderr, "item %d idx %d is impassable\n", item, xclip);
    190 				}
    191 			}
    192 		}
    193 		printf("\n");
    194 	}
    195 	
    196 	// spacescount + 1 but original position is also reckoned not open
    197 	printf("Open spaces %d\n", spacescount);
    198 	
    199 	if (spacescount == 0) {
    200 		return 0;
    201 	}
    202 	
    203 	target = rand() % spacescount;
    204 	printf("Target pointer pos is %d\n", target);
    205 	printf("Target is %d\n", *(spaces + target));
    206 	dumpmappathlayer(&map, 1, idx, *(spaces + target), NULL, 0);
    207 
    208 	lash_pathSimpleInit(&path, &map, idx, *(spaces + target));
    209 	space = lash_pathSimpleNext(&path);
    210 	space = lash_pathSimpleStepProcess(&path, &map, space, obstacles, obstaclestotal);
    211 	while (space->index != path.target) {
    212 			space = lash_pathSimpleStepProcess(&path, &map, space, obstacles, obstaclestotal);
    213 			if (space == NULL) {
    214 				printf("No path possible!!\n");
    215 				break;
    216 			}
    217 	} 
    218 		
    219 	i = 0;
    220 	
    221 	finalpath = (lash_path_simple_space_t*)malloc(sizeof(lash_path_simple_space_t) * (path.closedtree->position + 1));
    222 	*(finalpath + 0) = *space;
    223 	if (finalpath->index != path.target) {
    224 		printf("No path possible!!\n");
    225 	} else {
    226 		do {
    227 			space = (finalpath + i)->parent;
    228 			if (space != NULL) {
    229 				i++;
    230 				*(finalpath + i) = *space;
    231 			}
    232 		} while (space != NULL);
    233 	}
    234 	
    235 	dumpmappathlayer(&map, 1, idx, *(spaces + target), finalpath, i);
    236 	
    237 	
    238 	lash_pathSimpleFree(&path);
    239 	lash_mapSimpleFree(&map);
    240 	free(spaces);
    241 	free(finalpath);
    242 	free(obstacles);
    243 	
    244 	return 0;
    245 	
    246 }
    247