Border and Area plot iterators

whoward69 · Sep 5, 2012

The problem

There are many situations where we want "all the plots at distance r from a centre plot". Because of anomalies in the co-ordinate system used by plots on a Civ 5 Map, all of the solutions I've seen to this use scanning techniques to locate actual plots from within a larger set of possible plots - these methods are inefficient and return unordered lists. If you want "the next plot on the border" they quickly become unwieldy.

What we need is a Lua iterator that will efficiently return plots in order around the perimeter.

The Theory

In a rectangular based co-ordinate system, if we want to "walk" the perimeter of a box of "radius" r centered on (x, y) we need to traverse each side of the bounding square in turn, so we need to traverse the points (x-r, y-r) to (x-r, y+r) to (x+r, y+r) to (x+r, y-r) and finally back to (x-r, y-r). For each leg of the journey we keep either x or y constant and vary the other from -r to +r (or vice-versa)

For our Civ 5 hex based map, we need to traverse each side of the bounding hexagon

In trying to keep the Civ 5 map co-ordinate system "simple" by making it look like a rectangular grid, the developers introduced unnecessary complexity - anyone who has tried to iterate over plots on the map will know that the code needs to behave differently for odd and even values of y, and trying to (manually) calculate the distance between two plots is non-trivial (but fortunately there is a Map function for doing this)

If we can use a true hex based co-ordinate system, coding becomes much cleaner as we no longer have to allow for odd/even values of y. Fortunately (at least) one developer was of the same opinion, as we have ToHexFromGrid() and ToGridFromHex() methods, so we can convert our "Map co-ordinate" to a true hex based co-ordinate (with ToHexFromGrid()), work with it and then convert our result(s) back to "Map co-ordinates" (with ToGridFromHex())

Hex based co-ordinate systems have three axis - x, y and z - and have the property that for any (x, y, z) co-ordinate x+y+z is always equal to zero, which means we don't need to calculate or store one of the values (typically z) as it can always be calculated from the other two values, eg z = -(x+y)

To "walk" the edges of a bounding hexagon on a (true) hex based co-ordinate system we need to traverse the points as follows

along the North edge of the hex (x-r, y+r, z) to (x, y+r, z-r)
along the North-East edge (x, y+r, z-r) to (x+r, y, z-r)
along the South-East edge (x+r, y, z-r) to (x+r, y-r, z)
along the South edge (x+r, y-r, z) to (x, y-r, z+r)
along the South-West edge (x, y-r, z+r) to (x-r, y, z+r)
along the North-West edge (x-r, y, z+r) to (x-r, y+r, z)

which keeps one of x, y or z constant and varies one of the others from 0 to r (or vice-versa)

When coding this we need to bear in mind that if we traverse each side from start to finish we will include each corner twice, so we need to vary from 1 to r (or 0 to r-1)

We could calculate and store all the plots on the perimeter, but we can use Lua coroutines and closures to create an iterator function that will return one plot each time it is called

The scary code!

Spoiler :

Don't worry that it looks complex, as the good news is you don't need to understand it to use it!

Code:

for pEdgePlot in PlotRingIterator(pPlot, r) do
  print(pEdgePlot:GetX(), pEdgePlot:GetY())
end

As the Lua manual says "This is a common situation with iterators: They may be difficult to write, but are easy to use."

With a working "ring iterator" it's a straightforward task to write an "area iterator" - we just need to iterate each plot in each ring in turn

More scary code!

Spoiler :

Once again, don't worry that it looks complex, as the good news is you don't need to understand it to use it!

Code:

for pAreaPlot in PlotAreaSpiralIterator(pPlot, r, centre) do
  print(pEdgePlot:GetX(), pEdgePlot:GetY())
end

The plots are returned in order spiraling outwards from the centre, which if we just want all the plots within the area will suffice, however, sometimes we want a "radar sweep" effect, where we get all the points on a radius before moving on to any others. We can write such a "radar sweep" iterator with our ring iterator.

Yet more scary code!

Spoiler :

Once again, don't worry that it looks complex, as the good news is you don't need to understand it to use it!

Code:

for pAreaPlot in PlotAreaSweepIterator(pPlot, r, centre) do
  print(pEdgePlot:GetX(), pEdgePlot:GetY())
end

Some Full Examples

PlotRingIterator(pBabylon, 4, SECTOR_NORTH, DIRECTION_CLOCKWISE)

PlotRingIterator(pBabylon, 4, SECTOR_SOUTHWEST, DIRECTION_ANTICLOCKWISE)

