/**
 * Make a connected lake; fill all tiles in the circular tile search that are connected.
 * @param tile The tile to consider for lake making.
 * @param user_data The height of the lake.
 * @return Always false, so it continues searching.
 */
static bool MakeLake(TileIndex tile, void *user_data)
{
	uint height = *(uint*)user_data;
	if (!IsValidTile(tile) || TileHeight(tile) != height || !IsTileFlat(tile)) return false;
	if (_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) == TROPICZONE_DESERT) return false;

	for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
		TileIndex t2 = tile + TileOffsByDiagDir(d);
		if (IsWaterTile(t2)) {
			MakeRiver(tile, Random());
			return false;
		}
	}

	return false;
}

/**
 * Check whether a river could (logically) flow into a lock.
 * @param tile the middle tile of a lock.
 * @recursive whether the function is being called recursively.
 * @return true iff the water can be flowing into a lock.
 */
bool FlowsLock(TileIndex tile, bool recursive = false)
{
	DiagDirection dir = GetInclinedSlopeDirection(GetTileSlope(tile));
	if (dir == INVALID_DIAGDIR) return false;

	int delta_mid = TileOffsByDiagDir(dir);
	if (!IsTileFlat(tile + delta_mid)) return false;
	if (!IsTileFlat(tile - delta_mid)) return false;

	if (!recursive) return true;

	DiagDirection dir_rot = ChangeDiagDir(dir, DIAGDIRDIFF_90RIGHT);
	int delta = TileOffsByDiagDir(dir_rot);

	for (int m = -1; m <= 1; m += 2) {
		TileIndex t_dm = tile + m * delta_mid;
		if (IsValidTile(t_dm)) {
			if (DistanceFromEdgeDir(t_dm, dir) == 0 || DistanceFromEdgeDir(t_dm, ReverseDiagDir(dir)) == 0) {
				return false;
			}

			for (int d = -1; d <= 1; d += 2) {
				if (IsValidTile(t_dm + d * delta)) {
					if (!IsTileFlat(t_dm + d * delta) &&
							(GetInclinedSlopeDirection(GetTileSlope(t_dm + d * delta)) == dir_rot ||
							GetInclinedSlopeDirection(GetTileSlope(t_dm + d * delta)) == ReverseDiagDir(dir_rot)) &&
							FlowsLock(t_dm + d * delta)) {
						return false;
					}

					if (IsValidTile(t_dm + d * 2 * delta)) {
						if (!IsTileFlat(t_dm + d * 2 * delta) &&
								(GetInclinedSlopeDirection(GetTileSlope(t_dm + d * 2 * delta)) == dir_rot ||
								GetInclinedSlopeDirection(GetTileSlope(t_dm + d * 2 * delta)) == ReverseDiagDir(dir_rot)) &&
								FlowsLock(t_dm + d * 2 * delta)) {
							return false;
						}
					}
				}
			}

			TileIndex t_2dm = t_dm + m * delta_mid;
			if (IsValidTile(t_2dm)) {
				if (!IsTileFlat(t_2dm)) {
					return false;
				}

				for (int d = -1; d <= 1; d += 2) {
					if (IsValidTile(t_2dm + d * delta)) {
						if (IsTileFlat(t_dm + d * delta) && !IsTileFlat(t_2dm + d * delta)) {
							return false;
						}

						if (!IsTileFlat(t_2dm + d * delta) &&
								(GetInclinedSlopeDirection(GetTileSlope(t_2dm + d * delta)) == dir_rot ||
								GetInclinedSlopeDirection(GetTileSlope(t_2dm + d * delta)) == ReverseDiagDir(dir_rot)) &&
								FlowsLock(t_2dm + d * delta)) {
							return false;
						}
					}
				}

				TileIndex t_3dm = t_2dm + m * delta_mid;
				if (IsValidTile(t_3dm)) {
					if ((GetInclinedSlopeDirection(GetTileSlope(t_3dm)) == dir ||
							GetInclinedSlopeDirection(GetTileSlope(t_3dm)) == ReverseDiagDir(dir)) &&
							FlowsLock(t_3dm)) {
						return false;
					}
				}

				for (int d = -1; d <= 1; d += 2) {
					if (IsValidTile(t_3dm + d * delta)) {
						if ((GetInclinedSlopeDirection(GetTileSlope(t_3dm + d * delta)) == dir ||
								GetInclinedSlopeDirection(GetTileSlope(t_3dm + d * delta)) == ReverseDiagDir(dir)) &&
								FlowsLock(t_3dm + d * delta)) {
							return false;
						}
					}
				}
			}
		}
	}

	return true;
}

/**
 * Check whether a river at begin could (logically) flow down to end.
 * @param begin The origin of the flow.
 * @param end The destination of the flow.
 * @return True iff the water can be flowing down.
 */
static bool FlowsDown(TileIndex begin, TileIndex end)
{
	assert(DistanceManhattan(begin, end) == 1);

	int heightBegin;
	int heightEnd;
	Slope slopeBegin = GetTileSlope(begin, &heightBegin);
	Slope slopeEnd   = GetTileSlope(end, &heightEnd);

	return heightEnd <= heightBegin &&
			/* Slope either is inclined or flat; rivers don't support other slopes. */
			(slopeEnd == SLOPE_FLAT || (IsInclinedSlope(slopeEnd) && FlowsLock(end, true))) &&
			/* Slope continues, then it must be lower... or either end must be flat. */
			((slopeEnd == slopeBegin && heightEnd < heightBegin) || slopeEnd == SLOPE_FLAT || (slopeBegin == SLOPE_FLAT && GetTileMaxZ(end) == heightBegin));
}