require "common"

local DebugEnabled = false

local function EchoDebug(inStr)
	if DebugEnabled then
		game:SendToConsole("MapHandler: " .. inStr)
	end
end

local debugSquares = {}
local debugPlotFile

-- mobTypes = {}
local mobUnitType = {}
local UWMetalSpotCheckUnitType

local mobMap = {}
local savepositions = {}

local minDefenseNetworkSize = 100000

local function MapDataFilename()
	local mapName = string.gsub(map:MapName(), "%W", "_")
	return "cache/Shard-" .. game:GameName() .. "-" .. mapName .. ".lua"
end

local function serialize (o, keylist)
  if keylist == nil then keylist = "" end
  if type(o) == "number" then
    mapdatafile:write(o)
  elseif type(o) == "boolean" then
  	mapdatafile:write(tostring(o))
  elseif type(o) == "string" then
    mapdatafile:write(string.format("%q", o))
  elseif type(o) == "userdata" then
  	-- assume it's a position
  	mapdatafile:write("api.Position()")
  	table.insert(savepositions, {keylist = keylist, position = o})
  	--mapdatafile:write("{ x = " .. math.ceil(o.x) .. ", y = " .. math.ceil(o.y) .. ", z = " .. math.ceil(o.z) .. " }")
  elseif type(o) == "table" then
    mapdatafile:write("{\n")
    for k,v in pairs(o) do
      mapdatafile:write("  [")
      serialize(k)
      mapdatafile:write("] = ")
      local newkeylist
      if type(v) == "table" or type(v) == "userdata" then
      	if type(k) == "string" then
        	newkeylist = keylist .. "[\""  .. k .. "\"]"
        elseif type(k) == "number" then
        	newkeylist = keylist .. "["  .. k .. "]"
        end
      end
      serialize(v, newkeylist)
      mapdatafile:write(",\n")
    end
    mapdatafile:write("}\n")
  else
    error("cannot serialize a " .. type(o))
  end
end

local function EchoData(name, o)
	savepositions = {}
	mapdatafile:write(name)
	mapdatafile:write(" = ")
	serialize(o)
	mapdatafile:write("\n\n")
	if #savepositions > 0 then
		for i, sp in pairs (savepositions) do
			mapdatafile:write(name .. sp.keylist .. ".x = " .. sp.position.x .. "\n")
			mapdatafile:write(name .. sp.keylist .. ".y = " .. sp.position.y .. "\n")
			mapdatafile:write(name .. sp.keylist .. ".z = " .. sp.position.z .. "\n")
		end
		mapdatafile:write("\n\n")
	end
	EchoDebug("wrote " .. name)
end

local function PlotDebug(x, z, label)
	if DebugEnabled then
		if label == nil then label= "nil" end
		local string = math.ceil(x) .. " " .. math.ceil(z) .. " " .. label .. "\n"
		debugPlotFile:write(string)
	end
end

local function PlotSquareDebug(x, z, size, label)
	if DebugEnabled then
		x = math.ceil(x)
		z = math.ceil(z)
		size = math.ceil(size)
		-- if debugSquares[x .. "  " .. z .. " " .. size] == nil then
			if label == nil then label = "nil" end
			local string = x .. " " .. z .. " " .. size .. " " .. label .. "\n"
			debugPlotFile:write(string)
			-- debugSquares[x .. "  " .. z .. " " .. size] = true
		-- end
	end
end

local function PlotLineDebug(pos1, pos2)
	if DebugEnabled then
		local string = math.ceil(pos1.x) .. " " .. math.ceil(pos1.z) .. " " .. math.ceil(pos2.x) .. " " .. math.ceil(pos2.z) .. "\n"
		debugPlotFile:write(string)
	end
end

MapHandler = class(Module)

local function MiddleOfTwo(pos1, pos2)
	local deltax = pos2.x - pos1.x
	local deltaz = pos2.z - pos1.z
	local middle = api.Position()
	middle.y = 0
	middle.x = pos1.x + (deltax / 2)
	middle.z = pos1.z + (deltaz / 2)
	return middle
end

