[Lua] PlotToRadiusIterator()

[Pazyryk]

Iterators are hard to make but easy to use. This iterator returns x,y plot coordinates out to a given radius from given center coordinates (edit: including the center). It knows about map edges and map wrapping and deals with these appropriately. It is optimized for speed including the use of memoization (offsets are calculated once for a given radius; subsequent calls with that radius use stored result). It also has two optional args (nearX, nearY) that define a sorting order for the returned coordinates. Sorting is expensive so don't supply nearX, nearY if you don't need sorting. Radius should work up to half the width or height (whichever is smaller) of the current map (for much more than radius 10 I would suggest iteration over all plots with a distance test).

Usage:

for x, y in PlotToRadiusIterator(centerX, centerY, 1) do
	--x, y for plots at radius 1 and center
	--there will be 7 iterations unless we are next to a map edge without wrap
end

for x, y in PlotToRadiusIterator(centerX, centerY, 5) do
	--x, y for plots in radius 0 to 5
end

for x, y in PlotToRadiusIterator(centerX, centerY, 3, nearX, nearY) do
	--x, y for plots in radius 0 to 3,
	--sorted so that they iterate in order by closest to nearX,nearY
	--(sorting is expensive so don't supply nearX, nearY if you don't need it)
end

Here's the code:

local iW, iH = Map.GetGridSize()
local bWrapX, bWrapY = Map.IsWrapX(), Map.IsWrapY()
local yOffsets, xOffsetsEvenY, xOffsetsOddY = {}, {}, {}	--contain tables indexed by radius; created and kept as needed
local tempIdx, sortedOffsetsX, sortedOffsetsY = {}, {}, {}	--used for sorting when approach plot given (indexed by radius; created and kept as needed)

function PlotToRadiusIterator(x, y, radius, myX, myY)
	-- last 2 args (optional & expensive) specify an "approach" coordinate that will cause return values to be sorted by nearest-first
	local Distance = Map.PlotDistance
	local Floor = math.floor
	local yOffset = yOffsets[radius]
	if not yOffset then	--calculate and keep offsets for this radius (radius up to half map size)
		local centerX = Floor(iW / 2)
		local centerYeven = Floor(iH / 4) * 2
		local centerYodd = centerYeven + 1
		local evenPos, oddPos = 1, 1
		yOffsets[radius], xOffsetsEvenY[radius], xOffsetsOddY[radius] = {}, {}, {}
		for testYoffset = -radius, radius do
			local testYeven = centerYeven + testYoffset
			local testYodd = centerYodd + testYoffset
			for textXoffset = -radius, radius do
				local testX = centerX + textXoffset
				if Distance(centerX, centerYeven, testX, testYeven) <= radius then
					xOffsetsEvenY[radius][evenPos] = textXoffset
					yOffsets[radius][evenPos] = testYoffset
					evenPos = evenPos + 1
				end
				if Distance(centerX, centerYodd, testX, testYodd) <= radius then
					xOffsetsOddY[radius][oddPos] = textXoffset
					oddPos = oddPos + 1
				end
			end
		end
		yOffset = yOffsets[radius]
	end

	local xOffset
	if y % 2 == 0 then -- y is even
		xOffset = xOffsetsEvenY[radius]
	else				 -- y is odd
		xOffset = xOffsetsOddY[radius]
	end

	local number = #yOffset
	if myX then		--sort returned values by direction I am comming from
		local Sort = table.sort
		local sortIdx, sortX, sortY = tempIdx[radius], sortedOffsetsX[radius], sortedOffsetsY[radius]
		if not sortIdx then
			sortIdx, sortX, sortY = {}, {}, {}
			tempIdx[radius], sortedOffsetsX[radius], sortedOffsetsY[radius] = sortIdx, sortX, sortY
			for i = 1, number do
				sortIdx[i] = i
			end
		end

		Sort(sortIdx, function(a, b)
							local Distance = Map.PlotDistance
							local myX, myY, xOffset, yOffset = myX, myY, xOffset, yOffset
							return Distance(myX, myY, x + xOffset[a], y + yOffset[a]) < Distance(myX, myY, x + xOffset[b], y + yOffset[b])
						end)
		for i = 1, number do
			local sortIndex = sortIdx[i]
			sortX[i] = xOffset[sortIndex]
			sortY[i] = yOffset[sortIndex]
		end
		xOffset, yOffset = sortX, sortY		--use sorted table instead of unsorted table
	end

	local i = 0
	return function()
		local x, y, bWrapX, bWrapY, number, xOffest, yOffset = x, y, bWrapX, bWrapY, number, xOffest, yOffset	--for speed
		while i < number do
			i = i + 1
			local xAdj = x + xOffset[i]
			local yAdj = y + yOffset[i]
			if bWrapX then
				if xAdj < 0 then
					xAdj = xAdj + iW
				elseif xAdj >= iW then
					xAdj = xAdj - iW
				end
			end
			if bWrapY then
				if yAdj < 0 then
					yAdj = yAdj + iH
				elseif yAdj >= iH then
					yAdj = yAdj - iH
				end
			end
			if yAdj >= 0 and yAdj < iH and xAdj >= 0 and xAdj < iW then		--only return a valid map coordinant
				return xAdj, yAdj
			end
		end
	end
end

