ds_grid_fill (work in progress, wer kann helfen?)

Morpheus · 28. Januar 2016, 21:14

Abend,
in meinem Spiel dessen Trailer ich erst gezeigt hab, will ich machen das sich das Wasser ausbreitet wenn es auf keinen Widerstand stößt. Wie für normale Blöcke, verwende ich auch für die Wasserblöcke einen Grid. Also habe ich Funktionen geschrieben die eine freie Fläche mit einem Wert befüllt, bis an allen Seiten ein Widerstand ist. Also wie der Farbeimer in Paint.

Im Video könnt ihr sehen, dass das sehr lange dauert und mache Zellen nicht befüllt werden. Allerdings ist der Grid in meinem Example auch 1024 x 768 groß, pro Pixel eine Zelle. Ich denke für kleinere Grids sind meine Skripte gut brauchbar,die Präzesion kann man noch erhöhen was dann länger dauert aber eben bei kleineren Grids noch schnell genug gehen dürfte.

DIe Funktionsweise:
Ich habe drei Skripte geschrieben. SKript 1 füllt die Fläche mit einem Quadtrat, bis dieses am Rand anstößt. Dann werden umliegende Zellen Blockweise gefüllt wenn diese an dem Quadrat angrenzen. Im zweiten Skript mache ich das so, dass ich das feine Hauptgrid in gröbere Blöcke aufteile. Pro Block prüfe ich mit ds_grid_get_sum ob er leer ist, wenn ja befüll ich ihn. Dann werden die übrigig gebliebenen Blöcke an mein drittes Skript übergeben, dass die leeren Stellen pixelgenau füllt.

Also ich Teile die zubefüllende Fläche quasi in Planquadrate auf wo ich schau ob ein Quadrat in der Summe dem Wert entspricht der geändert werden darf. Dann kann ich das ganze Quadrat füllen und muss nur noch die Qaudrate die übrig bleiben pixelgenau prüfen und befüllen lassen. Eigentlich wollte ich ja googlen wie so eine Fill-Funktion in Paint oder Photoshop gemacht wurde, ob es da einen tollen Algorithmus gibt. Aber ich wollte es selber lösen, bin aber mit dem Ergebnis noch unzufrieden. Große Flächen sind nicht unbedingt ein Problem, da ich das "Grobe" ja mit dem Quadrat ausfüllen lasse. Aber bei großen Flächen mit einer komplexen Form dauert das Ganze dann schon ganz schön lang.

Vielleicht hat einer von euch ja die Idee, wie man das schneller und effektiver programmieren kann.

Tice · 28. Januar 2016, 21:59

Hab mir dein Code mal angeschaut, du machst es etwas komisch und verwirrend.
Du solltest am besten das Zeichnen und die Füll-Logik in unterschiedlichen Scripts machen.

Ich hab dir mal kurz ein Floodfill geschrieben (ungetestet)
Du kannst ja mal versuchen das zu implementieren und nachdem dieses Script ausgeführt ist, die Surface neu zu befüllen.

GML-Quellcode

/// ds_grid_floodfill(grid, x, y, old, new)
var grid = argument[0];
var startX = argument[1];
var startY = argument[2];
var valueOld = argument[3];
var valueNew = argument[4];
var stack = ds_stack_create();
ds_stack_push(stack, stackX, stackY);
while (ds_stack_size(stack) > 0)
{
// Nächste Position zum Checken aus dem Stack holen
var _x = ds_stack_pop(stack);
var _y = ds_stack_pop(stack);
// Out of bounds check
if (_x < 0 || _x >= ds_grid_width(grid) ||
_y < 0 || _y >= ds_grid_height(grid))
continue;
var value = ds_grid_get(grid, _x, _y);
if (value == valueOld)
{
ds_grid_set(grid, _x, _y, valueNew);
// Nachbar position in den Stack packen
ds_stack_push(stack, _x, _y - 1);
ds_stack_push(stack, _x, _y + 1);
ds_stack_push(stack, _x - 1, _y);
ds_stack_push(stack, _x + 1, _y);
}
}
ds_stack_destroy(stack);

Alles anzeigen

