また週末、ということは、趣味のプロジェクトで遊ぶことができるということです。
手動でテスト レベルを作成するのに飽きてきたので、エンジン開発から離れてレベル エディターに取り掛かることにしました。
レベルエディタ http://gfilter.net/junk/Editor.JPG
ペイント プログラムと同じように機能する塗りつぶしアルゴリズムをエディタに実装したいと考えています。ここで私にとってどのテクニックがうまくいくかについて誰かが何か指針を持っていますか?
レベルは単なる 2 次元配列なので、実際にはビットマップと同じと見なすことができます。
ありがとう！
ウィキペディアの記事はかなり良いです。グリッドが小さい限り、ほとんど何でも機能します。
今年の秋の初めに、10 メガピクセルのスキャン画像にフラッド フィリングを行いました。(問題は、コピー機でスキャンされた本のページから黒いエッジを削除することでした。) その場合、色は 2 つしかないため、基本的に無向グラフでの検索のように問題を処理し、各ピクセルを隣接するピクセルに沿って接続します。コンパスの 4 つの方向。どのピクセルがアクセスされたかを追跡するために、別のビットマップを維持しました。
主な調査結果は次のとおりです。
再帰的な深さ優先検索を試みないでください。明示的なデータ構造が本当に必要です。
補助キューは、スタックよりもはるかに少ないスペースを使用します。約40 分の 1 のスペースです。つまり、深さ優先検索よりも幅優先検索を優先します。
繰り返しますが、これらの調査結果は、複数のメガピクセルを持つグリッドにのみ適用されます。質問に示されているような素敵な小さなグリッドでは、単純なアルゴリズムが機能するはずです。
私たちは学校のためにそれをプログラムしなければなりませんでした:
1: stuff the start pixel into a queue, note its color. note it as added.
2: begin picking a pixel off the queue. If it's similar to the start pixel:
2: put all its neighbours into the queue
for each added pixel, note it's added. if already noted for a pixel, don't
add it anymore.
3: color it with the destination color.
3: nonempty => jump back to 2
4: empty => we are finished
8 隣接か 4 隣接かによって、8 つの隣接ピクセルすべてをチェックするか、特定のピクセルの左/右または上/下のピクセルのみをチェックします。これがコードです（ImageJを使用しています。関係のないコードをいくつか削除しました）。意味があるといいのですが、それは Java です。質問をしてください：
public class Uebung1_2 implements PlugInFilter, MouseListener {
private ImageProcessor ip;
boolean[] state;
int[] pixels;
Queue<Integer> nextPixels;
int threshould;
/**
* adds one pixel to the next-pixel queue only if it's not
* already added.
*/
void addNextPixel(int p) {
if(!state[p]) {
nextPixels.add(p);
state[p] = true;
}
}
boolean pixelsSimilar(int color1, int color2) {
int dr = Math.abs(((color1 >> 16) & 0xff) -
((color2 >> 16) & 0xff));
int dg = Math.abs(((color1 >> 8) & 0xff) -
((color2 >> 8) & 0xff));
int db = Math.abs(((color1 >> 0) & 0xff) -
((color2 >> 0) & 0xff));
return ((double)(dr + dg + db) / 3.0) <= threshould;
}
/**
* actually does the hard work :)
* @param x the x position from which to start filling
* @param y the y position from which to start filling
*/
private void doFill(int x, int y, boolean connect8) {
// first, add the start pixel
int width = ip.getWidth(),
height = ip.getHeight();
/* for 8bit, we just gonna take the median of rgb */
Color colorC = ij.gui.Toolbar.getForegroundColor();
int color = colorC.getRGB();
int firstPixel = ip.get(x, y);
// go on with the mainloop
addNextPixel(y * width + x);
while(!nextPixels.isEmpty()) {
int nextPixel = nextPixels.remove();
int pixel = pixels[nextPixel];
if(pixelsSimilar(pixel, firstPixel)) {
// yay it matches. put the neighbours.
int xN = nextPixel % width,
yN = nextPixel / width;
/* the three pixels above */
if(yN - 1 >= 0) {
if(connect8) {
if(xN + 1 < width) {
addNextPixel(nextPixel - width + 1);
}
if(xN - 1 >= 0) {
addNextPixel(nextPixel - width - 1);
}
}
addNextPixel(nextPixel - width);
}
/* pixels left and right from the current one */
if(xN > 0) {
addNextPixel(nextPixel - 1);
}
if(xN + 1 < width) {
addNextPixel(nextPixel + 1);
}
/* three pixels below */
if(yN + 1 < height) {
if(connect8) {
if(xN + 1 < width) {
addNextPixel(nextPixel + width + 1);
}
if(xN - 1 >= 0) {
addNextPixel(nextPixel + width - 1);
}
}
addNextPixel(nextPixel + width);
}
/* color it finally */
pixels[nextPixel] = color;
}
}
}
@Override
public void run(ImageProcessor ip) {
ij.WindowManager.getCurrentImage().getCanvas().addMouseListener(this);
this.ip = ip;
this.pixels = (int[])ip.getPixels();
this.state = new boolean[ip.getPixelCount()];
this.nextPixels = new LinkedList<Integer>();
}
@Override
public int setup(String arg0, ImagePlus arg1) {
return DOES_RGB;
}
@Override
public void mouseClicked(MouseEvent e) {
ij.WindowManager.getCurrentWindow().getCanvas().removeMouseListener(this);
ij.gui.GenericDialog g = new GenericDialog("Please enter parameters");
g.addChoice("connection", new String[]{"4-connect", "8-connect"}, "8-connect");
g.addNumericField("Threshould (0..255)", 0.0, 3);
g.showDialog();
boolean connect8 = g.getNextChoice().equals("8-connect");
threshould = (int) g.getNextNumber();
doFill(e.getX(), e.getY(), connect8);
ij.WindowManager.getCurrentImage().draw();
}
}
ウィクペディアでは、フラッド フィルの記事でさまざまなフラッド フィル手法の疑似コードの例をいくつか提供しています。どの手法を選択するかは、アプリケーションによって異なります。
フラッド フィリングは簡単にスレッド化できることに注意してください (クイックソートと同様)。
公平を期すために、それは非常に単純であるべきです。とにかく基本的なタイル構造があるので、アルゴリズムはかなり単純になります。
Select Tile To Fill:
Fill Till
Check neighbouring Tiles - If Empty Then Fill
Repeat, for all filled tiles.
免責事項: 上記は非常に基本的な説明です。ウェブ上には、私よりもはるかによく説明している参考文献がたくさんあります。
C# プログラムで GDI+ ルーチンを使用する方法の例を次に示します。
( https://www.pinvoke.net/default.aspx/gdi32.extfloodfill )
using System.Runtime.InteropServices;
//insert by Zswang(wjhu111#21cn.com) at 2007-05-22
[DllImport("gdi32.dll")]
public static extern IntPtr SelectObject(IntPtr hdc, IntPtr hgdiobj);
[DllImport("gdi32.dll")]
public static extern IntPtr CreateSolidBrush(int crColor);
[DllImport("gdi32.dll")]
public static extern bool ExtFloodFill(IntPtr hdc, int nXStart, int nYStart,
int crColor, uint fuFillType);
[DllImport("gdi32.dll")]
public static extern bool DeleteObject(IntPtr hObject);
[DllImport("gdi32.dll")]
public static extern int GetPixel(IntPtr hdc, int x, int y);
public static uint FLOODFILLBORDER = 0;
public static uint FLOODFILLSURFACE = 1;
private void button1_Click(object sender, EventArgs e)
{
Graphics vGraphics = Graphics.FromHwnd(Handle);
vGraphics.DrawRectangle(Pens.Blue, new Rectangle(0, 0, 300, 300));
vGraphics.DrawRectangle(Pens.Blue, new Rectangle(50, 70, 300, 300));
IntPtr vDC = vGraphics.GetHdc();
IntPtr vBrush = CreateSolidBrush(ColorTranslator.ToWin32(Color.Red));
IntPtr vPreviouseBrush = SelectObject(vDC, vBrush);
ExtFloodFill(vDC, 10, 10, GetPixel(vDC, 10, 10), FLOODFILLSURFACE);
SelectObject(vDC, vPreviouseBrush);
DeleteObject(vBrush);
vGraphics.ReleaseHdc(vDC);
}
を使用する代わりにGraphics vGraphics = Graphics.FromHwnd(Handle);、OnPaint イベント ハンドラでこれを呼び出す場合は、 を使用できますe.Graphics。私にとってはかなりうまくいきました。
アルゴリズムを再発明して既存のルーチンを使用しない方がよい場合もありますが、Mono に移植するときに問題が発生する可能性があります。