local function Check1Topology(x, z, mtype, network)
	if mobMap[mtype][x] == nil then
		return 1
	elseif mobMap[mtype][x][z] == nil then
		return 1
	else
		return mobMap[mtype][x][z]
	end
end

local function Flood4Topology(x, z, mtype, network)
	if x > ai.mobilityGridMaxX or x < 1 or z > ai.mobilityGridMaxZ or z < 1 then return end
	--precheck throws out 1-wide bottlenecks
	local blocked = 0
	blocked = blocked + Check1Topology(x+1, z, mtype, network)
	blocked = blocked + Check1Topology(x-1, z, mtype, network)
	if blocked == 2 then return end
	blocked = blocked + Check1Topology(x, z+1, mtype, network)
	if blocked == 2 then return end
	blocked = blocked + Check1Topology(x, z-1, mtype, network)
	if blocked == 2 then return end
	-- now actually flood fill
	local actualValue = mobMap[mtype][x][z]
	if actualValue and (actualValue == 0) and ai.topology[mtype][x][z] == nil then
		ai.topology[mtype][x][z] = network
		ai.networkSize[mtype][network] = ai.networkSize[mtype][network] + 1
		PlotSquareDebug(x * ai.mobilityGridSize - ai.mobilityGridSizeHalf, z * ai.mobilityGridSize - ai.mobilityGridSizeHalf, ai.mobilityGridSize, mtype)
		Flood4Topology(x+1,z,mtype,network)
		Flood4Topology(x-1,z,mtype,network)
		Flood4Topology(x,z+1,mtype,network)
		Flood4Topology(x,z-1,mtype,network)
	end
end

local function Flood8Topology(x, z, mtype, network)
	if x > ai.mobilityGridMaxX or x < 1 or z > ai.mobilityGridMaxZ or z < 1 then return end
	local actualValue = mobMap[mtype][x][z]
	if actualValue and (actualValue == 0) and ai.topology[mtype][x][z] == nil then
		ai.topology[mtype][x][z] = network
		ai.networkSize[mtype][network] = ai.networkSize[mtype][network] + 1
		PlotSquareDebug(x * ai.mobilityGridSize - ai.mobilityGridSizeHalf, z * ai.mobilityGridSize - ai.mobilityGridSizeHalf, ai.mobilityGridSize, mtype)
		Flood8Topology(x+1,z,mtype,network)
		Flood8Topology(x-1,z,mtype,network)
		Flood8Topology(x,z+1,mtype,network)
		Flood8Topology(x,z-1,mtype,network)
		Flood8Topology(x+1,z+1,mtype,network)
		Flood8Topology(x-1,z+1,mtype,network)
		Flood8Topology(x+1,z-1,mtype,network)
		Flood8Topology(x-1,z-1,mtype,network)
	end
end

local function MapMobility()
	-- check for water map works like this:
	-- the map is divided into sectors, then center of each sector is tested if specific unit can be built there (water, kbot, vehicle)
	local mapSize = map:MapDimensions()
	ai.mobilityGridSize = math.floor(math.max(mapSize.x * 8, mapSize.z * 8) / 128)
	ai.mobilityGridSize = math.max(ai.mobilityGridSize, 32) -- don't make grids smaller than 32
	ai.mobilityGridSizeHalf = ai.mobilityGridSize/ 2
	EchoDebug("grid size: " .. ai.mobilityGridSize)
	local maxX = math.ceil((mapSize.x * 8) / ai.mobilityGridSize)
	local maxZ = math.ceil((mapSize.z * 8) / ai.mobilityGridSize)
	EchoDebug("Map size in grids: x "..maxX.." z "..maxZ)
	ai.mobilityGridMaxX = maxX
	ai.mobilityGridMaxZ = maxZ
	local mobCount = {}
	local totalCount = maxX * maxZ
	ai.mobilityGridArea = totalCount
	local half = ai.mobilityGridSizeHalf
	local pos = api.Position()
	pos.y = 0
	for mtype, utype in pairs(mobUnitType) do
		mobMap[mtype] = {}
		mobCount[mtype] = 0
	end
	for x = 1, maxX do
		for mtype, utype in pairs(mobUnitType) do
			mobMap[mtype][x] = {}
		end
		for z = 1, maxZ do
			-- all blocked unless unblocked below
			for mtype, utype in pairs(mobUnitType) do
				mobMap[mtype][x][z] = 1
			end
			pos.x = (x * ai.mobilityGridSize) - half
			pos.z = (z * ai.mobilityGridSize) - half
			-- find out if each mobility type can exist there
			for mtype, utype in pairs(mobUnitType) do
				local canbuild = false
				if mtype == "hov" then
					-- hovers don't build on water for some reason, so use some logic with other unit types to figure it out
					canbuild = game.map:CanBuildHere(mobUnitType["hov"], pos) or game.map:CanBuildHere(game:GetTypeByName(WaterSurfaceUnitName), pos)
				else
					canbuild = game.map:CanBuildHere(mobUnitType[mtype], pos)
				end
				if canbuild then
					-- EchoDebug(mtype .. " at " .. x .. "," .. z .. " count " .. mobCount[mtype])
					mobCount[mtype] = mobCount[mtype] + 1
					mobMap[mtype][x][z] = 0
				end
			end
			-- EchoDebug(x .. "," .. z .. " sub " .. subMap[x][z] .. " bot " .. botMap[x][z] .. " veh " .. vehMap[x][z])
		end
	end
	return totalCount, maxX, maxZ, mobCount
