4

私のゲームの都市はランダムに生成されますが、長方形を形成することしかできない道路と交差点のグラフです。

ここに画像の説明を入力してください

ご覧のとおり、私の地形はかなり空っぽです。私がやりたいのは、空の長方形をそれぞれ見つけて、長方形のリストに格納し、ロットを形成することです。

ここに画像の説明を入力してください

この図でわかるように、私は3つの「ロット」を埋め、1つでそれが構成されている3つの長方形を示しました。

私のデータ構造は次のとおりです。

package com.jkgames.gta;

import android.graphics.Bitmap;
import android.graphics.RectF;

public class Intersection extends Entity
{
    Road topRoad;
    Road leftRoad;
    Road bottomRoad;
    Road rightRoad;
    Bitmap image;

    public Bitmap getImage() 
    {
        return image;
    }

    public void setImage(Bitmap image)
    {
        this.image = image;
    }

    public Intersection(RectF rect, Bitmap image)
    {
        setRect(rect);
        setImage(image);
    }

    public Road getTopRoad() 
    {
        return topRoad;
    }

    public void setTopRoad(Road topRoad)
    {
        this.topRoad = topRoad;
    }

    public Road getLeftRoad()
    {
        return leftRoad;
    }

    public void setLeftRoad(Road leftRoad)
    {
        this.leftRoad = leftRoad;
    }

    public Road getBottomRoad() 
    {
        return bottomRoad;
    }

    public void setBottomRoad(Road bottomRoad)
    {
        this.bottomRoad = bottomRoad;
    }

    public Road getRightRoad()
    {
        return rightRoad;
    }

    public void setRightRoad(Road rightRoad) 
    {
        this.rightRoad = rightRoad;
    }

    @Override
    public void draw(GraphicsContext c)
    {
        c.drawRotatedScaledBitmap(image, getCenterX(), getCenterY(),
                    getWidth(), getHeight(), getAngle());
    }

}

public class Road extends Entity
{
    private Bitmap image = null;
    private Intersection startIntersection;
    private Intersection endIntersection;
    private boolean topBottom;

    public Road(RectF rect, Intersection start, Intersection end,
            Bitmap image, boolean topBottom)
    {
        setRect(rect);
        setStartIntersection(start);
        setEndIntersection(end);
        setImage(image);
        setTopBottom(topBottom);
    }

    @Override
    public void draw(GraphicsContext c)
    {
        //Rect clipRect = c.getCanvas().getClipBounds();
        //c.getCanvas().clipRect(getRect());
        float sizeW;
        float sizeH;
        if(isTopBottom())
        {
            sizeW = getWidth();
            sizeH = (sizeW / image.getWidth()) * image.getHeight();
        }
        else
        {
            sizeW = getHeight();
            sizeH = (sizeW / image.getWidth()) * image.getHeight();

        }

        int numTiles = isTopBottom() ? (int)Math.ceil(getHeight() / sizeH) :
            (int)Math.ceil(getWidth() / sizeW);

        for(int i = 0; i < numTiles; ++i)
        {
            if(isTopBottom())
            {
                c.drawRotatedScaledBitmap(
                        image,
                        getRect().left + (sizeW / 2.0f),
                        (getRect().top + (sizeH / 2.0f)) + (sizeH * i), 
                        sizeW, sizeH, 0.0f);
            }
            else
            {
                c.drawRotatedScaledBitmap(
                        image,
                        getRect().left + (sizeH / 2.0f) + (sizeH * i),
                        getRect().top + (sizeH / 2.0f), 
                        sizeW, sizeH, (float)Math.PI / 2.0f);
            }

        }

    //  c.getCanvas().clipRect(clipRect);
    }

    public Bitmap getImage() 
    {
        return image;
    }

    public void setImage(Bitmap image) 
    {
        this.image = image;
    }

    public Intersection getStartIntersection()
    {
        return startIntersection;
    }

    public void setStartIntersection(Intersection startIntersection) 
    {
        this.startIntersection = startIntersection;
    }

    public Intersection getEndIntersection()
    {
        return endIntersection;
    }

    public void setEndIntersection(Intersection endIntersection) 
    {
        this.endIntersection = endIntersection;
    }

    public boolean isTopBottom()
    {
        return topBottom;
    }

    public void setTopBottom(boolean topBottom) 
    {
        this.topBottom = topBottom;
    }
}

街は道路と交差点のリストです。

これらのロットとその長方形を生成できる何らかのアルゴリズムはありますか？

ありがとう

4

2 に答える 2

2

私の頭に浮かぶ最も簡単な方法は、フラッドフィルアルゴリズムを使用して地域のリストを作成することです。だから基本的に

foreach square:
    if the square isn't part of a region:
        create a new empty region list
        add the square to it
        recursivly add all neighboring squares to the region

最終的には、地域のリストが作成され、好きなように操作できるようになります（含まれている正方形のいずれかに建物が表示されているかどうか、ユーザーに色を付けるなど）。

注：正方形が領域の一部であるかどうかを判断するには、マークされたフラグなどを正方形のデータ構造に追加します。これにより、開始時にすべてのフラグを確認してクリアし、追加するときに正方形をそのフラグを設定した領域に合わせます。正方形が領域内にあるかどうかを確認する場合は、そのフラグが設定されているかどうかを確認するだけです。そうすれば、地域のリストを作成するための線形時間アルゴリズムができあがります。

Markusがここのコメントで指摘したように、この「フラグ」は実際には、正方形のリストを保持するLotオブジェクトへのポインター/参照である可能性があります。これは、とにかく便利な場合があります。

于 2012-10-16T21:00:03.003 に答える
0 
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++) {
    if (x > 0 && squares[y][x].isConnectedTo(squares[y][x-1]) {
        // Connected from the left
        squares[y][x-1].getLot().addSquare(squares[y][x]);

        if (y > 0 && squares[y][x].isConnectedTo(squares[y-1][x]) {
            // Connected from both the left and above
            squares[y-1][x].getLot().mergeWith(squares[y][x].getLot());
        }
    }
    else if (y > 0 && squares[y][x].isConnectedTo(squares[y-1][x]) {
        // Connected from above
        squares[y-1][x].getLot().addSquare(squares[y][x]);
    }
    else {
        // Not connected from either
        createNewLot().addSquare(squares[y][x]);
    }
}
  • Lot.addSquare(…)ロットに正方形を追加し、正方形を呼び出しますsetLot(…)。
  • Lot.mergeWith(…)2つのロットをマージし、それらが同じロットでない場合は、それらに割り当てられた正方形を再割り当てします。
  • Square.isConnectedTo(…)彼らが隣人であるかどうか、そして間に道路がないかどうかをチェックします。

素集合データ構造を使用してこれを最適化できます

于 2012-10-17T00:53:08.883 に答える