liblashgame

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

pathsimpledemo.c (8868B)


      1 #include "../lash_game_path_simple.h"
      2 #include "../lash_game_map.h"
      3 #include "../lash_game_standard.h"
      4 #include "liblash/lash_tree3_dump.h"
      5 
      6 #include "liblash/lash_debug_timer.h"
      7 
      8 #include <stdio.h>
      9 #include <unistd.h>
     10 #include <stdlib.h>
     11 #include <math.h>
     12 #include <string.h>
     13 
     14 #define LASH_X_TEST_COUNT 1000
     15 
     16 int loadMap(char *filename, int *w, int *h, int *s, int *t, char **savemap) {
     17 	FILE *f;
     18 	size_t fpos;
     19 	
     20 	unsigned char buffer[1024];
     21 	char *tmpmap;
     22 	
     23 	f = fopen(filename, "rb");
     24 	
     25 	if (f == NULL)
     26 		return 1;
     27 		
     28 	fpos = fread(buffer, 1, 8, f);
     29 	
     30 	*w = (int)(buffer[0] | buffer[1] << 8);
     31 	*h = (int)(buffer[2] | buffer[3] << 8);
     32 	*s = (int)(buffer[4] | buffer[5] << 8);
     33 	*t = (int)(buffer[6] | buffer[7] << 8);
     34 	
     35 	tmpmap = (char*)calloc(*w * *h, sizeof(char));
     36 	if (tmpmap == NULL)
     37 		return 1;
     38 	
     39 	fseek(f, fpos, SEEK_SET);
     40 	
     41 	fpos += fread(buffer, 1, (size_t)*w, f);
     42 	
     43 	// if data in file is not aligned to w this will cause a segfault
     44 	while (!feof(f)) {
     45 		memcpy((tmpmap + fpos - *w - 8), buffer, (size_t)*w);
     46 		fseek(f, fpos, SEEK_SET);
     47 		fpos += fread(buffer, 1, (size_t)*w, f);
     48 		
     49 	}
     50 	
     51 	fclose(f);
     52 	
     53 	*savemap = tmpmap;
     54 	
     55 	return 0;
     56 }
     57 
     58 void freeMap(char *savemap) {
     59 	if (savemap != NULL)
     60 		free(savemap);
     61 }
     62 
     63 void dumpmappathlayer(lash_map_simple_t *map, unsigned int unitsize, int start, int target, int position, lash_path_simple_space_t *finalpath, unsigned int finalpathcount) {
     64 	lash_game_coords_t tmpcoords;
     65 	lash_game_map_index_t tmpidx;
     66 	for (tmpcoords.y = 0; tmpcoords.y < *map->h; tmpcoords.y++) {
     67 		for (tmpcoords.x = 0; tmpcoords.x < *map->w; tmpcoords.x++) {
     68 			lash_cartesianToIndex(&tmpidx, map->w, map->h, &unitsize, &tmpcoords);
     69 			if (tmpidx == start) {
     70 				printf("XX ");
     71 			} else if (tmpidx == target) {
     72 				printf("-- ");
     73 			} else if (tmpidx == position) {
     74 				printf("?? ");
     75 			} else if (finalpath != NULL) {
     76 				int i = 0;
     77 				int onpath = 0;
     78 				for (i = 0; i <= finalpathcount; i++) {
     79 					if (tmpidx == (finalpath+i)->index && onpath == 0) {
     80 						printf(".. ");
     81 						onpath = 1;
     82 					}
     83 				}
     84 				if (onpath == 0) {
     85 					printf("%02i ", (int)lash_mapSimpleLayerPeek(map->layer_path, tmpidx));	
     86 				}
     87 			} else {
     88 				printf("%02i ", (int)lash_mapSimpleLayerPeek(map->layer_path, tmpidx));
     89 			}
     90 		}
     91 		printf("\n");
     92 	}
     93 	printf("\n");	
     94 	fflush(stdout);
     95 }
     96 
     97 int main(int argc, char **argv) {
     98 	
     99 	lash_map_simple_t map;
    100 	lash_path_simple_t path;
    101 	lash_path_simple_space_t *space;
    102 	lash_debug_timer_t timer;
    103 	
    104 	int w = -1;
    105 	int h = -1;
    106 	int idx = -1;
    107 	int savedtarget = -1;
    108 	int r = -1;
    109 	char arg = -1;
    110 	char *filename = NULL;
    111 	
    112 	int i = 0;
    113 	int xclip = 0;
    114 	int yclip = 0;
    115 	
    116 	unsigned int indexunit;
    117 	unsigned int dleft;
    118 	unsigned int dright;
    119 	unsigned int dtop;
    120 	unsigned int dbottom;
    121 	
    122 	unsigned int ctop;
    123 	unsigned int cbottom;
    124 	unsigned int cleft;
    125 	unsigned int cright;
    126 	
    127 	unsigned int spacestotal;
    128 	lash_game_map_index_t *spaces;
    129 	unsigned int spacescount;
    130 	
    131 	unsigned int pathopenstepsresult;
    132 	int impossible = 0;
    133 	unsigned int attemptedsteps;
    134 	unsigned int testcount = LASH_X_TEST_COUNT;
    135 	
    136 	lash_game_map_index_t target;
    137 	lash_game_map_index_t targetglobalindex;
    138 	
    139 	char *savedmap = NULL;
    140 	
    141 	unsigned char obstaclestotal = 2;
    142 	
    143 	int dumpeverystep = 0;
    144 	
    145 	lash_path_simple_obstacle_t *obstacles = (lash_path_simple_obstacle_t*)malloc(sizeof(lash_path_simple_obstacle_t) * 3);
    146 	obstacles->val = 0;
    147 	obstacles->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_NONE;
    148 	(obstacles+1)->val = 1;
    149 	(obstacles+1)->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_FULL;
    150 	(obstacles+2)->val = 2;
    151 	(obstacles+2)->modifier = LASH_GAME_PATH_SIMPLE_OBSTACLE_MODIFIER_HALF;
    152 	
    153 	lash_path_simple_space_t *finalpath;
    154 	
    155 	time_t t;
    156 	
    157 	srand((unsigned) time(&t));
    158 		
    159 	while ((arg = getopt(argc, argv, "w:h:i:r:f:c:d")) != -1) {
    160 		switch(arg) {
    161 			case 'w':
    162 				w = atoi(optarg);
    163 				break;
    164 			case 'h':
    165 				h = atoi(optarg);
    166 				break;
    167 			case 'i':
    168 				idx = atoi(optarg);
    169 				break;
    170 			case 'r':
    171 				r = atoi(optarg);
    172 				break;
    173 			case 'c':
    174 				testcount = atoi(optarg);
    175 				break;
    176 			case 'd':
    177 				dumpeverystep = 1;
    178 				break;
    179 			case 'f':
    180 				filename = optarg;
    181 				break;
    182 		}
    183 	}
    184 	
    185 	if (filename != NULL) {
    186 		if (strcmp(filename, "")) {
    187 			if (loadMap(filename, &w, &h, &idx, &savedtarget, &savedmap))
    188 				return 1;
    189 			lash_mapSimpleInit(&map, &w, &h);
    190 			for (i = 0; i < w * h; i++)
    191 				lash_mapSimpleLayerPoke(map.layer_path, i, *(savedmap + i));
    192 		}
    193 	}
    194 	
    195 	if (savedmap != NULL) {
    196 		freeMap(savedmap);
    197 	} else {
    198 		if (w < 0 || h < 0 || r < 0) {
    199 			fprintf(stderr, "All options not set, exiting ...\n");
    200 			return 1;
    201 		} else {
    202 			lash_mapSimpleInit(&map, &w, &h);
    203 	
    204 			for (i = 0; i < w * h; i++) {
    205 				if (i != idx)
    206 					lash_mapSimpleLayerPoke(map.layer_path, i, rand() % 2);
    207 			}
    208 		}
    209 	}
    210 	
    211 	printf("Width %d Height %d index %d radius %d target %d\n", w, h, idx, r, savedtarget);
    212 	
    213 	// can potentially go on forever/for a long time if no/few vacant spaces are available
    214 	while (idx == -1) {
    215 		unsigned int trytarget = rand() % (w * h);
    216 		if (lash_mapSimpleLayerPeek(map.layer_path, trytarget) == 0)
    217 			idx = (int)trytarget;
    218 	}
    219 	
    220 	dumpmappathlayer(&map, 1, idx, -1, -1, NULL, 0);
    221 	
    222 	dtop = (int)floor(idx / w);
    223 	dbottom = h - dtop - 1;
    224 	dleft = idx - dtop * w;
    225 	dright = ((dtop + 1) * w) - idx - 1;
    226 	
    227 	ctop = r > dtop ? dtop : r;
    228 	cbottom = r > dbottom ? dbottom : r;
    229 	cleft = r > dleft ? dleft : r;
    230 	cright = r > dright ? dright : r;
    231 	
    232 	spacestotal = (cright + cleft + 1) * (cbottom + ctop + 1);
    233 	
    234 	printf("Spaces to left edge %d clipping %d\n", dleft, cleft);
    235 	printf("Spaces to right edge %d clipping %d\n", dright, cright);
    236 	printf("Spaces to upper edge %d clipping %d\n", dtop, ctop);
    237 	printf("Spaces to lower edge %d clipping %d\n", dbottom, cbottom);
    238 	printf("Total spaces in clip %d\n", spacestotal);
    239 		
    240 	spaces = (lash_game_map_index_t*)malloc(sizeof(lash_game_map_index_t) * spacestotal);
    241 	spacescount = 0;
    242 	
    243 	
    244 	
    245 	for (yclip = idx - (ctop * w); yclip <= idx + (cbottom * w); yclip += w) {
    246 		for (xclip = yclip - cleft; xclip <= yclip + cright; xclip++) {
    247 			lash_map_simple_layer_item_t item = lash_mapSimpleLayerPeek(map.layer_path, xclip);
    248 			if (xclip == idx) {
    249 				printf("XX ");
    250 			} else {
    251 				printf("%.2d ", item);
    252 				
    253 				// here insert obstacleslist check
    254 				//if (item == 0) {
    255 				if (lash_pathSimpleCheckModifier(&item, obstacles, obstaclestotal) > 0.0) {
    256 					*(spaces + spacescount) = xclip;
    257 					spacescount++;
    258 				} else {
    259 					//fprintf(stderr, "item %d idx %d is impassable\n", item, xclip);
    260 				}
    261 			}
    262 		}
    263 		printf("\n");
    264 	}
    265 	
    266 	// spacescount + 1 but original position is also reckoned not open
    267 	printf("Open spaces %d\n", spacescount);
    268 	
    269 	if (spacescount == 0) {
    270 		return 0;
    271 	}
    272 	
    273 	if (savedtarget == -1) {
    274 		target = rand() % spacescount;
    275 		printf("Target pointer pos is %d\n", (int)target);
    276 		targetglobalindex = *(spaces + target);
    277 	} else {
    278 		printf("Target is global pointer pos %d (from saved file)\n", (int)savedtarget);
    279 		targetglobalindex = savedtarget;
    280 	}
    281 		
    282 	
    283 	printf("Target is %d\n", (int)targetglobalindex);
    284 	dumpmappathlayer(&map, 1, idx, targetglobalindex, -1, NULL, 0);
    285 
    286 	// CALCULATE THE PATH
    287 	
    288 	lash_debugTimerReset(&timer);
    289 	
    290 	for (i = 0; i < testcount; i++) {
    291 		long ticksoutputcompensate = 0;
    292 		lash_pathSimpleInit(&path, &map, idx, targetglobalindex);
    293 		
    294 		lash_treeDumpInit(2);
    295 		lash_treeDumpAdd(path.opentree, "open");
    296 		lash_treeDumpAdd(path.closedtree, "closed");
    297 		
    298 		lash_pathSimpleNext(&path, &space);
    299 		//pathopenstepsresult = lash_pathSimpleStepProcess(&path, &map, space, obstacles, obstaclestotal);
    300 	
    301 	
    302 		attemptedsteps = 0;
    303 		lash_debugTimerStart(&timer);
    304 		while (space->index != path.target) {
    305 			
    306 			if (dumpeverystep && i == 0) {
    307 				lash_debugTimerPause(&timer);
    308 				printf("\ndumping idx %u\n", (unsigned int)space->index);
    309 				dumpmappathlayer(&map, 1, idx, targetglobalindex, space->index, NULL, 0);
    310 				lash_debugTimerPause(&timer);
    311 			}
    312 			
    313 			pathopenstepsresult = lash_pathSimpleStepProcess(&path, &map, space, obstacles, obstaclestotal);
    314 			attemptedsteps++;
    315 			lash_pathSimpleNext(&path, &space);
    316 			
    317 			if (space == NULL) {
    318 				impossible = 1;
    319 				break;
    320 			}
    321 			
    322 		} 
    323 		lash_debugTimerStop(&timer);
    324 	} //for test count
    325 	
    326 	
    327 	printf("number of runs: %u\ntotal ticks: %li\naverage ticks: %i\nattempted steps: %u\n", timer.count, timer.total, lash_debugTimerGetAverage(&timer), attemptedsteps);
    328 		
    329 	i = 0;
    330 	
    331 	if (!impossible) {
    332 		finalpath = (lash_path_simple_space_t*)malloc(sizeof(lash_path_simple_space_t) * (path.closedtree->count + 1));
    333 		*(finalpath + 0) = *space;
    334 		
    335 		do {
    336 			space = (finalpath + i)->parent;
    337 			if (space != NULL) {
    338 				i++;
    339 				*(finalpath + i) = *space;
    340 			}
    341 		} while (space != NULL);
    342 		
    343 		dumpmappathlayer(&map, 1, idx, targetglobalindex, -1, finalpath, i);
    344 		free(finalpath);
    345 	} else {
    346 		printf("No path possible!\n");
    347 	}
    348 	
    349 	lash_pathSimpleFree(&path);
    350 	lash_mapSimpleFree(&map);
    351 	free(spaces);
    352 	free(obstacles);
    353 	
    354 	return 0;
    355 	
    356 }
    357