Mercurial > hg > batmud > maputils

changeset 73:8bad1e87b45d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updates
author Matti Hamalainen <ccr@tnsp.org>
date Sat, 16 Dec 2006 06:18:24 +0000
parents 17aee03263c9
children fbea15a77235
files Makefile.gen maputils.c mkmap.c mkspecial.c
diffstat 4 files changed, 168 insertions(+), 57 deletions(-) [+]
line wrap: on
line diff
--- a/Makefile.gen	Sat Dec 16 06:16:54 2006 +0000
+++ b/Makefile.gen	Sat Dec 16 06:18:24 2006 +0000
@@ -58,10 +58,10 @@
 
 
 %.cmap: %.raw $(MKMAP_BIN)
-	$(MKMAP_BIN) -o $@ -r 10 -w 21 -h 21 $< -v -d -m 80
+	$(MKMAP_BIN) -o $@ -r 10 -w 21 -h 21 $< -v -d -m 80 -f 99
 
 %.map: %.raw $(MKMAP_BIN)
-	$(MKMAP_BIN) -o $@ -r 10 -w 13 -h 7 $< -v -d -m 70
+	$(MKMAP_BIN) -o $@ -r 10 -w 13 -h 7 $< -v -d -m 70 -f 99
 
 
 votk.html: votk.map $(COLORMAP_BIN)
--- a/maputils.c	Sat Dec 16 06:16:54 2006 +0000
+++ b/maputils.c	Sat Dec 16 06:18:24 2006 +0000
@@ -274,6 +274,7 @@
 		if ((dx >= 0) && (dx < map->w) &&
 			(dy >= 0) && (dy < map->h)) {
 			char c = b->d[(y * b->w) + x];
+
 			if (c != 0)
 				map->d[(dy * map->w) + dx] = c;
 		} else
@@ -317,6 +318,9 @@
 		return -3;
 	}
 	
+	tmp->x = -mx;
+	tmp->y = -my;
+	
 	/* Out with the old, in with the new */
 	freeBlock(*map);
 	*map = tmp;
--- a/mkmap.c	Sat Dec 16 06:16:54 2006 +0000
+++ b/mkmap.c	Sat Dec 16 06:18:24 2006 +0000
@@ -11,6 +11,7 @@
 #include "th_args.h"
 #include "th_string.h"
 
+
 #define	MAX_FILES	(256)
 
 