PlotAreaSpiralIterator(pBabylon, 4, SECTOR_NORTH, DIRECTION_CLOCKWISE, DIRECTION_OUTWARDS, CENTRE_EXCLUDE)

PlotAreaRadarIterator(pBabylon, 4, SECTOR_NORTH, DIRECTION_CLOCKWISE, DIRECTION_OUTWARDS, CENTRE_EXCLUDE)

The Full Code

This should be placed in a separate "PlotIterators.lua" file with VFS set to true and then included into your own code, eg

Code:

include("PlotIterators")

for pAreaPlot in PlotAreaSweepIterator(pPlot, r) do
  print(pEdgePlot:GetX(), pEdgePlot:GetY())
end

Code:

--
-- Plot iterator functions
--   All functions create an iterator centered on pPlot starting in the specified sector and working in the given direction around the ring/area
--   PlotRingIterator(pPlot, r, sector, anticlock) returns each plot around a border of radius r
--   PlotAreaSpiralIterator(pPlot, r, sector, anticlock, inwards, centre) returns each plot within an area of radius r in concentric rings
--   PlotAreaSweepIterator(pPlot, r, sector, anticlock, inwards, centre) returns each plot within an area of radius r by radial
--
-- By converting the Map (x,y) co-ordinates to hex (x,y,z) co-ordinates we can simply walk the edges of the bounding hex
-- To walk an edge we keep one of x, y or z invariant, iterate the others from 0 to r-1 and r-1 to 0  (r-1 otherwise we include each vertex twice)
--
-- By using Lua coroutines we can keep the walking code (fairly) simple
--
-- Use these functions as follows
--
--    for pEdgePlot in PlotRingIterator(pPlot, r, sector, anticlock) do
--      print(pEdgePlot:GetX(), pEdgePlot:GetY())
--    end
--
--    for pAreaPlot in PlotAreaSpiralIterator(pPlot, r, sector, anticlock, inwards, centre) do
--      print(pAreaPlot:GetX(), pAreaPlot:GetY())
--    end
--
--    for pAreaPlot in PlotAreaSweepIterator(pPlot, r, sector, anticlock, inwards, centre) do
--      print(pAreaPlot:GetX(), pAreaPlot:GetY())
--    end
--

SECTOR_NORTH = 1
SECTOR_NORTHEAST = 2
SECTOR_SOUTHEAST = 3
SECTOR_SOUTH = 4
SECTOR_SOUTHWEST = 5
SECTOR_NORTHWEST = 6

DIRECTION_CLOCKWISE = false
DIRECTION_ANTICLOCKWISE = true

DIRECTION_OUTWARDS = false
DIRECTION_INWARDS = true

CENTRE_INCLUDE = true
CENTRE_EXCLUDE = false

function PlotRingIterator(pPlot, r, sector, anticlock)
  --print(string.format("PlotRingIterator((%i, %i), r=%i, s=%i, d=%s)", pPlot:GetX(), pPlot:GetY(), r, (sector or SECTOR_NORTH), (anticlock and "rev" or "fwd")))
  -- The important thing to remember with hex-coordinates is that x+y+z = 0
  -- so we never actually need to store z as we can always calculate it as -(x+y)
  -- See http://keekerdc.com/2011/03/hexagon-grids-coordinate-systems-and-distance-calculations/

  if (pPlot ~= nil and r > 0) then
    local hex = ToHexFromGrid({x=pPlot:GetX(), y=pPlot:GetY()})
    local x, y = hex.x, hex.y

    -- Along the North edge of the hex (x-r, y+r, z) to (x, y+r, z-r)
    local function north(x, y, r, i) return {x=x-r+i, y=y+r} end
    -- Along the North-East edge (x, y+r, z-r) to (x+r, y, z-r)
    local function northeast(x, y, r, i) return {x=x+i, y=y+r-i} end
    -- Along the South-East edge (x+r, y, z-r) to (x+r, y-r, z)
    local function southeast(x, y, r, i) return {x=x+r, y=y-i} end
    -- Along the South edge (x+r, y-r, z) to (x, y-r, z+r)
    local function south(x, y, r, i) return {x=x+r-i, y=y-r} end
    -- Along the South-West edge (x, y-r, z+r) to (x-r, y, z+r)
    local function southwest(x, y, r, i) return {x=x-i, y=y-r+i} end
    -- Along the North-West edge (x-r, y, z+r) to (x-r, y+r, z)
    local function northwest(x, y, r, i) return {x=x-r, y=y+i} end

    local side = {north, northeast, southeast, south, southwest, northwest}
    if (sector) then
      for i=(anticlock and 1 or 2), sector, 1 do
        table.insert(side, table.remove(side, 1))
      end
    end

    -- This coroutine walks the edges of the hex centered on pPlot at radius r
    local next = coroutine.create(function ()
      if (anticlock) then
        for s=6, 1, -1 do
          for i=r, 1, -1 do
            coroutine.yield(side[s](x, y, r, i))
          end
        end
      else
        for s=1, 6, 1 do
          for i=0, r-1, 1 do
            coroutine.yield(side[s](x, y, r, i))
          end
        end
      end

      return nil
    end)

    -- This function returns the next edge plot in the sequence, ignoring those that fall off the edges of the map
    return function ()
      local pEdgePlot = nil
      local success, hex = coroutine.resume(next)
      --if (hex ~= nil) then print(string.format("hex(%i, %i, %i)", hex.x, hex.y, -1 * (hex.x+hex.y))) else print("hex(nil)") end

      while (success and hex ~= nil and pEdgePlot == nil) do
        pEdgePlot = Map.GetPlot(ToGridFromHex(hex.x, hex.y))
        if (pEdgePlot == nil) then success, hex = coroutine.resume(next) end
      end

      return success and pEdgePlot or nil
    end
  else
    -- Iterators have to return a function, so return a function that returns nil
    return function () return nil end
  end
