Code: Positions Picking Strategy

Positions Picking Strategy

In many situations, game designers have the demand to pick some random positions in a space for generating enemies, recourses or other items. However, it is not really the absolute randomness that they want, because it is counter-intuitive. Absolute randomness will, sometimes, lead us to extreme situations that the positions we picked are too close together, or some areas are rarely chosen. This is also known as “law of small numbers”.

This algorithm is a strategy for picking positions in a space both randomly and, to some degrees, uniformly. The mechanic is that we pick positions one by another, and every time we pick a new position randomly but with possibility weights of every unpicked positions, which stand for the summary of distances to every picked positions and border. And of course, the weights will be updated when a new position be picked.

The time complexity is O(mn), m means how many available positions in the space, and n means how many positions we need to pick.

The demo and the code(C#) are down below.

In the demo, the red cell means picked position, the brightness of other cells stands for the weights of possibility (more bright, more likely to be picked next time).

Demo link: https://lsqyzyx.itch.io/positions-picking-strategy

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using UnityEngine.Tilemaps;

public class CESim : MonoBehaviour
{
public Vector2Int minPos;
public Vector2Int maxPos;
public float howFarToborder;
public float bias;
public Tilemap tilemap;
public Tile tileDefault;

private Dictionary<Vector2Int, List<float>> distanceSum = new Dictionary<Vector2Int, List<float>>();
private float totalWeight = 0f;
private List<Vector2Int> positions = new List<Vector2Int>();

Vector2Int WeightedRandomSelect(Dictionary<Vector2Int, List<float>> distanceSum)
{
float rand = UnityEngine.Random.Range(0.0f, 1.0f);
float temp = 0f;
Vector2Int thePoint = new Vector2Int();
foreach (Vector2Int key in distanceSum.Keys)
{
temp += distanceSum[key][0];
thePoint = key;
if (temp >= rand) break;
}
return thePoint;
}

int distanceToBorder(Vector2Int point, Vector2Int minPos, Vector2Int maxPos)
{
List<int> distance = new List<int>() { point.x - minPos.x, point.y - minPos.y, maxPos.x - point.x, maxPos.y - point.y };
return distance.Min();
}

void paintTile()
{
for (int i = minPos.x; i <= maxPos.x; i++)
{
for (int j = minPos.y; j <= maxPos.y; j++)
{
tilemap.SetTile(new Vector3Int(i, j, 0), tileDefault);
tilemap.SetTileFlags(new Vector3Int(i, j, 0), TileFlags.None);
tilemap.SetColor(new Vector3Int(i, j, 0), Color.white);
}
}
}

bool TileAvailable(Vector3Int pos)
{
TileBase tb = tilemap.GetTile(pos);
if (tb == null) return false;
else return true;
}

void NewPointOnTilemap(Vector2Int newPoint)
{
tilemap.SetTile(new Vector3Int(newPoint.x, newPoint.y, 0), tileDefault);
tilemap.SetTileFlags(new Vector3Int(newPoint.x, newPoint.y, 0), TileFlags.None);
tilemap.SetColor(new Vector3Int(newPoint.x, newPoint.y, 0), Color.red);
}

void UpdateTileColor(Vector2Int pos, float value)
{
tilemap.SetTileFlags(new Vector3Int(pos.x, pos.y, 0), TileFlags.None);
tilemap.SetColor(new Vector3Int(pos.x, pos.y, 0), new Color(value, value, value, 1.0f));
}

void Initiate()
{
for (int i = minPos.y; i <= maxPos.y; i++)
{
for (int j = minPos.x; j <= maxPos.x; j++)
{
if (TileAvailable(new Vector3Int(j, i, 0)))
{
//initiate avaliable point & add it into dict
Vector2Int k = new Vector2Int(j, i);
distanceSum.Add(k, new List<float> { 0f, howFarToborder * distanceToBorder(new Vector2Int(j, i), minPos, maxPos) + bias });
totalWeight += distanceSum[k][1];
}
}
}
//update weights percentage
float max = 0f;
foreach (Vector2Int key in distanceSum.Keys)
{
distanceSum[key][0] = (float)(distanceSum[key][1] / totalWeight);
if (distanceSum[key][0] > max) max = distanceSum[key][0];
}
foreach (Vector2Int key in distanceSum.Keys)
{
UpdateTileColor(key, distanceSum[key][0] / max);
}
}

public void PutNewPoint()
{
Vector2Int newPoint = WeightedRandomSelect(distanceSum);
positions.Add(newPoint);
NewPointOnTilemap(newPoint);
//remove used point from dict
totalWeight -= distanceSum[newPoint][1];
distanceSum.Remove(newPoint);
//update weights
foreach (Vector2Int key in distanceSum.Keys)
{
float distanceWithBias = Vector2Int.Distance(key, newPoint) + bias;
distanceSum[key][1] += distanceWithBias;
totalWeight += distanceWithBias;
}
//update weights percentage
float max = 0f;
foreach (Vector2Int key in distanceSum.Keys)
{
distanceSum[key][0] = (float)(distanceSum[key][1] / totalWeight);
if (distanceSum[key][0] > max) max = distanceSum[key][0];
}
foreach (Vector2Int key in distanceSum.Keys)
{
UpdateTileColor(key, distanceSum[key][0]/max);
}
}

public void Put10NewPoints()
{
for (int i = 0; i < 10; i++) PutNewPoint();
}

void Start()
{
paintTile();
Initiate();
}
}