Morpheus · 29. Januar 2016, 00:14

Ah ok, mit ds_stack machst du das. Hab ich noch nie verwendet leider. Danke, ich bau das mal ein und berichte dann.

edit: Irgendwas stimmt in deinem Script nicht, hab einen Kreis gemalt und wollte den dann ausfüllen. Dann wurde er aber nur zur Hälfte ausgefüllt und ganz wo anders im Grid wurde nochmal die Hälfte abgebildet. Ich guck mir das mal genauer an...

Morpheus · 29. Januar 2016, 01:00

Funzt wunderbar dein Skript, wenn man die zwei Fehler behebt die es enthält. Hast du absichtlich eingebaut um Noobs daran zu hindern einfach copy&paste zumachen?

edit: Dein Skript gepaart mit mit meiner genialen Idee (bin bescheiden^^) die zufüllende Fläche erst mal mit groben Rechtecken zufüllen revolutioniert gerade zu Floodfill

Morpheus · 29. Januar 2016, 12:05

Entschuldigt meinen Triplepost.

Es gibt jetzt noch ein Problem, das ich gerne lösen würde. Wenn man kleine Flächen mit dem Skript von Tice befüllt funzt das wunderbar. Doch große Flächen dauern einfach zu lange. Es muss ja jeden einzelnen Pixel prüfen. Darum war meine Idee, die große Fläche erst grob zu füllen also mit großen Rechtecken auszufüllen. Dazu verwende ich auch sein Skript allerdings prüfe ich nicht eine Zelle sondern die Summe einer Region. Wenn die Summe des Rechtecks dem Vielfachen (also Höhe x Breite hoch 2 mal dem Wert) des Werts entspricht mache ich ds_grid_set_region.
Das funzt auch super alleine. Nun muss ich aber die Rechtecke die übrig bleiben, also wo eine andere Farbe drin steckt pixelgenau füllen. Also muss ich die großen Zellen des "goben" Skripts an das pixelgenaue Skript übergeben.
Und da entsteht folgendes Problem: Ich habe ja dann nicht die xy Position eines leeren Pixels sondern nur xy Position des groben Rechtecks. Ich muss also schauen wo im Rechteck leere Pixel sind und da blieb mir nichts anderes übrig als das mit 2 for-Schleifen zu machen und das dauert dann im Endeffekt wieder zu lange. Mein Code sieht so aus:

Spoiler anzeigen

GML-Quellcode

///ds_grid_floodfill_coarse_grained(grid, x,y, old value, new value, gridsize, fill pixel precise);
var grid = argument[0];
var startX = round(argument[1] / argument[5]);
var startY = round(argument[2] / argument[5]);
var valueOld = argument[3];
var valueNew = argument[4];
var stack = ds_stack_create();
ds_stack_push(stack, startX, startY);
while (ds_stack_size(stack) > 0)
{
// Nächste Position zum Checken aus dem Stack holen
var _y = ds_stack_pop(stack);
var _x = ds_stack_pop(stack);
// Out of bounds check
if (_x <= 0 || _x > ds_grid_width(grid) ||
_y <= 0 || _y > ds_grid_height(grid))
continue;
var value = ds_grid_get_sum(grid, _x*argument[5],_y*argument[5],_x*argument[5]+argument[5]-1,_y*argument[5]+argument[5]-1);
if (value == valueOld)
{
ds_grid_set_region(grid, _x*argument[5],_y*argument[5],_x*argument[5]+argument[5]-1,_y*argument[5]+argument[5]-1, valueNew);
draw_rectangle(_x*argument[5],_y*argument[5],_x*argument[5]+argument[5],_y*argument[5]+argument[5], false);
// Nachbar position in den Stack packen
ds_stack_push(stack, _x, _y - 1);
ds_stack_push(stack, _x, _y + 1);
ds_stack_push(stack, _x - 1, _y);
ds_stack_push(stack, _x + 1, _y);
}
else if argument[6] {
// und der code hier drunter dauert einfach zu lang trotz break-Konstruktion
var b = 0;
for(var i=argument[5]; i>=0; i--) {
if b = 1 break;
for(var j=argument[5]; j>=0; j--) {
if grid[# _x*argument[5]+i,_y*argument[5]+j] = valueOld {
ds_grid_floodfill(grid, _x*argument[5]+i,_y*argument[5]+j, valueOld,valueNew, 1);
b = 1;
break;
}
}
}
}
}
ds_stack_destroy(stack);