end


function PlotAreaSpiralIterator(pPlot, r, sector, anticlock, inwards, centre)
  --print(string.format("PlotAreaSpiralIterator((%i, %i), r=%i, s=%i, d=%s, w=%s, c=%s)", pPlot:GetX(), pPlot:GetY(), r, (sector or SECTOR_NORTH), (anticlock and "rev" or "fwd"), (inwards and "in" or "out"), (centre and "yes" or "no")))
  -- This coroutine walks each ring in sequence
  local next = coroutine.create(function ()
    if (centre and not inwards) then
      coroutine.yield(pPlot)
    end

    if (inwards) then
      for i=r, 1, -1 do
        for pEdgePlot in PlotRingIterator(pPlot, i, sector, anticlock) do
          coroutine.yield(pEdgePlot)
        end
      end
    else
      for i=1, r, 1 do
        for pEdgePlot in PlotRingIterator(pPlot, i, sector, anticlock) do
          coroutine.yield(pEdgePlot)
        end
      end
    end

    if (centre and inwards) then
      coroutine.yield(pPlot)
    end

    return nil
  end)

  -- This function returns the next plot in the sequence
  return function ()
    local success, pAreaPlot = coroutine.resume(next)
    return success and pAreaPlot or nil
  end
end


function PlotAreaSweepIterator(pPlot, r, sector, anticlock, inwards, centre)
  print(string.format("PlotAreaSweepIterator((%i, %i), r=%i, s=%i, d=%s, w=%s, c=%s)", pPlot:GetX(), pPlot:GetY(), r, (sector or SECTOR_NORTH), (anticlock and "rev" or "fwd"), (inwards and "in" or "out"), (centre and "yes" or "no")))
  -- This coroutine walks each radial in sequence
  local next = coroutine.create(function ()
    if (centre and not inwards) then
      coroutine.yield(pPlot)
    end

    local iterators = {}
    for i=1, r, 1 do
      iterators[i] = PlotRingIterator(pPlot, i, sector, anticlock)
    end

    for s=1, 6, 1 do
      -- In ring (n+1) there are (n+1)*6 or 6n + 6 plots,
      -- so we need to call the (n+1)th iterator six more times than the nth, or once more per outer loop
      -- eg for 3 rings we need a plot from ring 1, 2, 3, 2, 3, 3 repeated 6 times
      if (inwards) then
        for i=r, 1, -1 do
          for j=r, i, -1 do
            coroutine.yield(iterators[j]())
          end
        end
      else
        for i=1, r, 1 do
          for j=i, r, 1 do
            coroutine.yield(iterators[j]())
          end
        end
      end
    end

    if (centre and inwards) then
      coroutine.yield(pPlot)
    end

    return nil
  end)

  -- This function returns the next plot in the sequence
  return function ()
    local success, pAreaPlot = coroutine.resume(next)
    return success and pAreaPlot or nil
  end
end


--
-- Test functions
--

highlights = {
  RED     = {x=1.0, y=0.0, z=0.0, w=1.0},
  GREEN   = {x=0.0, y=1.0, z=0.0, w=1.0},
  BLUE    = {x=0.0, y=0.0, z=1.0, w=1.0},
  CYAN    = {x=0.0, y=1.0, z=1.0, w=1.0},
  YELLOW  = {x=1.0, y=1.0, z=0.0, w=1.0},
  MAGENTA = {x=1.0, y=0.0, z=1.0, w=1.0},
  BLACK   = {x=0.5, y=0.5, z=0.5, w=1.0}
}

