Cave Generation v2.0

Remember Cave Generation + Dynamic Lighting v1.0? Well we had a lot of really small areas in between all of those caves that aren’t really good for anything. Too small to be of much use for exploration value/mining value or anything. Writing an algorithm to detect those small ‘caverns’, lets call them, was not fairly simple. With such a large bitmap, I was encountering stack overflow with my recursive flood fill and area finder. What I really needed was a non-recursive function for the area finder and to use the bitmapdata.floodFill() function that is in the BitmapData class. The evolution of the area finder algorithm was recursive to color bounds using mass floodfilling to a non-recursive queue implementation. The filling algorithm just went straight to the bitmap’s floodfill which wasn’t limited by stack overflow as the recursive one I had designed. In the picture below you can see the areas that were detected as too small colored red, and will be filled in with the Solid color.


And the code which determines these caverns to be filled in is:

package
{
	import flash.display.BitmapData;
	import flash.geom.Rectangle;
	/**
	 * ...
	 * @author UnknownGuardian, Skyboy
	 */
	public class CavernRemover
	{
		public static var cavern:Vector.<int>;
		private static var threshold:int = 200;
		private static const store:Vector.<int> = new Vector.<int>();

		public function CavernRemover()
		{

		}

		public static function removeCaverns(arr:Vector.<uint>, data:BitmapData, mapWidth:int, mapHeight:int):Vector.<uint>
		{
			cavern = new Vector.<int>(arr.length, true);
			data.lock();
			for (var i:int = 0; i < mapWidth; i++)
			{
				for (var j:int = 0; j < mapHeight; j++)
				{
					if (arr[i + j * mapWidth] == Main.Solid) continue;
					if (cavern[i + j * mapWidth] == 1) continue;
					var dx:int = i;
					var dy:int = j;
					var ret:int = 0, open:uint = Main.Open, q:int;
					var items:Vector.<int> = store;
					items.length = arr.length * 4; // i suggest this be preallocated elsewhere to save time on first-run
					items[q++] = dx;
					items[q++] = dy;
					do {
						dy = items[--q];
						dx = items[--q];
						if (int(dx < 0) | int(dy < 0) | int(dx >= mapWidth) | int(dy >= mapHeight)) continue; // using bitor and int to remove 3 unneeded jumps that occur due to faulty compiler
						if (cavern[dx + dy * mapWidth] == 1) continue;
						cavern[dx + dy * mapWidth] = 1;
						if (arr[dx + dy * mapWidth] != open) continue;
						items[q++] = dx;
						items[q++] = dy - 1;
						items[q++] = dx;
						items[q++] = dy + 1;
						items[q++] = dx - 1;
						items[q++] = dy;
						items[q++] = dx + 1;
						items[q++] = dy;
						++ret;
					} while (q);

					if ( ret != 0 && ret < threshold)
					{
						data.floodFill(i, j, 0xFFFF0000);
						arr = data.getVector(new Rectangle(0, 0, mapWidth, mapHeight)).concat();
					}
				}
			}
			data.unlock();
			return data.getVector(new Rectangle(0, 0, mapWidth, mapHeight)).concat();
		}
	}
}