AreTilesQueued vs CircularTileQueue vs RectangleQueue

AreTilesQueued.nut

function MainClass::AreTilesQueued(min_noise_level_increase = null)
{
	if (!AreTileVariablesInitialized()) {
		if (min_noise_level_increase == null) min_noise_level_increase = GSController.GetSetting("min_noise_level_increase");
		local distance_outer = min_noise_level_increase == 1 ? _max_dist : min(_max_dist, GetMaxNoiseToleranceLevelDistance(min_noise_level_increase));
		local distance_inner = min(_max_dist, GetMinNoiseToleranceLevelDistance(min_noise_level_increase));

		local town_location_x = GetTileX(_town_location);
		local town_location_y = GetTileY(_town_location);

		local tile_Nx_outer = max(_min_x, town_location_x - distance_outer - (_noisiest_airport_width - 1));
		local tile_Ny_outer = max(_min_y, town_location_y - distance_outer - (_noisiest_airport_height - 1));
		local tile_Wx_outer = min(_max_x, town_location_x + distance_outer);
		local tile_Wy_outer = max(_min_y, town_location_y - distance_outer - (_noisiest_airport_height - 1));
		local tile_Sx_outer = min(_max_x, town_location_x + distance_outer);
		local tile_Sy_outer = min(_max_y, town_location_y + distance_outer);
		local tile_Ex_outer = max(_min_x, town_location_x - distance_outer - (_noisiest_airport_width - 1));
		local tile_Ey_outer = min(_max_y, town_location_y + distance_outer);

		local tile_Nx_inner = max(_min_x, town_location_x - distance_inner / 2 - (_noisiest_airport_width - 1) + 1);
		local tile_Ny_inner = max(_min_y, town_location_y - distance_inner / 2 - (_noisiest_airport_height - 1) + 1);
		local tile_Sx_inner = min(_max_x, town_location_x + distance_inner / 2 - 1);
		local tile_Sy_inner = min(_max_y, town_location_y + distance_inner / 2 - 1);

		local virtual_Nx_outer = town_location_x - distance_outer - (_noisiest_airport_width - 1);
		local virtual_Ny_outer = town_location_y - distance_outer - (_noisiest_airport_height - 1);
		local virtual_Wx_outer = town_location_x + distance_outer;
		local virtual_Wy_outer = town_location_y - distance_outer - (_noisiest_airport_height - 1);
		local virtual_Sx_outer = town_location_x + distance_outer;
		local virtual_Sy_outer = town_location_y + distance_outer;
		local virtual_Ex_outer = town_location_x - distance_outer - (_noisiest_airport_width - 1);
		local virtual_Ey_outer = town_location_y + distance_outer;

		local diff_Nx = tile_Nx_outer - virtual_Nx_outer;
		local diff_Ny = tile_Ny_outer - virtual_Ny_outer;
		local diff_Wx = virtual_Wx_outer - tile_Wx_outer;
		local diff_Wy = tile_Wy_outer - virtual_Wy_outer;
		local diff_Sx = virtual_Sx_outer - tile_Sx_outer;
		local diff_Sy = virtual_Sy_outer - tile_Sy_outer;
		local diff_Ex = tile_Ex_outer - virtual_Ex_outer;
		local diff_Ey = virtual_Ey_outer - tile_Ey_outer;

		local min_diff = min(diff_Nx, min(diff_Ny, min(diff_Wx, min(diff_Wy, min(diff_Sx, min(diff_Sy, min(diff_Ex, diff_Ey)))))));

		virtual_Nx_outer += min_diff;
		virtual_Ny_outer += min_diff;
		virtual_Wx_outer -= min_diff;
		virtual_Wy_outer += min_diff;
		virtual_Sx_outer -= min_diff;
		virtual_Sy_outer -= min_diff;
		virtual_Ex_outer += min_diff;
		virtual_Ey_outer -= min_diff;

		local area_outer = (tile_Sx_outer - tile_Nx_outer + 1) * (tile_Sy_outer - tile_Ny_outer + 1);
		local area_inner = (tile_Sx_inner - tile_Nx_inner + 1) * (tile_Sy_inner - tile_Ny_inner + 1);
		local tile_map = area_outer - area_inner;

		_tile = {
			/* Current tile in iteration */
			x = virtual_Nx_outer,
			y = virtual_Ny_outer
			/* North corner */
			N = {
				x = virtual_Nx_outer,
				y = virtual_Ny_outer
			},
			/* West corner */
			W = {
				x = virtual_Wx_outer,
				y = virtual_Wy_outer
			},
			/* South Corner */
			S = {
				x = virtual_Sx_outer,
				y = virtual_Sy_outer
			},
			/* East Corner */
			E = {
				x = virtual_Ex_outer,
				y = virtual_Ey_outer
			},
			min_x = tile_Nx_outer,
			max_x = tile_Sx_outer,
			min_y = tile_Ny_outer,
			max_y = tile_Sy_outer,
			map = tile_map
		};
	}

	if ((_tile.N.x < _tile.W.x || _tile.W.y < _tile.S.y || _tile.S.x > _tile.E.x || _tile.E.y > _tile.N.y)) {
//		GSLog.Info("_tile.N = " + _tile.N.x + "," + _tile.N.y + " ; _tile.W = " + _tile.W.x + "," + _tile.W.y + " ; _tile.S = " + _tile.S.x + "," + _tile.S.y + " ; _tile.E = " + _tile.E.x + "," + _tile.E.y);
//		local old_n = _tile_num;

		/* Walk N -> W */
		if (_tile.y >= _tile.min_y) {
			_tile.x += max(_tile.N.x, _tile.min_x) - _tile.x;
			local jump_out_NWx = min(_tile.W.x, _tile.max_x);
			while (_tile.x <= jump_out_NWx) {
				EvaluateTile(GSMap.GetTileIndex(_tile.x, _tile.y));
//				GSLog.Info("_tile_num = " + _tile_num + "; _tile = " + GSMap.GetTileIndex(_tile.x, _tile.y) + "; tileX = " + _tile.x + "; tileX_W = " + _tile.W.x);
//				PlaceSign(GSMap.GetTileIndex(_tile.x, _tile.y), "" + _tile_num);
				if ((_tile.x + 1) > jump_out_NWx) break;
				_tile.x++;
			}
		}
		if (_tile.x < _tile.W.x) {
			_tile.x += _tile.W.x - _tile.x;
		}
		_tile.N.x++;
		_tile.N.y++;
//		if (_tile.N.x >= _tile.min_x && _tile.N.x <= _tile.max_x && _tile.N.y >= _tile.min_y && _tile.N.y <= _tile.max_y) PlaceSign(GSMap.GetTileIndex(_tile.N.x, _tile.N.y), "_tile.N");
//		GSController.Break("_tile.N.x = " + _tile.N.x + "; _tile.N.y = " + _tile.N.y);

		/* Walk W -> S */
		if (_tile.x <= _tile.max_x) {
			_tile.y += max(_tile.W.y + 1, _tile.min_y) - _tile.y;
			local jump_out_WSy = min(_tile.S.y, _tile.max_y);
			while (_tile.y <= jump_out_WSy) {
				EvaluateTile(GSMap.GetTileIndex(_tile.x, _tile.y));
//				GSLog.Info("_tile_num = " + _tile_num + "; _tile = " + GSMap.GetTileIndex(_tile.x, _tile.y) + "; tileY = " + _tile.y + "; tileY_S = " + _tile.S.y);
//				PlaceSign(GSMap.GetTileIndex(_tile.x, _tile.y), "" + _tile_num);
				if ((_tile.y + 1) > jump_out_WSy) break;
				_tile.y++;
			}
		}
		if (_tile.y < _tile.S.y) {
			_tile.y += _tile.S.y - _tile.y;
		}
		_tile.W.x--;
		_tile.W.y++;
//		if (_tile.W.x >= _tile.min_x && _tile.W.x <= _tile.max_x && _tile.W.y >= _tile.min_y && _tile.W.y <= _tile.max_y) PlaceSign(GSMap.GetTileIndex(_tile.W.x, _tile.W.y), "_tile.W");
//		GSController.Break("_tile.W.x = " + _tile.W.x + "; _tile.W.y = " + _tile.W.y);

		/* Walk S -> E */
		if (_tile.y <= _tile.max_y) {
			_tile.x += min(_tile.S.x - 1, _tile.max_x) - _tile.x;
			local jump_out_SEx = max(_tile.E.x, _tile.min_x);
			while (_tile.x >= jump_out_SEx) {
				EvaluateTile(GSMap.GetTileIndex(_tile.x, _tile.y));
//				GSLog.Info("_tile_num = " + _tile_num + "; _tile = " + GSMap.GetTileIndex(_tile.x, _tile.y) + "; tileX = " + _tile.x + "; tileX_E = " + _tile.E.x);
//				PlaceSign(GSMap.GetTileIndex(_tile.x, _tile.y), "" + _tile_num);
				if ((_tile.x - 1) < jump_out_SEx) break;
				_tile.x--;
			}
		}
		if (_tile.x > _tile.E.x) {
			_tile.x += _tile.E.x - _tile.x;
		}
		_tile.S.x--;
		_tile.S.y--;
//		if (_tile.S.x >= _tile.min_x && _tile.S.x <= _tile.max_x && _tile.S.y >= _tile.min_y && _tile.S.y <= _tile.max_y) PlaceSign(GSMap.GetTileIndex(_tile.S.x, _tile.S.y), "_tile.S");
//		GSController.Break("_tile.S.x = " + _tile.S.x + "; _tile.S.y = " + _tile.S.y);

		/* Walk E -> N */
		if (_tile.x >= _tile.min_x) {
			_tile.y += min(_tile.E.y - 1, _tile.max_y) - _tile.y;
			local jump_out_ENy = max(_tile.N.y, _tile.min_y);
			while (_tile.y >= jump_out_ENy) {
				EvaluateTile(GSMap.GetTileIndex(_tile.x, _tile.y));
//				GSLog.Info("_tile_num = " + _tile_num + "; _tile = " + GSMap.GetTileIndex(_tile.x, _tile.y) + "; tileY = " + _tile.y + "; tileY_N = " + _tile.N.y);
//				PlaceSign(GSMap.GetTileIndex(_tile.x, _tile.y), "" + _tile_num);
				if ((_tile.y - 1) < jump_out_ENy) break;
				_tile.y--;
			}
		}
		if (_tile.y > _tile.N.y) {
			_tile.y += _tile.N.y - _tile.y;
		}
		_tile.E.x++;
		_tile.E.y--;
//		if (_tile.E.x >= _tile.min_x && _tile.E.x <= _tile.max_x && _tile.E.y >= _tile.min_y && _tile.E.y <= _tile.max_y) PlaceSign(GSMap.GetTileIndex(_tile.E.x, _tile.E.y), "_tile.E");
//		GSController.Break("_tile.E.x = " + _tile.E.x + "; _tile.E.y = " + _tile.E.y);

//		local added = _tile_num - old_n;
//		GSLog.Info("_tile.map: " + _tile.map + "; _tile_num: " + _tile_num + "; added: " + added + "; " + (_tile_num * 100 / _tile.map) + "% queued");
	} else {
		assert(_tile_num == _tile_queue.Count());
	}
	return _tile_num == _tile.map;
}