@@ -186,7 +187,6 @@
 	for (x = 0; x < match->w; x++) {
 		dx = (ox + x);
 		dy = (oy + y);
-		k++;
 		
 		if (dx >= 0 && dx < map->w && dy >= 0 && dy < map->h)
 			c2 = map->d[(dy * map->w) + dx];
@@ -195,16 +195,18 @@
 		
 		c1 = match->d[(y * match->w) + x];
 
+		if ((c1 != 0 && c2 == 0) || (c1 == 0 && c2 != 0)) {
+			/* Other is empty */
+			if (matchEmpty) n++;
+			k++;
+		} else 
+		if (c1 == 0 && c2 == 0) {
+			/* Both empty ... */
+		} else
 		if (c1 == c2) {
 			/* Exact match, increase % */
 			n++;
-		} else
-		if ((c1 != 0 && c2 == 0) || (c1 == 0 && c2 != 0)) {
-			/* Other is empty */
-			if (matchEmpty) n++;
-		} else 
-		if (c1 == 0 && c2 == 0) {
-			/* Both empty ... */
+			k++;
 		} else
 		if (hardDrop) {
 			/* Mismatch, return failure */
@@ -247,21 +249,22 @@
 	
 	o = y = 0;
 	while (!feof(inFile) && (y < tmp->h)) {
-		int x, c = 0;
+		int x = 0, c = 0;
 		
-		for (x = 0; x < tmp->w; x++) {
+		while (x < tmp->w) {
 			c = fgetc(inFile);
 			if (c == '\n' || c == EOF)
 				break;
 			else
 				tmp->d[o++] = c;
+			x++;
 		}
 		
-		if (c != '\n' && c != EOF)
-			c = fgetc(inFile);
-		
+		while ((c = fgetc(inFile)) != EOF && c != '\n') x++;
+
 		if (x != tmp->w) {
-			THERR("Broken block, line width %d != %d\n", x, tmp->w);
+			THERR("Broken block, line width %d != %d on block y=%d\n",
+				x, tmp->w, y);
 			freeBlock(tmp);
 			return NULL;
 		}
@@ -282,15 +285,53 @@
 
 /* Bruteforce search / block matching ..
  */
-BOOL blockSearchBrute(mapblock_t *map, mapblock_t *b, int *x, int *y, float m)
+BOOL blockSearchBruteDo2(mapblock_t *map, mapblock_t *b,
+	int *x, int *y, float m,
+	int dx, int dy, float *vm)
 {
 	int ox, oy;
 	float v;
+
+THPRINT(3, "\nDo2: x=%d, y=%d, m=%1.2f, dx=%d, dy=%d, vm=%1.2f\n",
+	*x, *y, m, dx, dy, *vm);
 	
-	for (oy = -(b->h); oy < (map->h + b->h); oy++)
-	for (ox = -(b->w); ox < (map->w + b->w); ox++) {
+	for (oy = (*y - dy); oy < (*y + dy); oy++)
+	for (ox = (*x - dx); ox < (*x + dx); ox++) {
 		v = matchBlock(map, b, ox, oy, FALSE, optHardDrop);
 		if (v >= m) {
+			*vm = v;
+			*x = ox;
+			*y = oy;
+			return TRUE;
+		}
+	}
+
+	return FALSE;
+}
+
+BOOL blockSearchBruteDo(mapblock_t *map, mapblock_t *b,
+	int *x, int *y, float m,
+	int dx, int dy, float *vm, int skipx, int skipy, int *chkx, int *chky)
+{
+	int ox, oy;
+	float v;
+
+
+	
+THPRINT(3, "\nDo: m=%1.2f, dx=%d, dy=%d, vm=%1.2f, skipx=%d, skipy=%d\n",
+	m, dx, dy, *vm, skipx, skipy);
+
+
+	for (oy = -(dy); oy < (map->h + dy); oy += skipy)
+	for (ox = -(dx); ox < (map->w + dx); ox += skipx) {
+		v = matchBlock(map, b, ox+skipx-1, oy+skipy-1, FALSE, optHardDrop);
+		if (v >= *vm) {
+			*vm = v;
+			*chkx = ox;
+			*chky = oy;
+		}
+		
+		if (v >= m) {
 			*x = ox;
 			*y = oy;
 			return TRUE;
@@ -300,6 +341,35 @@
 	return FALSE;
 }
 
+
+BOOL blockSearchBrute(mapblock_t *map, mapblock_t *b, int *x, int *y, float m, float q)
+{
+	int dx, dy, skip, chkx, chky;
+	float pvm = m * 0.5f, vm = -1;
+	
+	
+	for (skip = 64; skip >= 1; skip /= 2) {
+		dx = ((float) b->w) * q;
+		dy = ((float) b->h) * q;
+		
+		if (blockSearchBruteDo(map, b, x, y, m,
+			dx, dy, &vm, skip, skip, &chkx, &chky))
+			return TRUE;
+		
+		THPRINT(3, "[%d, %d: vm=%1.2f, pvm=%1.2f]\n", chkx, chky, vm, pvm);
+		if (vm > pvm) {
+			pvm = vm;
+			if (blockSearchBruteDo2(map, b, &chkx, &chky, m,
+				skip/2, skip/2, &vm))
+				return TRUE;
+			THPRINT(3, "[Q: %d, %d: vm=%1.2f, pvm=%1.2f]\n", chkx, chky, vm, pvm);
+		}
+	}
+	
+	return FALSE;
+}
+
+
 BOOL blockSearch(mapblock_t *map, mapblock_t *b, int *x, int *y, float m, float q)
 {
 	int ox, oy, dx, dy;
@@ -320,7 +390,7 @@
 
 	THPRINT(2, "?");
 	
-	return blockSearchBrute(map, b, x, y, m);
+	return blockSearchBrute(map, b, x, y, m, q);
 }
 
 
@@ -329,7 +399,7 @@
 	FILE *tmpFile;
 	BOOL isOK, isFirst;
 	int i, n, ox, oy, nmapBlocks = 0;
-	mapblock_t *map = NULL, *tmp = NULL, *initial = NULL;
+	mapblock_t *worldMap = NULL, *tmp = NULL, *initialMap = NULL;
 	mapblock_t **mapBlocks = NULL;
 
 	progName = argv[0];
@@ -349,10 +419,10 @@
 	/* Read initial map */
 	if (optInitialMap) {
 		THMSG(1, "Reading initial map '%s'\n", optInitialMap);
-		initial = parseFile(optInitialMap);
-		if (initial) {
+		initialMap = parseFile(optInitialMap);
+		if (initialMap) {
 			THMSG(2, "Initial dimensions %d x %d\n",
-				initial->w, initial->h);
+				initialMap->w, initialMap->h);
 		} else {
 			THERR("Initial map could not be loaded!\n");
 			exit(1);
@@ -389,31 +459,32 @@
 
 	/* Start matching the blocks with bruteforce
 	 */
-	if (initial) {
-		map = initial;
+	if (initialMap) {
+		worldMap = initialMap;
 	} else if (nmapBlocks > 0) {
 		if (optInverse)
 			tmp = mapBlocks[nmapBlocks - 1];
 		else
 			tmp = mapBlocks[0];
 		
-		if ((map = allocBlock(tmp->w * optMapFactor, tmp->h * optMapFactor)) == NULL) {
-			THERR("Could not allocate initial map.\n");
+		if ((worldMap = allocBlock(tmp->w * optMapFactor, tmp->h * optMapFactor)) == NULL) {
+			THERR("Could not allocate world map.\n");
 			exit(3);
 		}
 		
-		putBlockDo(map, tmp,
-			(map->w / 2) - (tmp->w / 2),
-			(map->h / 2) - (tmp->h / 2));
+		putBlockDo(worldMap, tmp,
+			(worldMap->w / 2) - (tmp->w / 2),
+			(worldMap->h / 2) - (tmp->h / 2));
 	} else {
-		if ((map = allocBlock(optBlockW * optMapFactor, optBlockH * optMapFactor)) == NULL) {
-			THERR("Could not allocate initial map.\n");
+		if ((worldMap = allocBlock(optBlockW * optMapFactor, optBlockH * optMapFactor)) == NULL) {
+			THERR("Could not allocate world map.\n");
 			exit(3);
 		}
 	}
 
 	
-	THMSG(1, "Initialized initial map of (%d x %d)\n", map->w, map->h);
+	THMSG(1, "Initialized world map of (%d x %d)\n",
+		worldMap->w, worldMap->h);
 
 	n = 0;
 	isFirst = TRUE;
@@ -426,10 +497,10 @@
 		for (i = 0; i < nmapBlocks; i++)
 		if (!mapBlocks[i]->mark) {
 			if ((isFirst &&
-			blockSearchBrute(map, mapBlocks[i], &ox, &oy, optMatch)) ||
-			blockSearch(map, mapBlocks[i], &ox, &oy, optMatch, optFudge/100.0f)) {
+			blockSearchBrute(worldMap, mapBlocks[i], &ox, &oy, optMatch, optFudge/100.0f)) ||
+			blockSearch(worldMap, mapBlocks[i], &ox, &oy, optMatch, optFudge/100.0f)) {
 				THPRINT(2, "X");
-				if (putBlock(&map, mapBlocks[i], ox, oy, 15) < 0) {
+				if (putBlock(&worldMap, mapBlocks[i], ox, oy, 15) < 0) {
 					THERR("putBlock(%d, %d, %d) failed!\n",
 						ox, oy, i);
 				}
@@ -445,8 +516,10 @@
 
 	/* Output generated map
 	 */
-	if (map) {
-		THMSG(1, "Outputting generated map ...\n");
+	if (worldMap) {
+		THMSG(1, "Outputting generated map of (%d x %d) ...\n",
+			worldMap->w, worldMap->h);
+
 		if (destFile == NULL)
 			tmpFile = stdout;
 		else if ((tmpFile = fopen(destFile, "wb")) == NULL) {
@@ -455,7 +528,7 @@
 			exit(1);
 		}
 	
-		printBlock(tmpFile, map);
+		printBlock(tmpFile, worldMap);
 	
 		fclose(tmpFile);
 
--- a/mkspecial.c	Sat Dec 16 06:16:54 2006 +0000
+++ b/mkspecial.c	Sat Dec 16 06:18:24 2006 +0000
@@ -23,11 +23,13 @@
 
 int	optBlockW = 21,
 	optBlockH = 21,
+	optInitialX = 0,
+	optInitialY = 0,
 	optMapFactor = 10,
 	optRounds = 100,
 	optReset = 50;
 BOOL	optHardDrop = FALSE;
-float	optMatch = 30.0, optMatchInit = 70.0;
+float	optMatch = 30.0, optMatchInit = 70.0, optFudge = 50.0;
 char	*optInitialMap = NULL;
 
 
@@ -40,12 +42,15 @@
 	{ 3, 'q', "quiet",	"Be quiet", 0 },
 	{ 4, 'm', "match",	"Match percentage", 1 },
 	{ 6, 'M', "minit",	"Initial block match percentage", 1 },
+	{ 13,'f', "fudge",	"Block match fudge factor", 1 },
 	{ 5, 'r', "rounds",	"Processing timeout # rounds", 1 },
 	{ 12,'R', "reset",	"Round reset after", 1 },
 	{ 11,'d', "drop",	"Use hard dropping (bailout on first mismatch)", 0 },
 	{ 8, 'w', "width",	"Block width", 1 },
 	{ 9, 'h', "height",	"Block height", 1 },
 	{ 10,'I', "initial",	"Initial map file", 1 },
+	{ 14,'x', "initial-x",	"Initial map X offset", 1 },
+	{ 15,'y', "initial-y",	"Initial map Y offset", 1 },
 };
 
 const int optListN = (sizeof(optList) / sizeof(optarg_t));
@@ -89,6 +94,11 @@
 		THMSG(1, "Initial Block Match at %1.4f%%\n", optMatchInit);
 		break;
 
+	case 13:
+		optFudge = atof(optArg);
+		THMSG(1, "Block match fudge factor = %1.4f%%\n", optFudge);
+		break;
+
 	case 5:
 		optRounds = atoi(optArg);
 		THMSG(1, "Processing rounds timeout %d\n", optRounds);
@@ -119,6 +129,16 @@
 		THMSG(1, "Using hard dropping (instant bailout on mismatch).\n");
 		break;
 
+	case 14:
+		optInitialX = atoi(optArg);
+		THMSG(1, "Initial map X offset = %d\n", optInitialX);
+		break;
+
+	case 15:
+		optInitialY = atoi(optArg);
+		THMSG(1, "Initial map Y offset = %d\n", optInitialY);
+		break;
+
 	default:
 		THERR("Unknown option '%s'.\n", currArg);
 		return FALSE;
@@ -165,13 +185,13 @@
 		
 		c1 = match->d[(y * match->w) + x];
 
-		if (c1 == c2) {
+		if (c1 == 0 && c2 == 0) {
+			/* Both empty ... */
+		} else
+		if (c1 != 0 && c1 == c2) {
 			/* Exact match, increase % */
 			n++;
 		} else
-		if (c2 == 0 || c1 == 0) {
-			if (matchEmpty) n++;
-		} else 
 		if (hardDrop) {
 			/* Mismatch, return failure */
 			return -1;
@@ -259,21 +279,30 @@
  * [-bw...mapw+bw, -bh...maph+bw]
  */
 BOOL blockSearchBrute(mapblock_t *map, mapblock_t *block,
-	int *x, int *y, float *matchValue)
+	int *x, int *y, float *matchValue, float q)
 {
-	int ox, oy;
+	int ox, oy, dx, dy;
+	float mv = -1;
 	
-	for (oy = -(block->h); oy < (map->h + block->h); oy++)
-	for (ox = -(block->w); ox < (map->w + block->w); ox++) {
+	dx = ((float) block->w) * q;
+	dy = ((float) block->h) * q;
+	
+	for (oy = -(dy); oy < (map->h + dy); oy++) {
+	for (ox = -(dx); ox < (map->w + dx); ox++) {
 		float v;
-		v = matchBlock(map, block, ox, oy, FALSE, optHardDrop);
+		v = matchBlock(map, block, ox + optInitialX, oy + optInitialY, TRUE, optHardDrop);
+		if (v > mv) mv = v;
+		
 		if (v >= *matchValue) {
 			*matchValue = v;
-			*x = ox;
-			*y = oy;
+			*x = ox + optInitialX;
+			*y = oy + optInitialY;
 			return TRUE;
 		}
 	}
+	
+	THPRINT(3, "?");
+	}
 
 	return FALSE;
 }
@@ -401,7 +430,7 @@
 		mapblock_t *resBlock = NULL;
 		
 		THMSG(1, "Matching with initial map ...\n");
-
+		
 		isOK = FALSE;
 		currRounds = 0;
 		while ((currRounds++ < optRounds) && !isOK) {
@@ -421,12 +450,12 @@
 				mv = optMatchInit;
 				resBlock = mapBlocks[i];
 				
-				THPRINT(1, ".");
+				THPRINT(2, ".");
 				resBlock->mark = TRUE;
-		
+				
 				if (blockSearchBrute(initialMap, resBlock,
-					&offsetX, &offsetY, &mv)) {
-					THMSG(1, "Found matching block #%d (%1.3f%%)\n", i, mv);
+					&offsetX, &offsetY, &mv, optFudge)) {
+					THMSG(1, "\nFound matching block #%d (%1.3f%%)\n", i, mv);
 					isOK = TRUE;
 				}
 			}
@@ -445,6 +474,11 @@
 		}
 
 		/* Compute inital map offset shit */
+		THPRINT(3, "%d,%d : %d,%d  :: %d,%d\n",
+			offsetX, offsetY, resBlock->x, resBlock->y,
+			-offsetX + resBlock->x,
+			-offsetY + resBlock->y);
+		
 		initialMap->x = -offsetX + resBlock->x;
 		initialMap->y = -offsetY + resBlock->y;
 	}