From 8cd7d24da3d2ad3f18b2e86f444d1457874820c0 Mon Sep 17 00:00:00 2001
From: Kevin Chabowski <kevin@kch42.de>
Date: Sat, 17 Aug 2013 00:54:41 +0200
Subject: A faster Fill implementation.

(Still not super fast, but it's OK, I guess)
---
 tools.go | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 68 insertions(+), 10 deletions(-)

diff --git a/tools.go b/tools.go
index 11b6cef..6397223 100644
--- a/tools.go
+++ b/tools.go
@@ -45,20 +45,78 @@ type fillTool struct{}
 
 func (f *fillTool) SingleClick() bool { return true }
 
+func chkBounds(x, z, xStart, zStart, xEnd, zEnd int) bool {
+	return (x >= xStart) && (z >= zStart) && (x < xEnd) && (z < zEnd)
+}
+
 func (f *fillTool) Do(bio mcmap.Biome, biogs BiomeGetSetter, x, z int) {
-	if oldbio, ok := biogs.GetBiomeAt(x, z); ok {
-		floodfill(oldbio, bio, biogs, x, z)
+	oldbio, ok := biogs.GetBiomeAt(x, z)
+	if !ok {
+		return
 	}
-}
 
-func floodfill(oldbio, newbio mcmap.Biome, biogs BiomeGetSetter, x, z int) {
-	if bio, ok := biogs.GetBiomeAt(x, z); ok && (bio == oldbio) {
-		biogs.SetBiomeAt(x, z, newbio)
+	inChunkQueue := []XZPos{}
+	outOfChunkQueue := []XZPos{{x, z}}
+
+	for {
+		oocqL := len(outOfChunkQueue) - 1
+		if oocqL < 0 {
+			break
+		}
+
+		pos := outOfChunkQueue[oocqL]
+		inChunkQueue = []XZPos{pos}
+		outOfChunkQueue = outOfChunkQueue[:oocqL]
+
+		cx, cz, _, _ := mcmap.BlockToChunk(pos.X, pos.Z)
+		xStart := cx * mcmap.ChunkSizeXZ
+		zStart := cz * mcmap.ChunkSizeXZ
+		xEnd := xStart + mcmap.ChunkSizeXZ
+		zEnd := zStart + mcmap.ChunkSizeXZ
 
-		floodfill(oldbio, newbio, biogs, x-1, z)
-		floodfill(oldbio, newbio, biogs, x+1, z)
-		floodfill(oldbio, newbio, biogs, x, z-1)
-		floodfill(oldbio, newbio, biogs, x, z+1)
+		for {
+			icqL := len(inChunkQueue) - 1
+			if icqL < 0 {
+				break
+			}
+
+			pos := inChunkQueue[icqL]
+			inChunkQueue = inChunkQueue[:icqL]
+
+			px, pz := pos.X, pos.Z
+
+			if haveBio, ok := biogs.GetBiomeAt(px, pz); ok && (haveBio == oldbio) {
+				biogs.SetBiomeAt(px, pz, bio)
+
+				nx, nz := px+1, pz
+				if chkBounds(nx, nz, xStart, zStart, xEnd, zEnd) {
+					inChunkQueue = append(inChunkQueue, XZPos{nx, nz})
+				} else {
+					outOfChunkQueue = append(outOfChunkQueue, XZPos{nx, nz})
+				}
+
+				nx, nz = px-1, pz
+				if chkBounds(nx, nz, xStart, zStart, xEnd, zEnd) {
+					inChunkQueue = append(inChunkQueue, XZPos{nx, nz})
+				} else {
+					outOfChunkQueue = append(outOfChunkQueue, XZPos{nx, nz})
+				}
+
+				nx, nz = px, pz+1
+				if chkBounds(nx, nz, xStart, zStart, xEnd, zEnd) {
+					inChunkQueue = append(inChunkQueue, XZPos{nx, nz})
+				} else {
+					outOfChunkQueue = append(outOfChunkQueue, XZPos{nx, nz})
+				}
+
+				nx, nz = px, pz-1
+				if chkBounds(nx, nz, xStart, zStart, xEnd, zEnd) {
+					inChunkQueue = append(inChunkQueue, XZPos{nx, nz})
+				} else {
+					outOfChunkQueue = append(outOfChunkQueue, XZPos{nx, nz})
+				}
+			}
+		}
 	}
 }
 
-- 
cgit v1.2.3-70-g09d2