function TestPlotHighlight(pPlot, highlight)
  print(pPlot:GetX(), pPlot:GetY())
  if (highlight ~= nil) then
    Events.SerialEventHexHighlight(ToHexFromGrid(Vector2(pPlot:GetX(), pPlot:GetY())), true, highlight)
  end
end

function TestPlotRingIterator(pPlot, r, sector, anticlock, highlight)
  for pEdgePlot in PlotRingIterator(pPlot, r, sector, anticlock) do
    TestPlotHighlight(pEdgePlot, highlight)
  end
end

function TestPlotAreaSpiralIterator(pPlot, r, sector, anticlock, inwards, centre, highlight)
  for pAreaPlot in PlotAreaSpiralIterator(pPlot, r, sector, anticlock, inwards, centre) do
    TestPlotHighlight(pAreaPlot, highlight)
  end
end

function TestPlotAreaSweepIterator(pPlot, r, sector, anticlock, inwards, centre, highlight)
  for pAreaPlot in PlotAreaSweepIterator(pPlot, r, sector, anticlock, inwards, centre) do
    TestPlotHighlight(pAreaPlot, highlight)
  end
end

-- TestPlotRingIterator(Players[0]:GetCapitalCity():Plot(), 4, SECTOR_NORTH, DIRECTION_CLOCKWISE, highlights.RED)
-- TestPlotAreaSpiralIterator(Players[0]:GetCapitalCity():Plot(), 3, SECTOR_SOUTH, DIRECTION_ANTICLOCKWISE, DIRECTION_OUTWARDS, CENTRE_INCLUDE)
-- TestPlotAreaSweepIterator(Players[0]:GetCapitalCity():Plot(), 3, SECTOR_SOUTH, DIRECTION_ANTICLOCKWISE, DIRECTION_OUTWARDS, CENTRE_INCLUDE)

DonQuiche · Sep 5, 2012

This is very nice, Whoward, I am sure many modders will be glad to find this. :goodjob:

Not only the code but also the explanations. I will definitely add a link to this post on the new wiki.

Now may I ask why you did need those specific orderings? I am just curious.

whoward69 · Sep 5, 2012

Three related links

Hex based co-ordinate systems explained

Lua iterators and closures reference

Lua coroutines tutorial

ww2commander · Sep 6, 2012

Second Don's comment.

Can you provide some examples that call for such functionality?

ww2commander · Sep 10, 2012

WHoward,

Notice a lack of response based on my previous comment which might have come across incorrectly.

To rephrase the question, can you briefly describe some situations that might call for this code to be used.

This would assist me in understand how to implement it in my mod if required.

whoward69 · Sep 11, 2012

Been busy with real work

All will become apparent when/if I complete my next major mod

ww2commander · Sep 11, 2012

No probs.

Curiosity is getting the better of me and your projects always surprise :drool:

ww2commander · Sep 16, 2012

Whoward,

To revisit this post..I am about to embark on writing some resupply code for my mod and was wondering if this code might assist in purpose.

My plan is to check if a unit needing resupply has enemy units nearby and determine priority of resupply. Thus units on the frontline get higher priority then quiet front units.

Is this code useful for such things or overkill?

I am not sure of any other way to get enemy units in area!

whoward69 · Sep 17, 2012

Like most things in computing the answer is "it depends". If there are only a few possible enemies it may be more efficient to iterate the units and calculate unit-to-enemyunit distances. If however there are many enemies (high chance of there actually being an enemy in that ring), it's probably more efficient to iterate the plots in the ring.

whoward69 · Sep 17, 2012

ww2commander said:
Curiosity is getting the better of me and your projects always surprise

A teaser then

whoward69 · Sep 17, 2012

ww2commander said:
My plan is to check if a unit needing resupply has enemy units nearby ...

If you know the expected direction of attack (so enemies coming from the West with an expected flanking strike from the South) you can "tweak" the iterator to allow for this. In this case you would start in sector NORTHWEST and set direction to be ANTICLOCKWISE as that will scan those tiles where you expect enemies to be first.

ww2commander · Sep 17, 2012

Thanks for the reply. Unfortunately I cant make out the text of the image too well so am not sure what it is!

I have studied your code further and am still a tad bit confused on how it works...specifically the spiral version. It mentions a parameter of 4 yet the screenshot shows only the northern 4 tiles being highlighted with east, south and west being only 3 tiles out. I am obviously misunderstanding the example somehow.