CircularTileQueue.nut

function MainClass::CircularTileQueue(min_noise_level_increase = null)
{
	if (!AreTileVariablesInitialized()) {
		if (min_noise_level_increase == null) min_noise_level_increase = GSController.GetSetting("min_noise_level_increase");
		local distance_outer = min_noise_level_increase == 1 ? _max_dist : min(_max_dist, GetMaxNoiseToleranceLevelDistance(min_noise_level_increase));
		local distance_inner = min(_max_dist, GetMinNoiseToleranceLevelDistance(min_noise_level_increase));

		local town_location_x = GetTileX(_town_location);
		local town_location_y = GetTileY(_town_location);

		_tile = GSMap.GetTileIndex(town_location_x - (_noisiest_airport_width - 1), town_location_y - (_noisiest_airport_height - 1));

//		GSLog.Info("_tile: " + _tile);
//		PlaceSign(_tile, "_tile");

//		GSLog.Info("distance_outer: " + distance_outer);
		local search = CircularTileSearch(_tile, distance_outer, distance_inner, _noisiest_airport_width, _noisiest_airport_height, EvaluateTile);
	}

	return true;
}

function MainClass::CircularTileSearch(tile, distance_outer, distance_inner, width, height, proc)
{
	assert(proc != null);
	assert(distance_outer > 0);
	assert(distance_inner % 2 == 0);

	local w = max(0, width - 2);
	local h = max(0, height - 2);

	local tile_x = GetTileX(tile);
	local tile_y = GetTileY(tile);
	local x = tile_x + w + 1 + distance_inner / 2;
	local y = tile_y - distance_inner / 2;

	/**
	 * Cut down excessive loops.
	 *  Determine the minimum distance difference required to be at each edge of the map.
	 *  A difference > 0 indicates the origin tile is outside the map.
	 *  Reduce the radius by the lowest distance of all four sides only if they're outside.
	 */
	local radius = distance_outer - distance_inner / 2;
	local diff_to_NE = _min_x - (tile_x - distance_inner / 2 - radius);
	local diff_to_SW = (tile_x + width - 1 + distance_inner / 2 + radius) - _max_x;
	local diff_to_NW = _min_y - (tile_y - distance_inner / 2 - radius);
	local diff_to_SE = (tile_y + height - 1 + distance_inner / 2 + radius) - _max_y;
	local minimum_diff = min(diff_to_NE, min(diff_to_SW, min(diff_to_NW, diff_to_SE)));
	radius = radius - max(0, minimum_diff);

	/**
	 * Cut down excessive sides.
	 *  Verify whether the fixed coordinate for the entire side iteration lies within the map.
	 */
	local is_inside = [
		function(x, y, min_y = _min_y) { return y >= min_y; }, // DIAGDIR_NE from W->N edge
		function(x, y, min_x = _min_x) { return x >= min_x; }, // DIAGDIR_SE from N->E edge
		function(x, y, max_y = _max_y) { return y <= max_y; }, // DIAGDIR_SW from E->S edge
		function(x, y, max_x = _max_x) { return x <= max_x; }  // DIAGDIR_NW from S->W edge
	];

	/**
	 * Cut down excessive tiles.
	 *  There are three possible outcomes for the returned value, each with a different meaning:
	 *  1. value > 0: The coordinate is outside the map and this side is just starting tile iteration.
	 *                The distance required to be inside the map is returned.
	 *  2. value == 0: The coordinate is of a valid tile iteration inside the map.
	 *                 The returned value serves to indicate that these tiles are to be processed.
	 *  3. value == -1: The coordinate is outside the map and this side has finished iterating all valid tiles.
	 *                  The returned value indicates that the remaining extent is to be skipped.
	 */
	local is_tile_outside = [
		function(x, y, max_x = _max_x, min_x = _min_x) { return x > max_x ? x - max_x : x < min_x ? -1 : 0; },  // DIAGDIR_NE from W->N edge
		function(x, y, min_y = _min_y, max_y = _max_y) { return y < min_y ? min_y - y : y > max_y ? -1 : 0; },  // DIAGDIR_SE from N->E edge
		function(x, y, min_x = _min_x, max_x = _max_x) { return x < min_x ? min_x - x : x > max_x ? -1 : 0; },  // DIAGDIR_SW from E->S edge
		function(x, y, max_y = _max_y, min_y = _min_y) { return y > max_y ? y - max_y : y < min_y ? -1 : 0; }   // DIAGDIR_NW from S->W edge
	];
	local extent = [
		w + distance_inner + 1, // DIAGDIR_NE from W->N edge
		h + distance_inner + 1, // DIAGDIR_SE from N->E edge
		w + distance_inner + 1, // DIAGDIR_SW from E->S edge
		h + distance_inner + 1  // DIAGDIR_NW from S->W edge
	];

	/** 'Lookup table' for tile offsets given a DiagDirection. */
	local tileoffs_by_diagdir = [
		{ x = -1, y =  0 }, // DIAGDIR_NE
		{ x =  0, y =  1 }, // DIAGDIR_SE
		{ x =  1, y =  0 }, // DIAGDIR_SW
		{ x =  0, y = -1 }  // DIAGDIR_NW
	];

	for (local n = 0; n <= radius; n++) {
		for (local dir = 0; dir <= 3; dir++) {
			local j = extent[dir] + n * 2;
			if (!is_inside[dir](x, y)) {
				/* All tiles for this side are outside the map edge. Skip to next side or loop. */
				x += tileoffs_by_diagdir[dir].x * j;
				y += tileoffs_by_diagdir[dir].y * j;
				continue;
			}
			do {
				if (is_tile_outside[dir](x, y) > 0) {
					/* Skip the initial tiles located outside the map and get to the first one inside. */
					j -= is_tile_outside[dir](x, y);
					x += tileoffs_by_diagdir[dir].x * is_tile_outside[dir](x, y);
					y += tileoffs_by_diagdir[dir].y * is_tile_outside[dir](x, y);
				} else if (is_tile_outside[dir](x, y) == -1) {
					/* Skip the remaining tiles located outside the map and get to the next side or loop. */
					x += tileoffs_by_diagdir[dir].x * j;
					y += tileoffs_by_diagdir[dir].y * j;
					break;
				}
				local t = GSMap.GetTileIndex(x, y);
				/* Is the callback successful? */
				if (proc(t)) {
					/* Stop the search. */
					return true;
				}
				/* Step to the next 'neighbour' in the circular line. */
				x += tileoffs_by_diagdir[dir].x;
				y += tileoffs_by_diagdir[dir].y;
			} while (--j != 0);
		}
		/* Jump to next circle to test. */
		x += 1;
		y -= 1;
	}

	return false;
}