end

local function InitializeTopology()
	ai.topology = {}
	for mtype, utype in pairs(mobUnitType) do
		ai.topology[mtype] = {}
	end
	ai.topology["air"] = {}
	for x = 1, ai.mobilityGridMaxX do
		for mtype, utype in pairs(mobUnitType) do
			ai.topology[mtype][x] = {}
		end
		ai.topology["air"][x] = {}
		for z = 1, ai.mobilityGridMaxZ do
			-- fill air topology with single network
			ai.topology["air"][x][z] = 1
		end
	end
end

local function MapSpotMobility(metals, geos)
	local half = ai.mobilityGridSizeHalf
	ai.networkSize = {}
	ai.scoutSpots = {}
	ai.scoutSpots["air"] = {}
	ai.scoutSpots["air"][1] = {}
	local mobNetworkMetals = {}
	mobNetworkMetals["air"] = {}
	mobNetworkMetals["air"][1] = {}
	local mobSpots = {}
	local mobNetworks = {}
	local mobNetworkCount = {}
	for mtype, utype in pairs(mobUnitType) do
		mobSpots[mtype] = {}
		mobNetworkMetals[mtype] = {}
		mobNetworkCount[mtype] = {}
		mobNetworks[mtype] = 0
		ai.networkSize[mtype] = {}
		ai.scoutSpots[mtype] = {}
	end
	for metalOrGeo = 1, 2 do
		local spots
		if metalOrGeo == 1 then
			spots = metals
		else
			spots = geos
		end
		for i, spot in pairs(spots) do
			local landOrWater
			if metalOrGeo == 1 then
				if game.map:CanBuildHere(UWMetalSpotCheckUnitType, spot) then
					table.insert(ai.UWMetalSpots, spot)
					landOrWater = 2
				else
					table.insert(ai.landMetalSpots, spot)
					landOrWater = 1
				end
			end
			local x = math.ceil(spot.x / ai.mobilityGridSize)
			local z = math.ceil(spot.z / ai.mobilityGridSize)
			for mtype, utype in pairs(mobUnitType) do
				if mobMap[mtype][x][z] == 0 then
					local thisNetwork
					if ai.topology[mtype][x][z] == nil then
						-- if topology is empty here, initiate a new network, and flood fill it
						mobNetworks[mtype] = mobNetworks[mtype] + 1
						thisNetwork = mobNetworks[mtype]
						mobNetworkCount[mtype][thisNetwork] = 1
						ai.networkSize[mtype][thisNetwork] = 0
						mobNetworkMetals[mtype][thisNetwork] = {}
						PlotDebug(x * ai.mobilityGridSize - ai.mobilityGridSizeHalf, z * ai.mobilityGridSize - ai.mobilityGridSizeHalf, mtype)
						Flood4Topology(x, z, mtype, mobNetworks[mtype])
					else
						-- if topology isn't empty here, add this spot to its count
						thisNetwork = ai.topology[mtype][x][z]
						mobNetworkCount[mtype][thisNetwork] = mobNetworkCount[mtype][thisNetwork] + 1
					end
					table.insert(mobSpots[mtype], {x = x, z = z})
					if metalOrGeo == 1 then
						if landOrWater == 1 and mtype ~= "sub" and mtype ~= "shp" then
							table.insert(mobNetworkMetals[mtype][thisNetwork], spot)
						elseif landOrWater == 2 and mtype ~= "veh" and mtype ~= "bot" then
							table.insert(mobNetworkMetals[mtype][thisNetwork], spot)
						end
					end
					if ai.scoutSpots[mtype][thisNetwork] == nil then ai.scoutSpots[mtype][thisNetwork] = {} end
					table.insert(ai.scoutSpots[mtype][thisNetwork], spot)
				end
			end
			if metalOrGeo == 1 then table.insert(mobNetworkMetals["air"][1], spot) end
			table.insert(ai.scoutSpots["air"][1], spot)
		end
	end
	return mobSpots, mobNetworkMetals, mobNetworks, mobNetworkCount
