いくつかの非衝突した長方をランダムに配置するにはどうすればよいですか？
https://stackoverflow.com/questions/4373741
-
09-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はPygameでいくつかの2Dゲームに取り組んでいます。ランダムにいくつかのオブジェクトを同時に配置する必要があります それらが交差することなく. 。私はいくつかの明白な方法を試しましたが、それらはうまくいきませんでした。
明白な方法が続きます（擬似で）：
create list of objects
for object in list:
for other object in list:
if object collides with other object:
create new list of objects
その方法は永遠にかかりました。
私が試した他の方法：
create list of objects
for object in list:
for other object in list:
if object collides with other object:
remove object from list
その方法は空のリストの近くに返されました。
2〜20個のオブジェクトが大きいリストを扱っています。助言がありますか？
編集： 長方形はすべてランダムな異なるサイズです。
解決
答えを少し変更して、フォローアップの質問に対処して、代わりにランダムな非collidingを生成するように変更できるかどうかについての質問に対処しました 正方形 任意に長方形ではなく。私はこれを機能させる最も簡単な方法でこれを行いました。これは、元の答えの長方形の出力を後処理し、その内容を正方形のサブ領域に変えることでした。また、オプションの視覚化コードを更新して、両方の種類の出力を表示しました。明らかに、この種のフィルタリングを拡張して、各長方形や正方形をわずかに挿入して、互いに触れないようにするなど、他のことを行うことができます。
私の答えは、既に投稿された回答の多くが行うことを避けます。つまり、すでに作成されたものと衝突するものを拒否しながら、長方形をランダムに生成します。代わりに、そもそもオーバーラップしない生成のみに集中します。
これにより、非常に迅速に実行できるエリアサブディビジョンの問題に変えることで、比較的単純なことをする必要があります。以下は、これがどのように行われるかの1つの実装です。それは、外側の境界を定義する長方形から始まり、それを4つの小さな非重複長方形に分割します。これは、半ランダムの内部ポイントを選択し、外側の長方形の4つの既存のコーナーポイントとともに、4つのサブセクションを形成することによって達成されます。
アクションのほとんどはで行われますquadsect()働き。内部ポイントの選択は、出力がどのように見えるかを判断する上で重要です。少なくとも一定の最小幅または高さのサブ長方形を選択するか、ある程度の量よりも大きくない場合、あなたが望む方法を制約することができます。私の回答のサンプルコードでは、それは中心点±として定義されています1/3 外側の長方形の幅と高さのうち、基本的には任意の内部ポイントがある程度機能します。
このアルゴリズムはサブ補体を非常に迅速に生成するため、内部分割ポイントを決定するために計算時間を費やしても構いません。
このアプローチの結果を視覚化するのに役立つために、最後に、PIL（Python Imaging Library）モジュールでは、私が作成したいくつかのテスト実行中に生成された長方形を表示する画像ファイルを作成します。
とにかく、これがコードサンプルと出力サンプルの最新バージョンです：
import random
from random import randint
random.seed()
NUM_RECTS = 20
REGION = Rect(0, 0, 640, 480)
class Point(object):
def __init__(self, x, y):
self.x, self.y = x, y
@staticmethod
def from_point(other):
return Point(other.x, other.y)
class Rect(object):
def __init__(self, x1, y1, x2, y2):
minx, maxx = (x1,x2) if x1 < x2 else (x2,x1)
miny, maxy = (y1,y2) if y1 < y2 else (y2,y1)
self.min, self.max = Point(minx, miny), Point(maxx, maxy)
@staticmethod
def from_points(p1, p2):
return Rect(p1.x, p1.y, p2.x, p2.y)
width = property(lambda self: self.max.x - self.min.x)
height = property(lambda self: self.max.y - self.min.y)
plus_or_minus = lambda v: v * [-1, 1][(randint(0, 100) % 2)] # equal chance +/-1
def quadsect(rect, factor):
""" Subdivide given rectangle into four non-overlapping rectangles.
'factor' is an integer representing the proportion of the width or
height the deviatation from the center of the rectangle allowed.
"""
# pick a point in the interior of given rectangle
w, h = rect.width, rect.height # cache properties
center = Point(rect.min.x + (w // 2), rect.min.y + (h // 2))
delta_x = plus_or_minus(randint(0, w // factor))
delta_y = plus_or_minus(randint(0, h // factor))
interior = Point(center.x + delta_x, center.y + delta_y)
# create rectangles from the interior point and the corners of the outer one
return [Rect(interior.x, interior.y, rect.min.x, rect.min.y),
Rect(interior.x, interior.y, rect.max.x, rect.min.y),
Rect(interior.x, interior.y, rect.max.x, rect.max.y),
Rect(interior.x, interior.y, rect.min.x, rect.max.y)]
def square_subregion(rect):
""" Return a square rectangle centered within the given rectangle """
w, h = rect.width, rect.height # cache properties
if w < h:
offset = (h - w) // 2
return Rect(rect.min.x, rect.min.y+offset,
rect.max.x, rect.min.y+offset+w)
else:
offset = (w - h) // 2
return Rect(rect.min.x+offset, rect.min.y,
rect.min.x+offset+h, rect.max.y)
# call quadsect() until at least the number of rects wanted has been generated
rects = [REGION] # seed output list
while len(rects) <= NUM_RECTS:
rects = [subrect for rect in rects
for subrect in quadsect(rect, 3)]
random.shuffle(rects) # mix them up
sample = random.sample(rects, NUM_RECTS) # select the desired number
print '%d out of the %d rectangles selected' % (NUM_RECTS, len(rects))
#################################################
# extra credit - create an image file showing results
from PIL import Image, ImageDraw
def gray(v): return tuple(int(v*255) for _ in range(3))
BLACK, DARK_GRAY, GRAY = gray(0), gray(.25), gray(.5)
LIGHT_GRAY, WHITE = gray(.75), gray(1)
RED, GREEN, BLUE = (255, 0, 0), (0, 255, 0), (0, 0, 255)
CYAN, MAGENTA, YELLOW = (0, 255, 255), (255, 0, 255), (255, 255, 0)
BACKGR, SQUARE_COLOR, RECT_COLOR = (245, 245, 87), (255, 73, 73), (37, 182, 249)
imgx, imgy = REGION.max.x + 1, REGION.max.y + 1
image = Image.new("RGB", (imgx, imgy), BACKGR) # create color image
draw = ImageDraw.Draw(image)
def draw_rect(rect, fill=None, outline=WHITE):
draw.rectangle([(rect.min.x, rect.min.y), (rect.max.x, rect.max.y)],
fill=fill, outline=outline)
# first draw outlines of all the non-overlapping rectanges generated
for rect in rects:
draw_rect(rect, outline=LIGHT_GRAY)
# then draw the random sample of them selected
for rect in sample:
draw_rect(rect, fill=RECT_COLOR, outline=WHITE)
# and lastly convert those into squares and re-draw them in another color
for rect in sample:
draw_rect(square_subregion(rect), fill=SQUARE_COLOR, outline=WHITE)
filename = 'square_quadsections.png'
image.save(filename, "PNG")
print repr(filename), 'output image saved'
出力サンプル1
出力サンプル2
他のヒント
3つのアイデア：
オブジェクトのサイズを小さくします
最初のメソッドは、20の非重複オブジェクトのランダムな配列を押すことが非常にありそうもないために失敗します（実際には (1-p)^20, 、 どこ 0<p<1 2つのオブジェクトが衝突する確率です）。劇的に（壮大なドラマの注文）サイズを減らすことができれば、それが役立つかもしれません。
それらを1つずつ選んでください
最も明らかな改善は、次のとおりです。
while len(rectangles)<N:
new_rectangle=get_random_rectangle()
for rectangle in rectangles:
if not any(intersects (rectangle, new_rectangle) for rectangle in rectangles)
rectangles.add(new_rectangle)
これにより、パフォーマンスが大幅に向上します。単一の交差点を持つことで、まったく新しいセットを生成することを余儀なくされないため、異なる単一の長方形を選ぶだけです。
事前計算
ゲームでこれらのセットを使用する頻度はどれくらいですか？ 1秒ごとに異なるセットを使用することは、1時間に1回セットを使用するのとは異なるシナリオです。これらのセットをあまり頻繁に使用しない場合は、Gamerがおそらく同じセットを2回表示することはないように、Sの大規模なセットを事前に計算してください。事前に計算するとき、あなたは費やした時間をあまり気にしません（したがって、あなたはあなたの非効率的な最初のアルゴリズムを使用することさえできます）。
実行時に実際にこれらの長方形を必要としている場合でも、CPUが何らかの理由でアイドル状態になっている場合、必要になる前に少し計算することをお勧めします。
実行時に、ランダムにセットを選択してください。これはおそらく、リアルタイムゲームの最良のアプローチです。
ノート：このソリューションは、長方形が空間節約方法で保持されることを前提としています。 (x, y) 座標。これらのペアはほとんどスペースを消費しておらず、実際には妥当なサイズのファイルで数千、さらに数百万を節約できます。
有用なリンク：
あなたの問題には非常に単純な近似があり、私にとってはうまくいきました：
- グリッドを定義します。たとえば、100ピクセルグリッドは（x、y） - >（int（x/100）、int（y/100））を書き込みます。グリッド要素は重複しません。
- 各オブジェクトを別のグリッドに入れ（グリッドの内側にランダムにきれいに見えます）、いくつかのオブジェクトのオーバーラップを許可できる場合、各グリッドにいくつかのオブジェクトをランダムに配置します。
これを使用して、2Dマップ（Zelda wike）をランダムに生成しました。私のオブジェクトの画像は<100*100>よりも小さいため、サイズ<500*500>のグリッドを使用し、各グリッドで1〜6個のオブジェクトを許可しました。
list_of_objects = []
for i in range(20):
while True:
new_object = create_object()
if not any(collides(new_object, x) for x in list_of_objects):
break
list_of_objects.append(new_object)
私はあなたがすでに持っていると思います create_object() と collides() 関数
また、これが何度もループしすぎると、長方のサイズを減らす必要があるかもしれません
試しましたか：
Until there are enough objects:
create new object
if it doesn't collide with anything in the list:
add it to the list
リスト全体を再現したり、衝突に関与しているすべてを取り出したりするセンスはありません。
別のアイデアは、次のアプローチのいずれかによって衝突を「修正」することです。
1）交差点の領域の中心を見つけ、それぞれの交差する長方の適切なコーナーをそのポイントに調整します。
2）長方形が何かと衝突したら、その長方形のサブ領域をランダムに生成し、代わりに試してください。
すでに述べたものに対する代替の擬似コード：
while not enough objects:
place object randomly
if overlaps with anything else:
reduce size until it fits or has zero size
if zero size:
remove
またはそのようなもの。
しかし、これには、意図したものよりも小さなオブジェクトを作成し、ほとんど交差するオブジェクトを作成するという利点があります（つまり、タッチ）。
プレーヤーがトラバースするマップである場合、パスがブロックされる可能性があるため、それらをトラバースすることができない場合があります。
私の場合、全体的な長方形の内部にいくつかの事前既存の長方形があったことを除いて、私は同様の問題を抱えていました。そのため、既存の長方形の周りに新しい長方形を配置する必要がありました。
私は貪欲なアプローチを使用しました：
- 全体的な（グローバル）長方形を長方形化する：これまでのすべての長方形のソートされたXとソートされたY座標からグリッドを作成します。そのため、不規則な（ただし長方形の）グリッドが得られます。
- 各グリッドセルが領域を計算すると、これにより領域のマトリックスが得られます。
- 使用する Kadanes 2d 最大領域を与えるサブ行列を見つけるアルゴリズム（=最大のフリー長方形）
- その自由空間にランダムな長方形を置きます
- 繰り返す
これには、元の座標空間からグリッドスペースからの間、およびそれが簡単に変換する必要があります。
（オリジナルのグローバルな長方形でカデンを直接実行するには長くかかることに注意してください。グリッド近似を介して行くことは私のアプリケーションには十分に高速です）
