Thread: WOD/Pre-patch
View Single Post
12-09-14, 08:44 AM   #704
atl77
A Chromatic Dragonspawn
Join Date: Oct 2014
Posts: 179
New algorithm for quest objective area

@ircdirk, I have created a new algorithm that worked quite well for the test data that I collected. I expand every coordinate with a circle using a bresenham algorithm and reduce the area with a game-of-life-like algorithm (the code in JS, but I can probably easily port it in any language you want):

Code:
function newgrid() {
	var grid = [];
	for (var x = 0; x < 100; x++) {
		grid[x] = [];
		for (var y = 0; y < 100; y++) {
			grid[x][y] = false;
		}
	}
	return grid;
}

function coords2grid(coords, radius, shrink) {

	// initialize grids
	var grid = newgrid();

	// set reasonable default radius
	radius = radius || 5;

	// fill/expand all coords circularly (using a modified Bresenham algorithm)
	for (var c = 0; c < coords.length; c++) {
		var cx = coords[c][0] | 0,
			cy = coords[c][1] | 0,
			rx = radius, 
			ry = 0,
			dx,
			dy,
			ln,
			rerr = radius;
		for (ln = rx; ln > 0 ; ln--) {
			(grid[cx+rx-ln] || [])[cy+ry] = true;
			(grid[cx-rx+ln] || [])[cy+ry] = true;
			(grid[cx-ry] || [])[cy-rx+ln] = true;
			(grid[cx+ry] || [])[cy-rx+ln] = true;
		}
		while (ry < rx) {
			dy = (ry++ << 1) + 1;
			rerr -= dy;
			if (rerr < 0) {
				dx = 1 - (rx-- << 1)
				rerr -= dx;
			}
			for (ln = rx; ln > 0 ; ln--) {
				(grid[cx+rx-ln] || [])[cy+ry] = true;
				(grid[cx-rx+ln] || [])[cy+ry] = true;
				(grid[cx-ry] || [])[cy-rx+ln] = true;
				(grid[cx+ry] || [])[cy-rx+ln] = true;
			}
		}
	}

	shrink = shrink || radius - 1;
	// reduce the shape based on a simple "game of life"-like algorithm in multiple steps
	var s, grid2;
	for (var s = shrink; s >= 0; s--) {
		grid2 = newgrid();
		for (x = 1; x < 99; x++) {
			for (y = 1; y < 99; y++) {
				grid2[x][y] = grid[x][y] && (grid[x+1][y-1] + grid[x+1][y] + grid[x+1][y+1] + grid[x][y-1] + grid[x][y+1] + grid[x-1][y-1] + grid[x-1][y] + grid[x-1][y+1]) > 4
			}
		}
		grid = grid2;
	}

	return grid;
}

function grid2boxes(grid) {
	var output = [], currentbox;
	for (var y = 0; y < 100; y++) {
		for (var x = 0; x < 100; x++) {
			if (currentbox) {
				if (grid[x][y]) {
					currentbox.width++;
				} else {
					output.push(currentbox);
					currentbox = false;
				}
			} else {
				if (grid[x][y]) {
					currentbox = {
						x: x,
						y: y,
						width: 1,
						height: 1
					}
				}
			}
		}
	}
	return output;
}

function showgrid(grid) {
	var output = '';
	for (var y = 0; y < 100; y++) {
		for (var x = 0; x < 100; x++) {
			output += grid[x][y] ? 'X' : ' ';
		}
		output += '\n';
	}
	return output;
}

// Usage: grid2boxes(coords2grid(coords[, radius][, shrink]))
// will return an array of box definitions (x, y, height, width)
Maybe you'll need to play a bit around with radius / shrink to get better results. Maybe I'll have to add another part to the algorithm to determine what radius / shrink values will yield optimal results.

Last edited by atl77 : 12-09-14 at 08:51 AM.