Island World Generator
Generate a bunch of random islands in the world....infinitely. Code arranged with the help of WonderFLCompiler . Click on light blue regions to generate islands. Revisiting back the same cell locations will generate back the same set of islands because of the seed. Use arrow keys or numeric steppers to navigate through world cells. World KD/Quadtree construction uses: http://wonderfl.net/c/6dsC and Island generation uses: https://github.com/amitp/mapgen2 algorithms
/**
* Copyright Glidias ( http://wonderfl.net/user/Glidias )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/x3eo
*/
package {
//import alternterrainxtras.msa.MathUtils;
//import alternterrainxtras.msa.Perlin;
//import alternterrainxtras.msa.Smoothing;
import com.bit101.components.NumericStepper;
import com.bit101.components.VBox;
//import de.polygonal.math.PM_PRNG;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.DisplayObject;
import flash.display.Graphics;
import flash.display.GraphicsPath;
import flash.display.GraphicsPathWinding;
import flash.display.IGraphicsData;
import flash.display.Loader;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.IEventDispatcher;
import flash.events.KeyboardEvent;
import flash.events.MouseEvent;
import flash.geom.Rectangle;
import flash.net.URLRequest;
import flash.system.LoaderContext;
import flash.text.TextField;
import flash.ui.Keyboard;
import flash.utils.Dictionary;
//import terraingen.island.mapgen2;
[SWF(width = "465", height = "465", frameRate = "30", backgroundColor = "#ffffff")]
public class WonderFLIsles extends Sprite
{
public static var LATE_LEAF:Boolean = false;
public var THRESHOLD:Number = LATE_LEAF ? .35 : .15;
public var COLOR_THRESHOLD:uint = 168;
private var fillRectangleArray:Array;
private var image:Bitmap;
private var imageData:BitmapData;
private var _canvas:Sprite;
public var seed:uint;
private var locField:TextField;
private var stepperX:NumericStepper;
private var stepperY:NumericStepper;
private var rootNode:KDNode;
private var prng:PM_PRNG;
private var seededNodeDict:Dictionary = new Dictionary();
private const OFFSETS:Vector.<int> = createOffsetTable();
private static function createOffsetTable():Vector.<int> {
var vec:Vector.<int> = new Vector.<int>(8, true);
var len:int = vec.length;
var count:int = 0;
for (var i:int = 1; i < len; i++) {
var totalPerLevel:int = (1 << (i-1));
totalPerLevel *= totalPerLevel;
vec[i] = count += totalPerLevel;
}
return vec;
}
public function WonderFLIsles():void
{
prng = new PM_PRNG();
loadComplete();
init();
if (stage) {
initStage();
}
else addEventListener(Event.ADDED_TO_STAGE, initStage);
}
private function initStage(e:Event=null):void
{
if (e != null) (e.currentTarget as IEventDispatcher).removeEventListener(e.type, initStage);
stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown, false, 0, true);
locField = new TextField();
locField.autoSize = "left";
locField.y = 64;
locField.multiline = true;
locField.height = 32;
addChild(locField);
var length:int = Math.sqrt(PM_PRNG.MAX);
vBox = new VBox(this, 0, 100);
stepperX = new NumericStepper(vBox, 0, 0, onStepperChange);
stepperY = new NumericStepper(vBox, 0, 0, onStepperChange);
stepperX.minimum = -length * .5;
stepperY.minimum = -length * .5;
stepperX.maximum = length * .5;
stepperY.maximum = length * .5;
updateLocField();
hitAreas = new Sprite();
hitAreas.addEventListener(MouseEvent.CLICK, onHitAreaClick);
hitAreas.x = _canvas.x;
hitAreas.y = _canvas.y;
cont.addChild(hitAreas);
renderTree();
}
private var foundLevel:int;
private function findNode(x:Number, y:Number):KDNode {
si = 1;
var curLevel:int;
searchStack[0] = rootNode;
searchStackLevels[0] = 0;
var node:KDNode = null;
while (si > 0) {
node = searchStack[--si];
curLevel = searchStackLevels[si];
if ( (node.flags & 1) && !(x < node.boundMinX || x > node.boundMaxX || y < node.boundMinY || y > node.boundMaxY) ) {
foundLevel = curLevel;
return node;
}
if (node.positive && (node.flags & KDNode.FLAG_SLAVE) == 0) {
searchStack[si] = node.positive;
searchStackLevels[si] = curLevel + (node.splitDownLevel() ? 1 : 0);
si++;
}
if (node.negative) {
searchStack[si] = node.negative;
searchStackLevels[si] = curLevel + (node.splitDownLevel() ? 1 : 0);
si++;
}
}
return null;
}
private function onHitAreaClick(e:MouseEvent):void
{
var node:KDNode = findNode(e.localX, e.localY);
if (node == null) return;
_canvas.graphics.beginFill(0x0000CC, 1);
_canvas.graphics.drawRect(node.boundMinX, node.boundMinY, (node.boundMaxX - node.boundMinX), (node.boundMaxY - node.boundMinY));
if (node.isSeeded()) {
if (_mapGen && _mapGen.parent) {
removeChild(_mapGen);
}
vBox.mouseChildren = false;
vBox.alpha = .5;
hitAreas.mouseChildren = false;
hitAreas.mouseEnabled = false;
mapgen2.PREVIEW_SIZE = getShortSide(foundLevel);
mapgen2.SIZE = 1024;
mapgen2.islandSeedInitial = node.seed+"-1";
_mapGen = new mapgen2();
//_mapGen.visible = false;
_mapGen.mouseChildren = false;
_mapGen.mouseEnabled = false;
_mapGen.addEventListener(mapgen2.COMPLETED, onMapGenCompleted);
addChild(_mapGen);
_mapGen.x = node.boundMinX + (node.isRectangle() === 1 ? node.offset : 0);
_mapGen.y = node.boundMinY + (node.isRectangle() === 2 ? node.offset : 0);
_mapGen.scaleX = .25;
_mapGen.scaleY = .25;
}
}
private function onMapGenCompleted(e:Event):void
{
_mapGen.removeEventListener(e.type, onMapGenCompleted);
var scaler:Number = 4;
var child:Bitmap = hitAreas.addChild( _mapGen.getPreviewBmp(mapgen2.PREVIEW_SIZE * scaler) ) as Bitmap;
previewBmps.push( child.bitmapData);
child.x = _mapGen.x;
child.y = _mapGen.y;
child.scaleX = 1/scaler;
child.scaleY = 1/scaler;
removeChild(_mapGen);
vBox.alpha = 1;
vBox.mouseChildren = true;
hitAreas.mouseChildren = true;
hitAreas.mouseEnabled = true;
_mapGen = null;
}
private var _mapGen:mapgen2;
private function onStepperChange(e:Event):void
{
if (e.currentTarget === stepperX) {
init(stepperX.value, ty);
}
else {
init(tx, stepperY.value);
}
updateLocField();
}
private function onKeyDown(e:KeyboardEvent):void
{
if (!vBox.mouseChildren) return;
var kc:uint = e.keyCode;
if (kc === Keyboard.UP ) {
init(tx, ty - 1);
updateLocField();
}
else if (kc === Keyboard.DOWN) {
init(tx, ty + 1);
updateLocField();
}
else if (kc === Keyboard.LEFT) {
init(tx - 1, ty);
updateLocField();
}
else if (kc === Keyboard.RIGHT) {
init(tx + 1, ty);
updateLocField();
}
}
private function updateLocField():void
{
locField.text = "(" + tx + ", " + ty + ")\n"+seed;
stepperX.value = tx;
stepperY.value = ty;
}
public function init(setX:Number = 0, setY:Number=0 ):void
{
seededNodeDict = new Dictionary();
var p:RectanglePiece = new RectanglePiece();
p.x0 = 0;
p.y0 = 0;
p.x1 = imageData.width;
p.y1 = imageData.height;
p.c = 0;
rootNode = setupNode(p);
fillRectangleArray = new Array(p);
tx = setX;
ty = setY;
var max:int = PM_PRNG.MAX;
var sqDim:int = Math.sqrt(max);
var radius:int = sqDim * .5;
seed = ( (ty +radius)*sqDim + tx+radius);
if (seed == 0) seed = 1;
prng.setSeed( seed);
updateLores();
_canvas.graphics.clear();
while (onEnterFrame()) { };
cleanupTree();
if (locField) renderTree();
}
private function cleanupTree():void
{
var nodeIndex:int;
var mult:Number;
var curLevel:int;
var node:KDNode;
si = 1;
searchStack[0] = rootNode;
searchStackLevels[0] = 0;
while (si > 0) {
node = searchStack[--si];
curLevel = searchStackLevels[si];
var shortSide:Number = getShortSide(curLevel);
if (node.flags & 1) {
node.positive = null;
node.negative = null;
mult = (1 /shortSide );
nodeIndex = OFFSETS[curLevel] + (node.boundMinY * mult) * (1 << curLevel) + (node.boundMinX * mult);
seededNodeDict[ nodeIndex ] = node;
seededNodeDict[node] = curLevel +"|"+nodeIndex+"|"+node.boundMinY+"|"+node.boundMinX + "| "+getShortSide(curLevel);
continue;
}
if (node.positive ) {
searchStack[si] = node.positive;
searchStackLevels[si] = curLevel + (node.splitDownLevel() ? 1 : 0);
si++;
}
if (node.negative) {
searchStack[si] = node.negative;
searchStackLevels[si] = curLevel + (node.splitDownLevel() ? 1 : 0);
si++;
}
}
si = 1;
searchStack[0] = rootNode;
searchStackLevels[0] = 0;
var masterOff:int;
var slaveCount:int;
while (si > 0) {
node = searchStack[--si];
curLevel = searchStackLevels[si];
shortSide = getShortSide(curLevel);
if (node.flags & 1) {
mult = (1 / shortSide);
nodeIndex = OFFSETS[curLevel] + (node.boundMinY * mult) * (1 << curLevel) + (node.boundMinX * mult);
var off:int;
var master:KDNode;
var masterNodeIndex:int;
var reachEnd:Boolean;
var slave:KDNode;
off = 0;
slaveCount = 0;
master = null;
reachEnd = false;
while (true) {
++off;
reachEnd = node.boundMinX * mult - off < 0;
nodeIndex = !reachEnd ? OFFSETS[curLevel] + (node.boundMinY * mult) * (1 << curLevel) + (node.boundMinX * mult) - off : -1;
if (nodeIndex != -1 && seededNodeDict[nodeIndex]) {
master = seededNodeDict[nodeIndex];
masterNodeIndex = nodeIndex;
masterOff = off;
}
else break;
}
if (master == null) off = 0;
else off = masterOff;
if (reachEnd) off--;
while (--off > -1) {
nodeIndex = OFFSETS[curLevel] + (node.boundMinY * mult) * (1 << curLevel) + (node.boundMinX * mult) - off;
slave = seededNodeDict[nodeIndex];
if (master === slave) {
continue;
}
slave.flags |= KDNode.FLAG_SLAVE;
slave.flags &= ~1;
slave.positive = master;
master.boundMaxX += shortSide;
slaveCount++;
delete seededNodeDict[nodeIndex];
}
if (slaveCount > 0) {
master.offset = prng.nextDoubleRange(0, slaveCount * shortSide);
}
if (master!=null) continue;
off = 0;
master = null;
slaveCount = 0;
reachEnd = false;
while (true) {
++off;
reachEnd = node.boundMinY * mult - off < 0;
nodeIndex = !reachEnd ? OFFSETS[curLevel] + (node.boundMinY * mult - off) * (1 << curLevel) + (node.boundMinX * mult) : -1;
if (nodeIndex != -1 && seededNodeDict[nodeIndex]) {
master = seededNodeDict[nodeIndex];
masterNodeIndex = nodeIndex;
masterOff = off;
}
else break;
}
if (master == null) off = 0;
else off = masterOff;
if (reachEnd) off--;
while (--off > -1) {
nodeIndex = OFFSETS[curLevel] + (node.boundMinY*mult- off) * (1 << curLevel) + (node.boundMinX * mult);
slave = seededNodeDict[nodeIndex];
if (master === slave) {
continue;
}
slave.flags |= KDNode.FLAG_SLAVE;
slave.flags &= ~1;
slave.positive = master;
master.boundMaxY += shortSide;
slaveCount++;
delete seededNodeDict[nodeIndex];
}
if (slaveCount > 0) {
master.offset = prng.nextDoubleRange(0, slaveCount * shortSide);
}
continue;
}
if (node.positive && ((node.flags & KDNode.FLAG_SLAVE)==0) ) {
searchStack[si] = node.positive;
searchStackLevels[si] = curLevel + (node.splitDownLevel() ? 1 : 0);
si++;
}
if (node.negative) {
searchStack[si] = node.negative;
searchStackLevels[si] = curLevel + (node.splitDownLevel() ? 1 : 0);
si++;
}
}
}
private static const BM_SIZE_SMALL:Number = 64;
private var bitmapData:BitmapData = new BitmapData(BM_SIZE_SMALL, BM_SIZE_SMALL, false, 0);
public var tx:Number = 0;
public var ty:Number = 0;
private var postFunction:Function = Smoothing.linear;
private var noiseFunction:Function = Perlin.fractalNoise;
private var phase:Number = 0;
private var brightness:Number = 0;
private var contrast:Number = 3.29;
private var scaler:Number = 128;
private var _noiseBmp:Bitmap;
public function updateLores():void {
var x:Number;
var y:Number;
bitmapData.lock();
for (y = 0; y < BM_SIZE_SMALL; y++)
for (x = 0; x < BM_SIZE_SMALL; x++) drawNoise(x, y, 4);
bitmapData.unlock();
}
public function drawNoise(x:Number, y:Number, r:Number):void {
var i:Number = (x * r - BM_SIZE_SMALL * 0.5) / scaler + tx*r;
var j:Number = (y * r - BM_SIZE_SMALL * 0.5) / scaler + ty*r;
var n:Number = int( 255 * MathUtils.clamp(postFunction (MathUtils.contrast (MathUtils.brightness( noiseFunction(i, j, phase), brightness), contrast) ) ));
bitmapData.setPixel(x, y, n + (n << 8) + (n << 16));
}
public function loadComplete():void
{
Perlin.setParams( {octaves:4, H:0.64, lacunarity:2 } );
imageData = bitmapData;
_canvas = new Sprite;
_noiseBmp = new Bitmap(bitmapData);
cont = new Sprite();
addChild(cont);
cont.scaleX = 4;
cont.scaleY = 4;
addChild(_noiseBmp);
cont.addChild(_canvas);
_canvas.x +=(BM_SIZE_SMALL+32) / 4;
}
private var searchStack:Vector.<KDNode> = new Vector.<KDNode>();
private var searchStackLevels:Vector.<int> = new Vector.<int>();
private var si:int = 0;
private var hitAreas:Sprite;
private var cont:Sprite;
private var vBox:VBox;
private var previewBmps:Vector.<BitmapData> = new Vector.<BitmapData>();
private function disposePreviewBmps():void {
var i:int = previewBmps.length;
while (--i > -1) {
previewBmps[i].dispose();
}
previewBmps.length = 0;
}
private function renderTree():void {
si = 1;
searchStack[0] = rootNode;
var graphics:Graphics =_canvas.graphics;
graphics.clear();
hitAreas.removeChildren();
disposePreviewBmps();
while (si > 0) {
var node:KDNode = searchStack[--si];
if (node.positive && !(node.flags & KDNode.FLAG_SLAVE)) searchStack[si++] = node.positive;
if (node.negative) searchStack[si++] = node.negative;
graphics.beginFill( node.flags & 1 ? 0x00CCFF : 0x0000CC );
graphics.drawRect(node.boundMinX, node.boundMinY, (node.boundMaxX - node.boundMinX), (node.boundMaxY - node.boundMinY));
hitAreas.addChild( new HitArea(node, node.boundMinX, node.boundMinY, (node.boundMaxX - node.boundMinX), (node.boundMaxY - node.boundMinY), node.flags & 1) );
}
}
private function getShortSide(level:int):int {
return BM_SIZE_SMALL / (1 << level);
}
private function onEnterFrame(e:Event=null):Boolean
{
if (fillRectangleArray.length < 1) {
removeEventListener(Event.ENTER_FRAME, onEnterFrame);
return false;
}else {
var rect:RectanglePiece = fillRectangleArray.shift();
var cArray:Array = deviationLogic(rect.x0, rect.y0, rect.x1, rect.y1);
rect.c = cArray[0];
var halfWidth:Number = (rect.x1 - rect.x0) *.5;
var halfHeight:Number = (rect.y1 - rect.y0) *.5;
if (rect.c > THRESHOLD && (halfWidth > 1 || halfHeight > 1)) {
var seeded:Boolean = (cArray[1] & 0xFF) > COLOR_THRESHOLD;
if (seeded) {
var mult:Number = (1 / getShortSide(rect.level));
var nodeIndex:int = OFFSETS[rect.level] + rect.y0*mult*(1<<rect.level) + rect.x0 *mult;
var isRect:int = rect.node.isRectangle();
if (isRect == 1) seededNodeDict[nodeIndex + 1] = rect.node;
var seededParent:RectanglePiece = LATE_LEAF ? rect.findSeededParent() : null;
if (seededParent) seededParent.node.transferSeedTo( rect.node );
else rect.node.setSeed( prng.nextInt() );
rect.node.offset = isRect === 0 ? 0 : isRect === 1 ? prng.nextDoubleRange(0, (rect.node.boundMaxX - rect.node.boundMinX)*.5 ): prng.nextDoubleRange(0,(rect.node.boundMaxY - rect.node.boundMinY)*.5);
}
else {
rect.node.flags &= ~1;
}
rect.node.flags |= 4;
var rect0:RectanglePiece = new RectanglePiece();
var rect1:RectanglePiece = new RectanglePiece();
if (halfWidth > halfHeight) {
rect.node.vertical = false;
rect0.x0 = rect.x0;
rect0.y0 = rect.y0;
rect0.x1 = rect.x0+halfWidth;
rect0.y1 = rect.y1;
fillRectangleArray.push(rect0);
rect1.x0 = rect.x0+halfWidth;
rect1.y0 = rect.y0;
rect1.x1 = rect.x1;
rect1.y1 = rect.y1;
fillRectangleArray.push(rect1);
}else {
rect.node.vertical = true;
rect0.x0 = rect.x0;
rect0.y0 = rect.y0;
rect0.x1 = rect.x1;
rect0.y1 = rect.y0+halfHeight;
fillRectangleArray.push(rect0);
rect1.x0 = rect.x0;
rect1.y0 = rect.y0+halfHeight;
rect1.x1 = rect.x1;
rect1.y1 = rect.y1;
fillRectangleArray.push(rect1);
}
var node0:KDNode = setupNode(rect0);
var node1:KDNode = setupNode(rect1);
rect0.level = rect.node.splitDownLevel() ? rect.level + 1 : rect.level;
rect1.level = rect0.level;
if (LATE_LEAF || !rect.node.isSeeded() ) {
rect0.parent = rect;
rect1.parent = rect;
rect.node.positive = node0;
rect.node.negative = node1;
}
}
return true;
}
return false;
}
private function setupNode(p:RectanglePiece):KDNode {
var node:KDNode;
node = new KDNode();
p.node = node;
node.boundMinX = p.x0;
node.boundMinY = p.y0;
node.boundMaxX = p.x1;
node.boundMaxY = p.y1;
return node;
}
private function deviationLogic(x0:Number,y0:Number,x1:Number,y1:Number):Array {
var rgb:uint = 0;
var r:uint = 0;
var g:uint = 0;
var b:uint = 0;
var hsb:Array = new Array();
var bArray:Array = new Array();
var br:Number = 0;
var av:Number = 0;
for (var i:int = x0; i < x1;i++ ) {
for (var j:int = y0; j < y1; j++ ) {
rgb = imageData.getPixel(i, j);
r += (rgb >> 16) & 255;
g += (rgb >> 8) & 255;
b += rgb & 255;
hsb = uintRGBtoHSB(rgb);
br += hsb[2];
bArray.push(hsb[2]);
}
}
av = br / bArray.length;
r = r / bArray.length;
g = g / bArray.length;
b = b / bArray.length;
rgb = (r << 16) | (g << 8) | (b << 0);
br = 0;
for (i = 0; i < bArray.length; i++ ) {
br += (bArray[i] - av) *(bArray[i] - av);
}
return [Math.sqrt(br / bArray.length),rgb];
}
private function uintRGBtoHSB(rgb:uint):Array {
var r:uint = (rgb >> 16) & 255;
var g:uint = (rgb >> 8) & 255;
var b:uint = rgb & 255;
return RGBtoHSB(r, g, b);
}
private function RGBtoHSB(r:int, g:int, b:int):Array {
var cmax:Number = Math.max(r, g, b);
var cmin:Number = Math.min(r, g, b);
var brightness:Number = cmax / 255.0;
var hue:Number = 0;
var saturation:Number = (cmax != 0) ? (cmax - cmin) / cmax : 0;
if (saturation != 0) {
var redc:Number = (cmax - r) / (cmax - cmin);
var greenc:Number = (cmax - g) / (cmax - cmin);
var bluec:Number = (cmax - b) / (cmax - cmin);
if (r == cmax) {
hue = bluec - greenc;
} else if (g == cmax) {
hue = 2.0 + redc - bluec;
} else {
hue = 4.0 + greenc - redc;
}
hue = hue / 6.0;
if (hue < 0) {
hue = hue + 1.0;
}
}
return [hue, saturation, brightness];
}
}
}
import flash.display.Sprite;
class RectanglePiece
{
public var x0:Number;
public var y0:Number;
public var x1:Number;
public var y1:Number;
public var c:Number;
public var node:KDNode;
public var parent:RectanglePiece;
public var level:int;
public function RectanglePiece()
{
this.x0 = 0;
this.y0 = 0;
this.x1 = 0;
this.x1 = 0;
this.c = 0;
this.level = 0;
}
public function findSeededParent():RectanglePiece {
var p:RectanglePiece = parent;
while (p != null) {
if (p.node.flags & 1) return p;
p = p.parent;
}
return null;
}
}
class KDNode
{
public var positive:KDNode;
public var negative:KDNode;
public var boundMinX:Number;
public var boundMaxX:Number;
public var boundMinY:Number;
public var boundMaxY:Number;
public var seed:uint;
public var flags:int;
public static const FLAG_SEEDED:int = 1;
public static const FLAG_VERTICAL:int = 2;
public static const FLAG_CONSIDERSEED:int = 4;
public static const FLAG_SLAVE:int = 8;
public var offset:int;
public function setSeed(val:uint):void {
flags |= FLAG_SEEDED;
seed = val;
}
public function isSeeded():Boolean {
return flags & FLAG_SEEDED;
}
public function get vertical():Boolean {
return flags & FLAG_VERTICAL;
}
public function set vertical(val:Boolean):void {
if (val) flags |= FLAG_VERTICAL
else flags &= ~FLAG_VERTICAL;
}
public function getMeasuredShortSide():Number {
return isRectangle() === 1 ? boundMaxY - boundMinY : boundMaxX - boundMinX;
}
public function splitDownLevel():Boolean {
return flags & FLAG_VERTICAL;
}
public function isRectangle():int {
return boundMaxY - boundMinY == boundMaxX - boundMinX ? 0 : boundMaxY - boundMinY < boundMaxX - boundMinX ? 1 : 2;
}
public function KDNode() {
flags = 0;
offset = 0;
}
public function transferSeedTo(node:KDNode):uint
{
node.setSeed(seed);
flags &= ~FLAG_SEEDED;
flags &= ~FLAG_CONSIDERSEED;
return seed;
}
}
class HitArea extends Sprite {
public var node:KDNode;
public function HitArea(node:KDNode, x:Number, y:Number, width:Number, height:Number, buttonMode:Boolean=true) {
this.node = node;
graphics.beginFill(0, 0);
graphics.drawRect(x, y, width, height);
this.buttonMode = buttonMode;
}
}//package {
import __AS3__.vec.Vector;
//import com.nodename.geom.LineSegment;
import flash.geom.Point;
internal function visibleLineSegments(edges:Vector.<DEdge>):Vector.<LineSegment>
{
var segments:Vector.<LineSegment> = new Vector.<LineSegment>();
for each (var edge:DEdge in edges)
{
if (edge.visible)
{
var p1:Point = edge.clippedEnds[LR.LEFT];
var p2:Point = edge.clippedEnds[LR.RIGHT];
segments.push(new LineSegment(p1, p2));
}
}
return segments;
}
//}
//package com.nodename.Delaunay
//{
import flash.geom.Point;
//internal
final class Vertex extends Object implements ICoord
{
internal static const VERTEX_AT_INFINITY:Vertex = new Vertex(PrivateConstructorEnforcer, NaN, NaN);
private static var _pool:Vector.<Vertex> = new Vector.<Vertex>();
private static function create(x:Number, y:Number):Vertex
{
if (isNaN(x) || isNaN(y))
{
return VERTEX_AT_INFINITY;
}
if (_pool.length > 0)
{
return _pool.pop().init(x, y);
}
else
{
return new Vertex(PrivateConstructorEnforcer, x, y);
}
}
private static var _nvertices:int = 0;
private var _coord:Point;
public function get coord():Point
{
return _coord;
}
private var _vertexIndex:int;
public function get vertexIndex():int
{
return _vertexIndex;
}
public function Vertex(lock:Class, x:Number, y:Number)
{
if (lock != PrivateConstructorEnforcer)
{
throw new Error("Vertex constructor is private");
}
init(x, y);
}
private function init(x:Number, y:Number):Vertex
{
_coord = new Point(x, y);
return this;
}
public function dispose():void
{
_coord = null;
_pool.push(this);
}
public function setIndex():void
{
_vertexIndex = _nvertices++;
}
public function toString():String
{
return "Vertex (" + _vertexIndex + ")";
}
/**
* This is the only way to make a Vertex
*
* @param halfedge0
* @param halfedge1
* @return
*
*/
public static function intersect(halfedge0:Halfedge, halfedge1:Halfedge):Vertex
{
var edge0:DEdge, edge1:DEdge, edge:DEdge;
var halfedge:Halfedge;
var determinant:Number, intersectionX:Number, intersectionY:Number;
var rightOfSite:Boolean;
edge0 = halfedge0.edge;
edge1 = halfedge1.edge;
if (edge0 == null || edge1 == null)
{
return null;
}
if (edge0.rightSite == edge1.rightSite)
{
return null;
}
determinant = edge0.a * edge1.b - edge0.b * edge1.a;
if (-1.0e-10 < determinant && determinant < 1.0e-10)
{
// the edges are parallel
return null;
}
intersectionX = (edge0.c * edge1.b - edge1.c * edge0.b)/determinant;
intersectionY = (edge1.c * edge0.a - edge0.c * edge1.a)/determinant;
if (Voronoi.compareByYThenX(edge0.rightSite, edge1.rightSite) < 0)
{
halfedge = halfedge0; edge = edge0;
}
else
{
halfedge = halfedge1; edge = edge1;
}
rightOfSite = intersectionX >= edge.rightSite.x;
if ((rightOfSite && halfedge.leftRight == LR.LEFT)
|| (!rightOfSite && halfedge.leftRight == LR.RIGHT))
{
return null;
}
return Vertex.create(intersectionX, intersectionY);
}
public function get x():Number
{
return _coord.x;
}
public function get y():Number
{
return _coord.y;
}
}
//}
// package com.nodename.Delaunay
//{
import flash.geom.Point;
import flash.geom.Rectangle;
//public
final class Site implements ICoord
{
private static var _pool:Vector.<Site> = new Vector.<Site>();
public static function create(p:Point, index:int, weight:Number, color:uint):Site
{
if (_pool.length > 0)
{
return _pool.pop().init(p, index, weight, color);
}
else
{
return new Site(PrivateConstructorEnforcer, p, index, weight, color);
}
}
internal static function sortSites(sites:Vector.<Site>):void
{
sites.sort(Site.compare);
}
/**
* sort sites on y, then x, coord
* also change each site's _siteIndex to match its new position in the list
* so the _siteIndex can be used to identify the site for nearest-neighbor queries
*
* haha "also" - means more than one responsibility...
*
*/
private static function compare(s1:Site, s2:Site):Number
{
var returnValue:int = Voronoi.compareByYThenX(s1, s2);
// swap _siteIndex values if necessary to match new ordering:
var tempIndex:int;
if (returnValue == -1)
{
if (s1._siteIndex > s2._siteIndex)
{
tempIndex = s1._siteIndex;
s1._siteIndex = s2._siteIndex;
s2._siteIndex = tempIndex;
}
}
else if (returnValue == 1)
{
if (s2._siteIndex > s1._siteIndex)
{
tempIndex = s2._siteIndex;
s2._siteIndex = s1._siteIndex;
s1._siteIndex = tempIndex;
}
}
return returnValue;
}
private static const EPSILON:Number = .005;
private static function closeEnough(p0:Point, p1:Point):Boolean
{
return Point.distance(p0, p1) < EPSILON;
}
private var _coord:Point;
public function get coord():Point
{
return _coord;
}
internal var color:uint;
internal var weight:Number;
private var _siteIndex:uint;
// the edges that define this Site's Voronoi region:
private var _edges:Vector.<DEdge>;
internal function get edges():Vector.<DEdge>
{
return _edges;
}
// which end of each edge hooks up with the previous edge in _edges:
private var _edgeOrientations:Vector.<LR>;
// ordered list of points that define the region clipped to bounds:
private var _region:Vector.<Point>;
public function Site(lock:Class, p:Point, index:int, weight:Number, color:uint)
{
if (lock != PrivateConstructorEnforcer)
{
throw new Error("Site constructor is private");
}
init(p, index, weight, color);
}
private function init(p:Point, index:int, weight:Number, color:uint):Site
{
_coord = p;
_siteIndex = index;
this.weight = weight;
this.color = color;
_edges = new Vector.<DEdge>();
_region = null;
return this;
}
public function toString():String
{
return "Site " + _siteIndex + ": " + coord;
}
private function move(p:Point):void
{
clear();
_coord = p;
}
public function dispose():void
{
_coord = null;
clear();
_pool.push(this);
}
private function clear():void
{
if (_edges)
{
_edges.length = 0;
_edges = null;
}
if (_edgeOrientations)
{
_edgeOrientations.length = 0;
_edgeOrientations = null;
}
if (_region)
{
_region.length = 0;
_region = null;
}
}
internal function addEdge(edge:DEdge):void
{
_edges.push(edge);
}
internal function nearestEdge():DEdge
{
_edges.sort(DEdge.compareSitesDistances);
return _edges[0];
}
internal function neighborSites():Vector.<Site>
{
if (_edges == null || _edges.length == 0)
{
return new Vector.<Site>();
}
if (_edgeOrientations == null)
{
reorderEdges();
}
var list:Vector.<Site> = new Vector.<Site>();
var edge:DEdge;
for each (edge in _edges)
{
list.push(neighborSite(edge));
}
return list;
}
private function neighborSite(edge:DEdge):Site
{
if (this == edge.leftSite)
{
return edge.rightSite;
}
if (this == edge.rightSite)
{
return edge.leftSite;
}
return null;
}
internal function region(clippingBounds:Rectangle):Vector.<Point>
{
if (_edges == null || _edges.length == 0)
{
return new Vector.<Point>();
}
if (_edgeOrientations == null)
{
reorderEdges();
_region = clipToBounds(clippingBounds);
if ((new Polygon(_region)).winding() == Winding.CLOCKWISE)
{
_region = _region.reverse();
}
}
return _region;
}
private function reorderEdges():void
{
//trace("_edges:", _edges);
var reorderer:EdgeReorderer = new EdgeReorderer(_edges, Vertex);
_edges = reorderer.edges;
//trace("reordered:", _edges);
_edgeOrientations = reorderer.edgeOrientations;
reorderer.dispose();
}
private function clipToBounds(bounds:Rectangle):Vector.<Point>
{
var points:Vector.<Point> = new Vector.<Point>;
var n:int = _edges.length;
var i:int = 0;
var edge:DEdge;
while (i < n && ((_edges[i] as DEdge).visible == false))
{
++i;
}
if (i == n)
{
// no edges visible
return new Vector.<Point>();
}
edge = _edges[i];
var orientation:LR = _edgeOrientations[i];
points.push(edge.clippedEnds[orientation]);
points.push(edge.clippedEnds[LR.other(orientation)]);
for (var j:int = i + 1; j < n; ++j)
{
edge = _edges[j];
if (edge.visible == false)
{
continue;
}
connect(points, j, bounds);
}
// close up the polygon by adding another corner point of the bounds if needed:
connect(points, i, bounds, true);
return points;
}
private function connect(points:Vector.<Point>, j:int, bounds:Rectangle, closingUp:Boolean = false):void
{
var rightPoint:Point = points[points.length - 1];
var newEdge:DEdge = _edges[j] as DEdge;
var newOrientation:LR = _edgeOrientations[j];
// the point that must be connected to rightPoint:
var newPoint:Point = newEdge.clippedEnds[newOrientation];
if (!closeEnough(rightPoint, newPoint))
{
// The points do not coincide, so they must have been clipped at the bounds;
// see if they are on the same border of the bounds:
if (rightPoint.x != newPoint.x
&& rightPoint.y != newPoint.y)
{
// They are on different borders of the bounds;
// insert one or two corners of bounds as needed to hook them up:
// (NOTE this will not be correct if the region should take up more than
// half of the bounds rect, for then we will have gone the wrong way
// around the bounds and included the smaller part rather than the larger)
var rightCheck:int = BoundsCheck.check(rightPoint, bounds);
var newCheck:int = BoundsCheck.check(newPoint, bounds);
var px:Number, py:Number;
if (rightCheck & BoundsCheck.RIGHT)
{
px = bounds.right;
if (newCheck & BoundsCheck.BOTTOM)
{
py = bounds.bottom;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.TOP)
{
py = bounds.top;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.LEFT)
{
if (rightPoint.y - bounds.y + newPoint.y - bounds.y < bounds.height)
{
py = bounds.top;
}
else
{
py = bounds.bottom;
}
points.push(new Point(px, py));
points.push(new Point(bounds.left, py));
}
}
else if (rightCheck & BoundsCheck.LEFT)
{
px = bounds.left;
if (newCheck & BoundsCheck.BOTTOM)
{
py = bounds.bottom;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.TOP)
{
py = bounds.top;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.RIGHT)
{
if (rightPoint.y - bounds.y + newPoint.y - bounds.y < bounds.height)
{
py = bounds.top;
}
else
{
py = bounds.bottom;
}
points.push(new Point(px, py));
points.push(new Point(bounds.right, py));
}
}
else if (rightCheck & BoundsCheck.TOP)
{
py = bounds.top;
if (newCheck & BoundsCheck.RIGHT)
{
px = bounds.right;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.LEFT)
{
px = bounds.left;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.BOTTOM)
{
if (rightPoint.x - bounds.x + newPoint.x - bounds.x < bounds.width)
{
px = bounds.left;
}
else
{
px = bounds.right;
}
points.push(new Point(px, py));
points.push(new Point(px, bounds.bottom));
}
}
else if (rightCheck & BoundsCheck.BOTTOM)
{
py = bounds.bottom;
if (newCheck & BoundsCheck.RIGHT)
{
px = bounds.right;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.LEFT)
{
px = bounds.left;
points.push(new Point(px, py));
}
else if (newCheck & BoundsCheck.TOP)
{
if (rightPoint.x - bounds.x + newPoint.x - bounds.x < bounds.width)
{
px = bounds.left;
}
else
{
px = bounds.right;
}
points.push(new Point(px, py));
points.push(new Point(px, bounds.top));
}
}
}
if (closingUp)
{
// newEdge's ends have already been added
return;
}
points.push(newPoint);
}
var newRightPoint:Point = newEdge.clippedEnds[LR.other(newOrientation)];
if (!closeEnough(points[0], newRightPoint))
{
points.push(newRightPoint);
}
}
internal function get x():Number
{
return _coord.x;
}
internal function get y():Number
{
return _coord.y;
}
internal function dist(p:ICoord):Number
{
return Point.distance(p.coord, this._coord);
}
}
//}
/*public*/ class PrivateConstructorEnforcer {}//package {
//import com.nodename.geom.Circle;
//import com.nodename.utils.IDisposable;
import flash.display.BitmapData;
import flash.geom.Point;
import flash.geom.Rectangle;
internal final class SiteList implements IDisposable
{
private var _sites:Vector.<Site>;
private var _currentIndex:uint;
private var _sorted:Boolean;
public function SiteList()
{
_sites = new Vector.<Site>();
_sorted = false;
}
public function dispose():void
{
if (_sites)
{
for each (var site:Site in _sites)
{
site.dispose();
}
_sites.length = 0;
_sites = null;
}
}
public function push(site:Site):uint
{
_sorted = false;
return _sites.push(site);
}
public function get length():uint
{
return _sites.length;
}
public function next():Site
{
if (_sorted == false)
{
throw new Error("SiteList::next(): sites have not been sorted");
}
if (_currentIndex < _sites.length)
{
return _sites[_currentIndex++];
}
else
{
return null;
}
}
internal function getSitesBounds():Rectangle
{
if (_sorted == false)
{
Site.sortSites(_sites);
_currentIndex = 0;
_sorted = true;
}
var xmin:Number, xmax:Number, ymin:Number, ymax:Number;
if (_sites.length == 0)
{
return new Rectangle(0, 0, 0, 0);
}
xmin = Number.MAX_VALUE;
xmax = Number.MIN_VALUE;
for each (var site:Site in _sites)
{
if (site.x < xmin)
{
xmin = site.x;
}
if (site.x > xmax)
{
xmax = site.x;
}
}
ymin = _sites[0].y;
ymax = _sites[_sites.length - 1].y;
return new Rectangle(xmin, ymin, xmax - xmin, ymax - ymin);
}
public function siteColors(referenceImage:BitmapData = null):Vector.<uint>
{
var colors:Vector.<uint> = new Vector.<uint>();
for each (var site:Site in _sites)
{
colors.push(referenceImage ? referenceImage.getPixel(site.x, site.y) : site.color);
}
return colors;
}
public function siteCoords():Vector.<Point>
{
var coords:Vector.<Point> = new Vector.<Point>();
for each (var site:Site in _sites)
{
coords.push(site.coord);
}
return coords;
}
public function circles():Vector.<Circle>
{
var circles:Vector.<Circle> = new Vector.<Circle>();
for each (var site:Site in _sites)
{
var radius:Number = 0;
var nearestEdge:DEdge = site.nearestEdge();
!nearestEdge.isPartOfConvexHull() && (radius = nearestEdge.sitesDistance() * 0.5);
circles.push(new Circle(site.x, site.y, radius));
}
return circles;
}
public function regions(plotBounds:Rectangle):Vector.<Vector.<Point>>
{
var regions:Vector.<Vector.<Point>> = new Vector.<Vector.<Point>>();
for each (var site:Site in _sites)
{
regions.push(site.region(plotBounds));
}
return regions;
}
public function nearestSitePoint(proximityMap:BitmapData, x:Number, y:Number):Point
{
var index:uint = proximityMap.getPixel(x, y);
if (index > _sites.length - 1)
{
return null;
}
return _sites[index].coord;
}
}
//}//package {
//import com.nodename.geom.Polygon;
//import com.nodename.geom.Winding;
import flash.geom.Point;
import flash.geom.Rectangle;
/*public*/ class BoundsCheck
{
public static const TOP:int = 1;
public static const BOTTOM:int = 2;
public static const LEFT:int = 4;
public static const RIGHT:int = 8;
public static function check(point:Point, bounds:Rectangle):int
{
var value:int = 0;
if (point.x == bounds.left)
{
value |= LEFT;
}
if (point.x == bounds.right)
{
value |= RIGHT;
}
if (point.y == bounds.top)
{
value |= TOP;
}
if (point.y == bounds.bottom)
{
value |= BOTTOM;
}
return value;
}
public function BoundsCheck()
{
throw new Error("BoundsCheck constructor unused");
}
}//package {
import flash.geom.Point;
import flash.display.BitmapData;
internal function selectNonIntersectingEdges(keepOutMask:BitmapData, edgesToTest:Vector.<DEdge>):Vector.<DEdge>
{
if (keepOutMask == null)
{
return edgesToTest;
}
var zeroPoint:Point = new Point();
return edgesToTest.filter(myTest);
function myTest(edge:DEdge, index:int, vector:Vector.<DEdge>):Boolean
{
var delaunayLineBmp:BitmapData = edge.makeDelaunayLineBmp();
var notIntersecting:Boolean = !(keepOutMask.hitTest(zeroPoint, 1, delaunayLineBmp, zeroPoint, 1));
delaunayLineBmp.dispose();
return notIntersecting;
}
}
//}
//package {
import __AS3__.vec.Vector;
import flash.geom.Point;
internal function selectEdgesForSitePoint(coord:Point, edgesToTest:Vector.<DEdge>):Vector.<DEdge>
{
return edgesToTest.filter(myTest);
function myTest(edge:DEdge, index:int, vector:Vector.<DEdge>):Boolean
{
return ((edge.leftSite && edge.leftSite.coord == coord)
|| (edge.rightSite && edge.rightSite.coord == coord));
}
}
//}//package {
import __AS3__.vec.Vector;
import flash.utils.Dictionary;
//import com.nodename.geom.LineSegment;
/*public*/ class Node
{
public static var pool:Vector.<Node> = new Vector.<Node>();
public var parent:Node;
public var treeSize:int;
public function Node() {}
}
//package {
import flash.geom.Point;
internal interface ICoord
{
function get coord():Point;
}
//}//package {
import flash.geom.Point;
internal final class HalfedgePriorityQueue
{
private var _hash:Vector.<Halfedge>;
private var _count:int;
private var _minBucket:int;
private var _hashsize:int;
private var _ymin:Number;
private var _deltay:Number;
public function HalfedgePriorityQueue(ymin:Number, deltay:Number, sqrt_nsites:int)
{
_ymin = ymin;
_deltay = deltay;
_hashsize = 4 * sqrt_nsites;
initialize();
}
public function dispose():void
{
for (var i:int = 0; i < _hashsize; ++i)
{
_hash[i].dispose();
_hash[i] = null;
}
_hash = null;
}
private function initialize():void
{
var i:int;
_count = 0;
_minBucket = 0;
_hash = new Vector.<Halfedge>(_hashsize);
for (i = 0; i < _hashsize; ++i)
{
_hash[i] = Halfedge.createDummy();
_hash[i].nextInPriorityQueue = null;
}
}
public function insert(halfEdge:Halfedge):void
{
var previous:Halfedge, next:Halfedge;
var insertionBucket:int = bucket(halfEdge);
if (insertionBucket < _minBucket)
{
_minBucket = insertionBucket;
}
previous = _hash[insertionBucket];
while ((next = previous.nextInPriorityQueue) != null
&& (halfEdge.ystar > next.ystar || (halfEdge.ystar == next.ystar && halfEdge.vertex.x > next.vertex.x)))
{
previous = next;
}
halfEdge.nextInPriorityQueue = previous.nextInPriorityQueue;
previous.nextInPriorityQueue = halfEdge;
++_count;
}
public function remove(halfEdge:Halfedge):void
{
var previous:Halfedge;
var removalBucket:int = bucket(halfEdge);
if (halfEdge.vertex != null)
{
previous = _hash[removalBucket];
while (previous.nextInPriorityQueue != halfEdge)
{
previous = previous.nextInPriorityQueue;
}
previous.nextInPriorityQueue = halfEdge.nextInPriorityQueue;
_count--;
halfEdge.vertex = null;
halfEdge.nextInPriorityQueue = null;
halfEdge.dispose();
}
}
private function bucket(halfEdge:Halfedge):int
{
var theBucket:int = (halfEdge.ystar - _ymin)/_deltay * _hashsize;
if (theBucket < 0) theBucket = 0;
if (theBucket >= _hashsize) theBucket = _hashsize - 1;
return theBucket;
}
private function isEmpty(bucket:int):Boolean
{
return (_hash[bucket].nextInPriorityQueue == null);
}
private function adjustMinBucket():void
{
while (_minBucket < _hashsize - 1 && isEmpty(_minBucket))
{
++_minBucket;
}
}
public function empty():Boolean
{
return _count == 0;
}
public function min():Point
{
adjustMinBucket();
var answer:Halfedge = _hash[_minBucket].nextInPriorityQueue;
return new Point(answer.vertex.x, answer.ystar);
}
public function extractMin():Halfedge
{
var answer:Halfedge;
answer = _hash[_minBucket].nextInPriorityQueue;
_hash[_minBucket].nextInPriorityQueue = answer.nextInPriorityQueue;
_count--;
answer.nextInPriorityQueue = null;
return answer;
}
}
//}//package {
import flash.geom.Point;
//package com.nodename.Delaunay
//{
import flash.geom.Point;
//internal
final class Halfedge
{
private static var _pool:Vector.<Halfedge> = new Vector.<Halfedge>();
public static function create(edge:DEdge, lr:LR):Halfedge
{
if (_pool.length > 0)
{
return _pool.pop().init(edge, lr);
}
else
{
return new Halfedge(PrivateConstructorEnforcer, edge, lr);
}
}
public static function createDummy():Halfedge
{
return create(null, null);
}
public var edgeListLeftNeighbor:Halfedge, edgeListRightNeighbor:Halfedge;
public var nextInPriorityQueue:Halfedge;
public var edge:DEdge;
public var leftRight:LR;
public var vertex:Vertex;
// the vertex's y-coordinate in the transformed Voronoi space V*
public var ystar:Number;
public function Halfedge(lock:Class, edge:DEdge = null, lr:LR = null)
{
if (lock != PrivateConstructorEnforcer)
{
throw new Error("Halfedge constructor is private");
}
init(edge, lr);
}
private function init(edge:DEdge, lr:LR):Halfedge
{
this.edge = edge;
leftRight = lr;
nextInPriorityQueue = null;
vertex = null;
return this;
}
public function toString():String
{
return "Halfedge (leftRight: " + leftRight + "; vertex: " + vertex + ")";
}
public function dispose():void
{
if (edgeListLeftNeighbor || edgeListRightNeighbor)
{
// still in EdgeList
return;
}
if (nextInPriorityQueue)
{
// still in PriorityQueue
return;
}
edge = null;
leftRight = null;
vertex = null;
_pool.push(this);
}
public function reallyDispose():void
{
edgeListLeftNeighbor = null;
edgeListRightNeighbor = null;
nextInPriorityQueue = null;
edge = null;
leftRight = null;
vertex = null;
_pool.push(this);
}
internal function isLeftOf(p:Point):Boolean
{
var topSite:Site;
var rightOfSite:Boolean, above:Boolean, fast:Boolean;
var dxp:Number, dyp:Number, dxs:Number, t1:Number, t2:Number, t3:Number, yl:Number;
topSite = edge.rightSite;
rightOfSite = p.x > topSite.x;
if (rightOfSite && this.leftRight == LR.LEFT)
{
return true;
}
if (!rightOfSite && this.leftRight == LR.RIGHT)
{
return false;
}
if (edge.a == 1.0)
{
dyp = p.y - topSite.y;
dxp = p.x - topSite.x;
fast = false;
if ((!rightOfSite && edge.b < 0.0) || (rightOfSite && edge.b >= 0.0) )
{
above = dyp >= edge.b * dxp;
fast = above;
}
else
{
above = p.x + p.y * edge.b > edge.c;
if (edge.b < 0.0)
{
above = !above;
}
if (!above)
{
fast = true;
}
}
if (!fast)
{
dxs = topSite.x - edge.leftSite.x;
above = edge.b * (dxp * dxp - dyp * dyp) <
dxs * dyp * (1.0 + 2.0 * dxp/dxs + edge.b * edge.b);
if (edge.b < 0.0)
{
above = !above;
}
}
}
else /* edge.b == 1.0 */
{
yl = edge.c - edge.a * p.x;
t1 = p.y - yl;
t2 = p.x - topSite.x;
t3 = yl - topSite.y;
above = t1 * t1 > t2 * t2 + t3 * t3;
}
return this.leftRight == LR.LEFT ? above : !above;
}
}
//}
internal final class EdgeReorderer
{
private var _edges:Vector.<DEdge>;
private var _edgeOrientations:Vector.<LR>;
public function get edges():Vector.<DEdge>
{
return _edges;
}
public function get edgeOrientations():Vector.<LR>
{
return _edgeOrientations;
}
public function EdgeReorderer(origEdges:Vector.<DEdge>, criterion:Class)
{
if (criterion != Vertex && criterion != Site)
{
throw new ArgumentError("Edges: criterion must be Vertex or Site");
}
_edges = new Vector.<DEdge>();
_edgeOrientations = new Vector.<LR>();
if (origEdges.length > 0)
{
_edges = reorderEdges(origEdges, criterion);
}
}
public function dispose():void
{
_edges = null;
_edgeOrientations = null;
}
private function reorderEdges(origEdges:Vector.<DEdge>, criterion:Class):Vector.<DEdge>
{
var i:int;
var j:int;
var n:int = origEdges.length;
var edge:DEdge;
var done:Vector.<Boolean> = new Vector.<Boolean>(n, true);
var nDone:int = 0;
for each (var b:Boolean in done)
{
b = false;
}
var newEdges:Vector.<DEdge> = new Vector.<DEdge>();
i = 0;
edge = origEdges[i];
newEdges.push(edge);
_edgeOrientations.push(LR.LEFT);
var firstPoint:ICoord = (criterion == Vertex) ? edge.leftVertex : edge.leftSite;
var lastPoint:ICoord = (criterion == Vertex) ? edge.rightVertex : edge.rightSite;
if (firstPoint == Vertex.VERTEX_AT_INFINITY || lastPoint == Vertex.VERTEX_AT_INFINITY)
{
return new Vector.<DEdge>();
}
done[i] = true;
++nDone;
while (nDone < n)
{
for (i = 1; i < n; ++i)
{
if (done[i])
{
continue;
}
edge = origEdges[i];
var leftPoint:ICoord = (criterion == Vertex) ? edge.leftVertex : edge.leftSite;
var rightPoint:ICoord = (criterion == Vertex) ? edge.rightVertex : edge.rightSite;
if (leftPoint == Vertex.VERTEX_AT_INFINITY || rightPoint == Vertex.VERTEX_AT_INFINITY)
{
return new Vector.<DEdge>();
}
if (leftPoint == lastPoint)
{
lastPoint = rightPoint;
_edgeOrientations.push(LR.LEFT);
newEdges.push(edge);
done[i] = true;
}
else if (rightPoint == firstPoint)
{
firstPoint = leftPoint;
_edgeOrientations.unshift(LR.LEFT);
newEdges.unshift(edge);
done[i] = true;
}
else if (leftPoint == firstPoint)
{
firstPoint = rightPoint;
_edgeOrientations.unshift(LR.RIGHT);
newEdges.unshift(edge);
done[i] = true;
}
else if (rightPoint == lastPoint)
{
lastPoint = leftPoint;
_edgeOrientations.push(LR.RIGHT);
newEdges.push(edge);
done[i] = true;
}
if (done[i])
{
++nDone;
}
}
}
return newEdges;
}
}
//}//package {
//import com.nodename.utils.IDisposable;
import flash.geom.Point;
internal final class EdgeList implements IDisposable
{
private var _deltax:Number;
private var _xmin:Number;
private var _hashsize:int;
private var _hash:Vector.<Halfedge>;
private var _leftEnd:Halfedge;
public function get leftEnd():Halfedge
{
return _leftEnd;
}
private var _rightEnd:Halfedge;
public function get rightEnd():Halfedge
{
return _rightEnd;
}
public function dispose():void
{
var halfEdge:Halfedge = _leftEnd;
var prevHe:Halfedge;
while (halfEdge != _rightEnd)
{
prevHe = halfEdge;
halfEdge = halfEdge.edgeListRightNeighbor;
prevHe.dispose();
}
_leftEnd = null;
_rightEnd.dispose();
_rightEnd = null;
var i:int;
for (i = 0; i < _hashsize; ++i)
{
_hash[i] = null;
}
_hash = null;
}
public function EdgeList(xmin:Number, deltax:Number, sqrt_nsites:int)
{
_xmin = xmin;
_deltax = deltax;
_hashsize = 2 * sqrt_nsites;
var i:int;
_hash = new Vector.<Halfedge>(_hashsize, true);
_leftEnd = Halfedge.createDummy();
_rightEnd = Halfedge.createDummy();
_leftEnd.edgeListLeftNeighbor = null;
_leftEnd.edgeListRightNeighbor = _rightEnd;
_rightEnd.edgeListLeftNeighbor = _leftEnd;
_rightEnd.edgeListRightNeighbor = null;
_hash[0] = _leftEnd;
_hash[_hashsize - 1] = _rightEnd;
}
public function insert(lb:Halfedge, newHalfedge:Halfedge):void
{
newHalfedge.edgeListLeftNeighbor = lb;
newHalfedge.edgeListRightNeighbor = lb.edgeListRightNeighbor;
lb.edgeListRightNeighbor.edgeListLeftNeighbor = newHalfedge;
lb.edgeListRightNeighbor = newHalfedge;
}
public function remove(halfEdge:Halfedge):void
{
halfEdge.edgeListLeftNeighbor.edgeListRightNeighbor = halfEdge.edgeListRightNeighbor;
halfEdge.edgeListRightNeighbor.edgeListLeftNeighbor = halfEdge.edgeListLeftNeighbor;
halfEdge.edge = DEdge.DELETED;
halfEdge.edgeListLeftNeighbor = halfEdge.edgeListRightNeighbor = null;
}
public function edgeListLeftNeighbor(p:Point):Halfedge
{
var i:int, bucket:int;
var halfEdge:Halfedge;
bucket = (p.x - _xmin)/_deltax * _hashsize;
if (bucket < 0)
{
bucket = 0;
}
if (bucket >= _hashsize)
{
bucket = _hashsize - 1;
}
halfEdge = getHash(bucket);
if (halfEdge == null)
{
for (i = 1; true ; ++i)
{
if ((halfEdge = getHash(bucket - i)) != null) break;
if ((halfEdge = getHash(bucket + i)) != null) break;
}
}
if (halfEdge == leftEnd || (halfEdge != rightEnd && halfEdge.isLeftOf(p)))
{
do
{
halfEdge = halfEdge.edgeListRightNeighbor;
}
while (halfEdge != rightEnd && halfEdge.isLeftOf(p));
halfEdge = halfEdge.edgeListLeftNeighbor;
}
else
{
do
{
halfEdge = halfEdge.edgeListLeftNeighbor;
}
while (halfEdge != leftEnd && !halfEdge.isLeftOf(p));
}
if (bucket > 0 && bucket <_hashsize - 1)
{
_hash[bucket] = halfEdge;
}
return halfEdge;
}
private function getHash(b:int):Halfedge
{
var halfEdge:Halfedge;
if (b < 0 || b >= _hashsize)
{
return null;
}
halfEdge = _hash[b];
if (halfEdge != null && halfEdge.edge == DEdge.DELETED)
{
_hash[b] = null;
return null;
}
else
{
return halfEdge;
}
}
}
//}//package {
//import com.nodename.geom.LineSegment;
import flash.display.BitmapData;
import flash.display.CapsStyle;
import flash.display.Graphics;
import flash.display.LineScaleMode;
import flash.display.Sprite;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.utils.Dictionary;
import __AS3__.vec.Vector;
//import com.nodename.geom.LineSegment;
internal function delaunayLinesForEdges(edges:Vector.<DEdge>):Vector.<LineSegment>
{
var segments:Vector.<LineSegment> = new Vector.<LineSegment>();
for each (var edge:DEdge in edges)
{
segments.push(edge.delaunayLine());
}
return segments;
}
//}
//package {
/*public*/ interface IDisposable
{
function dispose():void;
}
//}
//package {
internal class NoiseSuper {
static public var hash:Array = [0xA2,0xA0,0x19,0x3B,0xF8,0xEB,0xAA,0xEE,0xF3,0x1C,0x67,0x28,0x1D,0xED,0x0,0xDE,0x95,0x2E,0xDC,0x3F,0x3A,0x82,0x35,0x4D,0x6C,0xBA,0x36,0xD0,0xF6,0xC,0x79,0x32,0xD1,0x59,0xF4,0x8,0x8B,0x63,0x89,0x2F,0xB8,0xB4,0x97,0x83,0xF2,0x8F,0x18,0xC7,0x51,0x14,0x65,0x87,0x48,0x20,0x42,0xA8,0x80,0xB5,0x40,0x13,0xB2,0x22,0x7E,0x57,
0xBC,0x7F,0x6B,0x9D,0x86,0x4C,0xC8,0xDB,0x7C,0xD5,0x25,0x4E,0x5A,0x55,0x74,0x50,0xCD,0xB3,0x7A,0xBB,0xC3,0xCB,0xB6,0xE2,0xE4,0xEC,0xFD,0x98,0xB,0x96,0xD3,0x9E,0x5C,0xA1,0x64,0xF1,0x81,0x61,0xE1,0xC4,0x24,0x72,0x49,0x8C,0x90,0x4B,0x84,0x34,0x38,0xAB,0x78,0xCA,0x1F,0x1,0xD7,0x93,0x11,0xC1,0x58,0xA9,0x31,0xF9,0x44,0x6D,
0xBF,0x33,0x9C,0x5F,0x9,0x94,0xA3,0x85,0x6,0xC6,0x9A,0x1E,0x7B,0x46,0x15,0x30,0x27,0x2B,0x1B,0x71,0x3C,0x5B,0xD6,0x6F,0x62,0xAC,0x4F,0xC2,0xC0,0xE,0xB1,0x23,0xA7,0xDF,0x47,0xB0,0x77,0x69,0x5,0xE9,0xE6,0xE7,0x76,0x73,0xF,0xFE,0x6E,0x9B,0x56,0xEF,0x12,0xA5,0x37,0xFC,0xAE,0xD9,0x3,0x8E,0xDD,0x10,0xB9,0xCE,0xC9,0x8D,
0xDA,0x2A,0xBD,0x68,0x17,0x9F,0xBE,0xD4,0xA,0xCC,0xD2,0xE8,0x43,0x3D,0x70,0xB7,0x2,0x7D,0x99,0xD8,0xD,0x60,0x8A,0x4,0x2C,0x3E,0x92,0xE5,0xAF,0x53,0x7,0xE0,0x29,0xA6,0xC5,0xE3,0xF5,0xF7,0x4A,0x41,0x26,0x6A,0x16,0x5E,0x52,0x2D,0x21,0xAD,0xF0,0x91,0xFF,0xEA,0x54,0xFA,0x66,0x1A,0x45,0x39,0xCF,0x75,0xA4,0x88,0xFB,0x5D,
0xA2,0xA0,0x19,0x3B,0xF8,0xEB,0xAA,0xEE,0xF3,0x1C,0x67,0x28,0x1D,0xED,0x0,0xDE,0x95,0x2E,0xDC,0x3F,0x3A,0x82,0x35,0x4D,0x6C,0xBA,0x36,0xD0,0xF6,0xC,0x79,0x32,0xD1,0x59,0xF4,0x8,0x8B,0x63,0x89,0x2F,0xB8,0xB4,0x97,0x83,0xF2,0x8F,0x18,0xC7,0x51,0x14,0x65,0x87,0x48,0x20,0x42,0xA8,0x80,0xB5,0x40,0x13,0xB2,0x22,0x7E,0x57,
0xBC,0x7F,0x6B,0x9D,0x86,0x4C,0xC8,0xDB,0x7C,0xD5,0x25,0x4E,0x5A,0x55,0x74,0x50,0xCD,0xB3,0x7A,0xBB,0xC3,0xCB,0xB6,0xE2,0xE4,0xEC,0xFD,0x98,0xB,0x96,0xD3,0x9E,0x5C,0xA1,0x64,0xF1,0x81,0x61,0xE1,0xC4,0x24,0x72,0x49,0x8C,0x90,0x4B,0x84,0x34,0x38,0xAB,0x78,0xCA,0x1F,0x1,0xD7,0x93,0x11,0xC1,0x58,0xA9,0x31,0xF9,0x44,0x6D,
0xBF,0x33,0x9C,0x5F,0x9,0x94,0xA3,0x85,0x6,0xC6,0x9A,0x1E,0x7B,0x46,0x15,0x30,0x27,0x2B,0x1B,0x71,0x3C,0x5B,0xD6,0x6F,0x62,0xAC,0x4F,0xC2,0xC0,0xE,0xB1,0x23,0xA7,0xDF,0x47,0xB0,0x77,0x69,0x5,0xE9,0xE6,0xE7,0x76,0x73,0xF,0xFE,0x6E,0x9B,0x56,0xEF,0x12,0xA5,0x37,0xFC,0xAE,0xD9,0x3,0x8E,0xDD,0x10,0xB9,0xCE,0xC9,0x8D,
0xDA,0x2A,0xBD,0x68,0x17,0x9F,0xBE,0xD4,0xA,0xCC,0xD2,0xE8,0x43,0x3D,0x70,0xB7,0x2,0x7D,0x99,0xD8,0xD,0x60,0x8A,0x4,0x2C,0x3E,0x92,0xE5,0xAF,0x53,0x7,0xE0,0x29,0xA6,0xC5,0xE3,0xF5,0xF7,0x4A,0x41,0x26,0x6A,0x16,0x5E,0x52,0x2D,0x21,0xAD,0xF0,0x91,0xFF,0xEA,0x54,0xFA,0x66,0x1A,0x45,0x39,0xCF,0x75,0xA4,0x88,0xFB,0x5D];
static public function lerp(t:Number, a:Number, b:Number):Number {
return a + t * (b - a);
}
static public function smoothClamp(n:Number):Number {
return Smoothing.smooth5(clamp(n));
}
static public function clamp(n:Number):Number {
return n < 0 ? 0 : n > 1 ? 1 : n;
}
static public function smooth5(t:Number):Number {
return t * t * t * (t * (t * 6 - 15) + 10);
}
static public function smooth3(t:Number):Number {
return t * t * (3 - 2 * t);
}
static protected function grad(hash:int, x:Number, y:Number, z:Number):Number {
var h:Number = hash & 15;
var u:Number = h<8 ? x : y;
var v:Number = h<4 ? y : (h == 12 || h==14) ? x : z;
return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
}
}
// package com.nodename.geom
//{
import flash.errors.IllegalOperationError;
//public
final class Winding
{
public static const CLOCKWISE:Winding = new Winding(PrivateConstructorEnforcer, "clockwise");
public static const COUNTERCLOCKWISE:Winding = new Winding(PrivateConstructorEnforcer, "counterclockwise");
public static const NONE:Winding = new Winding(PrivateConstructorEnforcer, "none");
private var _name:String;
public function Winding(lock:Class, name:String)
{
super();
if (lock != PrivateConstructorEnforcer)
{
throw new IllegalOperationError("Invalid constructor access");
}
_name = name;
}
public function toString():String
{
return _name;
}
}
//}
//}//package {
import flash.geom.Point;
/*public*/ class Polygon
{
private var _vertices:Vector.<Point>;
public function Polygon(vertices:Vector.<Point>)
{
_vertices = vertices;
}
public function area():Number
{
return Math.abs(signedDoubleArea() * 0.5);
}
public function winding():Winding
{
var signedDoubleArea:Number = signedDoubleArea();
if (signedDoubleArea < 0)
{
return Winding.CLOCKWISE;
}
if (signedDoubleArea > 0)
{
return Winding.COUNTERCLOCKWISE;
}
return Winding.NONE;
}
private function signedDoubleArea():Number
{
var index:uint, nextIndex:uint;
var n:uint = _vertices.length;
var point:Point, next:Point;
var signedDoubleArea:Number = 0;
for (index = 0; index < n; ++index)
{
nextIndex = (index + 1) % n;
point = _vertices[index] as Point;
next = _vertices[nextIndex] as Point;
signedDoubleArea += point.x * next.y - next.x * point.y;
}
return signedDoubleArea;
}
}
//}//package {
import flash.errors.IllegalOperationError;
//package {
import flash.geom.Point;
/*public*/ class Circle extends Object
{
public var center:Point;
public var radius:Number;
public function Circle(centerX:Number, centerY:Number, radius:Number)
{
super();
this.center = new Point(centerX, centerY);
this.radius = radius;
}
public function toString():String
{
return "Circle (center: " + center + "; radius: " + radius + ")";
}
}
//}//package {
import __AS3__.vec.Vector;
/*public*/ class Triangle
{
private var _sites:Vector.<Site>;
public function get sites():Vector.<Site>
{
return _sites;
}
public function Triangle(a:Site, b:Site, c:Site)
{
_sites = Vector.<Site>([ a, b, c ]);
}
public function dispose():void
{
_sites.length = 0;
_sites = null;
}
}
//}//package {
import flash.display.BitmapData;
import __AS3__.vec.Vector;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.geom.Rectangle;
/*public*/ class BitmapDataUtil {
public static function getPointsMatchingColor(bmd:BitmapData,color:uint):Vector.<Point>{
var points:Vector.<Point>=new Vector.<Point>();
for(var i:uint=0;i<bmd.height;i++){
for(var j:uint=0;j<bmd.width;j++){
if(bmd.getPixel32(j,i)==color){
points.push(new Point(j,i));
}
}
}
return points;
}
public static function getPointNotMatchingColor(bmd:BitmapData,color:uint):Point {
for(var i:uint=0;i<bmd.height;i++){
for(var j:uint=0;j<bmd.width;j++){
if(bmd.getPixel32(j,i)!=color){
return new Point(j,i);
}
}
}
return null;
}
public static function getPointsMatchingColor32(bmd:BitmapData,color:uint):Vector.<Point>{
var points:Vector.<Point>=new Vector.<Point>();
for(var i:uint=0;i<bmd.height;i++){
for(var j:uint=0;j<bmd.width;j++){
if(bmd.getPixel32(j,i)==color){
points.push(new Point(j,i));
}
}
}
return points;
}
public static function getNonTransparentPoints(bmd:BitmapData,grab_every:uint=2,resize_percent:Number=1,offset:Point=null):Vector.<Point>{
if(offset==null)offset=new Point(0,0);
var points:Vector.<Point>=new Vector.<Point>();
for(var i:uint=0;i<bmd.height;i+=grab_every){
for(var j:uint=0;j<bmd.width;j+=grab_every){
if(bmd.getPixel32(j,i)>0x00000000){
points.push(new Point(j/resize_percent+offset.x,i/resize_percent+offset.y));
}
}
}
return points;
}
public static function toMonoChrome(source:BitmapData,mono_color:uint=0xFF000000):BitmapData{
var bmd:BitmapData=source.clone();
bmd.threshold(bmd,bmd.rect,new Point(),">",0x00000000,mono_color);
return bmd;
}
public static function containsTransparentPixels(bmd:BitmapData):Boolean{
if(!bmd.transparent)return false;
var test:BitmapData=bmd.clone();
return test.threshold(bmd,bmd.rect,new Point(),"<",0x01,0xFF000000) > 0 ? true : false ;
}
public static function containsSolidPixels(bmd:BitmapData):Boolean{
var rect:Rectangle=bmd.getColorBoundsRect(0xFF000000,0,false);
return !rect.equals(new Rectangle());
}
public static function stripTransparentEdges(bm:BitmapData):BitmapData{
bm=stripTransparentEdgeFromTop(bm);
bm=stripTransparentEdgeFromBottom(bm);
bm=stripTransparentEdgeFromRight(bm);
return stripTransparentEdgeFromLeft(bm);
}
public static function stripTransparentEdgeFromTop(bm:BitmapData):BitmapData{
var i:uint,j:uint,first_colored:uint=0;
outer:for(i=0;i<bm.height;i++){
for(j=0;j<bm.width;j++){
if(bm.getPixel32(j,i)!=0x00000000){
first_colored=i;
break outer;
}
}
}
if(first_colored==0)return bm;
var stripped:BitmapData=new BitmapData(bm.width,bm.height-first_colored,true,0x00000000);
stripped.draw(bm,new Matrix(1,0,0,1,0,-first_colored));
return stripped;
}
public static function stripTransparentEdgeFromBottom(bm:BitmapData):BitmapData{
var i:int,j:uint,first_colored:uint=bm.height;
outer:for(i=bm.height;i>-1;i--){
for(j=0;j<bm.width;j++){
if(bm.getPixel32(j,i)!=0x00000000){
first_colored=i+1;
break outer;
}
}
}
if(first_colored==bm.height)return bm;
var stripped:BitmapData=new BitmapData(bm.width,first_colored,true,0x00000000);
stripped.draw(bm);
return stripped;
}
public static function stripTransparentEdgeFromLeft(bm:BitmapData):BitmapData{
var i:uint,j:uint,first_colored:uint=0;
outer:for(i=0;i<bm.width;i++){
for(j=0;j<bm.height;j++){
if(bm.getPixel32(i,j)!=0x00000000){
first_colored=i;
break outer;
}
}
}
if(first_colored==0)return bm;
var stripped:BitmapData=new BitmapData(bm.width-first_colored,bm.height,true,0x00000000);
stripped.draw(bm,new Matrix(1,0,0,1,-first_colored,0));
return stripped;
}
public static function stripTransparentEdgeFromRight(bm:BitmapData):BitmapData{
var i:int,j:uint,first_colored:uint=bm.width;
outer:for(i=bm.width;i>-1;i--){
for(j=0;j<bm.height;j++){
if(bm.getPixel32(i,j)!=0x00000000){
first_colored=i+1;
break outer;
}
}
}
if(first_colored==bm.width)return bm;
var stripped:BitmapData=new BitmapData(first_colored,bm.height,true,0x00000000);
stripped.draw(bm);
return stripped;
}
public static function getFirstNonTransparentPixel( bmd:BitmapData, start_y:uint=0 ):Point{
var hit_rect:Rectangle=new Rectangle(0,0,bmd.width,1);
var p:Point = new Point();
for( hit_rect.y = start_y; hit_rect.y < bmd.height; hit_rect.y++ ){
if( bmd.hitTest(p, 0x01, hit_rect) ){
var hit_bmd:BitmapData=new BitmapData( bmd.width, 1, true, 0 );
hit_bmd.copyPixels( bmd, hit_rect, p );
return hit_rect.topLeft.add( hit_bmd.getColorBoundsRect(0xFF000000, 0, false).topLeft );
}
}
return null;
}
public static function getFirstNonTransparentPixel2( bmd:BitmapData ):Point{
var r1:Rectangle = bmd.getColorBoundsRect( 0xff000000, 0, false );
if ( r1.width > 0 ){
var temp:BitmapData = new BitmapData( r1.width, 1, true, 0 );
temp.copyPixels( bmd, r1, new Point());
var r2:Rectangle = temp.getColorBoundsRect( 0xff000000, 0, false );
return r1.topLeft.add( r2.topLeft );
}
return null;
}
public static function getFirstNonTransparentPixelLooping(bmd:BitmapData):Point{
var ix:uint,iy:uint,bmd_height:uint=bmd.height,bmd_width:uint=bmd.width;
for (iy=0;iy<bmd_height;iy++){
for(ix=0;ix<bmd_width;ix++){
if(bmd.getPixel32(ix,iy)>0x00000000){
return new Point(ix,iy);
}
}
}
return null;
}
public static function getFirstNonTransparentPixelFloodFill(bmd:BitmapData,test_fill_color:uint=0xFFFFFF00):Point{
var hit_bmd:BitmapData;
var m:Matrix=new Matrix();
for(var i:int=0;i<bmd.height;i++){
m.ty=-i;
hit_bmd=new BitmapData(bmd.width,1,true,0);
hit_bmd.draw(bmd,m);
hit_bmd.floodFill(0,0,test_fill_color);
var bounds:Rectangle=hit_bmd.getColorBoundsRect(0xFFFFFFFF,test_fill_color);
if(bounds.width!=bmd.width){
return new Point(i,bounds.width);
}
hit_bmd.dispose();
}
return null;
}
public static function getFirstNonTransparentPixelHitTest(bmd:BitmapData,test_fill_color:uint=0xFFFFFF00):Point{
var hit_rect:Rectangle=new Rectangle(0,0,bmd.width,1);
for(var i:uint=0;i<bmd.height;i++){
if(bmd.hitTest(new Point(),0x01,hit_rect)){
var hit_bmd:BitmapData=new BitmapData(bmd.width,1,true,0);
var m:Matrix=new Matrix(1,0,0,1,0,-i);
hit_bmd.draw(bmd,m);
hit_bmd.floodFill(0,0,test_fill_color);
var bounds:Rectangle=hit_bmd.getColorBoundsRect(0xFFFFFFFF,test_fill_color);
return new Point(bounds.width,i);
}
hit_rect.y++;
}
return null;
}
public static function changeEdgePixels(bmd:BitmapData,replace:uint):BitmapData{
var ix:uint,iy:uint,bmd_height:uint=bmd.height,bmd_width:uint=bmd.width;
var max_y:uint=bmd_height-1,max_x:uint=bmd_width-1;
var update:Vector.<Point>=new Vector.<Point>();
for (iy=0;iy<bmd_height;iy++){
for(ix=0;ix<bmd_width;ix++){
if(bmd.getPixel32(ix,iy)>0x00000000){
if(!iy || !ix || iy==max_y || ix==max_x){
update.push(new Point(ix,iy));
}else if(
!( bmd.getPixel32(ix-1,iy)>0x00000000 &&
bmd.getPixel32(ix+1,iy)>0x00000000 &&
bmd.getPixel32(ix,iy-1)>0x00000000 &&
bmd.getPixel32(ix,iy+1)>0x00000000 )
){
update.push(new Point(ix,iy));
}
}
}
}
var tot:uint=update.length;
var p:Point;
for (var i:uint=0;i<tot;i++){
p=update[i];
bmd.setPixel32(p.x,p.y,replace);
}
return bmd;
}
}
//}//package {
import __AS3__.vec.Vector;
import flash.display.Shape;
import flash.display.Bitmap;
import flash.display.BitmapData;
/*public*/ class ExtractedShapeCollection{
private var _shapes:Vector.<BitmapData>;
public function get shapes():Vector.<BitmapData>{return _shapes;}
public function set shapes(a:Vector.<BitmapData>):void{_shapes=a;}
private var _negative_shapes:Vector.<BitmapData>;
public function get negative_shapes():Vector.<BitmapData>{return _negative_shapes;}
public function set negative_shapes(a:Vector.<BitmapData>):void{_negative_shapes=a}
public function get all_shapes():Vector.<BitmapData>{return _shapes.concat(_negative_shapes);}
public function set all_shapes(a:Vector.<BitmapData>):void{}
public function ExtractedShapeCollection(){
_shapes=new Vector.<BitmapData>();
_negative_shapes=new Vector.<BitmapData>();
}
public function addShape(bmd:BitmapData):void{
_shapes.push(bmd);
}
public function addNegativeShape(bmd:BitmapData):void{
_negative_shapes.push(bmd);
}
public function dispose():void
{
var i:int;
i = _shapes ? _shapes.length : 0;
while (--i > -1) {
_shapes[i].dispose();
}
i = _negative_shapes ? _negative_shapes.length : 0;
while (--i > -1) {
_negative_shapes[i].dispose();
}
_shapes = null;
_negative_shapes = null;
}
}
//}//package {
import __AS3__.vec.Vector;
import flash.events.Event;
import flash.events.EventDispatcher;
import flash.events.TimerEvent;
import flash.geom.Rectangle;
import flash.utils.Timer;
import flash.display.BitmapData;
import flash.display.BitmapDataChannel;
import flash.geom.Matrix;
import flash.geom.Point;
/*public*/ class BitmapShapeExtractor extends EventDispatcher {
private static var TEMP_DATA:BitmapData;
public static function extractShapes2(source_bmd:BitmapData, extraction_color:uint = 0xFF000000):ExtractedShapeCollection {
if (TEMP_DATA == null || TEMP_DATA.width != source_bmd.width || TEMP_DATA.height != source_bmd.height) {
if (TEMP_DATA) TEMP_DATA.dispose();
TEMP_DATA = new BitmapData(source_bmd.width, source_bmd.height, true, 0);
}
TEMP_DATA.fillRect(TEMP_DATA.rect, 0);
TEMP_DATA.threshold(source_bmd, source_bmd.rect, new Point(), "!=", extraction_color, 0, 0xFF0000FF, true);
return extractShapes(TEMP_DATA, extraction_color);
}
public static function extractShapes2Async(source_bmd:BitmapData, extraction_color:uint = 0xFF000000):BitmapShapeExtractor {
if (TEMP_DATA == null || TEMP_DATA.width != source_bmd.width || TEMP_DATA.height != source_bmd.height) {
if (TEMP_DATA) TEMP_DATA.dispose();
TEMP_DATA = new BitmapData(source_bmd.width, source_bmd.height, true, 0);
}
TEMP_DATA.fillRect(TEMP_DATA.rect, 0);
TEMP_DATA.threshold(source_bmd, source_bmd.rect, new Point(), "!=", extraction_color, 0, 0xFF0000FF, true);
var me:BitmapShapeExtractor = new BitmapShapeExtractor();
me.extractShapesAsync(TEMP_DATA, extraction_color);
return me;
}
public static function extractShapes(source_bmd:BitmapData,extraction_color:uint=0xFF000000):ExtractedShapeCollection{
var extracted:ExtractedShapeCollection=new ExtractedShapeCollection();
var positive_two_color:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0x00);
positive_two_color.draw(source_bmd);
positive_two_color=BitmapDataUtil.toMonoChrome(positive_two_color,0xFFFF0000);
if(!BitmapDataUtil.containsTransparentPixels(source_bmd)){
extracted.addShape(positive_two_color);
return extracted;
}
var temp:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0xFF0000FF);
temp.draw(positive_two_color);
var negative_two_color:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0xFFFF0000);
negative_two_color.copyChannel(temp,positive_two_color.rect,new Point(),BitmapDataChannel.BLUE,BitmapDataChannel.ALPHA);
extracted.shapes=extractShapesFromMonochrome(positive_two_color);
extracted.negative_shapes=extractShapesFromMonochrome(negative_two_color);
return extracted;
}
public function extractShapesAsync(source_bmd:BitmapData,extraction_color:uint=0xFF000000):void {
var positive_two_color:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0x00);
positive_two_color.draw(source_bmd);
positive_two_color=BitmapDataUtil.toMonoChrome(positive_two_color,0xFFFF0000);
if(!BitmapDataUtil.containsTransparentPixels(source_bmd)){
extracted.addShape(positive_two_color);
return;
}
var temp:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0xFF0000FF);
temp.draw(positive_two_color);
var negative_two_color:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0xFFFF0000);
negative_two_color.copyChannel(temp,positive_two_color.rect,new Point(),BitmapDataChannel.BLUE,BitmapDataChannel.ALPHA);
extractShapesFromMonochromeAsync(positive_two_color, extracted.shapes);
extractShapesFromMonochromeAsync(negative_two_color, extracted.negative_shapes);
return;
}
public static function extractShapesDoubleSize(source_bmd:BitmapData,extraction_color:uint=0xFF000000):ExtractedShapeCollection{
var extracted:ExtractedShapeCollection=new ExtractedShapeCollection();
var mono_chrome:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0x00);
mono_chrome.draw(source_bmd);
mono_chrome=BitmapDataUtil.toMonoChrome(mono_chrome,0xFFFF0000);
var positive_two_color:BitmapData=new BitmapData(source_bmd.width*2,source_bmd.height*2,true,0x00);
var m:Matrix=new Matrix();
m.scale(2,2);
positive_two_color.draw(mono_chrome,m);
positive_two_color=BitmapDataUtil.toMonoChrome(positive_two_color,0xFFFF0000);
mono_chrome.dispose();
mono_chrome=null;
if(!BitmapDataUtil.containsTransparentPixels(source_bmd)){
extracted.addShape(positive_two_color);
return extracted;
}
var temp:BitmapData=new BitmapData(positive_two_color.width,positive_two_color.height,true,0xFF0000FF);
temp.draw(positive_two_color);
var negative_two_color:BitmapData=new BitmapData(positive_two_color.width,positive_two_color.height,true,0xFFFF0000);
negative_two_color.copyChannel(temp,positive_two_color.rect,new Point(),BitmapDataChannel.BLUE,BitmapDataChannel.ALPHA);
extracted.shapes=extractShapesFromMonochrome(positive_two_color);
extracted.negative_shapes=extractShapesFromMonochrome(negative_two_color);
return extracted;
}
private var scan_y:uint;
private var bmd:BitmapData;
public var extracted:ExtractedShapeCollection = new ExtractedShapeCollection();
private var found:Vector.<BitmapData>;
private var timer:Timer = new Timer(30, 0);
public function BitmapShapeExtractor() {
timer.addEventListener(TimerEvent.TIMER, extractShapeFromMonochromeAsync_iterate);
}
protected function extractShapesFromMonochromeAsync(bmd:BitmapData, found:Vector.<BitmapData>):void {
scan_y = 0;
this.bmd = bmd
this.found = found;
timer.start();
}
protected function extractShapeFromMonochromeAsync_iterate(e:Event):void {
var non_trans:Point;;
non_trans=BitmapDataUtil.getFirstNonTransparentPixel(bmd,scan_y);
if (non_trans == null) return;
bmd.floodFill(non_trans.x, non_trans.y, 0xFF0000FF);
var copy_bmd:BitmapData = new BitmapData(bmd.width, bmd.height, true, 0xFFFF0000);
copy_bmd.copyChannel(bmd,bmd.rect,new Point(),BitmapDataChannel.BLUE, BitmapDataChannel.ALPHA);
bmd.floodFill(non_trans.x,non_trans.y,0x00000000);
found.push(copy_bmd);
scan_y = non_trans.y;
if (scan_y >= bmd.height) {
timer.stop();
dispatchEvent( new Event(Event.COMPLETE) );
}
}
protected static function extractShapesFromMonochrome(bmd:BitmapData):Vector.<BitmapData>{
var scan_y:uint=0;
var non_trans:Point;
var found:Vector.<BitmapData>=new Vector.<BitmapData>();
var copy_bmd:BitmapData;
var iterations:uint=0;
while(scan_y<bmd.height){
non_trans=BitmapDataUtil.getFirstNonTransparentPixel(bmd,scan_y);
if(non_trans==null)return found;
bmd.floodFill(non_trans.x, non_trans.y, 0xFF0000FF);
copy_bmd=new BitmapData(bmd.width,bmd.height,true,0xFFFF0000);
copy_bmd.copyChannel(bmd,bmd.rect,new Point(),BitmapDataChannel.BLUE, BitmapDataChannel.ALPHA);
bmd.floodFill(non_trans.x,non_trans.y,0x00000000);
found.push(copy_bmd);
scan_y=non_trans.y;
iterations++;
}
return found;
}
}
//}//package {
import flash.display.BitmapData;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.utils.ByteArray;
import flash.utils.Dictionary;
/*public*/ class BiomePainter32
{
private var atlasTilesAcrossH:int;
private var atlasTilesAcrossV:int;
public var errorCount:int = 0;
private static var ROTATIONS:Vector.<int> = getRotations();
private static var READING_ORDER4:Vector.<uint> = new <uint>[
0, 1, 2, 3,
2, 0, 3, 1,
3, 2, 1, 0,
1, 3, 0, 2
];
private static var READING_ORDER_RGB:Vector.<uint> = new <uint>[
0, 0, 0,
0, 1, 2,
0, 1, 1,
0, 0, 1,
];
private static function getRotations():Vector.<int>
{
var vec:Vector.<int> = new Vector.<int>();
var mat:Matrix = new Matrix();
vec.push(mat.a, mat.b, mat.c, mat.d);
mat.rotate(.5*Math.PI);
vec.push(mat.a, mat.b, mat.c, mat.d);
mat.rotate(.5*Math.PI);
vec.push(mat.a, mat.b, mat.c, mat.d);
mat.rotate(.5*Math.PI);
vec.push(mat.a, mat.b, mat.c, mat.d);
return vec;
}
public function BiomePainter32(atlasTilesAcrossH:int, atlasTilesAcrossV:int)
{
if (!isValidTileAtlas(atlasTilesAcrossH, atlasTilesAcrossV)) {
throw new Error("Too many tiles exceeded 16! " + (atlasTilesAcrossH * atlasTilesAcrossV));
}
this.atlasTilesAcrossH = atlasTilesAcrossH;
this.atlasTilesAcrossV = atlasTilesAcrossV;
}
public function writeBmpData(data:ByteArray, tileBitmap:Vector.<uint>, tilesAcross:int):void {
data.writeShort(tilesAcross);
var len:int = tilesAcross * tilesAcross;
var color:uint;
for (var i:int = 0; i < len; i++) {
color = tileBitmap[i];
data.writeByte( (color & 0xFF0000) >> 16 );
data.writeByte( (color & 0xFF00) >> 8 );
data.writeByte( (color & 0xFF) );
}
}
public function getBmpData(data:ByteArray):BitmapData {
var tilesAcross:int = data.readShort();
var bmpData:BitmapData = new BitmapData(tilesAcross, tilesAcross, true, 0);
var color:uint;
for (var y:int = 0; y < tilesAcross; y++) {
for (var x:int = 0; x < tilesAcross; x++) {
color = 0xFF000000;
color |= (data.readUnsignedByte() << 16);
color |= (data.readUnsignedByte() << 8);
color |= data.readUnsignedByte();
bmpData.setPixel32(x, y, color);
}
}
return bmpData;
}
public function isValidTileAtlas(acrossH:int, acrossV:int):Boolean {
return (acrossH * acrossV) <= 16;
}
public function getUintFromIndices(ri:uint, gi:uint, bi:uint, ki:uint, ma:int, mb:int, mc:int, md:int):uint {
return getUint( uint(ri % atlasTilesAcrossH) / atlasTilesAcrossH, uint(ri / atlasTilesAcrossH) / atlasTilesAcrossV,
uint(gi % atlasTilesAcrossH) / atlasTilesAcrossH, uint(gi / atlasTilesAcrossH) / atlasTilesAcrossV,
uint(bi % atlasTilesAcrossH) / atlasTilesAcrossH, uint(bi / atlasTilesAcrossH) / atlasTilesAcrossV,
uint(ki % atlasTilesAcrossH) / atlasTilesAcrossH, 0,
ma, mb, mc, md);
}
public function getUintFromIndices2(ri:uint, gi:uint, bi:uint, ki:uint, mi:uint):uint {
var ma:int = ROTATIONS[mi * 4];
var mb:int = ROTATIONS[mi * 4+1];
var mc:int = ROTATIONS[mi * 4+2];
var md:int = ROTATIONS[mi * 4+3];
return getUintFromIndices(ri, gi, bi, ki, ma,mb,mc,md );
}
public function getUint(ru:Number, rv:Number, gu:Number, gv:Number, bu:Number, bv:Number, ku:Number, kv:Number, ma:int, mb:int, mc:int, md:int):uint {
ma++; mb++; mc++; md++;
if (ku == 0) {
kv = 0;
}
else {
kv = Math.floor( Math.random() * 5 );
if (kv < 4) {
kv *= .25;
}
else {
kv = ku;
ku = 0;
}
}
return ( 0xFF000000 | (uint(ru * 4) << 22) | (uint(rv * 4) << 20) |
(uint(gu * 4) << 18) | (uint(gv * 4) << 16) |
(uint(bu * 4) << 14) | (uint(bv * 4) << 12) |
(uint(ku * 4) << 10) | (uint(kv * 4) << 8) |
(uint(ma) << 6) |
(uint(mb) << 4) |
(uint(mc) << 2) |
(uint(md)) );
}
public function getUint16bits(color:uint):uint {
var r:uint = (color & 0xFF0000) >> 16;
var g:uint = (color & 0xFF00) >> 8;
var b:uint = (color & 0xFF);
var ru:uint = (r & 192) >> 6;
var rv:uint = (r & 48) >> 4;
var gu:uint = (r & 12) >> 2;
var gv:uint = (r & 3);
var bu:uint = (g & 192) >> 6;
var bv:uint = (g & 48) >> 4;
var ku:int = (g & 12) >> 2;
var kv:int = (g & 3);
if (ku == 0 && kv > 0) {
ku = kv;
}
var ma:int = (b & 192) >> 6;
var mb:int = (b & 48) >> 4;
var mc:int = (b & 12) >> 2;
var md:int = (b & 3);
ma--; mb--; mc--; md--;
var tindex:int = ma === 1 ? 0 : mc === -1 ? 1 : ma === -1 ? 2 : 3;
var readRGB:Vector.<uint> = READING_ORDER_RGB;
var readSquares:Vector.<uint> = READING_ORDER4;
var u:uint;
var v:uint;
var rr:int;
var result:uint = 0xFF000000;
var i:uint;
i = (readSquares[tindex * 4]); if (i > 2) i = 2;
i = ku * 3 + i ;
rr = readRGB[i];
u = rr === 0 ? ru : rr === 1 ? gu : bu;
v = rr === 0 ? rv : rr === 1 ? gv : bv;
result |= uint(v * .25 * atlasTilesAcrossV * atlasTilesAcrossH + u * .25 * atlasTilesAcrossH) << 0;
i = (readSquares[tindex * 4 + 1]); if (i > 2) i = 2;
i = ku * 3 + i;
rr = readRGB[i];
u = rr === 0 ? ru : rr === 1 ? gu : bu;
v = rr === 0 ? rv : rr === 1 ? gv : bv;
result |= uint(v * .25 * atlasTilesAcrossV * atlasTilesAcrossH + u * .25 * atlasTilesAcrossH) << 4;
i = (readSquares[tindex * 4 + 2]); if (i > 2) i = 2;
i = ku * 3 + i;
rr = readRGB[i];
u = rr === 0 ? ru : rr === 1 ? gu : bu;
v = rr === 0 ? rv : rr === 1 ? gv : bv;
result |= uint(v * .25 * atlasTilesAcrossV * atlasTilesAcrossH + u * .25 * atlasTilesAcrossH) << 8;
i = (readSquares[tindex * 4 + 3]); if (i > 2) i = 2;
i = ku * 3 + i;
rr = readRGB[i];
u = rr === 0 ? ru : rr === 1 ? gu : bu;
v = rr === 0 ? rv : rr === 1 ? gv : bv;
result |= uint(v * .25 * atlasTilesAcrossV * atlasTilesAcrossH + u * .25 * atlasTilesAcrossH) << 12;
return result;
}
private function getIdentityValue(s1:uint, s2:uint, s3:uint):uint {
var result:uint = 0xFF000000;
result |= (s1 << 0);
result |= (s2 << 4);
result |= (s3 << 8);
result |= (s3 << 12);
return result;
}
private function identifyTransform(s1:uint, s2:uint, s3:uint, layout16:uint):uint {
var result:uint;
result = 0xFF000000;
result |= (s1 << 0);
result |= (s2 << 4);
result |= (s3 << 8);
result |= (s3 << 12);
if (result == layout16) return 0;
result = 0xFF000000;
result |= (s3 << 0);
result |= (s1 << 4);
result |= (s3 << 8);
result |= (s2 << 12);
if (result == layout16) return 1;
result = 0xFF000000;
result |= (s3 << 0);
result |= (s3 << 4);
result |= (s2 << 8);
result |= (s1 << 12);
if (result == layout16) return 2;
result = 0xFF000000;
result |= (s2 << 0);
result |= (s3 << 4);
result |= (s1 << 8);
result |= (s3 << 12);
if (result == layout16) return 3;
return 0xFFFFFFFF;
}
private function setUint16bits(result:uint):uint {
var dict:Dictionary = new Dictionary();
var val:uint;
var u:Number;
var v:Number;
var readOrderRGB:Vector.<uint> = READING_ORDER_RGB;
var readOrderSquares:Vector.<uint> = READING_ORDER4;
var mValues:Vector.<int> = ROTATIONS;
var m:int;
val = result & 0xF;
if ( dict[val] == null) dict[val] = 1
else dict[val]++;
val = (result & 0xF0) >> 4;
if ( dict[val] == null) dict[val] = 1
else dict[val]++;
val =(result & 0xF00) >> 8;
if ( dict[val] == null) dict[val] = 1
else dict[val]++;
val = (result & 0xF000) >> 12;
if ( dict[val] == null) dict[val] = 1
else dict[val]++;
var count:int = 0;
var multiplier:int = 1;
for (var p:* in dict) {
multiplier *= dict[p]
count++;
}
var unique:int;
var unique2:int;
var swapVal:uint;
var swapVal2:uint;
var swappables:uint;
var ti:uint;
if (count != 1) {
var blendIndex:int = multiplier - 1;
if (blendIndex === 0) {
throw new Error("This should never happen under count!=1 case!")
}
else if (blendIndex === 1) {
unique = -1;
count = 0;
swappables = 0xFF000000;
for (p in dict) {
if (dict[p] === 2) {
unique = p;
}
else {
swappables |= (uint(p) << ((count++) << 2));
}
}
if (unique < 0) throw new Error("Could not find unique under blend index 1");
ti = identifyTransform( swapVal=(swappables & 0xF), swapVal2=((swappables & 0xF0) >> 4), unique, result);
if (ti ===0xFFFFFFFF) ti = identifyTransform( swapVal=(((swappables & 0xF0) >> 4)), swapVal2=(swappables & 0xF), unique, result);
if (ti === 0xFFFFFFFF) {
errorCount++;
return 0xFFFFFFFF;
throw new Error("Could not find valid transform index for blendIndex 1"+":"+getIdentityValue(swapVal, swapVal2, unique) + ", "+result + ", s1:"+swapVal + " s2:"+swapVal2 + " u:"+unique);
}
ti *= 4;
return getUintFromIndices(swapVal, swapVal2, unique, blendIndex, mValues[ti], mValues[ti + 1], mValues[ti + 2], mValues[ti + 3]);
}
else if (blendIndex === 2) {
unique = -1;
unique2 = -1;
count = 0;
for (p in dict) {
if (dict[p] === 3) {
unique2 = p;
}
else if (dict[p] === 1) {
unique = p;
}
}
if (unique < 0 || unique2 < 0) throw new Error("Could not find uniques under blend index 2");
ti = identifyTransform(unique, unique2, unique2, result);
if (ti === 0xFFFFFFFF) {
errorCount++;
return 0xFFFFFFFF;
throw new Error("Could not find valid transform index for blendIndex 2");
}
ti *= 4;
return getUintFromIndices(unique, unique2, 0, blendIndex, mValues[ti], mValues[ti + 1], mValues[ti + 2], mValues[ti + 3]);
}
else {
count = 0;
swappables = 0xFF000000;
for (p in dict) {
swappables |= ( uint(p) << ((count++) << 2) );
}
ti = identifyTransform( swapVal = (swappables & 0xF), (swappables & 0xF), swapVal2=(((swappables & 0xF0) >> 4)), result);
if (ti ===0xFFFFFFFF) ti = identifyTransform( swapVal=(((swappables & 0xF0) >> 4)), (((swappables & 0xF0) >> 4)), swapVal2=(swappables & 0xF), result);
if (ti === 0xFFFFFFFF) {
errorCount++;
return 0xFFFFFFFF;
throw new Error("Could not find valid transform index for blendIndex "+blendIndex+":"+getIdentityValue(swapVal, swapVal, swapVal2) + ", "+result + ", s1:"+swapVal + " s2:"+swapVal2);
}
ti *= 4;
return getUintFromIndices(swapVal, swapVal2, 0, blendIndex, mValues[ti], mValues[ti + 1], mValues[ti + 2], mValues[ti + 3]);
}
}
else {
v = int(val / atlasTilesAcrossH) / atlasTilesAcrossV;
u = int(val % atlasTilesAcrossH) / atlasTilesAcrossH;
return getUint(u, v, u, v, u, v, 0, 0, mValues[0], mValues[1], mValues[2], mValues[3]);
}
throw new Error("Failed to get valid value case!");
return 0xFFFFFFFF;
}
public function paintToTileMap(tileMap:Vector.<uint>, tilesAcross:int, tileIndex:uint, x:int, y:int):void {
var xi:int;
var yi:int;
var val16:uint;
var testVal:uint;
tileMap[y * tilesAcross + x] = getUintFromIndices(tileIndex, tileIndex, tileIndex, 0, 1, 0, 0, 1);
var lastIndex:int = -1;
xi = x -1;
yi = y - 1;
if (xi >= 0 && xi < tilesAcross && yi >= 0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
val16 &= ~(0xF000);
val16 |= (tileIndex << 12);
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
xi = x;
yi = y - 1;
if (xi >= 0 && xi < tilesAcross && yi >=0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
val16 &= ~(0xFF00);
val16 |= (tileIndex << 12);
val16 |= (tileIndex << 8);
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
xi = x +1;
yi = y -1;
if (xi >= 0 && xi < tilesAcross && yi >=0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
testVal = setUint16bits(val16);
val16 &= ~(0xF00);
val16 |= (tileIndex << 8);
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
xi = x - 1;
yi = y;
if (xi >= 0 && xi < tilesAcross && yi >=0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
val16 &= ~(0xF0F0);
val16 |= (tileIndex << 4);
val16 |= (tileIndex << 12);
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
xi = x +1;
yi = y;
if (xi >= 0 && xi < tilesAcross && yi >=0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
val16 &= ~(0xF0F);
val16 |= tileIndex;
val16 |= (tileIndex << 8);
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
xi = x -1;
yi = y + 1;
if (xi >= 0 && xi < tilesAcross && yi >=0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
val16 &= ~(0xF0);
val16 |= (tileIndex << 4);
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
xi = x;
yi = y + 1;
if (xi >= 0 && xi < tilesAcross && yi >=0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
val16 &= ~(0xFF);
val16 |= (tileIndex << 4);
val16 |= (tileIndex);
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
xi = x + 1;
yi = y + 1;
if (xi >= 0 && xi < tilesAcross && yi >=0 && yi < tilesAcross) {
val16 = getUint16bits( tileMap[yi * tilesAcross + xi] );
val16 &= ~(0xF);
val16 |= tileIndex;
testVal = setUint16bits(val16);
if (testVal != 0xFFFFFFFF) tileMap[yi * tilesAcross + xi] = testVal;
}
}
}
//package com.nodename.Delaunay
//{
//public
final class LR
{
public static const LEFT:LR = new LR(PrivateConstructorEnforcer, "left");
public static const RIGHT:LR = new LR(PrivateConstructorEnforcer, "right");
private var _name:String;
public function LR(lock:Class, name:String)
{
if (lock != PrivateConstructorEnforcer)
{
throw new Error("Illegal constructor access");
}
_name = name;
}
public static function other(leftRight:LR):LR
{
return leftRight == LEFT ? RIGHT : LEFT;
}
public function toString():String
{
return _name;
}
}
//}
//}//package {
//import com.nodename.geom.LineSegment;
import flash.display.BitmapData;
import flash.display.CapsStyle;
import flash.display.Graphics;
import flash.display.LineScaleMode;
import flash.display.Sprite;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.utils.Dictionary;
import flash.geom.Point;
/*public*/ class LineSegment extends Object
{
public static function compareLengths_MAX(segment0:LineSegment, segment1:LineSegment):Number
{
var length0:Number = Point.distance(segment0.p0, segment0.p1);
var length1:Number = Point.distance(segment1.p0, segment1.p1);
if (length0 < length1)
{
return 1;
}
if (length0 > length1)
{
return -1;
}
return 0;
}
public static function compareLengths(edge0:LineSegment, edge1:LineSegment):Number
{
return - compareLengths_MAX(edge0, edge1);
}
public var p0:Point;
public var p1:Point;
public function LineSegment(p0:Point, p1:Point)
{
super();
this.p0 = p0;
this.p1 = p1;
}
}
//}
//package com.nodename.Delaunay
//{
import __AS3__.vec.Vector;
import flash.utils.Dictionary;
//package {
//import com.nodename.geom.Circle;
//import com.nodename.geom.LineSegment;
import flash.display.BitmapData;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.utils.Dictionary;
/*public*/ class Voronoi
{
private var _sites:SiteList;
private var _sitesIndexedByLocation:Dictionary;
private var _triangles:Vector.<Triangle>;
private var _edges:Vector.<DEdge>;
private var _plotBounds:Rectangle;
public function get plotBounds():Rectangle
{
return _plotBounds;
}
public function dispose():void
{
var i:int, n:int;
if (_sites)
{
_sites.dispose();
_sites = null;
}
if (_triangles)
{
n = _triangles.length;
for (i = 0; i < n; ++i)
{
_triangles[i].dispose();
}
_triangles.length = 0;
_triangles = null;
}
if (_edges)
{
n = _edges.length;
for (i = 0; i < n; ++i)
{
_edges[i].dispose();
}
_edges.length = 0;
_edges = null;
}
_plotBounds = null;
_sitesIndexedByLocation = null;
}
public function Voronoi(points:Vector.<Point>, colors:Vector.<uint>, plotBounds:Rectangle)
{
_sites = new SiteList();
_sitesIndexedByLocation = new Dictionary(true);
addSites(points, colors);
_plotBounds = plotBounds;
_triangles = new Vector.<Triangle>();
_edges = new Vector.<DEdge>();
fortunesAlgorithm();
}
private function addSites(points:Vector.<Point>, colors:Vector.<uint>):void
{
var length:uint = points.length;
for (var i:uint = 0; i < length; ++i)
{
addSite(points[i], colors ? colors[i] : 0, i);
}
}
private function addSite(p:Point, color:uint, index:int):void
{
var weight:Number = Math.random() * 100;
var site:Site = Site.create(p, index, weight, color);
_sites.push(site);
_sitesIndexedByLocation[p] = site;
}
public function edges():Vector.<DEdge>
{
return _edges;
}
public function region(p:Point):Vector.<Point>
{
var site:Site = _sitesIndexedByLocation[p];
if (!site)
{
return new Vector.<Point>();
}
return site.region(_plotBounds);
}
public function neighborSitesForSite(coord:Point):Vector.<Point>
{
var points:Vector.<Point> = new Vector.<Point>();
var site:Site = _sitesIndexedByLocation[coord];
if (!site)
{
return points;
}
var sites:Vector.<Site> = site.neighborSites();
var neighbor:Site;
for each (neighbor in sites)
{
points.push(neighbor.coord);
}
return points;
}
public function circles():Vector.<Circle>
{
return _sites.circles();
}
public function voronoiBoundaryForSite(coord:Point):Vector.<LineSegment>
{
return visibleLineSegments(selectEdgesForSitePoint(coord, _edges));
}
public function delaunayLinesForSite(coord:Point):Vector.<LineSegment>
{
return delaunayLinesForEdges(selectEdgesForSitePoint(coord, _edges));
}
public function voronoiDiagram():Vector.<LineSegment>
{
return visibleLineSegments(_edges);
}
public function delaunayTriangulation(keepOutMask:BitmapData = null):Vector.<LineSegment>
{
return delaunayLinesForEdges(selectNonIntersectingEdges(keepOutMask, _edges));
}
public function hull():Vector.<LineSegment>
{
return delaunayLinesForEdges(hullEdges());
}
private function hullEdges():Vector.<DEdge>
{
return _edges.filter(myTest);
function myTest(edge:DEdge, index:int, vector:Vector.<DEdge>):Boolean
{
return (edge.isPartOfConvexHull());
}
}
public function hullPointsInOrder():Vector.<Point>
{
var hullEdges:Vector.<DEdge> = hullEdges();
var points:Vector.<Point> = new Vector.<Point>();
if (hullEdges.length == 0)
{
return points;
}
var reorderer:EdgeReorderer = new EdgeReorderer(hullEdges, Site);
hullEdges = reorderer.edges;
var orientations:Vector.<LR> = reorderer.edgeOrientations;
reorderer.dispose();
var orientation:LR;
var n:int = hullEdges.length;
for (var i:int = 0; i < n; ++i)
{
var edge:DEdge = hullEdges[i];
orientation = orientations[i];
points.push(edge.site(orientation).coord);
}
return points;
}
function kruskal(lineSegments:Vector.<LineSegment>, type:String = "minimum"):Vector.<LineSegment>
{
var nodes:Dictionary = new Dictionary(true);
var mst:Vector.<LineSegment> = new Vector.<LineSegment>();
var nodePool:Vector.<Node> = Node.pool;
switch (type)
{
// note that the compare functions are the reverse of what you'd expect
// because (see below) we traverse the lineSegments in reverse order for speed
case "maximum":
lineSegments.sort(LineSegment.compareLengths);
break;
default:
lineSegments.sort(LineSegment.compareLengths_MAX);
break;
}
for (var i:int = lineSegments.length; --i > -1;)
{
var lineSegment:LineSegment = lineSegments[i];
var node0:Node = nodes[lineSegment.p0];
var rootOfSet0:Node;
if (node0 == null)
{
node0 = nodePool.length > 0 ? nodePool.pop() : new Node();
// intialize the node:
rootOfSet0 = node0.parent = node0;
node0.treeSize = 1;
nodes[lineSegment.p0] = node0;
}
else
{
rootOfSet0 = find(node0);
}
var node1:Node = nodes[lineSegment.p1];
var rootOfSet1:Node;
if (node1 == null)
{
node1 = nodePool.length > 0 ? nodePool.pop() : new Node();
// intialize the node:
rootOfSet1 = node1.parent = node1;
node1.treeSize = 1;
nodes[lineSegment.p1] = node1;
}
else
{
rootOfSet1 = find(node1);
}
if (rootOfSet0 != rootOfSet1) // nodes not in same set
{
mst.push(lineSegment);
// merge the two sets:
var treeSize0:int = rootOfSet0.treeSize;
var treeSize1:int = rootOfSet1.treeSize;
if (treeSize0 >= treeSize1)
{
// set0 absorbs set1:
rootOfSet1.parent = rootOfSet0;
rootOfSet0.treeSize += treeSize1;
}
else
{
// set1 absorbs set0:
rootOfSet0.parent = rootOfSet1;
rootOfSet1.treeSize += treeSize0;
}
}
}
for each (var node:Node in nodes)
{
nodePool.push(node);
}
return mst;
}
function find(node:Node):Node
{
if (node.parent == node)
{
return node;
}
else
{
var root:Node = find(node.parent);
// this line is just to speed up subsequent finds by keeping the tree depth low:
node.parent = root;
return root;
}
}
public function spanningTree(type:String = "minimum", keepOutMask:BitmapData = null):Vector.<LineSegment>
{
var edges:Vector.<DEdge> = selectNonIntersectingEdges(keepOutMask, _edges);
var segments:Vector.<LineSegment> = delaunayLinesForEdges(edges);
return kruskal(segments, type);
}
public function regions():Vector.<Vector.<Point>>
{
return _sites.regions(_plotBounds);
}
public function siteColors(referenceImage:BitmapData = null):Vector.<uint>
{
return _sites.siteColors(referenceImage);
}
public function nearestSitePoint(proximityMap:BitmapData, x:Number, y:Number):Point
{
return _sites.nearestSitePoint(proximityMap, x, y);
}
public function siteCoords():Vector.<Point>
{
return _sites.siteCoords();
}
private function fortunesAlgorithm():void
{
var newSite:Site, bottomSite:Site, topSite:Site, tempSite:Site;
var v:Vertex, vertex:Vertex;
var newintstar:Point;
var leftRight:LR;
var lbnd:Halfedge, rbnd:Halfedge, llbnd:Halfedge, rrbnd:Halfedge, bisector:Halfedge;
var edge:DEdge;
var dataBounds:Rectangle = _sites.getSitesBounds();
var sqrt_nsites:int = int(Math.sqrt(_sites.length + 4));
var heap:HalfedgePriorityQueue = new HalfedgePriorityQueue(dataBounds.y, dataBounds.height, sqrt_nsites);
var edgeList:EdgeList = new EdgeList(dataBounds.x, dataBounds.width, sqrt_nsites);
var halfEdges:Vector.<Halfedge> = new Vector.<Halfedge>();
var vertices:Vector.<Vertex> = new Vector.<Vertex>();
var bottomMostSite:Site = _sites.next();
newSite = _sites.next();
for (;;)
{
if (heap.empty() == false)
{
newintstar = heap.min();
}
if (newSite != null
&& (heap.empty() || compareByYThenX(newSite, newintstar) < 0))
{
lbnd = edgeList.edgeListLeftNeighbor(newSite.coord);
rbnd = lbnd.edgeListRightNeighbor;
bottomSite = rightRegion(lbnd);
edge = DEdge.createBisectingEdge(bottomSite, newSite);
_edges.push(edge);
bisector = Halfedge.create(edge, LR.LEFT);
halfEdges.push(bisector);
edgeList.insert(lbnd, bisector);
if ((vertex = Vertex.intersect(lbnd, bisector)) != null)
{
vertices.push(vertex);
heap.remove(lbnd);
lbnd.vertex = vertex;
lbnd.ystar = vertex.y + newSite.dist(vertex);
heap.insert(lbnd);
}
lbnd = bisector;
bisector = Halfedge.create(edge, LR.RIGHT);
halfEdges.push(bisector);
edgeList.insert(lbnd, bisector);
if ((vertex = Vertex.intersect(bisector, rbnd)) != null)
{
vertices.push(vertex);
bisector.vertex = vertex;
bisector.ystar = vertex.y + newSite.dist(vertex);
heap.insert(bisector);
}
newSite = _sites.next();
}
else if (heap.empty() == false)
{
lbnd = heap.extractMin();
llbnd = lbnd.edgeListLeftNeighbor;
rbnd = lbnd.edgeListRightNeighbor;
rrbnd = rbnd.edgeListRightNeighbor;
bottomSite = leftRegion(lbnd);
topSite = rightRegion(rbnd);
v = lbnd.vertex;
v.setIndex();
lbnd.edge.setVertex(lbnd.leftRight, v);
rbnd.edge.setVertex(rbnd.leftRight, v);
edgeList.remove(lbnd);
heap.remove(rbnd);
edgeList.remove(rbnd);
leftRight = LR.LEFT;
if (bottomSite.y > topSite.y)
{
tempSite = bottomSite; bottomSite = topSite; topSite = tempSite; leftRight = LR.RIGHT;
}
edge = DEdge.createBisectingEdge(bottomSite, topSite);
_edges.push(edge);
bisector = Halfedge.create(edge, leftRight);
halfEdges.push(bisector);
edgeList.insert(llbnd, bisector);
edge.setVertex(LR.other(leftRight), v);
if ((vertex = Vertex.intersect(llbnd, bisector)) != null)
{
vertices.push(vertex);
heap.remove(llbnd);
llbnd.vertex = vertex;
llbnd.ystar = vertex.y + bottomSite.dist(vertex);
heap.insert(llbnd);
}
if ((vertex = Vertex.intersect(bisector, rrbnd)) != null)
{
vertices.push(vertex);
bisector.vertex = vertex;
bisector.ystar = vertex.y + bottomSite.dist(vertex);
heap.insert(bisector);
}
}
else
{
break;
}
}
heap.dispose();
edgeList.dispose();
for each (var halfEdge:Halfedge in halfEdges)
{
halfEdge.reallyDispose();
}
halfEdges.length = 0;
for each (edge in _edges)
{
edge.clipVertices(_plotBounds);
}
for each (vertex in vertices)
{
vertex.dispose();
}
vertices.length = 0;
function leftRegion(he:Halfedge):Site
{
var edge:DEdge = he.edge;
if (edge == null)
{
return bottomMostSite;
}
return edge.site(he.leftRight);
}
function rightRegion(he:Halfedge):Site
{
var edge:DEdge = he.edge;
if (edge == null)
{
return bottomMostSite;
}
return edge.site(LR.other(he.leftRight));
}
}
internal static function compareByYThenX(s1:Site, s2:*):Number
{
if (s1.y < s2.y) return -1;
if (s1.y > s2.y) return 1;
if (s1.x < s2.x) return -1;
if (s1.x > s2.x) return 1;
return 0;
}
}
//}
//package {
/*public*/ class Watersheds {
public var lowestCorner:Array = [];
public var watersheds:Array = [];
public function createWatersheds(map:Map):void {
var p:Center, q:Corner, s:Corner;
for each (p in map.centers) {
s = null;
for each (q in p.corners) {
if (s == null || q.elevation < s.elevation) {
s = q;
}
}
lowestCorner[p.index] = (s == null)? -1 : s.index;
watersheds[p.index] = (s == null)? -1 : (s.watershed == null)? -1 : s.watershed.index;
}
}
}
//}
//package {
import flash.geom.Point;
/*public*/ class Edge {
public var index:int;
public var d0:Center, d1:Center;
public var v0:Corner, v1:Corner;
public var midpoint:Point;
public var river:int;
}
//}
//package {
import flash.geom.Point;
/*public*/ class Center {
public var index:int;
public var point:Point;
public var water:Boolean;
public var ocean:Boolean;
public var coast:Boolean;
public var border:Boolean;
public var biome:String;
public var elevation:Number;
public var moisture:Number;
public var neighbors:Vector.<Center>;
public var borders:Vector.<Edge>;
public var corners:Vector.<Corner>;
}
//}
//package {
import flash.geom.Point;
/*public*/ class Corner {
public var index:int;
public var point:Point;
public var ocean:Boolean;
public var water:Boolean;
public var coast:Boolean;
public var border:Boolean;
public var elevation:Number;
public var moisture:Number;
public var touches:Vector.<Center>;
public var protrudes:Vector.<Edge>;
public var adjacent:Vector.<Corner>;
public var river:int;
public var downslope:Corner;
public var watershed:Corner;
public var watershed_size:int;
}
//}
//package {
/*public*/ class Lava {
static public var FRACTION_LAVA_FISSURES:Number = 0.2;
public var lava:Array = [];
public function createLava(map:Map, randomDouble:Function):void {
var edge:Edge;
for each (edge in map.edges) {
if (!edge.river && !edge.d0.water && !edge.d1.water
&& edge.d0.elevation > 0.8 && edge.d1.elevation > 0.8
&& edge.d0.moisture < 0.3 && edge.d1.moisture < 0.3
&& randomDouble() < FRACTION_LAVA_FISSURES) {
lava[edge.index] = true;
}
}
}
}
//}
//package {
//import com.sakri.utils.BitmapDataUtil;
//import com.sakri.utils.BitmapShapeExtractor;
//import com.sakri.utils.ExtractedShapeCollection;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.EventDispatcher;
import flash.geom.Point;
import flash.text.TextField;
import flash.utils.ByteArray;
import flash.utils.Dictionary;
import jp.progression.commands.Func;
import jp.progression.commands.lists.LoaderList;
import jp.progression.commands.lists.SerialList;
import jp.progression.commands.Wait;
/*public*/ class BiomeApplicator32 extends EventDispatcher
{
public var tileBitMap:Vector.<uint>;
public var tileMap:BitmapData;
public var extractedShapes:ExtractedShapeCollection;
public var painter:BiomePainter32;
public var tilesAcross:int;
public var textureList:Array = [
["d"], ["OCEAN"],
["d"],["RIVER","MARSH"],
["f"],["SUBTROPICAL_DESERT"],
["h"],["TEMPERATE_DESERT"],
["q"],["SHRUBLAND","GRASSLAND"],
["n"],["TEMPERATE_RAIN_FOREST","TEMPERATE_DECIDUOUS_FOREST"],
["s"],["COAST","LAKESHORE","LAKE"],
["r"], ["LAVA","BEACH"],
["c"], ["TROPICAL_SEASONAL_FOREST","TROPICAL_RAIN_FOREST"],
["k"], ["TAIGA","SCORCHED"],
["g"], ["BARE", "ROAD1", "ROAD2", "ROAD3", "BRIDGE"],
["i"], ["SNOW","TUNDRA","ICE"]
];
public var atlasReadString:String = "dfhqnsrckgi";
public var atlasTilesAcrossH:int = 4;
public var atlasTilesAcrossV:int = 4;
private var textureDict:Dictionary;
public static var LOOKUP_STRINGS:Vector.<String>;
private var _serialList:SerialList;
public function BiomeApplicator32()
{
displayField.autoSize = "left";
}
private var counter:int = 0;
private function getDummyColor(colorDebug:*):int {
throw new Error("Texture not supported !"+colorDebug);
var result:int = counter + 1;
counter++;
if (counter >= textureList.length) counter = 0;
return result;
}
public function processBiomes(b:ByteArray, tilesAcross:int, testSpr:Sprite=null):void {
}
private var _currentLayerIndex:int;
private function completedLayer():void
{
extractedShapes.dispose();
}
private function scanlineCheck(shape:BitmapData, y:int, colorDisc:uint = 0):Boolean {
for (var x:int = 0; x < shape.width; x++) {
if ( shape.getPixel(x, y) != colorDisc ) {
if (shape.getPixel(shape.width - 1, y) != colorDisc) {
throw new Error("FAILED2: Not empty at end of line!");
}
return true;
}
};
throw new Error("FAILED");
return false;
}
private function notifyComplete():void
{
tileMap.setVector( tileMap.rect, tileBitMap);
displayField.text = "Process complete:" +biomeCount + " biomes. "+painter.errorCount+" potential errors.";
dispatchEvent( new Event(Event.COMPLETE) );
}
public var displayField:TextField = new TextField();
public var biomeCount:int=0;
private var count:int = 0;
private var _serialColorIndex:int;
private var _serialAtlasIndex:int;
public var testbitMap:BitmapData;
private function initProcess(tilesAcross:int):void
{
painter = new BiomePainter32(atlasTilesAcrossH, atlasTilesAcrossV);
if (LOOKUP_STRINGS == null) LOOKUP_STRINGS = mapgen2.getExportIndexLookup();
if (textureDict == null) calculateTextureDictionary();
this.tilesAcross = tilesAcross;
}
public function getNewBitmapData():BitmapData {
var bmpData:BitmapData = new BitmapData(tilesAcross, tilesAcross, false, 0);
bmpData.setVector(bmpData.rect, tileBitMap);
return bmpData;
}
public function calculateTextureDictionary():void
{
textureDict = new Dictionary();
var len:int = textureList.length;
var count:int = 1;
for (var i:int = 0; i < len; i+=2) {
var keys:Array = textureList[i + 1];
for each(var k:String in keys) {
textureDict[k] =count;
}
if (textureList[i][0] is String) {
var atlasIndex:int = atlasReadString.indexOf( textureList[i][0] );
if (atlasIndex < 0) throw new Error("Could not find atlas index from string under texture dictionary!");
textureList[i][0] = atlasIndex;
}
count++;
}
}
public function dispose():void
{
tileMap.dispose();
extractedShapes.dispose();
}
public function get serialList():SerialList
{
return _serialList;
}
}
//}
//package {
import flash.geom.*;
import flash.utils.Dictionary;
import flash.utils.getTimer;
import flash.system.System;
//import com.nodename.geom.LineSegment;
//import com.nodename.Delaunay.Voronoi;
//import de.polygonal.math.PM_PRNG;
/*public*/ class IslandShape {
static public var ISLAND_FACTOR:Number = 1.07;
static public function makeRadial(seed:int):Function {
var islandRandom:PM_PRNG = new PM_PRNG();
islandRandom.seed = seed;
var bumps:int = islandRandom.nextIntRange(1, 6);
var startAngle:Number = islandRandom.nextDoubleRange(0, 2*Math.PI);
var dipAngle:Number = islandRandom.nextDoubleRange(0, 2*Math.PI);
var dipWidth:Number = islandRandom.nextDoubleRange(0.2, 0.7);
function inside(q:Point):Boolean {
var angle:Number = Math.atan2(q.y, q.x);
var length:Number = 0.5 * (Math.max(Math.abs(q.x), Math.abs(q.y)) + q.length);
var r1:Number = 0.5 + 0.40*Math.sin(startAngle + bumps*angle + Math.cos((bumps+3)*angle));
var r2:Number = 0.7 - 0.20*Math.sin(startAngle + bumps*angle - Math.sin((bumps+2)*angle));
if (Math.abs(angle - dipAngle) < dipWidth
|| Math.abs(angle - dipAngle + 2*Math.PI) < dipWidth
|| Math.abs(angle - dipAngle - 2*Math.PI) < dipWidth) {
r1 = r2 = 0.2;
}
return (length < r1 || (length > r1*ISLAND_FACTOR && length < r2));
}
return inside;
}
static public function makePerlin(seed:int):Function {
var perlin:BitmapData = new BitmapData(256, 256);
perlin.perlinNoise(64, 64, 8, seed, false, true);
return function (q:Point):Boolean {
var c:Number = (perlin.getPixel(int((q.x+1)*128), int((q.y+1)*128)) & 0xff) / 255.0;
return c > (0.3+0.3*q.length*q.length);
};
}
static public function makeSquare(seed:int):Function {
return function (q:Point):Boolean {
return true;
};
}
static public function makeBlob(seed:int):Function {
return function(q:Point):Boolean {
var eye1:Boolean = new Point(q.x-0.2, q.y/2+0.2).length < 0.05;
var eye2:Boolean = new Point(q.x+0.2, q.y/2+0.2).length < 0.05;
var body:Boolean = q.length < 0.8 - 0.18*Math.sin(5*Math.atan2(q.y, q.x));
return body && !eye1 && !eye2;
};
}
}
//package {
/*public*/ class Roads {
public var road:Array;
public var roadConnections:Array;
public function Roads() {
road = [];
roadConnections = [];
}
public function createRoads(map:Map):void {
var queue:Array = [];
var p:Center, q:Corner, r:Center, edge:Edge, newLevel:int;
var elevationThresholds:Array = [0, 0.05, 0.37, 0.64];
var cornerContour:Array = [];
var centerContour:Array = [];
for each (p in map.centers) {
if (p.coast || p.ocean) {
centerContour[p.index] = 1;
queue.push(p);
}
}
while (queue.length > 0) {
p = queue.shift();
for each (r in p.neighbors) {
newLevel = centerContour[p.index] || 0;
while (r.elevation > elevationThresholds[newLevel] && !r.water) {
newLevel += 1;
}
if (newLevel < (centerContour[r.index] || 999)) {
centerContour[r.index] = newLevel;
queue.push(r);
}
}
}
for each (p in map.centers) {
for each (q in p.corners) {
cornerContour[q.index] = Math.min(cornerContour[q.index] || 999,
centerContour[p.index] || 999);
}
}
for each (p in map.centers) {
for each (edge in p.borders) {
if (edge.v0 && edge.v1
&& cornerContour[edge.v0.index] != cornerContour[edge.v1.index]) {
road[edge.index] = Math.min(cornerContour[edge.v0.index],
cornerContour[edge.v1.index]);
if (!roadConnections[p.index]) {
roadConnections[p.index] = [];
}
roadConnections[p.index].push(edge);
}
}
}
}
}
//}
//package com.nodename.Delaunay
//{
import flash.display.BitmapData;
import flash.display.CapsStyle;
import flash.display.Graphics;
import flash.display.LineScaleMode;
import flash.display.Sprite;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.utils.Dictionary;
/**
* The line segment connecting the two Sites is part of the Delaunay triangulation;
* the line segment connecting the two Vertices is part of the Voronoi diagram
* @author ashaw
*
*/
//public
final class DEdge
{
private static var _pool:Vector.<DEdge> = new Vector.<DEdge>();
/**
* This is the only way to create a new DEdge
* @param site0
* @param site1
* @return
*
*/
internal static function createBisectingEdge(site0:Site, site1:Site):DEdge
{
var dx:Number, dy:Number, absdx:Number, absdy:Number;
var a:Number, b:Number, c:Number;
dx = site1.x - site0.x;
dy = site1.y - site0.y;
absdx = dx > 0 ? dx : -dx;
absdy = dy > 0 ? dy : -dy;
c = site0.x * dx + site0.y * dy + (dx * dx + dy * dy) * 0.5;
if (absdx > absdy)
{
a = 1.0; b = dy/dx; c /= dx;
}
else
{
b = 1.0; a = dx/dy; c /= dy;
}
var edge:DEdge = DEdge.create();
edge.leftSite = site0;
edge.rightSite = site1;
site0.addEdge(edge);
site1.addEdge(edge);
edge._leftVertex = null;
edge._rightVertex = null;
edge.a = a; edge.b = b; edge.c = c;
//trace("createBisectingEdge: a ", edge.a, "b", edge.b, "c", edge.c);
return edge;
}
private static function create():DEdge
{
var edge:DEdge;
if (_pool.length > 0)
{
edge = _pool.pop();
edge.init();
}
else
{
edge = new DEdge(PrivateConstructorEnforcer);
}
return edge;
}
private static const LINESPRITE:Sprite = new Sprite();
private static const GRAPHICS:Graphics = LINESPRITE.graphics;
private var _delaunayLineBmp:BitmapData;
internal function get delaunayLineBmp():BitmapData
{
if (!_delaunayLineBmp)
{
_delaunayLineBmp = makeDelaunayLineBmp();
}
return _delaunayLineBmp;
}
// making this available to Voronoi; running out of memory in AIR so I cannot cache the bmp
internal function makeDelaunayLineBmp():BitmapData
{
var p0:Point = leftSite.coord;
var p1:Point = rightSite.coord;
GRAPHICS.clear();
// clear() resets line style back to undefined!
GRAPHICS.lineStyle(0, 0, 1.0, false, LineScaleMode.NONE, CapsStyle.NONE);
GRAPHICS.moveTo(p0.x, p0.y);
GRAPHICS.lineTo(p1.x, p1.y);
var w:int = int(Math.ceil(Math.max(p0.x, p1.x)));
if (w < 1)
{
w = 1;
}
var h:int = int(Math.ceil(Math.max(p0.y, p1.y)));
if (h < 1)
{
h = 1;
}
var bmp:BitmapData = new BitmapData(w, h, true, 0);
bmp.draw(LINESPRITE);
return bmp;
}
public function delaunayLine():LineSegment
{
// draw a line connecting the input Sites for which the edge is a bisector:
return new LineSegment(leftSite.coord, rightSite.coord);
}
public function voronoiEdge():LineSegment
{
if (!visible) return new LineSegment(null, null);
return new LineSegment(_clippedVertices[LR.LEFT],
_clippedVertices[LR.RIGHT]);
}
private static var _nedges:int = 0;
internal static const DELETED:DEdge = new DEdge(PrivateConstructorEnforcer);
// the equation of the edge: ax + by = c
internal var a:Number, b:Number, c:Number;
// the two Voronoi vertices that the edge connects
// (if one of them is null, the edge extends to infinity)
private var _leftVertex:Vertex;
internal function get leftVertex():Vertex
{
return _leftVertex;
}
private var _rightVertex:Vertex;
internal function get rightVertex():Vertex
{
return _rightVertex;
}
internal function vertex(leftRight:LR):Vertex
{
return (leftRight == LR.LEFT) ? _leftVertex : _rightVertex;
}
internal function setVertex(leftRight:LR, v:Vertex):void
{
if (leftRight == LR.LEFT)
{
_leftVertex = v;
}
else
{
_rightVertex = v;
}
}
internal function isPartOfConvexHull():Boolean
{
return (_leftVertex == null || _rightVertex == null);
}
public function sitesDistance():Number
{
return Point.distance(leftSite.coord, rightSite.coord);
}
public static function compareSitesDistances_MAX(edge0:DEdge, edge1:DEdge):Number
{
var length0:Number = edge0.sitesDistance();
var length1:Number = edge1.sitesDistance();
if (length0 < length1)
{
return 1;
}
if (length0 > length1)
{
return -1;
}
return 0;
}
public static function compareSitesDistances(edge0:DEdge, edge1:DEdge):Number
{
return - compareSitesDistances_MAX(edge0, edge1);
}
// Once clipVertices() is called, this Dictionary will hold two Points
// representing the clipped coordinates of the left and right ends...
private var _clippedVertices:Dictionary;
internal function get clippedEnds():Dictionary
{
return _clippedVertices;
}
// unless the entire DEdge is outside the bounds.
// In that case visible will be false:
internal function get visible():Boolean
{
return _clippedVertices != null;
}
// the two input Sites for which this DEdge is a bisector:
private var _sites:Dictionary;
internal function set leftSite(s:Site):void
{
_sites[LR.LEFT] = s;
}
internal function get leftSite():Site
{
return _sites[LR.LEFT];
}
internal function set rightSite(s:Site):void
{
_sites[LR.RIGHT] = s;
}
internal function get rightSite():Site
{
return _sites[LR.RIGHT] as Site;
}
internal function site(leftRight:LR):Site
{
return _sites[leftRight] as Site;
}
private var _edgeIndex:int;
public function dispose():void
{
if (_delaunayLineBmp)
{
_delaunayLineBmp.dispose();
_delaunayLineBmp = null;
}
_leftVertex = null;
_rightVertex = null;
if (_clippedVertices)
{
_clippedVertices[LR.LEFT] = null;
_clippedVertices[LR.RIGHT] = null;
_clippedVertices = null;
}
_sites[LR.LEFT] = null;
_sites[LR.RIGHT] = null;
_sites = null;
_pool.push(this);
}
public function DEdge(lock:Class)
{
if (lock != PrivateConstructorEnforcer)
{
throw new Error("DEdge: constructor is private");
}
_edgeIndex = _nedges++;
init();
}
private function init():void
{
_sites = new Dictionary(true);
}
public function toString():String
{
return "DEdge " + _edgeIndex + "; sites " + _sites[LR.LEFT] + ", " + _sites[LR.RIGHT]
+ "; endVertices " + (_leftVertex ? _leftVertex.vertexIndex : "null") + ", "
+ (_rightVertex ? _rightVertex.vertexIndex : "null") + "::";
}
/**
* Set _clippedVertices to contain the two ends of the portion of the Voronoi edge that is visible
* within the bounds. If no part of the DEdge falls within the bounds, leave _clippedVertices null.
* @param bounds
*
*/
internal function clipVertices(bounds:Rectangle):void
{
var xmin:Number = bounds.x;
var ymin:Number = bounds.y;
var xmax:Number = bounds.right;
var ymax:Number = bounds.bottom;
var vertex0:Vertex, vertex1:Vertex;
var x0:Number, x1:Number, y0:Number, y1:Number;
if (a == 1.0 && b >= 0.0)
{
vertex0 = _rightVertex;
vertex1 = _leftVertex;
}
else
{
vertex0 = _leftVertex;
vertex1 = _rightVertex;
}
if (a == 1.0)
{
y0 = ymin;
if (vertex0 != null && vertex0.y > ymin)
{
y0 = vertex0.y;
}
if (y0 > ymax)
{
return;
}
x0 = c - b * y0;
y1 = ymax;
if (vertex1 != null && vertex1.y < ymax)
{
y1 = vertex1.y;
}
if (y1 < ymin)
{
return;
}
x1 = c - b * y1;
if ((x0 > xmax && x1 > xmax) || (x0 < xmin && x1 < xmin))
{
return;
}
if (x0 > xmax)
{
x0 = xmax; y0 = (c - x0)/b;
}
else if (x0 < xmin)
{
x0 = xmin; y0 = (c - x0)/b;
}
if (x1 > xmax)
{
x1 = xmax; y1 = (c - x1)/b;
}
else if (x1 < xmin)
{
x1 = xmin; y1 = (c - x1)/b;
}
}
else
{
x0 = xmin;
if (vertex0 != null && vertex0.x > xmin)
{
x0 = vertex0.x;
}
if (x0 > xmax)
{
return;
}
y0 = c - a * x0;
x1 = xmax;
if (vertex1 != null && vertex1.x < xmax)
{
x1 = vertex1.x;
}
if (x1 < xmin)
{
return;
}
y1 = c - a * x1;
if ((y0 > ymax && y1 > ymax) || (y0 < ymin && y1 < ymin))
{
return;
}
if (y0 > ymax)
{
y0 = ymax; x0 = (c - y0)/a;
}
else if (y0 < ymin)
{
y0 = ymin; x0 = (c - y0)/a;
}
if (y1 > ymax)
{
y1 = ymax; x1 = (c - y1)/a;
}
else if (y1 < ymin)
{
y1 = ymin; x1 = (c - y1)/a;
}
}
_clippedVertices = new Dictionary(true);
if (vertex0 == _leftVertex)
{
_clippedVertices[LR.LEFT] = new Point(x0, y0);
_clippedVertices[LR.RIGHT] = new Point(x1, y1);
}
else
{
_clippedVertices[LR.RIGHT] = new Point(x0, y0);
_clippedVertices[LR.LEFT] = new Point(x1, y1);
}
}
}
//}
//package {
import flash.geom.Point;
//import de.polygonal.math.PM_PRNG;
/*public*/ class NoisyEdges {
static public var NOISY_LINE_TRADEOFF:Number = 0.5;
public var path0:Array = [];
public var path1:Array = [];
public function NoisyEdges() {
}
public function buildNoisyEdges(map:Map, lava:Lava, random:PM_PRNG):void {
var p:Center, edge:Edge;
for each (p in map.centers) {
for each (edge in p.borders) {
if (edge.d0 && edge.d1 && edge.v0 && edge.v1 && !path0[edge.index]) {
var f:Number = NOISY_LINE_TRADEOFF;
var t:Point = Point.interpolate(edge.v0.point, edge.d0.point, f);
var q:Point = Point.interpolate(edge.v0.point, edge.d1.point, f);
var r:Point = Point.interpolate(edge.v1.point, edge.d0.point, f);
var s:Point = Point.interpolate(edge.v1.point, edge.d1.point, f);
var minLength:int = 10;
if (edge.d0.biome != edge.d1.biome) minLength = 3;
if (edge.d0.ocean && edge.d1.ocean) minLength = 100;
if (edge.d0.coast || edge.d1.coast) minLength = 1;
if (edge.river || lava.lava[edge.index]) minLength = 1;
path0[edge.index] = buildNoisyLineSegments(random, edge.v0.point, t, edge.midpoint, q, minLength);
path1[edge.index] = buildNoisyLineSegments(random, edge.v1.point, s, edge.midpoint, r, minLength);
}
}
}
}
static public function buildNoisyLineSegments(random:PM_PRNG, A:Point, B:Point, C:Point, D:Point, minLength:Number):Vector.<Point> {
var points:Vector.<Point> = new Vector.<Point>();
function subdivide(A:Point, B:Point, C:Point, D:Point):void {
if (A.subtract(C).length < minLength || B.subtract(D).length < minLength) {
return;
}
var p:Number = random.nextDoubleRange(0.2, 0.8);
var q:Number = random.nextDoubleRange(0.2, 0.8);
var E:Point = Point.interpolate(A, D, p);
var F:Point = Point.interpolate(B, C, p);
var G:Point = Point.interpolate(A, B, q);
var I:Point = Point.interpolate(D, C, q);
var H:Point = Point.interpolate(E, F, q);
var s:Number = 1.0 - random.nextDoubleRange(-0.4, +0.4);
var t:Number = 1.0 - random.nextDoubleRange(-0.4, +0.4);
subdivide(A, Point.interpolate(G, B, s), H, Point.interpolate(E, D, t));
points.push(H);
subdivide(H, Point.interpolate(F, C, s), C, Point.interpolate(I, D, t));
}
points.push(A);
subdivide(A, B, C, D);
points.push(C);
return points;
}
}
//}
//package {
/*public*/ class Smoothing {
static public const functionsList:Array =[
{ data: Smoothing.linear, label:'<none> (linear)'},
{ data: Smoothing.smooth3, label:'smooth3'},
{ data: Smoothing.smooth5, label:'smooth5'},
{ data: Smoothing.quadIn, label:'quadIn'},
{ data: Smoothing.quadOut, label:'quadOut'},
{ data: Smoothing.quadInOut, label:'quadInOut'},
{ data: Smoothing.cubicIn, label:'cubicIn'},
{ data: Smoothing.cubicOut, label:'cubicOut'},
{ data: Smoothing.cubicInOut, label:'cubicInOut'},
{ data: Smoothing.quartIn, label:'quartIn'},
{ data: Smoothing.quartOut, label:'quartOut'},
{ data: Smoothing.quartInOut, label:'quartInOut'},
{ data: Smoothing.quintIn, label:'quintIn'},
{ data: Smoothing.quintOut, label:'quintOut'},
{ data: Smoothing.quintInOut, label:'quintInOut'},
{ data: Smoothing.expoIn, label:'expoIn'},
{ data: Smoothing.expoOut, label:'expoOut'},
{ data: Smoothing.expoInOut, label:'expoInOut'},
{ data: Smoothing.sinIn, label:'sinIn'},
{ data: Smoothing.sinOut, label:'sinOut'},
{ data: Smoothing.sinInOut, label:'sinInOut'},
{ data: Smoothing.bounceIn, label:'bounceIn'},
{ data: Smoothing.bounceOut, label:'bounceOut'},
{ data: Smoothing.bounceInOut, label:'bounceInOut'},
{ data: Smoothing.circIn, label:'circIn'},
{ data: Smoothing.circOut, label:'circOut'},
{ data: Smoothing.circInOut, label:'circInOut'},
];
static public function smooth5(t:Number):Number {
return t * t * t * (t * (t * 6 - 15) + 10);
}
static public function smooth3(t:Number):Number {
return t * t * (3 - 2 * t);
}
static public function linear(t:Number):Number {
return t;
}
static public function quadIn (t:Number):Number {
return t * t;
}
static public function quadOut (t:Number):Number {
return -t * (t-2);
}
static public function quadInOut (t:Number):Number {
if ((t *= 2) < 1) return 0.5 * t * t;
return -0.5 * ((--t)*(t-2) - 1);
}
static public function cubicIn(t:Number):Number {
return t*t*t;
}
static public function cubicOut(t:Number):Number {
return (--t)*t*t + 1;
}
static public function cubicInOut (t:Number):Number {
if ((t *= 2) < 1) return 0.5*t*t*t;
return 0.5*((t-=2)*t*t + 2);
}
static public function quartIn (t:Number):Number {
return t*t*t*t;
}
static public function quartOut (t:Number):Number {
return -((t=t/1-1)*t*t*t - 1);
}
static public function quartInOut (t:Number):Number {
if ((t *= 2) < 1) return 0.5*t*t*t*t;
return -0.5 * ((t-=2)*t*t*t - 2);
}
static public function quintIn(t:Number):Number {
return t*t*t*t*t;
}
static public function quintOut(t:Number):Number {
return ((t=t/1-1)*t*t*t*t + 1);
}
static public function quintInOut(t:Number):Number {
if ((t *= 2) < 1) return 0.5*t*t*t*t*t;
return 0.5*((t-=2)*t*t*t*t + 2);
}
static public function expoIn (t:Number):Number {
return (t==0) ? 0 : Math.pow(2, 10 * (t/1 - 1));
}
static public function expoOut (t:Number):Number {
return (t==1) ? 0+1 : (-Math.pow(2, -10 * t/1) + 1);
}
static public function expoInOut (t:Number):Number {
if (t==0 || t ==1) return t;
if ((t *= 2) < 1) return 0.5 * Math.pow(2, 10 * (t - 1));
return 0.5 * (-Math.pow(2, -10 * --t) + 2);
}
static public function sinIn (t:Number):Number {
return -Math.cos(t * (Math.PI/2)) + 1;
}
static public function sinOut (t:Number):Number {
return Math.sin(t * (Math.PI/2));
}
static public function sinInOut (t:Number):Number {
return -0.5 * (Math.cos(Math.PI*t) - 1);
}
static public function bounceOut (t:Number):Number {
if (t < (1/2.75)) {
return (7.5625*t*t);
} else if (t < (2/2.75)) {
return (7.5625*(t-=(1.5/2.75))*t + .75);
} else if (t < (2.5/2.75)) {
return (7.5625*(t-=(2.25/2.75))*t + .9375);
} else {
return (7.5625*(t-=(2.625/2.75))*t + .984375);
}
}
static public function bounceIn (t:Number):Number {
return 1 - bounceOut (1-t);
}
static public function bounceInOut (t:Number):Number {
if (t < 0.5) return bounceIn (t*2) * 0.5;
else return bounceOut (t*2-1) * 0.5 + 00.5;
}
static public function circIn (t:Number):Number {
return -(Math.sqrt(1 - t*t) - 1);
}
static public function circOut (t:Number):Number {
return Math.sqrt(1 - (t=t/1-1)*t);
}
static public function circInOut (t:Number):Number {
if ((t *= 2) < 1) return -0.5 * (Math.sqrt(1 - t*t) - 1);
return 0.5 * (Math.sqrt(1 - (t-=2)*t) + 1);
}
}
//}
//package {
/*public*/ class Perlin extends NoiseSuper {
static private var noiseBasis:Function = improved;
static private var interpolation:Function = smooth5;
static private var octaves:int = 4;
static private var lacunarity:Number = 2;
static private var H:Number = 0.5;
static private var offset:Number = 0.8;
static private var maxAmp:Number = 0;
static public function setParams(initObject:Object):void {
if(initObject.noiseBasis) noiseBasis = initObject.noiseBasis;
if(initObject.interpolation) interpolation = initObject.interpolation;
if(initObject.octaves) octaves = initObject.octaves;
if(initObject.lacunarity) lacunarity = initObject.lacunarity;
if(initObject.H) H = initObject.H;
if(initObject.offset) offset = initObject.offset;
calcMax();
}
static public function fractalNoise(x:Number, y:Number, z:Number):Number {
var amp:Number = 1;
var fscale:Number = 1;
var sum:Number = 0;
if (maxAmp == 0) calcMax();
for (var i:int = 0; i < octaves; i++, amp *= H, fscale *= lacunarity) {
sum += amp * noiseBasis(fscale*x, fscale*y, fscale*z);
}
return (sum * maxAmp + 1) * 0.5;
}
static public function turbulence(x:Number, y:Number, z:Number):Number {
var amp:Number = 1;
var fscale:Number = 1;
var sum:Number = 0;
if(maxAmp == 0) calcMax();
for (var i:int = 0; i < octaves; i++, amp *= H, fscale *= lacunarity) {
sum += amp * Math.abs( noiseBasis(fscale*x, fscale*y, fscale*z) );
}
return (sum * maxAmp + 1) * 0.5;
}
static public function turbulenceHard(x:Number, y:Number, z:Number):Number {
var amp:Number = 1;
var fscale:Number = 1;
var sum:Number = 0;
if(maxAmp == 0) calcMax();
for (var i:int = 0; i < octaves; i++, amp *= H, fscale *= lacunarity) {
sum += amp * Math.abs( 2 * noiseBasis(fscale*x, fscale*y, fscale*z) - 1 );
}
return (sum * maxAmp + 1) * 0.5;
}
static public function improved(x:Number, y:Number, z:Number):Number {
var X:int = Math.floor(x) & 255;
var Y:int = Math.floor(y) & 255;
var Z:int = Math.floor(z) & 255;
x -= Math.floor(x);
y -= Math.floor(y);
z -= Math.floor(z);
var u:Number = interpolation(x);
var v:Number = interpolation(y);
var w:Number = interpolation(z);
var A:int = hash[X]+Y;
var AA:int = hash[A]+Z;
var AB:int = hash[A+1]+Z;
var B:int = hash[X+1]+Y;
var BA:int = hash[B]+Z;
var BB:int = hash[B+1]+Z;
return lerp(w, lerp(v, lerp(u, grad(hash[AA ], x , y , z ),
grad(hash[BA ], x-1, y , z )),
lerp(u, grad(hash[AB ], x , y-1, z ),
grad(hash[BB ], x-1, y-1, z ))),
lerp(v, lerp(u, grad(hash[AA+1], x , y , z-1 ),
grad(hash[BA+1], x-1, y , z-1 )),
lerp(u, grad(hash[AB+1], x , y-1, z-1 ),
grad(hash[BB+1], x-1, y-1, z-1 ))));
}
static public function improvedU(x:Number, y:Number, z:Number):Number {
return 0.5 + 0.5 * improved(x, y, z);
}
static private function calcMax():void {
maxAmp = 0;
for (var i:int; i<octaves; i++) maxAmp += Math.pow(H, i);
maxAmp = 1/maxAmp;
}
}
//}
//package {
import flash.filters.BlurFilter;
import flash.ui.Keyboard;
import flash.utils.Dictionary;
import flash.geom.*;
import flash.display.*;
import flash.events.*;
import flash.text.*;
import flash.utils.ByteArray;
import flash.utils.getTimer;
import flash.utils.Timer;
import flash.net.FileReference;
import flash.system.System;
//import de.polygonal.math.PM_PRNG;
/*public*/ class mapgen2 extends Sprite {
static public var SIZE:int = 512;
static public var EXPORT_SIZE:int = 512;
static public var previewColors:Object = {
OCEAN: 0x0000CC,
COAST: 0x33335a,
LAKESHORE: 0x225588,
LAKE: 0x336699,
RIVER: 0x225588,
MARSH: 0x2f6666,
ICE: 0x99ffff,
BEACH: 0xa09077,
ROAD1: 0x442211,
ROAD2: 0x553322,
ROAD3: 0x664433,
BRIDGE: 0x686860,
LAVA: 0xcc3333,
SNOW: 0xffffff,
TUNDRA: 0xbbbbaa,
BARE: 0x888888,
SCORCHED: 0x555555,
TAIGA: 0x99aa77,
SHRUBLAND: 0x889977,
TEMPERATE_DESERT: 0xc9d29b,
TEMPERATE_RAIN_FOREST: 0x448855,
TEMPERATE_DECIDUOUS_FOREST: 0x679459,
GRASSLAND: 0x88aa55,
SUBTROPICAL_DESERT: 0xd2b98b,
TROPICAL_RAIN_FOREST: 0x337755,
TROPICAL_SEASONAL_FOREST: 0x559944
};
static public var displayColors:Object = {
OCEAN: 0x000000,
COAST: 0x000000,
LAKESHORE: 0x000000,
LAKE: 0x000000,
RIVER: 0x000000,
MARSH: 0x00FF00,
ICE: 0x0000FF,
BEACH: 0xFF0000,
ROAD1: 0x442211,
ROAD2: 0x553322,
ROAD3: 0x664433,
BRIDGE: 0x686860,
LAVA: 0x0000FF,
SNOW: 0x0000FF,
TUNDRA: 0x0000FF,
BARE: 0x0000FF,
SCORCHED: 0x0000FF,
TAIGA: 0x0000FF,
SHRUBLAND: 0xFF0000,
TEMPERATE_DESERT: 0xFF0000,
TEMPERATE_RAIN_FOREST: 0x00FF00,
TEMPERATE_DECIDUOUS_FOREST: 0x00FF00,
GRASSLAND: 0x00FF00,
SUBTROPICAL_DESERT: 0xFF0000,
TROPICAL_RAIN_FOREST: 0x00FF00,
TROPICAL_SEASONAL_FOREST: 0x00FF00
};
static public var exportDisplayColors:Object = {
OCEAN: 1,
COAST: 2,
LAKESHORE: 3,
LAKE: 4,
RIVER: 5,
MARSH: 6,
ICE: 7,
BEACH: 8,
ROAD1: 9,
ROAD2: 10,
ROAD3: 11,
BRIDGE: 12,
LAVA: 13,
SNOW: 14,
TUNDRA: 15,
BARE: 16,
SCORCHED: 17,
TAIGA: 18,
SHRUBLAND: 19,
TEMPERATE_DESERT: 20,
TEMPERATE_RAIN_FOREST: 21,
TEMPERATE_DECIDUOUS_FOREST: 22,
GRASSLAND: 23,
SUBTROPICAL_DESERT: 24,
TROPICAL_RAIN_FOREST: 25,
TROPICAL_SEASONAL_FOREST: 26
};
static public function getExportIndexLookup():Vector.<String> {
var i:String
var count:int = 0;
for (i in exportDisplayColors) {
count++;
}
var v:Vector.<String> = new Vector.<String>(count, true);
for (i in exportDisplayColors) {
v [ exportDisplayColors[i] - 1 ] = i;
}
return v;
}
static public var elevationGradientColors:Object = {
OCEAN: 0x000000,
GRADIENT_LOW: 0x000001,
GRADIENT_HIGH: 0xffffff
};
static public var lightGradientColors:Object = {
OCEAN: 0x000000,
GRADIENT_LOW: 0x000001,
GRADIENT_HIGH: 0xffffff
};
static public var moistureGradientColors:Object = {
OCEAN: 0x4466ff,
GRADIENT_LOW: 0xbbaa33,
GRADIENT_HIGH: 0x4466ff
};
public var islandType:String = 'Perlin';
static public var islandSeedInitial:String = "85882-1";
public var controls:Sprite = new Sprite();
public var islandSeedInput:TextField;
public var statusBar:TextField;
public var mapMode:String = 'smooth';
public var render3dTimer:Timer = new Timer(1000/20, 0);
public var noiseLayer:Bitmap = new Bitmap(new BitmapData(SIZE, SIZE));
private var rotationAnimation:Number = 0.0;
private var triangles3d:Array = [];
private var graphicsData:Vector.<IGraphicsData>;
public var map:Map;
public var roads:Roads;
public var lava:Lava;
public var watersheds:Watersheds;
public var noisyEdges:NoisyEdges;
[SWF(width="800", height="600", frameRate=60)]
public function mapgen2() {
addEventListener(Event.ADDED_TO_STAGE, onAddedToStage);
}
private function onAddedToStage(e:Event):void
{
removeEventListener(Event.ADDED_TO_STAGE, onAddedToStage);
stage.scaleMode = 'noScale';
stage.align = 'TL';
scaleX = SIZE > 512 ? .5 : 1;
scaleY = SIZE > 512 ? .5 : 1;
addChild(noiseLayer);
noiseLayer.bitmapData.noise(555, 128-10, 128+10, 7, true);
noiseLayer.blendMode = BlendMode.HARDLIGHT;
controls.x = SIZE;
addChild(controls);
addExportButtons();
addViewButtons();
addGenerateButtons();
addMiscLabels();
map = new Map(SIZE);
go(islandType);
render3dTimer.addEventListener(TimerEvent.TIMER, function (e:TimerEvent):void {
drawMap(mapMode);
});
}
public function newIsland(type:String):void {
var seed:int = 0, variant:int = 0;
var t:Number = getTimer();
if (islandSeedInput.text.length == 0) {
islandSeedInput.text = (Math.random()*100000).toFixed(0);
}
var match:Object = /\s*(\d+)(?:\-(\d+))\s*$/.exec(islandSeedInput.text);
if (match != null) {
seed = parseInt(match[1]);
variant = parseInt(match[2] || "0");
}
if (seed == 0) {
for (var i:int = 0; i < islandSeedInput.text.length; i++) {
seed = (seed << 4) | islandSeedInput.text.charCodeAt(i);
}
seed %= 100000;
variant = 1+Math.floor(9*Math.random());
}
islandType = type;
map.newIsland(type, seed, variant);
}
public function graphicsReset():void {
triangles3d = [];
graphics.clear();
graphics.beginFill(0xbbbbaa);
graphics.drawRect(0, 0, 2000, 2000);
graphics.endFill();
graphics.beginFill(displayColors.OCEAN);
graphics.drawRect(0, 0, SIZE, SIZE);
graphics.endFill();
}
public function go(type:String):void {
cancelCommands();
roads = new Roads();
lava = new Lava();
watersheds = new Watersheds();
noisyEdges = new NoisyEdges();
commandExecute("Shaping map...",
function():void {
newIsland(type);
});
commandExecute("Placing points...",
function():void {
map.go(0, 1);
drawMap('polygons');
});
commandExecute("Improving points...",
function():void {
map.go(1, 2);
drawMap('polygons');
});
commandExecute("Building graph...",
function():void {
map.go(2, 3);
map.assignBiomes();
drawMap('polygons');
});
commandExecute("Features...",
function():void {
map.go(3, 6);
map.assignBiomes();
drawMap('polygons');
});
commandExecute("Edges...",
function():void {
roads.createRoads(map);
watersheds.createWatersheds(map);
noisyEdges.buildNoisyEdges(map, lava, map.mapRandom);
drawMap(mapMode);
});
}
private var _guiQueue:Array = [];
private function _onEnterFrame(e:Event):void {
(_guiQueue.shift()[1])();
if (_guiQueue.length == 0) {
stage.removeEventListener(Event.ENTER_FRAME, _onEnterFrame);
statusBar.text = "";
dispatchEvent( new Event(COMPLETED));
} else {
statusBar.text = _guiQueue[0][0];
}
}
public function cancelCommands():void {
if (_guiQueue.length != 0) {
stage.removeEventListener(Event.ENTER_FRAME, _onEnterFrame);
statusBar.text = "";
_guiQueue = [];
}
}
public function commandExecute(status:String, command:Function):void {
if (_guiQueue.length == 0) {
statusBar.text = status;
stage.addEventListener(Event.ENTER_FRAME, _onEnterFrame);
}
_guiQueue.push([status, command]);
}
private static var _biomeMap:Array =
['BEACH', 'LAKE', 'ICE', 'MARSH', 'SNOW', 'TUNDRA', 'BARE', 'SCORCHED',
'TAIGA', 'SHRUBLAND', 'TEMPERATE_DESERT', 'TEMPERATE_RAIN_FOREST',
'TEMPERATE_DECIDUOUS_FOREST', 'GRASSLAND', 'SUBTROPICAL_DESERT',
'TROPICAL_RAIN_FOREST', 'TROPICAL_SEASONAL_FOREST'];
public function drawHistograms():void {
function landTypeBucket(p:Center):int {
if (p.ocean) return 1;
else if (p.coast) return 2;
else if (p.water) return 3;
else return 4;
}
function landTypeColor(bucket:int):uint {
if (bucket == 1) return displayColors.OCEAN;
else if (bucket == 2) return displayColors.BEACH;
else if (bucket == 3) return displayColors.LAKE;
else return displayColors.TEMPERATE_DECIDUOUS_FOREST;
}
function elevationBucket(p:Center):int {
if (p.ocean) return -1;
else return Math.floor(p.elevation*10);
}
function elevationColor(bucket:int):uint {
return interpolateColor(displayColors.TEMPERATE_DECIDUOUS_FOREST,
displayColors.GRASSLAND, bucket*0.1);
}
function moistureBucket(p:Center):int {
if (p.water) return -1;
else return Math.floor(p.moisture*10);
}
function moistureColor(bucket:int):uint {
return interpolateColor(displayColors.BEACH, displayColors.RIVER, bucket*0.1);
}
function biomeBucket(p:Center):int {
return _biomeMap.indexOf(p.biome);
}
function biomeColor(bucket:int):uint {
return displayColors[_biomeMap[bucket]];
}
function computeHistogram(bucketFn:Function):Array {
var p:Center, histogram:Array, bucket:int;
histogram = [];
for each (p in map.centers) {
bucket = bucketFn(p);
if (bucket >= 0) histogram[bucket] = (histogram[bucket] || 0) + 1;
}
return histogram;
}
function drawHistogram(x:Number, y:Number, bucketFn:Function, colorFn:Function,
width:Number, height:Number):void {
var scale:Number, i:int;
var histogram:Array = computeHistogram(bucketFn);
scale = 0.0;
for (i = 0; i < histogram.length; i++) {
scale = Math.max(scale, histogram[i] || 0);
}
for (i = 0; i < histogram.length; i++) {
if (histogram[i]) {
graphics.beginFill(colorFn(i));
graphics.drawRect(SIZE+x+i*width/histogram.length, y+height,
Math.max(0, width/histogram.length-1), -height*histogram[i]/scale);
graphics.endFill();
}
}
}
function drawDistribution(x:Number, y:Number, bucketFn:Function, colorFn:Function,
width:Number, height:Number):void {
var scale:Number, i:int, x:Number, w:Number;
var histogram:Array = computeHistogram(bucketFn);
scale = 0.0;
for (i = 0; i < histogram.length; i++) {
scale += histogram[i] || 0.0;
}
for (i = 0; i < histogram.length; i++) {
if (histogram[i]) {
graphics.beginFill(colorFn(i));
w = histogram[i]/scale*width;
graphics.drawRect(SIZE+x, y, Math.max(0, w-1), height);
x += w;
graphics.endFill();
}
}
}
var x:Number = 23, y:Number = 140, width:Number = 154;
drawDistribution(x, y, landTypeBucket, landTypeColor, width, 20);
drawDistribution(x, y+25, biomeBucket, biomeColor, width, 20);
drawHistogram(x, y+55, elevationBucket, elevationColor, width, 30);
drawHistogram(x, y+95, moistureBucket, moistureColor, width, 20);
}
private function drawPathForwards(graphics:Graphics, path:Vector.<Point>):void {
for (var i:int = 0; i < path.length; i++) {
graphics.lineTo(path[i].x, path[i].y);
}
}
private function drawPathBackwards(graphics:Graphics, path:Vector.<Point>):void {
for (var i:int = path.length-1; i >= 0; i--) {
graphics.lineTo(path[i].x, path[i].y);
}
}
private function interpolateColor(color0:uint, color1:uint, f:Number):uint {
var r:uint = uint((1-f)*(color0 >> 16) + f*(color1 >> 16));
var g:uint = uint((1-f)*((color0 >> 8) & 0xff) + f*((color1 >> 8) & 0xff));
var b:uint = uint((1-f)*(color0 & 0xff) + f*(color1 & 0xff));
if (r > 255) r = 255;
if (g > 255) g = 255;
if (b > 255) b = 255;
return (r << 16) | (g << 8) | b;
}
private function drawGradientTriangle(graphics:Graphics,
v1:Vector3D, v2:Vector3D, v3:Vector3D,
colors:Array, fillFunction:Function):void {
var m:Matrix = new Matrix();
var V:Vector3D = v1.add(v2).add(v3);
V.scaleBy(1/3.0);
var N:Vector3D = v2.subtract(v1).crossProduct(v3.subtract(v1));
N.normalize();
var G:Vector3D = new Vector3D(-N.x/N.z, -N.y/N.z, 0);
var C:Vector3D = new Vector3D(V.x - G.x*((V.z-0.5)/G.length/G.length), V.y - G.y*((V.z-0.5)/G.length/G.length));
if (G.length < 1e-6) {
var color:uint = colors[0];
if (colors.length == 2) {
color = interpolateColor(colors[0], colors[1], V.z);
} else if (colors.length == 3) {
if (V.z < 0.5) {
color = interpolateColor(colors[0], colors[1], V.z*2);
} else {
color = interpolateColor(colors[1], colors[2], V.z*2-1);
}
}
graphics.beginFill(color);
} else {
m.createGradientBox(1, 1, 0, 0, 0);
m.translate(-0.5, -0.5);
m.scale((1/G.length), (1/G.length));
m.rotate(Math.atan2(G.y, G.x));
m.translate(C.x, C.y);
var alphas:Array = colors.map(function (_:*, index:int, A:Array):Number { return 1.0; });
var spread:Array = colors.map(function (_:*, index:int, A:Array):int { return 255*index/(A.length-1); });
graphics.beginGradientFill(GradientType.LINEAR, colors, alphas, spread, m, SpreadMethod.PAD);
}
fillFunction();
graphics.endFill();
}
public function drawMap(mode:String):void {
graphicsReset();
noiseLayer.visible = true;
drawHistograms();
if (mode == '3d') {
if (!render3dTimer.running) render3dTimer.start();
noiseLayer.visible = false;
render3dPolygons(graphics, displayColors, colorWithSlope);
return;
} else if (mode == 'polygons') {
noiseLayer.visible = false;
renderDebugPolygons(graphics, displayColors);
} else if (mode == 'watersheds') {
noiseLayer.visible = false;
renderDebugPolygons(graphics, displayColors);
renderWatersheds(graphics);
return;
} else if (mode == 'biome') {
noiseLayer.visible = false;
renderPolygons(graphics, displayColors, null, null);
} else if (mode == 'slopes') {
noiseLayer.visible = false;
renderPolygons(graphics, {} , null, colorWithSlope, 0x808080);
} else if (mode == 'smooth') {
renderPolygons(graphics, displayColors, null, colorWithSmoothColors);
} else if (mode == 'elevation') {
noiseLayer.visible = false;
renderPolygons(graphics, elevationGradientColors, 'elevation', null);
} else if (mode == 'moisture') {
noiseLayer.visible = false;
renderPolygons(graphics, moistureGradientColors, 'moisture', null);
}
if (render3dTimer.running) render3dTimer.stop();
if (mode != 'slopes' && mode != 'moisture') {
}
if (mode != 'polygons') {
}
if (mode != 'slopes' && mode != 'moisture') {
}
}
public function render3dPolygons(graphics:Graphics, colors:Object, colorFunction:Function):void {
var p:Center, q:Corner, edge:Edge;
var zScale:Number = 0.15*SIZE;
graphics.beginFill(colors.OCEAN);
graphics.drawRect(0, 0, SIZE, SIZE);
graphics.endFill();
if (triangles3d.length == 0) {
graphicsData = new Vector.<IGraphicsData>();
for each (p in map.centers) {
if (p.ocean) continue;
for each (edge in p.borders) {
var color:int = colors[p.biome] || 0;
if (colorFunction != null) {
color = colorFunction(color, p, q, edge, colors, 0x808080);
}
var corner0:Corner = edge.v0;
var corner1:Corner = edge.v1;
if (corner0 == null || corner1 == null) {
continue;
}
var zp:Number = zScale*p.elevation;
var z0:Number = zScale*corner0.elevation;
var z1:Number = zScale*corner1.elevation;
triangles3d.push({
a:new Vector3D(p.point.x, p.point.y, zp),
b:new Vector3D(corner0.point.x, corner0.point.y, z0),
c:new Vector3D(corner1.point.x, corner1.point.y, z1),
rA:null,
rB:null,
rC:null,
z:0.0,
color:color
});
graphicsData.push(new GraphicsSolidFill());
graphicsData.push(new GraphicsPath(Vector.<int>([GraphicsPathCommand.MOVE_TO, GraphicsPathCommand.LINE_TO, GraphicsPathCommand.LINE_TO]),
Vector.<Number>([0, 0, 0, 0, 0, 0])));
graphicsData.push(new GraphicsEndFill());
}
}
}
var camera:Matrix3D = new Matrix3D();
camera.appendRotation(rotationAnimation, new Vector3D(0, 0, 1), new Vector3D(SIZE/2, SIZE/2));
camera.appendRotation(60, new Vector3D(1,0,0), new Vector3D(SIZE/2, SIZE/2));
rotationAnimation += 1;
for each (var tri:Object in triangles3d) {
tri.rA = camera.transformVector(tri.a);
tri.rB = camera.transformVector(tri.b);
tri.rC = camera.transformVector(tri.c);
tri.z = (tri.rA.z + tri.rB.z + tri.rC.z)/3;
}
triangles3d.sortOn('z', Array.NUMERIC);
for (var i:int = 0; i < triangles3d.length; i++) {
tri = triangles3d[i];
GraphicsSolidFill(graphicsData[i*3]).color = tri.color;
var data:Vector.<Number> = GraphicsPath(graphicsData[i*3+1]).data;
data[0] = tri.rA.x;
data[1] = tri.rA.y;
data[2] = tri.rB.x;
data[3] = tri.rB.y;
data[4] = tri.rC.x;
data[5] = tri.rC.y;
}
graphics.drawGraphicsData(graphicsData);
}
public function renderPolygons(graphics:Graphics, colors:Object, gradientFillProperty:String, colorOverrideFunction:Function, defaultColor:uint=0):void {
var p:Center, r:Center;
graphics.beginFill(defaultColor != 0 ? defaultColor : colors.OCEAN);
graphics.drawRect(0, 0, SIZE, SIZE);
graphics.endFill();
for each (p in map.centers) {
for each (r in p.neighbors) {
var edge:Edge = map.lookupEdgeFromCenter(p, r);
var color:int = colors[p.biome] || defaultColor;
if (colorOverrideFunction != null) {
color = colorOverrideFunction(color, p, r, edge, colors, defaultColor);
}
function drawPath0():void {
var path:Vector.<Point> = noisyEdges.path0[edge.index];
graphics.moveTo(p.point.x, p.point.y);
graphics.lineTo(path[0].x, path[0].y);
drawPathForwards(graphics, path);
graphics.lineTo(p.point.x, p.point.y);
}
function drawPath1():void {
var path:Vector.<Point> = noisyEdges.path1[edge.index];
graphics.moveTo(p.point.x, p.point.y);
graphics.lineTo(path[0].x, path[0].y);
drawPathForwards(graphics, path);
graphics.lineTo(p.point.x, p.point.y);
}
if (noisyEdges.path0[edge.index] == null
|| noisyEdges.path1[edge.index] == null) {
continue;
}
if (gradientFillProperty != null) {
var corner0:Corner = edge.v0;
var corner1:Corner = edge.v1;
var midpoint:Point = edge.midpoint;
var midpointAttr:Number = 0.5*(corner0[gradientFillProperty]+corner1[gradientFillProperty]);
drawGradientTriangle
(graphics,
new Vector3D(p.point.x, p.point.y, p[gradientFillProperty]),
new Vector3D(corner0.point.x, corner0.point.y, corner0[gradientFillProperty]),
new Vector3D(midpoint.x, midpoint.y, midpointAttr),
[colors.GRADIENT_LOW, colors.GRADIENT_HIGH], drawPath0);
drawGradientTriangle
(graphics,
new Vector3D(p.point.x, p.point.y, p[gradientFillProperty]),
new Vector3D(midpoint.x, midpoint.y, midpointAttr),
new Vector3D(corner1.point.x, corner1.point.y, corner1[gradientFillProperty]),
[colors.GRADIENT_LOW, colors.GRADIENT_HIGH], drawPath1);
} else {
graphics.beginFill(color);
drawPath0();
drawPath1();
graphics.endFill();
}
}
}
}
public function renderBridges(graphics:Graphics, colors:Object):void {
var edge:Edge;
for each (edge in map.edges) {
if (edge.river > 0 && edge.river < 4
&& !edge.d0.water && !edge.d1.water
&& (edge.d0.elevation > 0.05 || edge.d1.elevation > 0.05)) {
var n:Point = new Point(-(edge.v1.point.y - edge.v0.point.y), edge.v1.point.x - edge.v0.point.x);
n.normalize(0.25 + (roads.road[edge.index]? 0.5 : 0) + 0.75*Math.sqrt(edge.river));
graphics.lineStyle(1.1, colors.BRIDGE, 1.0, false, LineScaleMode.NORMAL, CapsStyle.SQUARE);
graphics.moveTo(edge.midpoint.x - n.x, edge.midpoint.y - n.y);
graphics.lineTo(edge.midpoint.x + n.x, edge.midpoint.y + n.y);
graphics.lineStyle();
}
}
}
public function renderRoads(graphics:Graphics, colors:Object):void {
var p:Center, A:Point, B:Point, C:Point;
var i:int, j:int, d:Number, edge1:Edge, edge2:Edge, edges:Vector.<Edge>;
function normalTowards(e:Edge, c:Point, len:Number):Point {
var n:Point = new Point(-(e.v1.point.y - e.v0.point.y), e.v1.point.x - e.v0.point.x);
var d:Point = c.subtract(e.midpoint);
if (n.x * d.x + n.y * d.y < 0) {
n.x = -n.x;
n.y = -n.y;
}
n.normalize(len);
return n;
}
for each (p in map.centers) {
if (roads.roadConnections[p.index]) {
if (roads.roadConnections[p.index].length == 2) {
edges = p.borders;
for (i = 0; i < edges.length; i++) {
edge1 = edges[i];
if (roads.road[edge1.index] > 0) {
for (j = i+1; j < edges.length; j++) {
edge2 = edges[j];
if (roads.road[edge2.index] > 0) {
d = 0.5*Math.min
(edge1.midpoint.subtract(p.point).length,
edge2.midpoint.subtract(p.point).length);
A = normalTowards(edge1, p.point, d).add(edge1.midpoint);
B = normalTowards(edge2, p.point, d).add(edge2.midpoint);
C = Point.interpolate(A, B, 0.5);
graphics.lineStyle(1.1, colors['ROAD'+roads.road[edge1.index]]);
graphics.moveTo(edge1.midpoint.x, edge1.midpoint.y);
graphics.curveTo(A.x, A.y, C.x, C.y);
graphics.lineStyle(1.1, colors['ROAD'+roads.road[edge2.index]]);
graphics.curveTo(B.x, B.y, edge2.midpoint.x, edge2.midpoint.y);
graphics.lineStyle();
}
}
}
}
} else {
for each (edge1 in p.borders) {
if (roads.road[edge1.index] > 0) {
d = 0.25*edge1.midpoint.subtract(p.point).length;
A = normalTowards(edge1, p.point, d).add(edge1.midpoint);
graphics.lineStyle(1.4, colors['ROAD'+roads.road[edge1.index]]);
graphics.moveTo(edge1.midpoint.x, edge1.midpoint.y);
graphics.curveTo(A.x, A.y, p.point.x, p.point.y);
graphics.lineStyle();
}
}
}
}
}
}
public function renderEdges(graphics:Graphics, colors:Object):void {
var p:Center, r:Center, edge:Edge;
for each (p in map.centers) {
for each (r in p.neighbors) {
edge = map.lookupEdgeFromCenter(p, r);
if (noisyEdges.path0[edge.index] == null
|| noisyEdges.path1[edge.index] == null) {
continue;
}
if (p.ocean != r.ocean) {
graphics.lineStyle(2, colors.COAST);
} else if ((p.water > 0) != (r.water > 0) && p.biome != 'ICE' && r.biome != 'ICE') {
graphics.lineStyle(1, colors.LAKESHORE);
} else if (p.water || r.water) {
continue;
} else if (lava.lava[edge.index]) {
graphics.lineStyle(1, colors.LAVA);
} else if (edge.river > 0) {
graphics.lineStyle(Math.sqrt(edge.river), colors.RIVER);
} else {
continue;
}
graphics.moveTo(noisyEdges.path0[edge.index][0].x,
noisyEdges.path0[edge.index][0].y);
drawPathForwards(graphics, noisyEdges.path0[edge.index]);
drawPathBackwards(graphics, noisyEdges.path1[edge.index]);
graphics.lineStyle();
}
}
}
public function renderDebugPolygons(graphics:Graphics, colors:Object):void {
var p:Center, q:Corner, edge:Edge, point:Point, color:int;
if (map.centers.length == 0) {
graphics.beginFill(0xdddddd);
graphics.drawRect(0, 0, SIZE, SIZE);
graphics.endFill();
for each (point in map.points) {
graphics.beginFill(0x000000);
graphics.drawCircle(point.x, point.y, 1.3);
graphics.endFill();
}
}
for each (p in map.centers) {
color = colors[p.biome] || (p.ocean? colors.OCEAN : p.water? colors.RIVER : 0xffffff);
graphics.beginFill(interpolateColor(color, 0xdddddd, 0.2));
for each (edge in p.borders) {
if (edge.v0 && edge.v1) {
graphics.moveTo(p.point.x, p.point.y);
graphics.lineTo(edge.v0.point.x, edge.v0.point.y);
if (edge.river > 0) {
graphics.lineStyle(2, displayColors.RIVER, 1.0);
} else {
graphics.lineStyle(0, 0x000000, 0.4);
}
graphics.lineTo(edge.v1.point.x, edge.v1.point.y);
graphics.lineStyle();
}
}
graphics.endFill();
graphics.beginFill(p.water > 0 ? 0x003333 : 0x000000, 0.7);
graphics.drawCircle(p.point.x, p.point.y, 1.3);
graphics.endFill();
for each (q in p.corners) {
graphics.beginFill(q.water? 0x0000ff : 0x009900);
graphics.drawRect(q.point.x-0.7, q.point.y-0.7, 1.5, 1.5);
graphics.endFill();
}
}
}
public function renderWatersheds(graphics:Graphics):void {
var edge:Edge, w0:int, w1:int;
for each (edge in map.edges) {
if (edge.d0 && edge.d1 && edge.v0 && edge.v1
&& !edge.d0.ocean && !edge.d1.ocean) {
w0 = watersheds.watersheds[edge.d0.index];
w1 = watersheds.watersheds[edge.d1.index];
if (w0 != w1) {
graphics.lineStyle(3.5, 0x000000, 0.1*Math.sqrt((map.corners[w0].watershed_size || 1) + (map.corners[w1].watershed.watershed_size || 1)));
graphics.moveTo(edge.v0.point.x, edge.v0.point.y);
graphics.lineTo(edge.v1.point.x, edge.v1.point.y);
graphics.lineStyle();
}
}
}
for each (edge in map.edges) {
if (edge.river) {
graphics.lineStyle(1.0, 0x6699ff);
graphics.moveTo(edge.v0.point.x, edge.v0.point.y);
graphics.lineTo(edge.v1.point.x, edge.v1.point.y);
graphics.lineStyle();
}
}
}
private var lightVector:Vector3D = new Vector3D(-1, -1, 0);
private var biomeApplicator:BiomeApplicator32;
private var _testSpr:Sprite;
public function calculateLighting(p:Center, r:Corner, s:Corner):Number {
var A:Vector3D = new Vector3D(p.point.x, p.point.y, p.elevation);
var B:Vector3D = new Vector3D(r.point.x, r.point.y, r.elevation);
var C:Vector3D = new Vector3D(s.point.x, s.point.y, s.elevation);
var normal:Vector3D = B.subtract(A).crossProduct(C.subtract(A));
if (normal.z < 0) { normal.scaleBy(-1); }
normal.normalize();
var light:Number = 0.5 + 35*normal.dotProduct(lightVector);
if (light < 0) light = 0;
if (light > 1) light = 1;
return light;
}
public function colorWithSlope(color:int, p:Center, q:Center, edge:Edge, displayColors:Object, defaultColor:uint):int {
var r:Corner = edge.v0;
var s:Corner = edge.v1;
if (!r || !s) {
return displayColors.OCEAN;
} else if (p.water) {
return color;
}
if (q != null && p.water == q.water) color = interpolateColor(color, displayColors[q.biome]!= null ? displayColors[q.biome] : defaultColor, 0.4);
var colorLow:int = interpolateColor(color, 0x333333, 0.7);
var colorHigh:int = interpolateColor(color, 0xffffff, 0.3);
var light:Number = calculateLighting(p, r, s);
if (light < 0.5) return interpolateColor(colorLow, color, light*2);
else return interpolateColor(color, colorHigh, light*2-1);
}
public function colorWithSmoothColors(color:int, p:Center, q:Center, edge:Edge, displayColors:Object, defaultColor:uint):int {
if (q != null && p.water == q.water) {
color = interpolateColor(displayColors[p.biome], displayColors[q.biome]!= null ? displayColors[q.biome] : defaultColor, 0.25);
}
return color;
}
static public var exportOverrideColors:Object = {
POLYGON_CENTER: 0x01,
POLYGON_CENTER_SAFE: 0x03,
OCEAN: 0x50,
COAST: 0x80,
LAKE: 0x60,
LAKESHORE: 0x70,
RIVER: 0x10,
MARSH: 0x10,
ICE: 0x40,
LAVA: 0x20,
SNOW: 0x30,
ROAD1: 0x90,
ROAD2: 0xa0,
ROAD3: 0xb0,
BRIDGE: 0xc0
};
static public var exportElevationColors:Object = {
OCEAN: 0x00,
GRADIENT_LOW: 0x00,
GRADIENT_HIGH: 0xff
};
static public const COMPLETED:String = "mapGenCompleted";
static public var PREVIEW_SIZE:int = 64;
static public var exportMoistureColors:Object = {
OCEAN: 0xff,
GRADIENT_LOW: 0x00,
GRADIENT_HIGH: 0xff
};
public function getPreviewBmp(exportSize:int = 0):Bitmap {
if (exportSize == 0) exportSize = PREVIEW_SIZE;
var exportBitmap:BitmapData = new BitmapData(exportSize, exportSize, false, 0);
var exportGraphics:Shape = new Shape();
renderPolygons(exportGraphics.graphics, previewColors, null, colorWithSmoothColors);
var m:Matrix = new Matrix();
m.scale(exportSize / SIZE, exportSize / SIZE);
exportBitmap.draw(exportGraphics, m, null,null,null,true);
return new Bitmap(exportBitmap, "auto", true);
}
public function makeExport(layer:String, exportSize:int = 0, compress:Boolean=true):ByteArray {
exportSize = exportSize != 0 ? exportSize : EXPORT_SIZE;
var exportBitmap:BitmapData = new BitmapData(exportSize, exportSize);
var exportGraphics:Shape = new Shape();
var exportData:ByteArray = new ByteArray();
var m:Matrix = new Matrix();
m.scale(exportSize / SIZE, exportSize / SIZE);
function saveBitmapToArray():void {
for (var y:int = 0; y < EXPORT_SIZE; y++) {
for (var x:int = 0; x < EXPORT_SIZE; x++) {
exportData.writeByte(exportBitmap.getPixel(x, y) & 0xff);
}
}
}
if (layer == 'overrides') {
renderPolygons(exportGraphics.graphics, exportOverrideColors, null, null);
renderEdges(exportGraphics.graphics, exportOverrideColors);
renderBridges(exportGraphics.graphics, exportOverrideColors);
stage.quality = 'low';
exportBitmap.draw(exportGraphics, m);
stage.quality = 'best';
for each (var p:Center in map.centers) {
if (!p.ocean) {
var r:Point = new Point(Math.floor(p.point.x * exportSize/SIZE),
Math.floor(p.point.y * exportSize/SIZE));
exportBitmap.setPixel(r.x, r.y,
exportBitmap.getPixel(r.x, r.y)
| (roads.roadConnections[p]?
exportOverrideColors.POLYGON_CENTER_SAFE
: exportOverrideColors.POLYGON_CENTER));
}
}
saveBitmapToArray();
} else if (layer == 'elevation') {
renderPolygons(exportGraphics.graphics, exportElevationColors, 'elevation', null);
exportBitmap.draw(exportGraphics, m);
saveBitmapToArray();
} else if (layer == 'moisture') {
renderPolygons(exportGraphics.graphics, exportMoistureColors, 'moisture', null);
exportBitmap.draw(exportGraphics, m);
saveBitmapToArray();
}
else if (layer == 'biometiles') {
renderPolygons(exportGraphics.graphics, exportDisplayColors, null, null);
stage.quality = 'low';
exportBitmap.draw(exportGraphics, m);
stage.quality = 'best';
saveBitmapToArray();
}
else if (layer === 'biomediffuse') {
renderPolygons(exportGraphics.graphics, displayColors, null, colorWithSmoothColors);
exportBitmap.draw(exportGraphics, m);
exportBitmap.applyFilter( exportBitmap, exportBitmap.rect, new Point(), new BlurFilter(12, 12, 4) );
addChild( new Bitmap(exportBitmap));
saveBitmapToArray();
}
else if (layer === 'slopes') {
renderPolygons(exportGraphics.graphics, {}, null, colorWithSlope, 0x808080);
exportBitmap.draw(exportGraphics, m);
exportBitmap.applyFilter( exportBitmap, exportBitmap.rect, new Point(), new BlurFilter(4, 4, 4) );
addChild( new Bitmap(exportBitmap));
saveBitmapToArray();
}
if (compress) exportData.compress();
return exportData;
}
public function makeButton(label:String, x:int, y:int, width:int, callback:Function):TextField {
var button:TextField = new TextField();
var format:TextFormat = new TextFormat();
format.font = "Arial";
format.align = 'center';
button.defaultTextFormat = format;
button.text = label;
button.selectable = false;
button.x = x;
button.y = y;
button.width = width;
button.height = 20;
if (callback != null) {
button.background = true;
button.backgroundColor = 0xffffcc;
button.addEventListener(MouseEvent.CLICK, callback);
}
return button;
}
public function addGenerateButtons():void {
var y:int = 4;
var islandShapeButton:TextField = makeButton("Island Shape:", 25, y, 150, null);
var seedLabel:TextField = makeButton("Shape #", 20, y+22, 50, null);
islandSeedInput = makeButton(islandSeedInitial, 70, y+22, 54, null);
islandSeedInput.background = true;
islandSeedInput.backgroundColor = 0xccddcc;
islandSeedInput.selectable = true;
islandSeedInput.type = TextFieldType.INPUT;
islandSeedInput.addEventListener(KeyboardEvent.KEY_UP, function (e:KeyboardEvent):void {
if (e.keyCode == 13) {
go(islandType);
}
});
function markActiveIslandShape(type:String):void {
mapTypes[islandType].backgroundColor = 0xffffcc;
mapTypes[type].backgroundColor = 0xffff00;
}
function switcher(type:String):Function {
return function(e:Event):void {
markActiveIslandShape(type);
go(type);
}
}
var mapTypes:Object = {
'Radial': makeButton("Radial", 23, y+44, 40, switcher('Radial')),
'Perlin': makeButton("Perlin", 65, y+44, 35, switcher('Perlin')),
'Square': makeButton("Square", 102, y+44, 44, switcher('Square')),
'Blob': makeButton("Blob", 148, y+44, 29, switcher('Blob'))
};
markActiveIslandShape(islandType);
controls.addChild(islandShapeButton);
controls.addChild(seedLabel);
controls.addChild(islandSeedInput);
controls.addChild(makeButton("Random", 125, y+22, 56,
function (e:Event):void {
islandSeedInput.text =
( (Math.random()*100000).toFixed(0)
+ "-"
+ (1 + Math.floor(9*Math.random())).toFixed(0) );
go(islandType);
}));
controls.addChild(mapTypes.Radial);
controls.addChild(mapTypes.Perlin);
controls.addChild(mapTypes.Square);
controls.addChild(mapTypes.Blob);
}
public function addViewButtons():void {
var y:int = 300;
function markViewButton(mode:String):void {
views[mapMode].backgroundColor = 0xffffcc;
views[mode].backgroundColor = 0xffff00;
}
function switcher(mode:String):Function {
return function(e:Event):void {
markViewButton(mode);
mapMode = mode;
drawMap(mapMode);
}
}
var views:Object = {
'biome': makeButton("Biomes", 25, y+22, 74, switcher('biome')),
'smooth': makeButton("Smooth", 101, y+22, 74, switcher('smooth')),
'slopes': makeButton("2D slopes", 25, y+44, 74, switcher('slopes')),
'3d': makeButton("3D slopes", 101, y+44, 74, switcher('3d')),
'elevation': makeButton("Elevation", 25, y+66, 74, switcher('elevation')),
'moisture': makeButton("Moisture", 101, y+66, 74, switcher('moisture')),
'polygons': makeButton("Polygons", 25, y+88, 74, switcher('polygons')),
'watersheds': makeButton("Watersheds", 101, y+88, 74, switcher('watersheds'))
};
markViewButton(mapMode);
controls.addChild(makeButton("View:", 50, y, 100, null));
controls.addChild(views.biome);
controls.addChild(views.smooth);
controls.addChild(views.slopes);
controls.addChild(views['3d']);
controls.addChild(views.elevation);
controls.addChild(views.moisture);
controls.addChild(views.polygons);
controls.addChild(views.watersheds);
}
public function addMiscLabels():void {
controls.addChild(makeButton("Distribution:", 50, 120, 100, null));
statusBar = makeButton("", SIZE/2-50, 10, 100, null);
addChild(statusBar);
}
public function addExportButtons():void {
var y:Number = 420;
controls.addChild(makeButton("Export Bitmaps:", 25, y, 150, null));
controls.addChild(makeButton("Elevation", 50, y+22, 100,
function (e:Event):void {
new FileReference().save(makeExport('elevation'), 'map_elevation.data');
}));
controls.addChild(makeButton("Moisture", 50, y+44, 100,
function (e:Event):void {
new FileReference().save(makeExport('moisture'), 'moisture.data');
}));
controls.addChild(makeButton("Overrides", 50, y+66, 100,
function (e:Event):void {
new FileReference().save(makeExport('overrides'), 'overrides.data');
}));
controls.addChild(makeButton("Biome Diffuse", 50, y+88, 100,
function (e:Event):void {
new FileReference().save(makeExport('biomediffuse'), 'map_biomediffuse.data');
}));
controls.addChild(makeButton("Biome Tiles", 50, y+88+22, 100,
function (e:Event):void {
createBiomeApplication( makeExport('biometiles') );
}));
controls.addChild(makeButton("2D Slope (lighting)", 50, y+88+44, 100,
function (e:Event):void {
new FileReference().save( makeExport('slopes'), 'map_slopelighting.data' );
}));
}
private function createBiomeApplication(bytes:ByteArray):void
{
biomeApplicator = new BiomeApplicator32();
biomeApplicator.addEventListener(Event.COMPLETE, onBiomeApplyComplete);
bytes.position = 0;
addChild( biomeApplicator.displayField);
bytes.uncompress();
biomeApplicator.processBiomes(bytes, Math.sqrt(bytes.length), this);
addChild( new Bitmap( biomeApplicator.testbitMap ) );
}
private function onBiomeApplyComplete(e:Event):void
{
biomeApplicator.removeEventListener(Event.COMPLETE, onBiomeApplyComplete);
var data:ByteArray = new ByteArray();
biomeApplicator.painter.writeBmpData(data, biomeApplicator.tileBitMap, biomeApplicator.tilesAcross);
data.compress();
new FileReference().save(data, "map_biometiles.data");
data.uncompress();
biomeApplicator.testbitMap.setVector(biomeApplicator.testbitMap.rect, biomeApplicator.tileBitMap);
if ( biomeApplicator.painter.getBmpData(data).compare(biomeApplicator.testbitMap) != 0) throw new Error("mismatch bitmapdata save!");
var spr:Sprite = new Sprite();
spr.addChild( new Bitmap(biomeApplicator.testbitMap) );
addChild( spr );
_testSpr = spr;
spr.addEventListener(MouseEvent.MOUSE_MOVE, traceBitmap);
addChild( biomeApplicator.displayField );
biomeApplicator.displayField.backgroundColor = 0xFFFFFF;
biomeApplicator.displayField.textColor = 0;
var resultField:TextField;
addChild( resultField= new TextField() );
resultField.text = biomeApplicator.displayField.text;
resultField.y = biomeApplicator.displayField.y + 20;
stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyboardEvent);
}
private function onKeyboardEvent(e:KeyboardEvent):void {
if (e.keyCode === Keyboard.TAB) {
_testSpr.mouseEnabled = !_testSpr.mouseEnabled;
}
}
private function traceBitmap(e:MouseEvent):void
{
var mx:int= e.localX;
var my:int = e.localY;
var color:uint = biomeApplicator.testbitMap.getPixel32(mx, my);
biomeApplicator.displayField.text = String( biomeApplicator.painter.getUint16bits(color) + ", "+color );
}
}
//}
// Make a map out of a voronoi graph
// Author: amitp@cs.stanford.edu
// License: MIT
//package terraingen.island {
import flash.geom.*;
import flash.utils.Dictionary;
import flash.utils.getTimer;
import flash.system.System;
// public
class Map {
static public var NUM_POINTS:int = 1000;
static public var LAKE_THRESHOLD:Number = 0.3; // 0 to 1, fraction of water corners for water polygon
static public var NUM_LLOYD_ITERATIONS:int = 2;
// Passed in by the caller:
public var SIZE:Number;
// Island shape is controlled by the islandRandom seed and the
// type of island, passed in when we set the island shape. The
// islandShape function uses both of them to determine whether any
// point should be water or land.
public var islandShape:Function;
// Island details are controlled by this random generator. The
// initial map upon loading is always deterministic, but
// subsequent maps reset this random number generator with a
// random seed.
public var mapRandom:PM_PRNG = new PM_PRNG();
// These store the graph data
public var points:Vector.<Point>; // Only useful during map construction
public var centers:Vector.<Center>;
public var corners:Vector.<Corner>;
public var edges:Vector.<Edge>;
public function Map(size:Number) {
SIZE = size;
reset();
}
// Random parameters governing the overall shape of the island
public function newIsland(type:String, seed:int, variant:int):void {
islandShape = IslandShape['make'+type](seed);
mapRandom.seed = variant;
}
public function reset():void {
var p:Center, q:Corner, edge:Edge;
// Break cycles so the garbage collector will release data.
if (points) {
points.splice(0, points.length);
}
if (edges) {
for each (edge in edges) {
edge.d0 = edge.d1 = null;
edge.v0 = edge.v1 = null;
}
edges.splice(0, edges.length);
}
if (centers) {
for each (p in centers) {
p.neighbors.splice(0, p.neighbors.length);
p.corners.splice(0, p.corners.length);
p.borders.splice(0, p.borders.length);
}
centers.splice(0, centers.length);
}
if (corners) {
for each (q in corners) {
q.adjacent.splice(0, q.adjacent.length);
q.touches.splice(0, q.touches.length);
q.protrudes.splice(0, q.protrudes.length);
q.downslope = null;
q.watershed = null;
}
corners.splice(0, corners.length);
}
// Clear the previous graph data.
if (!points) points = new Vector.<Point>();
if (!edges) edges = new Vector.<Edge>();
if (!centers) centers = new Vector.<Center>();
if (!corners) corners = new Vector.<Corner>();
System.gc();
}
public function go(first:int, last:int):void {
var stages:Array = [];
function timeIt(name:String, fn:Function):void {
var t:Number = getTimer();
fn();
}
// Generate the initial random set of points
stages.push
(["Place points...",
function():void {
reset();
points = generateRandomPoints();
}]);
stages.push
(["Improve points...",
function():void {
improveRandomPoints(points);
}]);
// Create a graph structure from the Voronoi edge list. The
// methods in the Voronoi object are somewhat inconvenient for
// my needs, so I transform that data into the data I actually
// need: edges connected to the Delaunay triangles and the
// Voronoi polygons, a reverse map from those four points back
// to the edge, a map from these four points to the points
// they connect to (both along the edge and crosswise).
stages.push
( ["Build graph...",
function():void {
var voronoi:Voronoi = new Voronoi(points, null, new Rectangle(0, 0, SIZE, SIZE));
buildGraph(points, voronoi);
improveCorners();
voronoi.dispose();
voronoi = null;
points = null;
}]);
stages.push
(["Assign elevations...",
function():void {
// Determine the elevations and water at Voronoi corners.
assignCornerElevations();
// Determine polygon and corner type: ocean, coast, land.
assignOceanCoastAndLand();
// Rescale elevations so that the highest is 1.0, and they're
// distributed well. We want lower elevations to be more common
// than higher elevations, in proportions approximately matching
// concentric rings. That is, the lowest elevation is the
// largest ring around the island, and therefore should more
// land area than the highest elevation, which is the very
// center of a perfectly circular island.
redistributeElevations(landCorners(corners));
// Assign elevations to non-land corners
for each (var q:Corner in corners) {
if (q.ocean || q.coast) {
q.elevation = 0.0;
}
}
// Polygon elevations are the average of their corners
assignPolygonElevations();
}]);
stages.push
(["Assign moisture...",
function():void {
// Determine downslope paths.
calculateDownslopes();
// Determine watersheds: for every corner, where does it flow
// out into the ocean?
calculateWatersheds();
// Create rivers.
createRivers();
// Determine moisture at corners, starting at rivers
// and lakes, but not oceans. Then redistribute
// moisture to cover the entire range evenly from 0.0
// to 1.0. Then assign polygon moisture as the average
// of the corner moisture.
assignCornerMoisture();
redistributeMoisture(landCorners(corners));
assignPolygonMoisture();
}]);
stages.push
(["Decorate map...",
function():void {
assignBiomes();
}]);
for (var i:int = first; i < last; i++) {
timeIt(stages[i][0], stages[i][1]);
}
}
// Generate random points and assign them to be on the island or
// in the water. Some water points are inland lakes; others are
// ocean. We'll determine ocean later by looking at what's
// connected to ocean.
public function generateRandomPoints():Vector.<Point> {
var p:Point, i:int, points:Vector.<Point> = new Vector.<Point>();
for (i = 0; i < NUM_POINTS; i++) {
p = new Point(mapRandom.nextDoubleRange(10, SIZE-10),
mapRandom.nextDoubleRange(10, SIZE-10));
points.push(p);
}
return points;
}
// Improve the random set of points with Lloyd Relaxation.
public function improveRandomPoints(points:Vector.<Point>):void {
// We'd really like to generate "blue noise". Algorithms:
// 1. Poisson dart throwing: check each new point against all
// existing points, and reject it if it's too close.
// 2. Start with a hexagonal grid and randomly perturb points.
// 3. Lloyd Relaxation: move each point to the centroid of the
// generated Voronoi polygon, then generate Voronoi again.
// 4. Use force-based layout algorithms to push points away.
// 5. More at http://www.cs.virginia.edu/~gfx/pubs/antimony/
// Option 3 is implemented here. If it's run for too many iterations,
// it will turn into a grid, but convergence is very slow, and we only
// run it a few times.
var i:int, p:Point, q:Point, voronoi:Voronoi, region:Vector.<Point>;
for (i = 0; i < NUM_LLOYD_ITERATIONS; i++) {
voronoi = new Voronoi(points, null, new Rectangle(0, 0, SIZE, SIZE));
for each (p in points) {
region = voronoi.region(p);
p.x = 0.0;
p.y = 0.0;
for each (q in region) {
p.x += q.x;
p.y += q.y;
}
p.x /= region.length;
p.y /= region.length;
region.splice(0, region.length);
}
voronoi.dispose();
}
}
// Although Lloyd relaxation improves the uniformity of polygon
// sizes, it doesn't help with the edge lengths. Short edges can
// be bad for some games, and lead to weird artifacts on
// rivers. We can easily lengthen short edges by moving the
// corners, but **we lose the Voronoi property**. The corners are
// moved to the average of the polygon centers around them. Short
// edges become longer. Long edges tend to become shorter. The
// polygons tend to be more uniform after this step.
public function improveCorners():void {
var newCorners:Vector.<Point> = new Vector.<Point>(corners.length);
var q:Corner, r:Center, point:Point, i:int, edge:Edge;
// First we compute the average of the centers next to each corner.
for each (q in corners) {
if (q.border) {
newCorners[q.index] = q.point;
} else {
point = new Point(0.0, 0.0);
for each (r in q.touches) {
point.x += r.point.x;
point.y += r.point.y;
}
point.x /= q.touches.length;
point.y /= q.touches.length;
newCorners[q.index] = point;
}
}
// Move the corners to the new locations.
for (i = 0; i < corners.length; i++) {
corners[i].point = newCorners[i];
}
// The edge midpoints were computed for the old corners and need
// to be recomputed.
for each (edge in edges) {
if (edge.v0 && edge.v1) {
edge.midpoint = Point.interpolate(edge.v0.point, edge.v1.point, 0.5);
}
}
}
// Create an array of corners that are on land only, for use by
// algorithms that work only on land. We return an array instead
// of a vector because the redistribution algorithms want to sort
// this array using Array.sortOn.
public function landCorners(corners:Vector.<Corner>):Array {
var q:Corner, locations:Array = [];
for each (q in corners) {
if (!q.ocean && !q.coast) {
locations.push(q);
}
}
return locations;
}
// Build graph data structure in 'edges', 'centers', 'corners',
// based on information in the Voronoi results: point.neighbors
// will be a list of neighboring points of the same type (corner
// or center); point.edges will be a list of edges that include
// that point. Each edge connects to four points: the Voronoi edge
// edge.{v0,v1} and its dual Delaunay triangle edge edge.{d0,d1}.
// For boundary polygons, the Delaunay edge will have one null
// point, and the Voronoi edge may be null.
public function buildGraph(points:Vector.<Point>, voronoi:Voronoi):void {
var p:Center, q:Corner, point:Point, other:Point;
var libedges:Vector.<DEdge> = voronoi.edges();
var centerLookup:Dictionary = new Dictionary();
// Build Center objects for each of the points, and a lookup map
// to find those Center objects again as we build the graph
for each (point in points) {
p = new Center();
p.index = centers.length;
p.point = point;
p.neighbors = new Vector.<Center>();
p.borders = new Vector.<Edge>();
p.corners = new Vector.<Corner>();
centers.push(p);
centerLookup[point] = p;
}
// Workaround for Voronoi lib bug: we need to call region()
// before Edges or neighboringSites are available
for each (p in centers) {
voronoi.region(p.point);
}
// The Voronoi library generates multiple Point objects for
// corners, and we need to canonicalize to one Corner object.
// To make lookup fast, we keep an array of Points, bucketed by
// x value, and then we only have to look at other Points in
// nearby buckets. When we fail to find one, we'll create a new
// Corner object.
var _cornerMap:Array = [];
function makeCorner(point:Point):Corner {
var q:Corner;
if (point == null) return null;
for (var bucket:int = int(point.x)-1; bucket <= int(point.x)+1; bucket++) {
for each (q in _cornerMap[bucket]) {
var dx:Number = point.x - q.point.x;
var dy:Number = point.y - q.point.y;
if (dx*dx + dy*dy < 1e-6) {
return q;
}
}
}
bucket = int(point.x);
if (!_cornerMap[bucket]) _cornerMap[bucket] = [];
q = new Corner();
q.index = corners.length;
corners.push(q);
q.point = point;
q.border = (point.x == 0 || point.x == SIZE
|| point.y == 0 || point.y == SIZE);
q.touches = new Vector.<Center>();
q.protrudes = new Vector.<Edge>();
q.adjacent = new Vector.<Corner>();
_cornerMap[bucket].push(q);
return q;
}
for each (var libedge:DEdge in libedges) {
var dedge:LineSegment = libedge.delaunayLine();
var vedge:LineSegment = libedge.voronoiEdge();
// Fill the graph data. Make an Edge object corresponding to
// the edge from the voronoi library.
var edge:Edge = new Edge();
edge.index = edges.length;
edge.river = 0;
edges.push(edge);
edge.midpoint = vedge.p0 && vedge.p1 && Point.interpolate(vedge.p0, vedge.p1, 0.5);
// Edges point to corners. Edges point to centers.
edge.v0 = makeCorner(vedge.p0);
edge.v1 = makeCorner(vedge.p1);
edge.d0 = centerLookup[dedge.p0];
edge.d1 = centerLookup[dedge.p1];
// Centers point to edges. Corners point to edges.
if (edge.d0 != null) { edge.d0.borders.push(edge); }
if (edge.d1 != null) { edge.d1.borders.push(edge); }
if (edge.v0 != null) { edge.v0.protrudes.push(edge); }
if (edge.v1 != null) { edge.v1.protrudes.push(edge); }
function addToCornerList(v:Vector.<Corner>, x:Corner):void {
if (x != null && v.indexOf(x) < 0) { v.push(x); }
}
function addToCenterList(v:Vector.<Center>, x:Center):void {
if (x != null && v.indexOf(x) < 0) { v.push(x); }
}
// Centers point to centers.
if (edge.d0 != null && edge.d1 != null) {
addToCenterList(edge.d0.neighbors, edge.d1);
addToCenterList(edge.d1.neighbors, edge.d0);
}
// Corners point to corners
if (edge.v0 != null && edge.v1 != null) {
addToCornerList(edge.v0.adjacent, edge.v1);
addToCornerList(edge.v1.adjacent, edge.v0);
}
// Centers point to corners
if (edge.d0 != null) {
addToCornerList(edge.d0.corners, edge.v0);
addToCornerList(edge.d0.corners, edge.v1);
}
if (edge.d1 != null) {
addToCornerList(edge.d1.corners, edge.v0);
addToCornerList(edge.d1.corners, edge.v1);
}
// Corners point to centers
if (edge.v0 != null) {
addToCenterList(edge.v0.touches, edge.d0);
addToCenterList(edge.v0.touches, edge.d1);
}
if (edge.v1 != null) {
addToCenterList(edge.v1.touches, edge.d0);
addToCenterList(edge.v1.touches, edge.d1);
}
}
}
// Determine elevations and water at Voronoi corners. By
// construction, we have no local minima. This is important for
// the downslope vectors later, which are used in the river
// construction algorithm. Also by construction, inlets/bays
// push low elevation areas inland, which means many rivers end
// up flowing out through them. Also by construction, lakes
// often end up on river paths because they don't raise the
// elevation as much as other terrain does.
public function assignCornerElevations():void {
var q:Corner, s:Corner;
var queue:Array = [];
for each (q in corners) {
q.water = !inside(q.point);
}
for each (q in corners) {
// The edges of the map are elevation 0
if (q.border) {
q.elevation = 0.0;
queue.push(q);
} else {
q.elevation = Infinity;
}
}
// Traverse the graph and assign elevations to each point. As we
// move away from the map border, increase the elevations. This
// guarantees that rivers always have a way down to the coast by
// going downhill (no local minima).
while (queue.length > 0) {
q = queue.shift();
for each (s in q.adjacent) {
// Every step up is epsilon over water or 1 over land. The
// number doesn't matter because we'll rescale the
// elevations later.
var newElevation:Number = 0.01 + q.elevation;
if (!q.water && !s.water) {
newElevation += 1;
}
// If this point changed, we'll add it to the queue so
// that we can process its neighbors too.
if (newElevation < s.elevation) {
s.elevation = newElevation;
queue.push(s);
}
}
}
}
// Change the overall distribution of elevations so that lower
// elevations are more common than higher
// elevations. Specifically, we want elevation X to have frequency
// (1-X). To do this we will sort the corners, then set each
// corner to its desired elevation.
public function redistributeElevations(locations:Array):void {
// SCALE_FACTOR increases the mountain area. At 1.0 the maximum
// elevation barely shows up on the map, so we set it to 1.1.
var SCALE_FACTOR:Number = 1.1;
var i:int, y:Number, x:Number;
locations.sortOn('elevation', Array.NUMERIC);
for (i = 0; i < locations.length; i++) {
// Let y(x) be the total area that we want at elevation <= x.
// We want the higher elevations to occur less than lower
// ones, and set the area to be y(x) = 1 - (1-x)^2.
y = i/(locations.length-1);
// Now we have to solve for x, given the known y.
// * y = 1 - (1-x)^2
// * y = 1 - (1 - 2x + x^2)
// * y = 2x - x^2
// * x^2 - 2x + y = 0
// From this we can use the quadratic equation to get:
x = Math.sqrt(SCALE_FACTOR) - Math.sqrt(SCALE_FACTOR*(1-y));
if (x > 1.0) x = 1.0; // TODO: does this break downslopes?
locations[i].elevation = x;
}
}
// Change the overall distribution of moisture to be evenly distributed.
public function redistributeMoisture(locations:Array):void {
var i:int;
locations.sortOn('moisture', Array.NUMERIC);
for (i = 0; i < locations.length; i++) {
locations[i].moisture = i/(locations.length-1);
}
}
// Determine polygon and corner types: ocean, coast, land.
public function assignOceanCoastAndLand():void {
// Compute polygon attributes 'ocean' and 'water' based on the
// corner attributes. Count the water corners per
// polygon. Oceans are all polygons connected to the edge of the
// map. In the first pass, mark the edges of the map as ocean;
// in the second pass, mark any water-containing polygon
// connected an ocean as ocean.
var queue:Array = [];
var p:Center, q:Corner, r:Center, numWater:int;
for each (p in centers) {
numWater = 0;
for each (q in p.corners) {
if (q.border) {
p.border = true;
p.ocean = true;
q.water = true;
queue.push(p);
}
if (q.water) {
numWater += 1;
}
}
p.water = (p.ocean || numWater >= p.corners.length * LAKE_THRESHOLD);
}
while (queue.length > 0) {
p = queue.shift();
for each (r in p.neighbors) {
if (r.water && !r.ocean) {
r.ocean = true;
queue.push(r);
}
}
}
// Set the polygon attribute 'coast' based on its neighbors. If
// it has at least one ocean and at least one land neighbor,
// then this is a coastal polygon.
for each (p in centers) {
var numOcean:int = 0;
var numLand:int = 0;
for each (r in p.neighbors) {
numOcean += int(r.ocean);
numLand += int(!r.water);
}
p.coast = (numOcean > 0) && (numLand > 0);
}
// Set the corner attributes based on the computed polygon
// attributes. If all polygons connected to this corner are
// ocean, then it's ocean; if all are land, then it's land;
// otherwise it's coast.
for each (q in corners) {
numOcean = 0;
numLand = 0;
for each (p in q.touches) {
numOcean += int(p.ocean);
numLand += int(!p.water);
}
q.ocean = (numOcean == q.touches.length);
q.coast = (numOcean > 0) && (numLand > 0);
q.water = q.border || ((numLand != q.touches.length) && !q.coast);
}
}
// Polygon elevations are the average of the elevations of their corners.
public function assignPolygonElevations():void {
var p:Center, q:Corner, sumElevation:Number;
for each (p in centers) {
sumElevation = 0.0;
for each (q in p.corners) {
sumElevation += q.elevation;
}
p.elevation = sumElevation / p.corners.length;
}
}
// Calculate downslope pointers. At every point, we point to the
// point downstream from it, or to itself. This is used for
// generating rivers and watersheds.
public function calculateDownslopes():void {
var q:Corner, s:Corner, r:Corner;
for each (q in corners) {
r = q;
for each (s in q.adjacent) {
if (s.elevation <= r.elevation) {
r = s;
}
}
q.downslope = r;
}
}
// Calculate the watershed of every land point. The watershed is
// the last downstream land point in the downslope graph. TODO:
// watersheds are currently calculated on corners, but it'd be
// more useful to compute them on polygon centers so that every
// polygon can be marked as being in one watershed.
public function calculateWatersheds():void {
var q:Corner, r:Corner, i:int, changed:Boolean;
// Initially the watershed pointer points downslope one step.
for each (q in corners) {
q.watershed = q;
if (!q.ocean && !q.coast) {
q.watershed = q.downslope;
}
}
// Follow the downslope pointers to the coast. Limit to 100
// iterations although most of the time with NUM_POINTS=2000 it
// only takes 20 iterations because most points are not far from
// a coast. TODO: can run faster by looking at
// p.watershed.watershed instead of p.downslope.watershed.
for (i = 0; i < 100; i++) {
changed = false;
for each (q in corners) {
if (!q.ocean && !q.coast && !q.watershed.coast) {
r = q.downslope.watershed;
if (!r.ocean) q.watershed = r;
changed = true;
}
}
if (!changed) break;
}
// How big is each watershed?
for each (q in corners) {
r = q.watershed;
r.watershed_size = 1 + (r.watershed_size || 0);
}
}
// Create rivers along edges. Pick a random corner point, then
// move downslope. Mark the edges and corners as rivers.
public function createRivers():void {
var i:int, q:Corner, edge:Edge;
for (i = 0; i < SIZE/2; i++) {
q = corners[mapRandom.nextIntRange(0, corners.length-1)];
if (q.ocean || q.elevation < 0.3 || q.elevation > 0.9) continue;
// Bias rivers to go west: if (q.downslope.x > q.x) continue;
while (!q.coast) {
if (q == q.downslope) {
break;
}
edge = lookupEdgeFromCorner(q, q.downslope);
edge.river = edge.river + 1;
q.river = (q.river || 0) + 1;
q.downslope.river = (q.downslope.river || 0) + 1; // TODO: fix double count
q = q.downslope;
}
}
}
// Calculate moisture. Freshwater sources spread moisture: rivers
// and lakes (not oceans). Saltwater sources have moisture but do
// not spread it (we set it at the end, after propagation).
public function assignCornerMoisture():void {
var q:Corner, r:Corner, newMoisture:Number;
var queue:Array = [];
// Fresh water
for each (q in corners) {
if ((q.water || q.river > 0) && !q.ocean) {
q.moisture = q.river > 0? Math.min(3.0, (0.2 * q.river)) : 1.0;
queue.push(q);
} else {
q.moisture = 0.0;
}
}
while (queue.length > 0) {
q = queue.shift();
for each (r in q.adjacent) {
newMoisture = q.moisture * 0.9;
if (newMoisture > r.moisture) {
r.moisture = newMoisture;
queue.push(r);
}
}
}
// Salt water
for each (q in corners) {
if (q.ocean || q.coast) {
q.moisture = 1.0;
}
}
}
// Polygon moisture is the average of the moisture at corners
public function assignPolygonMoisture():void {
var p:Center, q:Corner, sumMoisture:Number;
for each (p in centers) {
sumMoisture = 0.0;
for each (q in p.corners) {
if (q.moisture > 1.0) q.moisture = 1.0;
sumMoisture += q.moisture;
}
p.moisture = sumMoisture / p.corners.length;
}
}
// Assign a biome type to each polygon. If it has
// ocean/coast/water, then that's the biome; otherwise it depends
// on low/high elevation and low/medium/high moisture. This is
// roughly based on the Whittaker diagram but adapted to fit the
// needs of the island map generator.
static public function getBiome(p:Center):String {
if (p.ocean) {
return 'OCEAN';
} else if (p.water) {
if (p.elevation < 0.1) return 'MARSH';
if (p.elevation > 0.8) return 'ICE';
return 'LAKE';
} else if (p.coast) {
return 'BEACH';
} else if (p.elevation > 0.8) {
if (p.moisture > 0.50) return 'SNOW';
else if (p.moisture > 0.33) return 'TUNDRA';
else if (p.moisture > 0.16) return 'BARE';
else return 'SCORCHED';
} else if (p.elevation > 0.6) {
if (p.moisture > 0.66) return 'TAIGA';
else if (p.moisture > 0.33) return 'SHRUBLAND';
else return 'TEMPERATE_DESERT';
} else if (p.elevation > 0.3) {
if (p.moisture > 0.83) return 'TEMPERATE_RAIN_FOREST';
else if (p.moisture > 0.50) return 'TEMPERATE_DECIDUOUS_FOREST';
else if (p.moisture > 0.16) return 'GRASSLAND';
else return 'TEMPERATE_DESERT';
} else {
if (p.moisture > 0.66) return 'TROPICAL_RAIN_FOREST';
else if (p.moisture > 0.33) return 'TROPICAL_SEASONAL_FOREST';
else if (p.moisture > 0.16) return 'GRASSLAND';
else return 'SUBTROPICAL_DESERT';
}
}
public function assignBiomes():void {
var p:Center;
for each (p in centers) {
p.biome = getBiome(p);
}
}
// Look up a Voronoi Edge object given two adjacent Voronoi
// polygons, or two adjacent Voronoi corners
public function lookupEdgeFromCenter(p:Center, r:Center):Edge {
for each (var edge:Edge in p.borders) {
if (edge.d0 == r || edge.d1 == r) return edge;
}
return null;
}
public function lookupEdgeFromCorner(q:Corner, s:Corner):Edge {
for each (var edge:Edge in q.protrudes) {
if (edge.v0 == s || edge.v1 == s) return edge;
}
return null;
}
// Determine whether a given point should be on the island or in the water.
public function inside(p:Point):Boolean {
return islandShape(new Point(2*(p.x/SIZE - 0.5), 2*(p.y/SIZE - 0.5)));
}
}
//}
//package {
/*public*/ class MathUtils {
static public function clamp(n:Number):Number {
return n < 0 ? 0 : n > 1 ? 1 : n;
}
static public function contrast(n:Number, c:Number = 1):Number {
return ((n*2 - 1) * c * c + 1) * 0.5;
}
static public function brightness(n:Number, b:Number = 0):Number {
return (b<0) ? n * (1 + b) : 1 - (1 - n) * (1 - b);
}
}
//}
//package {
/*public*/ class PM_PRNG
{
public var seed:uint;
public static const MAX:uint = 0X7FFFFFFE;
public function PM_PRNG()
{
seed = 1;
}
public function nextInt():uint
{
return gen();
}
public function nextDouble():Number
{
return (gen() / 2147483647);
}
public function nextIntRange(min:Number, max:Number):uint
{
min -= .4999;
max += .4999;
return Math.round(min + ((max - min) * nextDouble()));
}
public function nextDoubleRange(min:Number, max:Number):Number
{
return min + ((max - min) * nextDouble());
}
public function setSeed(v:uint):void
{
if (v == 0) throw new Error("Seed value cannot be zero!");
if (v > MAX) throw new Error("Seed cannot exceed max:"+seed+" /" + MAX);
seed = v;
}
private function gen():uint
{
return seed = (seed * 16807) % 2147483647;
}
}
//}