Calculating a unit's movement range.

[ThorHammerz]

In the base game, every time a player clicks on a unit, it's range of movement (usually delineated with a blue-ish border) appears on the tile map, and from what I can gather, this requires some expensive (and hidden/abstracted) pathfinder calls with

Events.ShowMovementRange( iPlayerID, unit:GetID() );
UI.SendPathfinderUpdate();
Events.DisplayMovementIndicator( true );

Spoiler :

These events are not in the C++ source.

Has anyone tried to compute a "list of all plots that this unit can move into this turn" (e.g. with a Lua mod)?

My current plan is to modify the pathfinder and make it return (or cache) a vector/stack of CvPlot* pointers (this is the most straightforward way I can think of), but I wonder if there may be a more efficient way that someone else may have already tried.

 

[whoward69]

Might be worth investigating TurnsToReachTarget() (in CvAStar.cpp)

 

[ThorHammerz]

Might be worth investigating TurnsToReachTarget() (in CvAStar.cpp)

Yes, that is indeed the current function using:

Spoiler :

for(iDX = -(iRange); iDX <= iRange; iDX++)
	{
		for(iDY = -(iRange); iDY <= iRange; iDY++)
		{
			pPlot = plotXY(pTarget->getX(), pTarget->getY(), iDX, iDY);
                        if (TurnsToReachTarget(pLoopUnit, pTarget) == 0)
                        {
                           // do stuff
                         }
                 }
       }

I could set iRange could be dynamically set to [pUnit->getMoves() * highest road tech multiplier * highest promotion bonus]. But once railroads come into play (along with other movement bonuses), searching all plots in a range of potentially 50+ in the late-game may be a little impractical (would need to find a way to stop a search if a tile is already in an large region of impassibility due to circumstances like unit-blocking, or maybe a chain of mountains cuts across the continent, or perhaps the railroad only extends a few tiles in direction X, with the rest of the tiles unpaved).

Some comments in the code by Firaxis also seem to reflect the problem of RR making pathfinder very expensive, and is mostly the reason why most unit move calculations/searches are made with the assumption that tiles aren't paved (e.g. the search range for nearby plots is equivalent to the number of moves a unit has).

 

[whoward69]

Try something like

plots = {unitPlot}
iLWM = 0
iHWM = 1

bMore = true
while (bMore) {
  bMore = false
  
  for (i = iLWM; i < iHWM; i++) {
    startPlot = plots[i]
    
    for (targetPlot in allPlotsAround(startPlot)) {
      // If we've not already been here
      if (!plots.contains(targetPlot)) {
        iTurns = TurnsToReach(unitPlot, targetPlot)
        if (iTurns <= 1) {
          if (iTurns == 0) {
            // Not only can we reach this plot, but we have movement points left, so we need to consider plots around it
            plots.add(targetPlot)
            bMore = true
          } else {
            // While we can reach this plot, we can go no further
            plots.insert(iLWM, targetPlot)
            iHWM = iHWM + 1
          }
        }
      }
    }
  }
  
  iLWM = iHWM
  iHWM = #plots
}

which will only consider those plots that can still be reached, working outwards from the unit's plot

Note: If you can't implement plots.contains() as a hashed lookup but have to use a linear search, do it from #plots to 0, as a plot near to the target is much more likely to be further from the initial unitPlot

 

[ThorHammerz]

Thankyou Whoward

 

[whoward69]

Some clarification, in case others are trying to follow along ...

#plots - Lua style "number of entries in the array plots"

iLWM is Low Water Mark (as in tide line, not marks in paper!)
iHWM is High Water Mark

In effect the code uses the plots array to store three sets of data
a) plots seen in previous iterations are in offsets 0 to iLWM-1
b) plots to visit in this iteration are in offsets iLWM to iHWM-1
c) plots to visit in the next iteration are in offsets iHWM to #plots-1

You could use three data structures, but
a) that would give you three arrays to search for the contains() function
b) at the end of the iteration you have to add all the current plots to the previous plots and then move all the next plots into the current plots
and it's just much easier to move boundaries/water-marks as integer offsets into a single array

The code saves a bit of time by placing a newly discovered plot which we cannot progress from into the "plots we're visiting this iteration" section as opposed to the "plots to visit next iteration" section as we know there's no point checking it.

A possible optimisation would be to keep a list of plots we know we can't reach and not bother checking them again - it would all depend on how big that list would become on average and the associated lookup cost vs the time taken to calculate TurnsToReach() for the average distance plot