はじめに

中心地点からランダムになにかをポップさせたい時って結構ありますよね？
でも、いい感じにばらけさせようとするとちょっと面倒だったりします
ちゃんとやろうと思ったらコリジョン判定などで行うことはできますが、そこまでやるつもりはない…めんどくさい…

ということで大体実装するとこんな感じになるとは思うんですが
こういうプログラムをみんな車輪を再開発している気がしたので僕が書いた場合のコードをまとめておきます
もっといいやり方ないかな～と思ってるんで定番のアルゴリズムとかあったら教えてください
(こういうよく使う系の処理ってEngine側で用意してあると助かるけど、これは求めすぎかなぁ)

実行環境

UE4.24.3
Microsoft Visual Studio Community 2017 Version 15.9.21

実装

確認方法

中心地点から一定範囲以内（250以内）に10個の椅子を発生させます

「いい感じ」とは

偏りが少ない
座標同士はある程度離れている

ランダムに取得する際にバイアスをかける

実装したコード

// Fill out your copyright notice in the Description page of Project Settings.


# include "JGSUtility.h"
# include "Math/UnrealMathUtility.h"

FVector UJGSUtility::GetNonOverlapVector(float maxRange,int index, float degree, float repossessionRange,const TArray<FVector>& vectorArray)
{
	auto getRandomVector = [maxRange](FVector biasVector)
	{
		float xMin = FMath::Clamp((-maxRange) + biasVector.X, -maxRange, maxRange);
		float xMax = FMath::Clamp(maxRange + biasVector.X, -maxRange, maxRange);
		float yMin = FMath::Clamp((-maxRange) + biasVector.Y, -maxRange, maxRange);
		float yMax = FMath::Clamp(maxRange + biasVector.Y, -maxRange, maxRange);
		float xRange = FMath::RandRange(xMin, xMax);
		float yRange = FMath::RandRange(yMin, yMax);
		return FVector(xRange, yRange, 0);
	};
	float theta = FMath::DegreesToRadians(index * degree);
	int r = maxRange / 2;//中心点から最大範囲の中間の長さ
	FVector biasVector = FVector(FMath::Cos(theta) * r,FMath::Sin(theta) * r,0);
	FVector retVector = getRandomVector(biasVector);
	const int safeTryCount = 10;
	int count = 0;
	bool isLoopEnd = false;
	//とり続けると設定値次第では無限LOOPしかねないのでセーフラインを設けておく
	while (!isLoopEnd && count < safeTryCount)
	{
		isLoopEnd = true;
		for (const auto& vec : vectorArray)
		{
			//再取得範囲内だったら再取得
			float xMax = vec.X + repossessionRange;
			float xMin = vec.X - repossessionRange;
			if (xMin <= retVector.X && retVector.X <= xMax)
			{
				retVector = getRandomVector(biasVector);
				isLoopEnd = false;
				break;
			}
			float yMax = vec.Y + repossessionRange;
			float yMin = vec.Y - repossessionRange;
			if (yMin <= retVector.Y && retVector.Y <= yMax)
			{
				retVector = getRandomVector(biasVector);
				isLoopEnd = false;
				break;
			}
		}
		count++;
	}
	return retVector;
}

void UJGSUtility::GetNonOverlapVectorArray(float maxRange, int degree, float repossessionRange,int requestCount ,TArray<FVector>& OutVecArray)
{
	OutVecArray.Empty();
	for (int i = 0; i < requestCount; i++)
	{
		FVector vector = GetNonOverlapVector(maxRange,i,degree,repossessionRange,OutVecArray);
		OutVecArray.Add(vector);
	}
}

解説

今回実装したコードは単純で、ランダムで座標を取得する際にバイアスを足してあげて既存の確定済みの座標にある程度被っていたら再取得しているだけです
問題はこのバイアスをどう求めるかですが、これも単純に以下の画像のように求められると思います

r : 座標取得の最大範囲
θ : 取得回数 × 任意の角度
α : 最大範囲座標
α’: αから半分の距離にある座標

実行した際の設定値とBlueprint

Max Range	Degree	Repossesion Range	Request Count
250	36度	35	10回

結果

なにも考えずにランダムにした場合

「いい感じ」とは程遠いですね

今回のアルゴリズムを試した結果

わりといい感じにバラすことができた気がします

おわりに

まぁ実際このコードで繰り返し試してみればわかるんですが、これでもわりと椅子と被るときあります
それはまぁsafeCount以内に取得できないケースもあるので、ある程度は許容かなと…
こういうコード、色んなゲームでみんな車輪の再開発しまくってると思うんだよね…
定番化してほしい…