Alles anzeigen

Und selbst wenn das schnell gehen würde besteht da noch das Problem, dass dann vielleicht eine Stelle befüllt wird die außerhalb der zu befüllenden Form liegt.
Hat jemand eine Idee?

edit: Habs mal so gemacht:

Spoiler anzeigen

GML-Quellcode

///ds_grid_floodfill_coarse_grained(grid, x,y, old value, new value, gridsize, fill pixel precise);
var grid = argument[0];
var startX = round(argument[1] / argument[5]);
var startY = round(argument[2] / argument[5]);
var valueOld = argument[3];
var valueNew = argument[4];
var stack = ds_stack_create();
ds_stack_push(stack, startX, startY, "center");
while (ds_stack_size(stack) > 0)
{
// Nächste Position zum Checken aus dem Stack holen
var dir = ds_stack_pop(stack);
var _y = ds_stack_pop(stack);
var _x = ds_stack_pop(stack);
// Out of bounds check
if (_x <= 0 || _x > ds_grid_width(grid) ||
_y <= 0 || _y > ds_grid_height(grid))
continue;
var value = ds_grid_get_sum(grid, _x*argument[5],_y*argument[5],_x*argument[5]+argument[5]-1,_y*argument[5]+argument[5]-1);
if (value == valueOld)
{
ds_grid_set_region(grid, _x*argument[5],_y*argument[5],_x*argument[5]+argument[5]-1,_y*argument[5]+argument[5]-1, valueNew);
draw_rectangle(_x*argument[5],_y*argument[5],_x*argument[5]+argument[5],_y*argument[5]+argument[5], false);
// Nachbar position in den Stack packen
ds_stack_push(stack, _x, _y - 1, "up");
ds_stack_push(stack, _x, _y + 1, "down");
ds_stack_push(stack, _x - 1, _y, "left");
ds_stack_push(stack, _x + 1, _y, "right");
}
else if argument[6] {
if dir = "up" {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5]+i,_y*argument[5]+argument[5]-1) = valueOld {
ds_grid_floodfill(grid, _x*argument[5]+i,_y*argument[5]+argument[5]-1, valueOld, valueNew, 1);
break;
}
}
}
else if dir = "down" {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5]+i,_y*argument[5]) = valueOld {
ds_grid_floodfill(grid, _x*argument[5]+i,_y*argument[5], valueOld, valueNew, 1);
break;
}
}
}
else if dir = "left" {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5]+argument[5]-1,_y*argument[5]+i) = valueOld {
ds_grid_floodfill(grid, _x*argument[5]+argument[5]-1,_y*argument[5]+i, valueOld, valueNew, 1);
break;
}
}
}
else if dir = "right" {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5],_y*argument[5]+i) = valueOld {
ds_grid_floodfill(grid, _x*argument[5],_y*argument[5]+i, valueOld, valueNew, 1);
break;
}
}
}
}
}
ds_stack_destroy(stack);

Alles anzeigen

Aber das dauert immernoch gefühlt genauso lange als wenn ich gleich die ganze Fläche pixelgenau befüllen lasse

Morpheus · 29. Januar 2016, 14:07

Hoffe ich krieg keinen Ärger für soviele Posts hiintereinander

Also ich habs jetzt gelöst. Der Code sieht wie folgt aus:

Spoiler anzeigen

GML-Quellcode