Another concern that came to mind was the processing time if over 200 units had to loop through this code for the relevant plot.

Anyhow, I will wait patiently and see what you do with the code

whoward69 · Sep 17, 2012

ww2commander said:
a tad bit confused on how it works...specifically the spiral version. It mentions a parameter of 4 yet the screenshot shows only the northern 4 tiles being highlighted with east, south and west being only 3 tiles out.

The arrow head is meant to mean "et cetera" (If I'd highlighted all the hexes the start location and direction wouldn't have been clear)

whoward69 · Sep 18, 2012

ww2commander said:
Another concern that came to mind was the processing time if over 200 units had to loop through this code for the relevant plot.

If your resupply algorithm depends on the proximity of enemy units, you're going to have to iterate over X units and check for any one of Y units within range no matter what approach you adopt.

However, there are different iteration strategies, some of which are significantly more efficient than others.

The worst approach would be

Code:

  for x = 1 to MaxX do
    for y = 1 to MaxY do
      if (Distance(x,y) < N) then
        resupply(x)
        break
      end
    end
  end

as this is potentially MaxX * MaxY distance calculations, with an average if MaxX * MaxY/2

The spiral area iterator requires no distance calculations and only a simple test to see if the owner of any unit in the tile is Mr Y

For an area of 2 (N=2) this is MaxX * 18 comparisons (6 in ring 1 and 12 in ring 2), for an average of MaxX * 9, so if there are more than 18 enemy units, the area iterator will be much more efficient.

If the ratio of MaxY to MaxX to small (ie many more X than Y) it will be even more efficient to iterate over the Y units and resupply any X units within their range.

Also, if you know the expected direction of attack, you can focus the iterators (sector, direction, type) to check that region first, which will further decrease the number of comparisions (as you are more likely to find an enemy unit quickly)

HTH

W

ww2commander · Sep 18, 2012

Thanks much for clarifying my concern.

I will give it a try without consideration for attack direction. Reason being that I want to focus on units being cutoff as well as expected attacks.

Whoward, you wealth of knowledge is a godsend to our community. If only I could convince you to somehow help me with my scenario UI screens! :joke:

whoward69 · Sep 19, 2012

ww2commander said:
I will give it a try without consideration for attack direction. Reason being that I want to focus on units being cutoff as well as expected attacks.

There is nothing to lose from adding the expected direction as the iterators will always check all possible plots. Adding such information just reduces the predicted number of tiles checked as you are starting where you expect an enemy to be (ie don't look to the left, then behind, then to your right if you expect the an enemy to be in front of you!)

For example, if you have a North vs South scenario with expected flank attacks from the East, start the iterator for the South player units in the NorthWest sector and proceed clockwise (NW, N, NE, SE, S, SW) and for the North player in the SouthWest sector and proceed anticlockwise (SW, S, SE, NE, N, NW)

For an East vs West scenario where expected flank attacks for either side will come from the South, start the East player at NW and proceed anticlockwise (NW, SW, S etc) and the West player at NE and proceed clockwise (NE, SE, S etc)

(draw them out, they make much more sense on paper!)

FramedArchitect · Dec 7, 2012

Thank you; very useful and easy to use.

General Tso · Jan 7, 2013

Thank you for this truly awesome piece of code. I need to place resources and units relative to each player's starting plot and it definitely saved some major time for me. I made a small change to the PlotAreaSpiralIterator so that it gets passed a minimum radius value instead of the centre boolean value and it works great!

Just curious - why did you use coroutines? I didn't even know that they existed until now, so I looked them up. Are you using them to increase speed or is there some other reason?

whoward69 · Jan 8, 2013

General Tso said:
or is there some other reason?

For me, they simplify the logic, "Set up processing, do some of it, pause, do something else, then resume processing" is a more logical flow than "stuff lots of state into external variables, process those variables for some amount, do something else (which may or may not inadvertantly affect those variables via bugs) and then come back and process them some more"

Also, the sector iterator has N ring iterators, which would mean that I would need an array of states - oh the opportunity to index incorrectly into those arrays - so the sector iterator needs to know something about the ring iterator that it shouldn't have to know.

General Tso · Jan 8, 2013

So if I understand properly you are using coroutine to keep the function alive so that it's values do not disappear. Very interesting.

Border and Area plot iterators

DLL Minion

Emperor

DLL Minion

Emperor

Emperor

DLL Minion

Emperor

Emperor

DLL Minion

DLL Minion

DLL Minion

Emperor

DLL Minion

DLL Minion

Emperor

DLL Minion

Reluctant Modder

Panzer General

DLL Minion

Panzer General

Similar threads