[REQUEST] Framework for iterating over tiles randomly and efficiently

[Darxo]

Is your feature request related to a problem? Please describe.

The World Map and Tactical Map consist of a fixed and known number of tiles, once they are generated.

A bunch of features require to pick random tiles with certain properties, to then do something with them.

• World: World Generation, Settlement Placement, Camp Generation, Beast Party Generation
• Tactical: Bush/Tree placement, Decoration/Decals, Spawn Positions (Alps), Skill Targeting (Summon Skulls, Ijirok Teleport)

The poor way that vanilla picks random tiles is by choosing a random X and Y and viewing the tile, and doing that until they are happy or have done a number of look-ups.

This approach is poor, because it is non-deterministically and at times inefficient (double lookups).

Describe the solution you'd like

A better solution is to create an array with all World or Tactical Tiles, randomize all elements in it and then iterate over that array until we are at the last element or found a valid tile for our purpose.

MSU could provide the Framework for this:

Interface

• getRandomWorldTileArray() could give an already randomized world tile array ready to be used
• getRandomTacticalTileArray() could give an already randomized tactical tile array ready to be used

Furthermore MSU could make sure that those arrays are calculated and provided as efficient as possible

• pre-calculate the next array before it is needed
  • keep multiple precalculated ones cached?
• determine the most efficient way to generate a randomized array and apply it here

Practical Example

This is code from a project of mine, where I use this tech to vastly improve settlement generation:
This uses an additional performance improvement, by reducing the core array in size as we come across tiles in it, which are invalid. So every further shuffle of it is a bit faster

local validTiles = [];
foreach (column in this.m.WorldTiles)
{
	foreach (tile in column)
	{
		// Currently no settlement is ever allowed to spawn on these tiles, so we filter them out right from the beginning
		if (tile.Type == ::Const.World.TerrainType.Shore) continue;
		if (tile.Type == ::Const.World.TerrainType.Ocean) continue;

		// Settlements may never spawn near the map border
		if (tile.SquareCoords.X <= this.m.HD_MapBorderSize) continue;
		if (tile.SquareCoords.X >= _rect.W - this.m.HD_MapBorderSize) continue;
		if (tile.SquareCoords.Y <= this.m.HD_MapBorderSize) continue;
		if (tile.SquareCoords.Y >= _rect.H - this.m.HD_MapBorderSize) continue;

		validTiles.push(tile);
	}
}

[...]

// We randomize validTiles, so that we have a fresh random list of tiles to iterate over for trying to place the settlement
::MSU.Array.shuffle(validTiles);
for (local index = validTiles.len() -1; index >= 0; --index)	// We go in reverse, so that we can delete validTiles entries without invalidating the loop
{
	[...]
}