///ds_grid_floodfill_coarse_grained(grid, x,y, old value, new value, gridsize, fill pixel precise);
var grid = argument[0];
var startX = round(argument[1] / argument[5]);
var startY = round(argument[2] / argument[5]);
var valueOld = argument[3];
var valueNew = argument[4];
var stack = ds_stack_create();
var stack2 = ds_stack_create();
ds_stack_push(stack, startX, startY, 0);
while (ds_stack_size(stack) > 0)
{
// Nächste Position zum Checken aus dem Stack holen
var dir = ds_stack_pop(stack);
var _y = ds_stack_pop(stack);
var _x = ds_stack_pop(stack);
// Out of bounds check
if (_x < 0 || _x >= ds_grid_width(grid) ||
_y < 0 || _y >= ds_grid_height(grid))
continue;
var value = ds_grid_get_sum(grid, _x*argument[5],_y*argument[5],_x*argument[5]+argument[5]-1,_y*argument[5]+argument[5]-1);
if (value == valueOld * power(argument[5],2))
{
ds_grid_set_region(grid, _x*argument[5],_y*argument[5],_x*argument[5]+argument[5]-1,_y*argument[5]+argument[5]-1, valueNew);
draw_rectangle(_x*argument[5],_y*argument[5],_x*argument[5]+argument[5],_y*argument[5]+argument[5], false);
// Nachbar position in den Stack packen
ds_stack_push(stack, _x, _y - 1, 1);
ds_stack_push(stack, _x, _y + 1, 2);
ds_stack_push(stack, _x - 1, _y, 3);
ds_stack_push(stack, _x + 1, _y, 4);
}
else
{
ds_stack_push(stack2, _x, _y, dir);
}
}
if argument[6] {
while (ds_stack_size(stack2) > 0)
{
dir = ds_stack_pop(stack2);
_y = ds_stack_pop(stack2);
_x = ds_stack_pop(stack2);
if dir == 1 {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5]+i,_y*argument[5]+argument[5]-1) = valueOld {
ds_grid_floodfill(grid, _x*argument[5]+i,_y*argument[5]+argument[5]-1, valueOld, valueNew, 1);
break;
}
}
}
else if dir == 2 {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5]+i,_y*argument[5]) = valueOld {
ds_grid_floodfill(grid, _x*argument[5]+i,_y*argument[5], valueOld, valueNew, 1);
break;
}
}
}
else if dir == 3 {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5]+argument[5]-1,_y*argument[5]+i) = valueOld {
ds_grid_floodfill(grid, _x*argument[5]+argument[5]-1,_y*argument[5]+i, valueOld, valueNew, 1);
break;
}
}
}
else if dir == 4 {
for(var i=argument[5]; i>0; i-=1) {
if ds_grid_get(grid, _x*argument[5],_y*argument[5]+i) = valueOld {
ds_grid_floodfill(grid, _x*argument[5],_y*argument[5]+i, valueOld, valueNew, 1);
break;
}
}
}
}
}
ds_stack_destroy(stack);
ds_stack_destroy(stack2);

Alles anzeigen

Hab die pixelgenaue Methode von Tice mit meiner erweiterten Methode zeitlich verglichen, mit current_time. Die erweiterte Methode ist um ein vielfaches schneller!
Damit hab ich "Floodfill" revolutioniert!! xD

Morpheus · 29. Januar 2016, 19:52

Sowas kann man z.B. damit anstellen:

oder eben sowas wie Paint:

Atomicmaster · 29. Januar 2016, 21:42

Das Beispiel mit dem Wasser sieht sehr gut aus

Aber, das Wasser wird im Behälter nicht weniger? Oder hab ich das einfach nich gesehen im Video?

Morpheus · 29. Januar 2016, 21:49

Ja da hast du dich nicht verguckt. Es wird nicht weniger

Das könnte ich eigentlich noch einbauen, muss mal überlegen wie ich das mach.

Es gibt bestimmt noch viele andere Anwendungsgebiete für floodfill. Mir fiel nur das mit dem Wasser ein. Viellecicht fallen euch ja noch paar ein. A* Pathfinding oder G* Pathfinding baut doch im Prinzip auf sowas auf oder nicht?

Atomicmaster · 29. Januar 2016, 21:56

OT: Ich bin im Video immer hin und her gesprungen

"Wird das wasser weniger? Ich glaub es hat sich bewegt! Nochma zurück... hm nein doch net... oder hä? doch?"

Aufjedenfall sehr schön gelöst und scheint ja super zu funktionieren

GML-Quellcode

GML-Quellcode

GML-Quellcode

GML-Quellcode

Ähnliche Themen