RectangleQueue.nut

function MainClass::RectangleQueue(min_noise_level_increase = null)
{
	if (!AreTileVariablesInitialized()) {
		if (min_noise_level_increase == null) min_noise_level_increase = GSController.GetSetting("min_noise_level_increase");
		local distance_outer = min_noise_level_increase == 1 ? _max_dist : min(_max_dist, GetMaxNoiseToleranceLevelDistance(min_noise_level_increase));
		local distance_inner = min(_max_dist, GetMinNoiseToleranceLevelDistance(min_noise_level_increase));

		local town_location_x = GetTileX(_town_location);
		local town_location_y = GetTileY(_town_location);

		local tile_Nx_outer = max(_min_x, town_location_x - distance_outer - (_noisiest_airport_width - 1));
		local tile_Ny_outer = max(_min_y, town_location_y - distance_outer - (_noisiest_airport_height - 1));
		local tile_Sx_outer = min(_max_x, town_location_x + distance_outer);
		local tile_Sy_outer = min(_max_y, town_location_y + distance_outer);

		local tile_N_outer = GSMap.GetTileIndex(tile_Nx_outer, tile_Ny_outer);
		local tile_S_outer = GSMap.GetTileIndex(tile_Sx_outer, tile_Sy_outer);

		local tile_Nx_inner = max(_min_x, town_location_x - distance_inner / 2 - (_noisiest_airport_width - 1) + 1);
		local tile_Ny_inner = max(_min_y, town_location_y - distance_inner / 2 - (_noisiest_airport_height - 1) + 1);
		local tile_Sx_inner = min(_max_x, town_location_x + distance_inner / 2 - 1);
		local tile_Sy_inner = min(_max_y, town_location_y + distance_inner / 2 - 1);

		local tile_N_inner = GSMap.GetTileIndex(tile_Nx_inner, tile_Ny_inner);
		local tile_S_inner = GSMap.GetTileIndex(tile_Sx_inner, tile_Sy_inner);

		_tile = tile_N_outer;

		local tile_list = GSTileList();
		tile_list.AddRectangle(tile_N_outer, tile_S_outer);
		tile_list.RemoveRectangle(tile_N_inner, tile_S_inner);
		foreach (tile, _ in tile_list) {
			EvaluateTile(tile);
		}
	}
}