end

local function MergePositions(posTable, cutoff, includeNonMerged)
	local list = {} -- make copy to prevent clearing table
	for k, v in pairs(posTable) do table.insert(list, v) end
	EchoDebug(#list .. " " .. cutoff)
	local merged = {}
	while #list > 0 do
		local pos1 = table.remove(list)
		local merge = nil
		for i, pos2 in pairs(list) do
			local dist = Distance(pos1, pos2)
			if dist < cutoff then
				EchoDebug("merging " .. pos1.x .. "," .. pos1.z .. " with " .. pos2.x .. "," .. pos2.z .. " -- " .. dist .. " away")
				merge = MiddleOfTwo(pos1, pos2)
				pos1 = merge
				table.remove(list, i)
			end
		end
		if merge ~= nil then
			table.insert(merged, merge)
		elseif includeNonMerged then
			table.insert(merged, pos1)
		end
	end
	EchoDebug(#merged)
	return merged
end

function MapHandler:GuessStartLocations(spots)
	if spots == nil then return end
	if #spots == 0 then
		EchoDebug("spot table for start location guessing is empty")
		return
	end

	-- find links
	local spotsCopy = {}
	for i, v in pairs(spots) do table.insert(spotsCopy, v) end
	local minDist = 1000
	local links = {}
	local from = table.remove(spotsCopy)
	while #spotsCopy > 0 do
		local closest = nil
		for i, to in pairs(spotsCopy) do
			local dist = Distance(from, to)
			if dist < minDist then
				minDist = dist
				closest = i
			end
			local middle = MiddleOfTwo(from, to)
			table.insert(links, {dist = dist, middle = middle})
		end
		if closest ~= nil then
			from = table.remove(spotsCopy, closest)
		else
			from = table.remove(spotsCopy)
		end
	end

	-- look for matches
	local matches = {}
	local tolerance = minDist * 0.5
	local cutoff = minDist + tolerance
	EchoDebug("tolerance: " .. tolerance .. "  cutoff: " .. cutoff)
	for i, l in pairs(links) do
		if l.dist < cutoff then
			EchoDebug("metal spot link at " .. math.ceil(l.middle.x) .. "," .. math.ceil(l.middle.z) .. " within cutoff with distance of " .. math.ceil(l.dist))
			table.insert(matches, l.middle)
		end
	end
	if #matches == 0 then return end

	-- merge matches close to each other
	local merged = MergePositions(matches, cutoff, false)
	if #merged < 2 then
		EchoDebug("not enough merged, using all matches")
		return matches
	else
		EchoDebug("using merged links")
		return merged
	end
end

function MapHandler:Name()
	return "MapHandler"
end

function MapHandler:internalName()
	return "maphandler"
end

function MapHandler:SaveMapData()
	local mdfilename = MapDataFilename()
	EchoDebug("saving map data to " .. mdfilename)
	mapdatafile = io.open(mdfilename,'w')
	if mapdatafile ~= nil then
		EchoData("ai.mobilityGridSize", ai.mobilityGridSize)
		EchoData("ai.mobilityGridMaxX", ai.mobilityGridMaxX)
		EchoData("ai.mobilityGridMaxZ", ai.mobilityGridMaxZ)
		EchoData("ai.waterMap", ai.waterMap)
		EchoData("ai.mapHasGeothermal", ai.mapHasGeothermal)
		EchoData("ai.mobilityRatingFloor", ai.mobilityRatingFloor)
		EchoData("ai.hasUWSpots", ai.hasUWSpots)
		EchoData("ai.mobilityGridSizeHalf", ai.mobilityGridSizeHalf)
		EchoData("ai.mobilityGridArea", ai.mobilityGridArea)
		EchoData("ai.mobRating", ai.mobRating)
		EchoData("ai.mobCount", ai.mobCount)
		EchoData("ai.mobNetworks", ai.mobNetworks)
		EchoData("ai.networkSize", ai.networkSize)
		EchoData("ai.landMetalSpots", ai.landMetalSpots)
		EchoData("ai.UWMetalSpots", ai.UWMetalSpots)
		EchoData("ai.geoSpots", ai.geoSpots)
		EchoData("ai.startLocations", ai.startLocations)
		EchoData("ai.mobNetworkMetals", ai.mobNetworkMetals)
		EchoData("ai.scoutSpots", ai.scoutSpots)
		EchoData("ai.topology", ai.topology)
		mapdatafile:close()
	else
		EchoDebug("unable to write map data file " .. mdfilename)
	end
end

function MapHandler:LoadMapData()
	-- check for existing map data and load it
	local dataloaded = false
	local mdfilename = MapDataFilename()
	local mapdatafile = io.open(mdfilename ,"r")
	if mapdatafile ~= nil then
		mapdatafile:close()
		dofile(mdfilename)
		dataloaded = true
		EchoDebug("map data loaded from " .. mdfilename)
	end
	return dataloaded
end

function MapHandler:Update()
	-- workaround for shifting metal spots: map dats is reloaded every two minutess
	local f = game:Frame()
	if f > self.lastDataResetFrame + 3600 then
		self:LoadMapData()
		self.lastDataResetFrame = f
	end
end

function MapHandler:Init()

	ai.activeMobTypes = {}
	ai.factoryListMap = {}

	local dataloaded = self:LoadMapData()

	self.lastDataResetFrame = game:Frame()

	if dataloaded then
		return
	end

	if DebugEnabled then 
		debugPlotFile = assert(io.open("debugplot",'w'), "Unable to write debugplot")
	end

	ai.mobilityGridSize = 256 -- will be recalculated by MapMobility()

	for mtype, uname in pairs(mobUnitName) do
		mobUnitType[mtype] = game:GetTypeByName(uname)
	end
	UWMetalSpotCheckUnitType = game:GetTypeByName(UWMetalSpotCheckUnit)

	local totalCount, maxX, maxZ, mobCount = MapMobility()
	ai.mobilityGridMaxX = maxX
	ai.mobilityGridMaxZ = maxZ
	ai.mobCount = mobCount
	InitializeTopology()

	-- now let's see how much water we found
	EchoDebug("total sectors "..totalCount)
	local wetness = mobCount["sub"] * 100 / totalCount
	EchoDebug("map wetness is "..wetness)
	ai.waterMap = wetness >= 10
	EchoDebug("there is water on the map")

	for mtype, count in pairs(mobCount) do
		local ness = count * 100 / totalCount
		EchoDebug("map " .. mtype .. "-ness is " .. ness .. " and total grids: " .. count)
	end

	self.spots = game.map:GetMetalSpots()
	-- copy metal spots
	local metalSpots = {}
	for k, v in pairs(self.spots) do table.insert(metalSpots, v) end

	-- now let's find out are there any geo spots on the map
	-- and add them to allSpots
	-- supposedly they have "geo" in names (don't know of a better way)
	local tmpFeatures = map:GetMapFeatures()
	ai.mapHasGeothermal = false
	local geoSpots = {}
	for _, feature in pairs(tmpFeatures) do
		if feature then
			tmpName = feature:Name()
			if tmpName == "geovent" then
				ai.mapHasGeothermal = true
				table.insert(geoSpots, feature:GetPosition())
			end
		end
	end
	ai.geoSpots = geoSpots

	ai.UWMetalSpots = {}
	ai.landMetalSpots = {}
	local mobSpots, mobNetworks, mobNetworkCount
	mobSpots, ai.mobNetworkMetals, mobNetworks, mobNetworkCount = MapSpotMobility(metalSpots, geoSpots)
	ai.mobNetworks = mobNetworks
	for mtype, mspots in pairs(mobSpots) do
		EchoDebug(mtype .. " spots: " .. #mspots)
	end
	-- EchoDebug(" spots sub:" .. #mobSpots["sub"] .. " bot:" .. #mobSpots["bot"] .. " veh:" .. #mobSpots["veh"])
	for mtype, utype in pairs(mobUnitType) do
		EchoDebug(mtype .. "  networks: " .. mobNetworks[mtype])
		for n, count in pairs(mobNetworkCount[mtype]) do
			EchoDebug("network #" .. n .. " has " .. count .. " spots and " .. ai.networkSize[mtype][n] .. " grids")
		end
	end


	-- deciding what kind of map it is
	local maxSpots = 0
	local minNetworks = 5
	local best = nil
	local mobRating = {}
	local totalRating = 0
	local numberOfRatings = 0
	for mtype, spots in pairs(mobSpots) do
		if #spots > maxSpots then
			if mobNetworks[mtype] < minNetworks then
				maxSpots = #spots
				minNetworks = mobNetworks[mtype]
				best = mtype
			end
		end
		local mostGrids = 0
		local mostSpots = 0
		if ai.networkSize[mtype] ~= nil then
			for n, size in pairs(ai.networkSize[mtype]) do
				if size > mostGrids and #ai.scoutSpots[mtype][n] > mostSpots then
					mostGrids = size
					mostSpots = #ai.scoutSpots[mtype][n]
				end
			end
		end
		if mobNetworks[mtype] == 0 then
			mobRating[mtype] = 0
		else
			mobRating[mtype] = ((mostSpots - mobNetworks[mtype]) + ((mostGrids / ai.mobilityGridArea) * mostSpots * 0.25))
		end
		totalRating = totalRating + mobRating[mtype]
		numberOfRatings = numberOfRatings + 1
		EchoDebug(mtype .. " rating: " .. mobRating[mtype])
	end

	-- add in bechmark air rating
	totalRating = totalRating + ((#ai.scoutSpots["air"][1] + (#ai.scoutSpots["air"][1] * 0.25)) * 0.5)
	local avgRating = totalRating / numberOfRatings
	local ratingFloor = avgRating * 0.65
	ai.mobilityRatingFloor = ratingFloor

	ai.mobRating = mobRating

	ai.hasUWSpots = #mobSpots["sub"] > 0

	if ai.hasUWSpots then
		EchoDebug("MapHandler: Submerged metal spots detected")
	end

	-- find start locations (loading them into air's list for later localization)
	ai.startLocations = {}
	if ai.startLocations["air"] == nil then ai.startLocations["air"] = {} end
	ai.startLocations["air"][1] = self:GuessStartLocations(metalSpots)
	if ai.startLocations["air"][1] ~= nil then
		-- localize start locations into mobility networks
		for i, start in pairs(ai.startLocations["air"][1]) do
			EchoDebug("start location guessed at: " .. start.x .. ", " .. start.z)
			PlotDebug(start.x, start.z, "start")
			for mtype, networkList in pairs(ai.scoutSpots) do
				if mtype ~= "air" then -- air list is already filled
					for n, spots in pairs(networkList) do
						if ai.startLocations[mtype] == nil then ai.startLocations[mtype] = {} end
						if ai.startLocations[mtype][n] == nil then ai.startLocations[mtype][n] = {} end
						table.insert(ai.startLocations[mtype][n], start)
					end
				end
			end
		end
	end

	if DebugEnabled then debugPlotFile:close() end

	self:SaveMapData()

	-- cleanup
	mobMap = {}

end
 
function MapHandler:ClosestFreeSpot(unittype, builder, position)

	-- local kbytes, threshold = gcinfo()
	-- game:SendToConsole("maphandler gcinfo: " .. kbytes .. " (before ClosestFreeSpot)")

	if position == nil then position = builder:GetPosition() end
	local spots = {}
	local bname = builder:Name()
	if commanderList[bname] then
		-- give the commander both hov and bot spots
		local pos = builder:GetPosition()
		local network = self:MobilityNetworkHere("bot", pos)
		if network ~= nil then
			-- EchoDebug("found bot metal spot network for commander")
			spots = ai.mobNetworkMetals["bot"][network]
		end
		network = self:MobilityNetworkHere("hov", pos)
		if network ~= nil then
			-- EchoDebug("found hover metal spot network for commander")
			if #spots == 0 then
				spots = ai.mobNetworkMetals["hov"][network]
			else
				for i, p in pairs(ai.mobNetworkMetals["hov"][network]) do
					table.insert(spots, p)
				end
			end
		end
		-- give the commander all metal spots if shp or bot doesn't work out
		if #spots == 0 then spots = ai.mobNetworkMetals["air"][1] end
	else
		local mtype, network = self:MobilityOfUnit(builder)
		if ai.mobNetworkMetals[mtype][network] ~= nil then
			spots = ai.mobNetworkMetals[mtype][network]
		end
	end
	if spots == nil then 
		EchoDebug(builder:Name() .. " has nil spots")
		return end
	if #spots == 0 then
		EchoDebug(builder:Name() .. " has zero spots")
		return
	end
	local uname = unittype:Name()
	local pos = nil
	local reclaimEnemyMex = false
	local bestDistance = 10000
 	-- check for armed enemy units nearby
	local uw = nil
	local uwutype = nil
	if ai.hasUWSpots then
		-- underwater mex check
		-- EchoDebug("map has uw spots")
		local coruwtype
		local armuwtype
		if uname == "cormex" or uname == "armmex" then
			coruwtype = game:GetTypeByName("coruwmex")
			armuwtype = game:GetTypeByName("armuwmex")
		elseif uname == "cormoho" or uname == "armoho" then
			coruwtype = game:GetTypeByName("coruwmme")
			armuwtype = game:GetTypeByName("armuwmme")
		end
		if coruwtype ~= nil then
			if builder:CanBuild(coruwtype) then
				uwutype = coruwtype
			elseif builder:CanBuild(armuwtype) then
				uwutype = armuwtype
			end
		end
		-- if uwutype ~= nil then EchoDebug("builder can build uw mexes") end
	end
	local f = game:Frame()
	for i,p in pairs(spots) do
		-- dont use this spot if we're already building there
		local alreadyPlanned = ai.buildsitehandler:PlansOverlap(p, uname)
		if not alreadyPlanned then
			local dist = Distance(position, p)
			-- don't add if it's already too high
			if dist < bestDistance then
				-- now check if we can build there
				local uwcheck
				if uwutype ~= nil then
					 uwcheck = game.map:CanBuildHere(uwutype, p)
					 -- EchoDebug("builder can build uw mex here? " .. tostring(uwcheck))
				end
				if game.map:CanBuildHere(unittype, p) or uwcheck then
					-- EchoDebug("can build mex at" .. p.x .. " " .. p.z)
					if ai.targethandler:IsSafePosition(p, builder) then
						bestDistance = dist
						pos = p
						reclaimEnemyMex = false
						if uwcheck then
							-- EchoDebug("uw mex is best distance")
							uw = uwutype
						else
							uw = nil
						end
					end
				elseif ai.targethandler:IsSafePosition(p, builder, 200) then
					-- is it an enemy mex that's blocking a safe position (or an unknown radar blip)?
					for i, enemySpot in pairs(ai.enemyMexSpots) do
						local epos = enemySpot.position
						if p.x > epos.x - 100 and p.x < epos.x + 100 and p.z > epos.z - 100 and p.z < epos.z + 100 then
							bestDistance = dist
							pos = epos
							reclaimEnemyMex = enemySpot.unit
							if uwcheck then
								-- EchoDebug("uw mex is best distance")
								uw = uwutype
							else
								uw = nil
							end
							break
						end
					end
				end
			end
		end
	end
	
	-- local kbytes, threshold = gcinfo()
	-- game:SendToConsole("maphandler gcinfo: " .. kbytes .. " (after ClosestFreeSpot)")

	-- if uw then EchoDebug("uw mex is final best distance") end
	return pos, uw, reclaimEnemyMex
end

function MapHandler:MobilityNetworkHere(mtype, position)
	if mtype == "air" then return 1 end
	local x = math.ceil(position.x / ai.mobilityGridSize)
	local z = math.ceil(position.z / ai.mobilityGridSize)
	local network
	if ai.topology[mtype][x] ~= nil then
		network = ai.topology[mtype][x][z]
	end
	return network
end

function MapHandler:MobilityOfUnit(unit)
	local position = unit:GetPosition()
	local name = unit:Name()
	local mtype = unitTable[name].mtype
	if ai.activeMobTypes[mtype] == nil then ai.activeMobTypes[mtype] = true end
	return mtype, self:MobilityNetworkHere(mtype, position)
end

function MapHandler:UnitCanGoHere(unit, position)
	if unit == nil then return false end
	if position == nil then return false end
	local mtype, unet = self:MobilityOfUnit(unit)
	local pnet = self:MobilityNetworkHere(mtype, position)
	if unet == pnet then
		return true
	else
		EchoDebug(mtype .. " " .. tostring(unet) .. " " .. tostring(pnet))
		return false
	end
end

function MapHandler:UnitCanGetToUnit(unit1, unit2)
	local position = unit2:GetPosition()
	return self:UnitCanGoHere(unit1, position)
end

function MapHandler:UnitCanHurtVictim(unit, victim)
	if unit:WeaponCount() == 0 then return false end
	local vname = victim:Name()
	local mtype = unitTable[vname].mtype
	local name = unit:Name()
	local canhurt = false
	if unitTable[name].groundRange > 0 and mtype == "veh" or mtype == "bot" or mtype == "amp" or mtype == "hov" then
		canhurt = "ground"
	elseif unitTable[name].airRange > 0 and mtype == "air" then
		canhurt = "air"
	elseif unitTable[name].submergedRange > 0 and mtype == "shp" or mtype == "sub" or mtype == "amp" then
		canhurt = "submerged"
	end
	return canhurt
end

function MapHandler:MobilityNetworkSizeHere(mtype, position)
	if mtype == "air" then return ai.mobilityGridArea end
	local x = math.ceil(position.x / ai.mobilityGridSize)
	local z = math.ceil(position.z / ai.mobilityGridSize)
	if ai.topology[mtype][x] == nil then
		return 0
	elseif ai.topology[mtype][x][z] == nil then
		return 0
	else
		local network = ai.topology[mtype][x][z]
		return ai.networkSize[mtype][network]
	end
end

function MapHandler:IsUnderWater(position)
	local x = math.ceil(position.x / ai.mobilityGridSize)
	local z = math.ceil(position.z / ai.mobilityGridSize)
	if ai.topology["sub"][x] ~= nil then
		if ai.topology["sub"][x][z] then return true end
	end
	return false
end

function MapHandler:OutmodedFactoryHere(mtype, position, network)
	if mtype == "air" then return false end
	if position and network == nil then
		network = self:MobilityNetworkHere(mtype, position)
	end
	if network == nil then
		return false
	else
		if ai.networkSize[mtype][network] < ai.mobCount[mtype] * 0.67 and ai.mobNetworks[mtype] > 1 then
	 		return true
		else
			return false
		end
	end
end

function MapHandler:CheckDefenseLocalization(unitName, position)
	local size = 0
	if unitTable[unitName].groundRange > 0 then
		local vehsize = self:MobilityNetworkSizeHere("veh", position)
		local botsize = self:MobilityNetworkSizeHere("bot", position)
		size = math.max(vehsize, botsize)
	elseif unitTable[unitName].airRange > 0 then
		return true
	elseif  unitTable[unitName].submergedRange > 0 then
		size = self:MobilityNetworkSizeHere("sub", position)
	else
		return true
	end
	local minimumSize = ai.mobilityGridArea / 4
	EchoDebug("network size here: " .. size .. ", minimum: " .. minimumSize)
	if size < minimumSize then
		return false
	else
		return true
	end
end