Here's a bit of debug code I used to test it. This will highlight hexes out to supplied radius from the currently selected unit (with a different colored one indicating the first iteration coordinates, which is useful if you supply nearX, nearY for sorting). You'll need include( "FLuaVector" ) for this debug function.

function DebugPlotIterator(radius, nearX, nearY)	--nearX, nearY optional
	local unit = UI.GetHeadSelectedUnit()
	Events.ClearHexHighlights()
	local bStarted = false
	print("calling PlotToRadiusIterator", unit:GetX(), unit:GetY(), radius, nearX, nearY)
	for x, y in PlotToRadiusIterator(unit:GetX(), unit:GetY(), radius, nearX, nearY) do
		print(x, y)
		if bStarted then
			Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( x, y ) ), true, Vector4( 0, 1, 0, 1 ))
		else
			Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( x, y ) ), true, Vector4( 1, 0, 1, 1 ))
			bStarted = true
		end
	end
end

Edit (7/26/12): Contrary to my original post, this function also returns the center plot. My apologies if this inaccuracy messed anyone up. When I have time, I'll modify this with an optional "bExcludeCenter" arg, since I sometimes want the center but other times don't. But for now you'll just have to add this logic yourself.

[Nefliqus]

Thank you. Nice tool for map script developers, I think that i will use it for starting plots optimization.

[Pazyryk]

I fixed a minor error in the code. Changed,

local x, y, bWrapY, bWrapY, number, xOffest, yOffset = x, y, bWrapY, bWrapY, number, xOffest, yOffset

to

local x, y, bWrapX, bWrapY, number, xOffest, yOffset = x, y, bWrapX, bWrapY, number, xOffest, yOffset

It seemed to be working fine despite this error. The line is just localizing variables to the innermost function for a little speed boost (so bWrapX was still valid but localized at the file level).


Also, in the spirit of full disclosure, I must admit that I never tested Y map wrapping. If you plan to use doughnut-shaped worlds, you might want to test this to make sure it is working properly. If not, you can delete out some code for a 0.000001 second boost if you like.

[Evalis]

So I have a question about using this (yes yes I know you said it was simple to use but I am dumb). Let's say that I acquired the plot value of a city with :GetCityPlot (or whatever it is) would I then be able to simply put that variable into the location where it says centerx, centery?

For example:

Spoiler:

local pPlayer = Players[Game.GetActivePlayer()]
for iCity in pPlayer:Cities() do
   for x, y in PlotToRadiusIterator(iCity:GetCityPlot, 2) do
          -- Code stuff that makes other stuff happen
   end
end

[DonQuiche]

Just use that.

local plot = iCity:GetCityPlot()
PlotToRadiusIterator(plot:GetX(), plot:GetY(), 2)

[Evalis]

Thanks Don! For future reference it was actually iCity:Plot to get the value.

On that note however, the radius thingy did use the city tile! The radius was correctly within 2 squares, but the tile the function started on was also altered. What did I do wrong?

The code looked like this:

Spoiler:

for iCity in pPlayer:Cities() do
             local plot = iCity:Plot()
	for x, y in PlotToRadiusIterator(plot:GetX(), plot:GetY(), 2) do
		local pPlot = Map.GetPlot(x, y)
		if pPlot:GetResourceType(-1) == -1 then
			pPlot:SetResourceType(1, 1)
		end
	end
end

[DonQuiche]

You mean the iterator also returns the city plot itself? Nothing wrong with that, it's expected. For your own needs, you just need to check that the returned plot is not the city plot. Btw, GetResourceType does not take any argument.

if pPlot ~= plot and pPlot:GetResourceType() == -1 then

Also, I suggest to not use a hardcoded resource ID. Rather do something like that:

local resourceID = GameInfo.Resources["RESOURCE_GOLD"].ID

And you may also want to consider whether you want to make your mod compatible with another one that would remove gold for example (GameInfo.Resources would return nil in such a case, causing an error). Do you want to support that scenario and what should your mod do?

[xxhe]

Hello! Here's the code from the 1066AD Viking scenario. I wonder if the Map.PlotDistance(pCity:GetX(), pCity:GetY(), iLondonX, iLondonY) has the same function.

if (iBuildingType == GameInfo.Buildings["BUILDING_COURTHOUSE"].ID) then

		-- Only 8+ tiles from London
		if (Map.PlotDistance(pCity:GetX(), pCity:GetY(), iLondonX, iLondonY) < 8) then
			return false;
		end

		-- Only in originally Anglo-Saxon cities
		if (pCity:GetOriginalOwner() ~= iEngland)
 then
			return false;

		end

	end

[whoward69]

Map.PlotDistance() will tell you the number of tiles in a direct line between two plots, however, it will not get you a sequence of plots X tiles from a given plot - which is what the iterator does.

Two related, but completely different, functions.

[Pazyryk]

Originally Posted by DonQuiche

You mean the iterator also returns the city plot itself? Nothing wrong with that, it's expected.

Oops! Yes. Contrary to what I said in the OP, but that is what it does. I'll fix the OP to say what it really does. (I may modify it with an extra arg to make this optional, as I need both situations.)

@xxhe,
You could iterate over all plots on the map and then use Map.PlotDistance to determine which ones are within a certain radius. That would do the same exact thing. But PlotToRadiusIterator() will be much much faster, especially for short radii (or long radii if it is called repeatedly).