Ticket #658: mapgen.js

var startTime = dateNow();

function log(msg)
{
    println(msg);
}

function error(msg)
{
    println("Error: "+msg);
}

function warning(msg)
{
    println("Warning: "+msg);
}

function Area(points)
{
    this.points = (points !== undefined ? points : []);
}

///////////////////////////////////////////////////////////////////////////
//  NullConstraints: No constraint - always return true
///////////////////////////////////////////////////////////////////////////
function NullConstraint() {}

NullConstraint.prototype.allows = function(x, y)
{
    return true;
};

///////////////////////////////////////////////////////////////////////////
//  AndConstraints: Check multiple constraints  
///////////////////////////////////////////////////////////////////////////
function AndConstraint(constraints)
{
    this.constraints = constraints;
}

AndConstraint.prototype.allows = function(x, y)
{
    for (var i=0; i < this.constraints.length; ++i)
    {
        if (!this.constraints[i].allows(x, y))
            return false;
    }

    return true;
};

///////////////////////////////////////////////////////////////////////////
//  AvoidAreaConstraint
///////////////////////////////////////////////////////////////////////////
function AvoidAreaConstraint(area)
{
    this.area = area;
}

AvoidAreaConstraint.prototype.allows = function(x, y)
{
    return g_Map.area[x][y] != this.area;
};

///////////////////////////////////////////////////////////////////////////
//  AvoidTextureConstraint
///////////////////////////////////////////////////////////////////////////
function AvoidTextureConstraint(textureID)
{
    this.textureID = textureID;
}

AvoidTextureConstraint.prototype.allows = function(x, y)
{
    return g_Map.texture[x][y] != this.textureID;
};

///////////////////////////////////////////////////////////////////////////
//  AvoidTileClassConstraint
///////////////////////////////////////////////////////////////////////////
function AvoidTileClassConstraint(tileClassID, distance)
{
    this.tileClass = getTileClass(tileClassID);
    this.distance = distance;
}

AvoidTileClassConstraint.prototype.allows = function(x, y)
{
    return this.tileClass.countMembersInRadius(x, y, this.distance) == 0;
};

///////////////////////////////////////////////////////////////////////////
//  StayInTileClassConstraint
///////////////////////////////////////////////////////////////////////////
function StayInTileClassConstraint(tileClassID, distance)
{
    this.tileClass = getTileClass(tileClassID);
    this.distance = distance;
}

StayInTileClassConstraint.prototype.allows = function(x, y)
{
    return this.tileClass.countNonMembersInRadius(x, y, this.distance) == 0;
};

///////////////////////////////////////////////////////////////////////////
//  BorderTileClassConstraint
///////////////////////////////////////////////////////////////////////////
function BorderTileClassConstraint(tileClassID, distanceInside, distanceOutside)
{
    this.tileClass = getTileClass(tileClassID);
    this.distanceInside = distanceInside;
    this.distanceOutside = distanceOutside;
}

BorderTileClassConstraint.prototype.allows = function(x, y)
{
    return (this.tileClass.countMembersInRadius(x, y, this.distanceOutside) > 0
        && this.tileClass.countNonMembersInRadius(x, y, this.distanceInside) > 0);
};
function Entity(name, player, x, y, angle)
{
    // Get unique ID
    this.id = g_Map.getEntityID();
    this.name = name;

    // Convert from tile coords to map coords
    this.x = x;
    this.y = y;

    if (player !== undefined)
    {
        this.player = player;
        this.isActor = false;
    }
    else
    {   // Actors  have no player ID
        this.isActor = true;
    }

    this.orientation = (angle !== undefined ? angle : 0);
}

/////////////////////////////////////////////////////////////////////////////////////////////
//  Constant definitions
/////////////////////////////////////////////////////////////////////////////////////////////

const PI = Math.PI;

const SEA_LEVEL = 20.0;

const TERRAIN_SEPARATOR = "|";

const TILES_PER_PATCH = 16;

/////////////////////////////////////////////////////////////////////////////////////////////
//  Utility functions
/////////////////////////////////////////////////////////////////////////////////////////////

function fractionToTiles(f) {
    return getMapSize() * f;
}

function tilesToFraction(t) {
    return t / getMapSize();
}

function fractionToSize(f) {
    return getMapSizeSqr() * f;
}

function sizeToFraction(s) {
    return s / getMapSizeSqr();
}

function cos(x) {
    return Math.cos(x);
}

function sin(x) {
    return Math.sin(x);
}

function tan(x) {
    return Math.tan(x);
}

function abs(x) {
    return Math.abs(x);
}

function round(x) {
    return Math.round(x);
}

function lerp(a, b, t) {
    return a + (b-a) * t;
}

function sqrt(x) {
    return Math.sqrt(x);
}

function ceil(x) {
    return Math.ceil(x);
}

function floor(x) {
    return Math.floor(x);
}

function max(x, y) {
    return x > y ? x : y;
}

function min(x, y) {
    return x < y ? x : y;
}

function println(x) {
    print(x);
    print("\n");
}

function argsToArray(x)
{
    var numArgs = x.length;
    if (numArgs != 1)
    {
        var ret = new Array(numArgs);
        for (var i=0; i < numArgs; i++)
        {
            ret[i] = x[i];
        }
        return ret;
    }
    else
    {
        return x[0];
    }
}

function chooseRand()
{
    if (arguments.length==0)
    {
        error("chooseRand: requires at least 1 argument");
    }
    var ar = argsToArray(arguments);
    return ar[randInt(ar.length)];
}

function createAreas(centeredPlacer, painter, constraint, num, retryFactor)
{
    if (retryFactor === undefined)
        retryFactor = 10;

    var maxFail = num * retryFactor;
    var good = 0;
    var bad = 0;
    var ret = [];
    while(good < num && bad <= maxFail)
    {
        centeredPlacer.x = randInt(getMapSize());
        centeredPlacer.y = randInt(getMapSize());
        var r = g_Map.createArea(centeredPlacer, painter, constraint);
        if (r !== undefined)
        {
            good++;
            ret.push(r);
        }
        else
        {
            bad++;
        }
    }

    return ret;
}

function createObjectGroups(placer, player, constraint, num, retryFactor)
{
    if (retryFactor === undefined)
        retryFactor = 10;

    var maxFail = num * retryFactor;
    var good = 0;
    var bad = 0;
    while(good < num && bad <= maxFail)
    {
        placer.x = randInt(getMapSize());
        placer.y = randInt(getMapSize());
        var r = createObjectGroup(placer, player, constraint);

        if (r !== undefined)
        {
            good++;
        }
        else
        {
            bad++;
        }
    }
    return good;
}

function createTerrain(terrain)
{
    if (terrain instanceof Array)
    {
        var terrainList = [];

        for (var i = 0; i < terrain.length; ++i)
            terrainList.push(createTerrain(terrain[i]));

        return new RandomTerrain(terrainList);
    }
    else
    {
        return createSimpleTerrain(terrain);
    }
}

function createSimpleTerrain(terrain)
{
    if (typeof(terrain) == "string")
    {   // Split string by pipe | character, this allows specifying terrain + tree type in single string
        var params = terrain.split(TERRAIN_SEPARATOR, 2);

        if (params.length != 2)
        {
            return new SimpleTerrain(terrain);
        }
        else
        {
            return new SimpleTerrain(params[0], params[1]);
        }
    }
    else
    {
        error("createSimpleTerrain expects string as input, received "+terrain);
        return undefined;
    }
}

function placeObject(type, player, x, y, angle)
{
    g_Map.addObjects(new Entity(type, player, x, y, angle));
}

function placeTerrain(x, y, terrain)
{
    // convert terrain param into terrain object
    g_Map.placeTerrain(x, y, createTerrain(terrain));

}

/////////////////////////////////////////////////////////////////////////////////////////////
//  Access global map variable
/////////////////////////////////////////////////////////////////////////////////////////////

function createTileClass()
{
    return g_Map.createTileClass();
}

function getTileClass(id)
{
    // Check for valid class id
    if (id < 1 || id > g_Map.tileClasses.length)
    {
        //error("Invalid tile class id: "+id);
        return null;
    }

    return g_Map.tileClasses[id - 1];
}

function createArea(placer, painter, constraint)
{
    return g_Map.createArea(placer, painter, constraint);
}

function createObjectGroup(placer, player, constraint)
{
    return g_Map.createObjectGroup(placer, player, constraint);
}

function getMapSize()
{
    return g_Map.size;
}

function getMapSizeSqr()
{
    return g_Map.size*g_Map.size;
}

function getNumPlayers()
{
    return g_MapSettings.PlayerData.length;
}

function getCivCode(player)
{
    return g_MapSettings.PlayerData[player].Civ;
}

function getHeight(x, y)
{
    g_Map.getHeight(x, y);
}

function setHeight(x, y, height)
{
    g_Map.setHeight(x, y, height);
}

/////////////////////////////////////////////////////////////////////////////////////////////
//  Utility functions for classes
/////////////////////////////////////////////////////////////////////////////////////////////


// Add point to given class by id
function addToClass(x, y, id)
{
    var tileClass = getTileClass(id);

    if (tileClass !== null)
        tileClass.add(x, y);
}

// Create a painter for the given class
function paintClass(id)
{
    return new TileClassPainter(getTileClass(id));
}

// Create an avoid constraint for the given classes by the given distances
function avoidClasses(/*class1, dist1, class2, dist2, etc*/)
{
    var ar = new Array(arguments.length/2);
    for (var i=0; i < arguments.length/2; i++)
    {
        ar[i] = new AvoidTileClassConstraint(arguments[2*i], arguments[2*i+1]);
    }
    // Return single constraint
    return new AndConstraint(ar);
}
//////////////////////////////////////////////////////////////////////
//  Map
//////////////////////////////////////////////////////////////////////

function Map(size, baseHeight)
{
    // Size must be 0 to 1024, divisible by 16
    this.size = size;

    // Create 2D arrays for texture, object, and area maps
    this.texture = new Array(size);
    this.terrainObjects = new Array(size);
    this.area = new Array(size);

    for (var i=0; i < size; i++)
    {
        this.texture[i] = new Uint16Array(size);        // uint16
        this.terrainObjects[i] = new Array(size);       // entity
        this.area[i] = new Array(size);         // area

        for (var j = 0; j < size; j++)
        {
            this.terrainObjects[i][j] = [];
        }
    }

    var mapSize = size+1;

    // Create 2D array for heightmap
    this.height = new Array(mapSize);
    for (var i=0; i < mapSize; i++)
    {
        this.height[i] = new Float32Array(mapSize); //float32
        for (var j=0; j < mapSize; j++)
        {   // Initialize height map to baseHeight
            this.height[i][j] = baseHeight;
        }
    }

    // Create name <-> id maps for textures
    this.nameToID = {};
    this.IDToName = [];             //string

    // Other arrays
    this.objects = [];              //object
    this.areas = [];                    //area
    this.tileClasses = [];              //int

    // Starting entity ID
    this.entityCount = 150;
}

Map.prototype.initTerrain = function(baseTerrain)
{
    // Initialize base terrain
    var size = this.size;
    for (var i=0; i < size; i++)
    {
        for (var j=0; j < size; j++)
        {
            baseTerrain.place(i, j);
        }
    }
};

// Return ID of texture (by name)
Map.prototype.getID = function(texture)
{
    if (texture in (this.nameToID))
    {
        return this.nameToID[texture];
    }

    // Add new texture
    var id = this.IDToName.length;
    this.nameToID[texture] = id;
    this.IDToName[id] = texture;

    return id;
};

// Return next free entity ID
Map.prototype.getEntityID = function()
{
    return this.entityCount++;
}

// Check bounds
Map.prototype.validT = function(x, y)
{
    return x >= 0 && y >= 0 && x < this.size && y < this.size;
};

// Check bounds on height map (size + 1 by size + 1)
Map.prototype.validH = function(x, y)
{
    return x >= 0 && y >= 0 && x <= this.size && y <= this.size;
};

// Check bounds on tile class
Map.prototype.validClass = function(c)
{
    return c >= 0 && c < this.tileClasses.length;
};

Map.prototype.getTexture = function(x, y)
{
    if (!this.validT(x, y))
        error("getTexture: invalid tile position ("+x+", "+y+")");

    return this.IDToName[this.texture[x][y]];
};

Map.prototype.setTexture = function(x, y, texture)
{
    if (!this.validT(x, y))
        error("setTexture: invalid tile position ("+x+", "+y+")");

     this.texture[x][y] = this.getID(texture);
};

Map.prototype.getHeight = function(x, y)
{
    if (!this.validH(x, y))
        error("getHeight: invalid vertex position ("+x+", "+y+")");

    return this.height[x][y];
};

Map.prototype.setHeight = function(x, y, height)
{
    if (!this.validH(x, y))
        error("setHeight: invalid vertex position ("+x+", "+y+")");

    this.height[x][y] = height;
};

Map.prototype.getTerrainObjects = function(x, y)
{
    if (!this.validT(x, y))
        error("getTerrainObjects: invalid tile position ("+x+", "+y+")");

    return this.terrainObjects[x][y];
};

Map.prototype.setTerrainObjects = function(x, y, objects)
{
    if (!this.validT(x, y))
        error("setTerrainObjects: invalid tile position ("+x+", "+y+")");

    this.terrainObjects[x][y] = objects;
};

Map.prototype.placeTerrain = function(x, y, terrain)
{
    terrain.place(x, y);
};

Map.prototype.addObjects = function(obj)
{
    this.objects = this.objects.concat(obj);
};

Map.prototype.createArea = function(placer, painter, constraint)
{
    // Check for multiple painters
    if (painter instanceof Array)
    {
        var painterArray = painter;
        painter = new MultiPainter(painterArray);
    }

    // Check for null constraint
    if (constraint === undefined || constraint === null)
    {
        constraint = new NullConstraint();
    }
    else if (constraint instanceof Array)
    {   // Check for multiple constraints
        var constraintArray = constraint;
        constraint = new AndConstraint(constraintArray);
    }

    var points = placer.place(constraint);
    if (!points)
        return undefined;

    var a = new Area(points);
    for (var i=0; i < points.length; i++)
    {
        this.area[points[i].x][points[i].y] = a;
    }

    painter.paint(a);
    this.areas.push(a);

    return a;
};

Map.prototype.createObjectGroup = function(placer, player, constraint)
{
    // Check for null constraint
    if (constraint === undefined || constraint === null)
    {
        constraint = new NullConstraint();
    }
    else if (constraint instanceof Array)
    {   // Check for multiple constraints
        var constraintArray = constraint;
        constraint = new AndConstraint(constraintArray);
    }

    return placer.place(player, constraint);
};

Map.prototype.createTileClass = function()
{
    this.tileClasses.push(new TileClass(this.size));

    return this.tileClasses.length;
};

// Get height taking into account terrain curvature
Map.prototype.getExactHeight = function(x, y)
{
    var xi = min(Math.floor(x), this.size);
    var yi = min(Math.floor(y), this.size);
    var xf = x - xi;
    var yf = y - yi;

    var h00 = this.height[xi][yi];
    var h01 = this.height[xi][yi+1];
    var h10 = this.height[xi+1][yi];
    var h11 = this.height[xi+1][yi+1];

    return ( 1 - yf ) * ( ( 1 - xf ) * h00 + xf * h10 ) + yf * ( ( 1 - xf ) * h01 + xf * h11 ) ;
};

Map.prototype.getMapData = function()
{
    var data = {};

    // Build entity array
    var entities = [];

    // Terrain objects first (trees)
    var size = this.size;
    for (var x=0; x < size; ++x)
    {
        for (var y=0; y < size; ++y)
        {
            if (this.terrainObjects[x][y].length)
                entities = entities.concat(this.terrainObjects[x][y]);
        }
    }

    // Now other entities
    for (var n in this.objects)
    {
        entities = entities.concat(this.objects[n]);
    }

    // Convert from tiles to map coordinates
    for (var n in entities)
    {
        var e = entities[n];
        e.x *= 4;
        e.y *= 4;

        entities[n] = e;
    }
    data["entities"] = entities;

    // Terrain
    data["size"] = this.size;

    // Convert 2D heightmap array to flat array
    //  Flat because it's easier to handle by the engine
    var mapSize = size+1;
    var height16 = new Array(mapSize*mapSize);      // uint16
    for (var x=0; x < mapSize; x++)
    {
        for (var y=0; y < mapSize; y++)
        {
            var intHeight = Math.floor((this.height[x][y] + SEA_LEVEL) * 256.0 / 0.35); // floor

            if (intHeight > 65000)
                intHeight = 65000;
            else if (intHeight < 0)
                intHeight = 0;

            height16[y*mapSize + x] = intHeight;
        }
    }
    data["height"] = height16;
    data["seaLevel"] = SEA_LEVEL;

    // Get array of textures used in this map
    var textureNames = [];
    for (var name in this.nameToID)
        textureNames.push(name);

    data["textureNames"] = textureNames;
    data["numTextures"] = textureNames.length;

    //  Convert 2D tile data to flat array, reodering into patches as expected by MapReader
    var tiles = new Array(size*size);
    var patches = size/16;
    for (var x=0; x < size; x++)
    {
        var patchX = Math.floor(x/16);
        var offX = x%16;
        for (var y=0; y < size; y++)
        {
            var patchY = Math.floor(y/16);
            var offY = y%16;
            tiles[(patchY*patches + patchX)*256 + (offY*16 + offX)] = this.texture[x][y];
        }
    }
    data["tileData"] = tiles;

    return data;
};
// TODO: Since there's only one map anyway, just use this global variable
var g_Map;

// Map settings - once initialized, has all the game setup data, including player array
var g_MapSettings = {
    Size : 13,
    BaseTerrain: "grass1_spring",
    BaseHeight: 0,
    PlayerData : [ {}, {} ]
};

var g_Environment = {
    SkySet: "cirrus",
    SunColour: {r: 1.47461, g: 1.47461, b: 1.47461},
    SunElevation: 0.951868,
    SunRotation: -0.532844,
    TerrainAmbientColour: {r: 0.337255, g: 0.403922, b: 0.466667},
    UnitsAmbientColour: {r: 0.501961, g: 0.501961, b: 0.501961},
    Water: {
        WaterBody: {
            Type: "default",
            Colour: {r: 0.294118, g: 0.34902, b: 0.694118},
            Height: 17.6262,
            Shininess: 150,
            Waviness: 8,
            Murkiness: 0.458008,
            Tint: {r: 0.447059, g: 0.411765, b: 0.321569},
            ReflectionTint: {r: 0.619608, g: 0.584314, b: 0.47451},
            ReflectionTintStrength: 0.298828
        }
    }
};

var g_Camera = {
    Position: {x: 100, y: 150, z: -100},
    Rotation: 0,
    Declination: 0.523599
};

function InitMapGen(settings)
{
    if (settings === undefined || settings == {})
    {
        warn("InitMapGen: settings missing");
    }
    else
    {
        g_MapSettings = settings;
    }

    // Create new map
    log("Creating new map...");
    var terrain = createTerrain(g_MapSettings.BaseTerrain);

    g_Map = new Map(g_MapSettings.Size * TILES_PER_PATCH, g_MapSettings.BaseHeight);
    g_Map.initTerrain(terrain);
}

function SaveMap()
{
    log("Saving map...");

    // Get necessary data from map
    var data = g_Map.getMapData();

    // Add environment and camera settings
    g_Environment.Water.WaterBody.Height = SEA_LEVEL - 0.1;
    data.Environment = g_Environment;
    data.Camera = g_Camera;

    return data;
}
// Utility function used in both noises as an ease curve
function easeCurve(t)
{
    return t*t*t*(t*(t*6-15)+10);
}

// Find mod of number but only positive values
function modPos(num, m)
{
    var p = num % m;
    if (p < 0)
        p += m;

    return p;
}

/////////////////////////////////////////////////////////////////////
//  Noise2D
/////////////////////////////////////////////////////////////////////

function Noise2D(freq)
{
    freq = Math.floor(freq);
    this.freq = freq;
    this.grads = new Array(freq);

    for (var i=0; i < freq; ++i)
    {
        this.grads[i] = new Array(freq);
        for (var j=0; j < freq; ++j)
        {
            var a = randFloat() * 2 * PI;

            this.grads[i][j] = new Vector2D(Math.cos(a), Math.sin(a));
        }
    }
}

Noise2D.prototype.get = function(x, y)
{
    x *= this.freq;
    y *= this.freq;

    var ix = modPos(Math.floor(x), this.freq);
    var iy = modPos(Math.floor(y), this.freq);

    var fx = x - ix;
    var fy = y - iy;

    var ix1 = (ix+1) % this.freq;
    var iy1 = (iy+1) % this.freq;

    var s = this.grads[ix][iy].dot(new Vector2D(fx, fy));
    var t = this.grads[ix1][iy].dot(new Vector2D(fx-1, fy));
    var u = this.grads[ix][iy1].dot(new Vector2D(fx, fy-1));
    var v = this.grads[ix1][iy1].dot(new Vector2D(fx-1, fy-1));

    var ex = easeCurve(fx);
    var ey = easeCurve(fy);
    var a = s + ex*(t-s);
    var b = u + ex*(v-u);
    return (a + ey*(b-a)) * 0.5 + 0.5;
};

/////////////////////////////////////////////////////////////////////
//  Noise3D
/////////////////////////////////////////////////////////////////////

function Noise3D(freq, vfreq)
{
    freq = Math.floor(freq);
    vfreq = Math.floor(vfreq);
    this.freq = freq;
    this.vfreq = vfreq;
    this.grads = new Array(freq);

    for (var i=0; i < freq; ++i)
    {
        this.grads[i] = new Array(freq);
        for (var j=0; j < freq; ++j)
        {
            this.grads[i][j] = new Array(vfreq);
            for(var k=0; k < vfreq; ++k)
            {
                var v = new Vector3D();
                do
                {
                    v.set(2*randFloat()-1, 2*randFloat()-1, 2*randFloat()-1);
                }
                while(v.lengthSquared() > 1 || v.lengthSquared() < 0.1);

                v.normalize();

                this.grads[i][j][k] = v;
            }
        }
    }
}

Noise3D.prototype.get = function(x, y, z)
{
    x *= this.freq;
    y *= this.freq;
    z *= this.vfreq;

    var ix =modPos(Math.floor(x), this.freq);
    var iy = modPos(Math.floor(y), this.freq);
    var iz = modPos(Math.floor(z), this.vfreq);

    var fx = x - ix;
    var fy = y - iy;
    var fz = z - iz;

    var ix1 = (ix+1) % this.freq;
    var iy1 = (iy+1) % this.freq;
    var iz1 = (iz+1) % this.vfreq;

    var s0 = this.grads[ix][iy][iz].dot(new Vector3D(fx, fy, fz));
    var t0 = this.grads[ix1][iy][iz].dot(new Vector3D(fx-1, fy, fz));
    var u0 = this.grads[ix][iy1][iz].dot(new Vector3D(fx, fy-1, fz));
    var v0 = this.grads[ix1][iy1][iz].dot(new Vector3D(fx-1, fy-1, fz));

    var s1 = this.grads[ix][iy][iz1].dot(new Vector3D(fx, fy, fz-1));
    var t1 = this.grads[ix1][iy][iz1].dot(new Vector3D(fx-1, fy, fz-1));
    var u1 = this.grads[ix][iy1][iz1].dot(new Vector3D(fx, fy-1, fz-1));
    var v1 = this.grads[ix1][iy1][iz1].dot(new Vector3D(fx-1, fy-1, fz-1));

    var ex = easeCurve(fx);
    var ey = easeCurve(fy);
    var ez = easeCurve(fz);

    var a0 = s0 + ex*(t0-s0);
    var b0 = u0 + ex*(v0-u0);
    var c0 = a0 + ey*(b0-a0);

    var a1 = s1 + ex*(t1-s1);
    var b1 = u1 + ex*(v1-u1);
    var c1 = a1 + ey*(b1-a1);

    return (c0 + ez*(c1-c0)) * 0.5 + 0.5;
};
const ELEVATION_SET = 0;
const ELEVATION_MODIFY = 1;

/////////////////////////////////////////////////////////////////////////////
//  ElevationPainter
/////////////////////////////////////////////////////////////////////////////

function ElevationPainter(elevation)
{
    this.elevation = elevation;
    this.DX = [0, 1, 1, 0];
    this.DY = [0, 0, 1, 1];
}

ElevationPainter.prototype.paint = function(area)
{
    var length = area.points.length;
    var elevation = this.elevation;

    for (var i=0; i < length; i++)
    {
        var pt = area.points[i];

        for (var j=0; j < 4; j++)
        {
            g_Map.height[pt.x+this.DX[j]][pt.y+this.DY[j]] = elevation;
        }
    }
};

/////////////////////////////////////////////////////////////////////////////
//  LayeredPainter
/////////////////////////////////////////////////////////////////////////////

function LayeredPainter(terrainArray, widths)
{
    if (!(terrainArray instanceof Array))
        error("terrains must be an array!");

    this.terrains = [];
    for (var i = 0; i < terrainArray.length; ++i)
        this.terrains.push(createTerrain(terrainArray[i]));

    this.widths = widths;
}

LayeredPainter.prototype.paint = function(area)
{
    var size = getMapSize();
    var saw = new Array(size);
    var dist = new Array(size);

    // init typed arrays
    for (var i = 0; i < size; ++i)
    {
        saw[i] = new Array(size);           // bool / uint8
        dist[i] = new Uint16Array(size);        // uint16
    }

    // Point queue (implemented with array)
    var pointQ = [];

    // push edge points
    var pts = area.points;
    var length = pts.length;

    for (var i=0; i < length; i++)
    {
        var x = pts[i].x;
        var y = pts[i].y;

        for (var dx=-1; dx <= 1; dx++)
        {
            var nx = x+dx;
            for (var dy=-1; dy <= 1; dy++)
            {
                var ny = y+dy;

                if (g_Map.validT(nx, ny) && g_Map.area[nx][ny] && g_Map.area[nx][ny] != area && !saw[nx][ny])
                {
                    saw[nx][ny] = 1;
                    dist[nx][ny] = 0;
                    pointQ.push(new Point(nx, ny));
                }
            }
        }
    }

    // do BFS inwards to find distances to edge
    while (pointQ.length)
    {
        var pt = pointQ.shift();    // Pop queue
        var px = pt.x;
        var py = pt.y;
        var d = dist[px][py];

        // paint if in area
        if (g_Map.area[px][py] == area)
        {
            var w=0;
            var i=0;

            for (; i < this.widths.length; i++)
            {
                w += this.widths[i];
                if (w >= d)
                {
                    break;
                }
            }
            this.terrains[i].place(px, py);
        }

        // enqueue neighbours
        for (var dx=-1; dx<=1; dx++)
        {
            var nx = px+dx;
            for (var dy=-1; dy<=1; dy++)
            {
                var ny = py+dy;

                if (g_Map.validT(nx, ny) && g_Map.area[nx][ny] && g_Map.area[nx][ny] == area && !saw[nx][ny])
                {
                    saw[nx][ny] = 1;
                    dist[nx][ny] = d+1;
                    pointQ.push(new Point(nx, ny));
                }
            }
        }
    }
};

/////////////////////////////////////////////////////////////////////////////
//  MultiPainter
/////////////////////////////////////////////////////////////////////////////

function MultiPainter(painters)
{
    this.painters = painters;
}

MultiPainter.prototype.paint = function(area)
{
    for (var i=0; i < this.painters.length; i++)
    {
        this.painters[i].paint(area);
    }
};

/////////////////////////////////////////////////////////////////////////////
//  SmoothElevationPainter
/////////////////////////////////////////////////////////////////////////////

function SmoothElevationPainter(type, elevation, blendRadius)
{
    this.type = type;
    this.elevation = elevation;
    this.blendRadius = blendRadius;

    if (type != ELEVATION_SET && type != ELEVATION_MODIFY)
        error("SmoothElevationPainter: invalid type '"+type+"'");
}

SmoothElevationPainter.prototype.checkInArea = function(area, x, y)
{
    if (g_Map.validT(x, y))
    {
        return (g_Map.area[x][y] && g_Map.area[x][y] == area);
    }
    else
    {
        return false;
    }
};
var mapSize;
SmoothElevationPainter.prototype.paint = function(area)
{
    var pointQ = [];
    var pts = area.points;
    var heightPts = [];

    mapSize = getMapSize()+1;

    var saw = new  Array(mapSize);
    var dist = new Array(mapSize);
    var gotHeightPt = new Array(mapSize);
    var newHeight = new Array(mapSize);

    // init typed arrays
    for (var i = 0; i < mapSize; ++i)
    {
        saw[i] = new Array(mapSize);            // bool / uint8
        dist[i] = new Uint16Array(mapSize);     // uint16
        gotHeightPt[i] = new Array(mapSize);        // bool / uint8
        newHeight[i] = new Float32Array(mapSize);   // float32
    }

    var length = pts.length;

    // get a list of all points
    for (var i=0; i < length; i++)
    {
        var x = pts[i].x;
        var y = pts[i].y;

        for (var dx=-1; dx <= 2; dx++)
        {
            var nx = x+dx;
            for (var dy=-1; dy <= 2; dy++)
            {
                var ny = y+dy;

                if (g_Map.validH(nx, ny) && !gotHeightPt[nx][ny])
                {
                    gotHeightPt[nx][ny] = 1;
                    heightPts.push(new Point(nx, ny));
                    newHeight[nx][ny] = g_Map.height[nx][ny];
                }
            }
        }
    }

    // push edge points
    for (var i=0; i < length; i++)
    {
        var x = pts[i].x, y = pts[i].y;
        for (var dx=-1; dx <= 2; dx++)
        {
            var nx = x+dx;
            for (var dy=-1; dy <= 2; dy++)
            {
                var ny = y+dy;

                if (g_Map.validH(nx, ny)
                    && !this.checkInArea(area, nx, ny)
                    && !this.checkInArea(area, nx-1, ny)
                    && !this.checkInArea(area, nx, ny-1)
                    && !this.checkInArea(area, nx-1, ny-1)
                    && !saw[nx][ny])
                {
                    saw[nx][ny]= 1;
                    dist[nx][ny] = 0;
                    pointQ.push(new Point(nx, ny));
                }
            }
        }
    }

    // do BFS inwards to find distances to edge
    while(pointQ.length)
    {
        var pt = pointQ.shift();
        var px = pt.x;
        var py = pt.y;
        var d = dist[px][py];

        // paint if in area
        if (g_Map.validH(px, py)
            && (this.checkInArea(area, px, py) || this.checkInArea(area, px-1, py)
            || this.checkInArea(area, px, py-1) || this.checkInArea(area, px-1, py-1)))
        {
            if (d <= this.blendRadius)
            {
                var a = (d-1) / this.blendRadius;
                if (this.type == ELEVATION_SET)
                {
                    newHeight[px][py] = a*this.elevation + (1-a)*g_Map.height[px][py];
                }
                else
                {   // type == MODIFY
                    newHeight[px][py] += a*this.elevation;
                }
            }
            else
            {   // also happens when blendRadius == 0
                if (this.type == ELEVATION_SET)
                {
                    newHeight[px][py] = this.elevation;
                }
                else
                {   // type == MODIFY
                    newHeight[px][py] += this.elevation;
                }
            }
        }

        // enqueue neighbours
        for (var dx=-1; dx <= 1; dx++)
        {
            var nx = px+dx;
            for (var dy=-1; dy <= 1; dy++)
            {
                var ny = py+dy;

                if (g_Map.validH(nx, ny)
                    && (this.checkInArea(area, nx, ny) || this.checkInArea(area, nx-1, ny)
                        || this.checkInArea(area, nx, ny-1) || this.checkInArea(area, nx-1, ny-1))
                    && !saw[nx][ny])
                {
                    saw[nx][ny] = 1;
                    dist[nx][ny] = d+1;
                    pointQ.push(new Point(nx, ny));
                }
            }
        }
    }

    length = heightPts.length;

    // smooth everything out
    for (var i = 0; i < length; ++i)
    {
        var pt = heightPts[i];
        var px = pt.x;
        var py = pt.y;

        if ((this.checkInArea(area, px, py) || this.checkInArea(area, px-1, py)
            || this.checkInArea(area, px, py-1) || this.checkInArea(area, px-1, py-1)))
        {
            var sum = 8 * newHeight[px][py];
            var count = 8;

            for (var dx=-1; dx <= 1; dx++)
            {
                var nx = px+dx;
                for (var dy=-1; dy <= 1; dy++)
                {
                    var ny = py+dy;

                    if (g_Map.validH(nx, ny))
                    {
                        sum += newHeight[nx][ny];
                        count++;
                    }
                }
            }

            g_Map.height[px][py] = sum/count;
        }
    }
};

/////////////////////////////////////////////////////////////////////////////
//  TerrainPainter
/////////////////////////////////////////////////////////////////////////////

function TerrainPainter(terrain)
{
    this.terrain = createTerrain(terrain);
}

TerrainPainter.prototype.paint = function(area)
{
    var length = area.points.length;
    for (var i=0; i < length; i++)
    {
        var pt = area.points[i];
        this.terrain.place(pt.x, pt.y);
    }
};

/////////////////////////////////////////////////////////////////////////////
//  TileClassPainter
/////////////////////////////////////////////////////////////////////////////

function TileClassPainter(tileClass)
{
    this.tileClass = tileClass;
}

TileClassPainter.prototype.paint = function(area)
{
    var length = area.points.length;
    for (var i=0; i < length; i++)
    {
        var pt = area.points[i];
        this.tileClass.add(pt.x, pt.y);
    }
};

/////////////////////////////////////////////////////////////////////////////////////////
//  ClumpPlacer
/////////////////////////////////////////////////////////////////////////////////////////

function ClumpPlacer(size, coherence, smoothness, failFraction, x, y)
{
    this.size = size;
    this.coherence = coherence;
    this.smoothness = smoothness;
    this.failFraction = (failFraction !== undefined ? failFraction : 0);
    this.x = (x !== undefined ? x : -1);
    this.y = (y !== undefined ? y : -1);
}

ClumpPlacer.prototype.place = function(constraint)
{
    if (!g_Map.validT(this.x, this.y) || !constraint.allows(this.x, this.y))
    {
        return false;
    }

    var retVec = [];

    var size = getMapSize();
    var gotRet = new Array(size);
    for (var i = 0; i < size; ++i)
    {
        gotRet[i] = new Array(size);        // bool / uint8
    }

    var radius = Math.sqrt(this.size / PI);
    var perim = 4 * radius * 2 * PI;
    var intPerim = Math.ceil(perim);

    var ctrlPts = 1 + Math.floor(1.0/Math.max(this.smoothness,1.0/intPerim));

    if (ctrlPts > radius * 2 * PI)
        ctrlPts = Math.floor(radius * 2 * PI) + 1;

    var noise = new Float32Array(intPerim);     //float32
    var ctrlCoords = new Float32Array(ctrlPts+1);   //float32
    var ctrlVals = new Float32Array(ctrlPts+1); //float32

    for (var i=0; i < ctrlPts; i++)
    {
        ctrlCoords[i] = i * perim / ctrlPts;
        ctrlVals[i] = 2.0*randFloat();
    }

    var c = 0;
    var looped = 0;
    for (var i=0; i < intPerim; i++)
    {
        if (ctrlCoords[(c+1) % ctrlPts] < i && !looped)
        {
            c = (c+1) % ctrlPts;
            if (c == ctrlPts-1)
                looped = 1;
        }

        var t = (i - ctrlCoords[c]) / ((looped ? perim : ctrlCoords[(c+1)%ctrlPts]) - ctrlCoords[c]);
        var v0 = ctrlVals[(c+ctrlPts-1)%ctrlPts];
        var v1 = ctrlVals[c];
        var v2 = ctrlVals[(c+1)%ctrlPts];
        var v3 = ctrlVals[(c+2)%ctrlPts];
        var P = (v3 - v2) - (v0 - v1);
        var Q = (v0 - v1) - P;
        var R = v2 - v0;
        var S = v1;

        noise[i] = P*t*t*t + Q*t*t + R*t + S;
    }

    var failed = 0;
    for (var p=0; p < intPerim; p++)
    {
        var th = 2 * PI * p / perim;
        var r = radius * (1 + (1-this.coherence)*noise[p]);
        var s = Math.sin(th);
        var c = Math.cos(th);
        var xx=this.x;
        var yy=this.y;

        for (var k=0; k < Math.ceil(r); k++)
        {
            var i = Math.floor(xx);
            var j = Math.floor(yy);
            if (g_Map.validT(i, j) && constraint.allows(i, j))
            {
                if (!gotRet[i][j])
                {   // Only include each point once
                    gotRet[i][j] = 1;
                    retVec.push(new Point(i, j));
                }
            }
            else
            {
                failed++;
            }
            xx += s;
            yy += c;
        }
    }

    return ((failed > this.size*this.failFraction) ? undefined : retVec);
};

/////////////////////////////////////////////////////////////////////////////////////////
//  RectPlacer
/////////////////////////////////////////////////////////////////////////////////////////

function RectPlacer(x1, y1, x2, y2)
{
    this.x1 = x1;
    this.y1 = y1;
    this.x2 = x2;
    this.y2 = y2;

    if (x1 > x2 || y1 > y2)
        error("RectPlacer: incorrect bounds on rect");
}

RectPlacer.prototype.place = function(constraint)
{
    var ret = [];

    var x2 = this.x2;
    var y2 = this.y2;

    for (var x=this.x1; x < x2; x++)
    {
        for (var y=this.y1; y < y2; y++)
        {
            if (g_Map.validT(x, y) && constraint.allows(x, y))
            {
                ret.push(new Point(x, y));
            }
            else
            {
                return undefined;
            }
        }
    }

    return ret;

};

/////////////////////////////////////////////////////////////////////////////////////////
//  ObjectGroupPlacer
/////////////////////////////////////////////////////////////////////////////////////////

function ObjectGroupPlacer() {}

/////////////////////////////////////////////////////////////////////////////////////////
//  SimpleGroup
/////////////////////////////////////////////////////////////////////////////////////////

function SimpleObject(type, minCount, maxCount, minDistance, maxDistance, minAngle, maxAngle)
{
    this.type = type;
    this.minCount = minCount;
    this.maxCount = maxCount;
    this.minDistance = minDistance;
    this.maxDistance = maxDistance;
    this.minAngle = (minAngle !== undefined ? minAngle : 0);
    this.maxAngle = (maxAngle !== undefined ? maxAngle : 2*PI);

    if (minCount > maxCount)
        error("SimpleObject: minCount must be less than or equal to maxCount");

    if (minDistance > maxDistance)
        error("SimpleObject: minDistance must be less than or equal to maxDistance");

    if (minAngle > maxAngle)
        error("SimpleObject: minAngle must be less than or equal to maxAngle");
}

SimpleObject.prototype.place = function(cx, cy, player, avoidSelf, constraint)
{
    var failCount = 0;
    var count = randInt(this.minCount, this.maxCount);
    var resultObjs = [];

    for (var i=0; i < count; i++)
    {
        while(true)
        {
            var distance = randFloat(this.minDistance, this.maxDistance);
            var direction = randFloat(0, 2*PI);

            var x = cx + 0.5 + distance * Math.cos(direction);
            var y = cy + 0.5 + distance * Math.sin(direction);
            var fail = false; // reset place failure flag

            if (x < 0 || y < 0 || x > g_Map.size || y > g_Map.size)
            {
                fail = true;
            }
            else
            {
                if (avoidSelf)
                {
                    var length = resultObjs.length;
                    for (var i = 0; (i < length) && !fail; i++)
                    {
                        var dx = x - resultObjs[i].x;
                        var dy = y - resultObjs[i].y;

                        if ((dx*dx + dy*dy) < 1)
                        {
                            fail = true;
                        }
                    }
                }

                if (!fail)
                {
                    if (!constraint.allows(Math.floor(x), Math.floor(y)))
                    {
                        fail = true;
                    }
                    else
                    {   // if we got here, we're good
                        var angle = randFloat(this.minAngle, this.maxAngle);
                        resultObjs.push(new Entity(this.type, player, x, y, angle));
                        break;
                    }
                }
            }

            if (fail)
            {
                failCount++;
                if (failCount > 20) // TODO: Make this adjustable
                {
                    return undefined;
                }
            }
        }
    }

    return resultObjs;
};

function SimpleGroup(elements, avoidSelf, tileClass, x, y)
{
    this.elements = elements;
    this.tileClass = (tileClass !== undefined ? getTileClass(tileClass) : null);
    this.avoidSelf = (avoidSelf !== undefined ? avoidSelf : false);
    this.x = (x !== undefined ? x : -1);
    this.y = (y !== undefined ? y : -1);
}

SimpleGroup.prototype.place = function(player, constraint)
{
    var resultObjs = [];

    // Try placement of objects
    var length = this.elements.length;
    for (var i=0; i < length; i++)
    {
        var objs = this.elements[i].place(this.x, this.y, player, this.avoidSelf, constraint);
        if (objs === undefined)
        {   // Failure
            return false;
        }
        else
        {
            resultObjs = resultObjs.concat(objs);
        }
    }

    // Add placed objects to map
    length = resultObjs.length;
    for (var i=0; i < length; i++)
    {
        g_Map.addObjects(resultObjs[i]);

        if (this.tileClass !== null)
        {   // Round object position to integer
            this.tileClass.add(Math.floor(resultObjs[i].x), Math.floor(resultObjs[i].y));
        }
    }

    return true;
};

function Point(x, y)
{
    this.x = (x !== undefined ? x : 0);
    this.y = (y !== undefined ? y : 0);
}

/*
 * Return a random floating point number using Math.random library
 *
 * If no parameter given, the returned float is in the interval [0, 1)
 * If two parameters are given, they are minval and maxval, and the returned float is in the interval [minval, maxval)
 */
function randFloat()
{
    if (arguments.length == 0)
    {
        return Math.random();
    }
    else if (arguments.length == 2)
    {
        var minVal = arguments[0];
        var maxVal = arguments[1];

        return minVal + randFloat() * (maxVal - minVal);
    }
    else
    {
        error("randFloat() received invalid number of arguments: "+arguments.length);
        return undefined;
    }
}

/*
 * Return a random integer using Math.random library
 *
 * If one parameter given, it's maxval, and the returned integer is in the interval [0, maxval)
 * If two parameters are given, they are minval and maxval, and the returned integer is in the interval [minval, maxval]
 */
function randInt()
{
    if (arguments.length == 1)
    {
        var maxVal = arguments[0];
        return Math.floor(Math.random() * maxVal);
    }
    else if (arguments.length == 2)
    {
        var minVal = arguments[0];
        var maxVal = arguments[1];

        return minVal + randInt(maxVal - minVal + 1);
    }
    else
    {
        error("randInt() received invalid number of arguments: "+arguments.length);
        return undefined;
    }
}
//////////////////////////////////////////////////////////////////////
//  Terrain
//////////////////////////////////////////////////////////////////////

function Terrain() {}

Terrain.prototype.place = function(x, y)
{
    // Clear old array
    g_Map.terrainObjects[x][y] = [];

    this.placeNew(x, y);
};

Terrain.prototype.placeNew = function() {};

//////////////////////////////////////////////////////////////////////
//  SimpleTerrain
//////////////////////////////////////////////////////////////////////

function SimpleTerrain(texture, treeType)
{
    if (texture === undefined)
        error("SimpleTerrain: texture not defined");

    this.texture = texture;
    this.treeType = treeType;
}

SimpleTerrain.prototype = new Terrain();
SimpleTerrain.prototype.constructor = SimpleTerrain;
SimpleTerrain.prototype.placeNew = function(x, y)
{
    if (this.treeType !== undefined)
        g_Map.terrainObjects[x][y].push(new Entity(this.treeType, 0, x+0.5, y+0.5, randFloat()*PI));

    g_Map.texture[x][y] = g_Map.getID(this.texture);
};

//////////////////////////////////////////////////////////////////////
//  RandomTerrain
//////////////////////////////////////////////////////////////////////

function RandomTerrain(terrains)
{
    if (!(terrains instanceof Array) || !terrains.length)
        error("Invalid terrains array");

    this.terrains = terrains;
}

RandomTerrain.prototype = new Terrain();
RandomTerrain.prototype.constructor = RandomTerrain;
RandomTerrain.prototype.placeNew = function(x, y)
{
    this.terrains[randInt(this.terrains.length)].placeNew(x, y);
};
//////////////////////////////////////////////////////////////////////
//  RangeOp
//////////////////////////////////////////////////////////////////////

function RangeOp(size)
{
    // Get smallest power of 2 which is greater than or equal to size
    this.nn = 1;
    while (this.nn < size) {
        this.nn *= 2;
    }

    this.vals = new Int16Array(2*this.nn);  // int16
}

RangeOp.prototype.set = function(pos, amt)
{
    this.add(pos, amt - this.vals[this.nn + pos]);
};

RangeOp.prototype.add = function(pos, amt)
{
    for(var s = this.nn; s >= 1; s /= 2)
    {
        this.vals[s + pos] += amt;
        pos = Math.floor(pos/2);
    }
};

RangeOp.prototype.get = function(start, end)
{
    var ret = 0;
    var i;
    var nn = this.nn;

    // Count from start to end by powers of 2
    for (i = 1; start+i <= end; i *= 2)
    {
        if (start & i)
        {   // For each bit in start
            ret += this.vals[nn/i + Math.floor(start/i)];
            start += i;
        }
    }

    // 
    while(i >= 1)
    {
        if(start+i <= end)
        {
            ret += this.vals[nn/i + Math.floor(start/i)];
            start += i;
        }
        i /= 2;
    }

    return ret;
};


//////////////////////////////////////////////////////////////////////
//  TileClass
//////////////////////////////////////////////////////////////////////

function TileClass(size)
{
    this.size = size;
    this.inclusionCount = new Array(size);
    this.rangeCount = new Array(size);

    for (var i=0; i < size; ++i)
    {
        this.inclusionCount[i] = new Int16Array(size); //int16      
        this.rangeCount[i] = new RangeOp(size);
    }
}

TileClass.prototype.add = function(x, y)
{
    if (!this.inclusionCount[x][y])
    {
        this.rangeCount[y].add(x, 1);
    }

    this.inclusionCount[x][y]++;
};

TileClass.prototype.remove = function(x, y)
{
    this.inclusionCount[x][y]--;
    if(!this.inclusionCount[x][y])
    {
        this.rangeCount[y].add(x, -1);
    }
};

TileClass.prototype.countInRadius = function(cx, cy, radius, returnMembers)
{
    var members = 0;
    var nonMembers = 0;
    var size = this.size;

    var ymax = cy+radius;

    for (var y = cy-radius; y <= ymax; y++)
    {
        var iy = Math.floor(y);
        if(iy >= 0 && iy < size)
        {
            var dy = y - cy;
            var dx = Math.sqrt(radius*radius - dy*dy);

            var lowerX = Math.floor(cx - dx);
            var upperX = Math.floor(cx + dx);

            var minX = (lowerX > 0 ? lowerX : 0);
            var maxX = (upperX < size ? upperX+1 : size);

            var total = maxX - minX;
            var mem = this.rangeCount[iy].get(minX, maxX);

            members += mem;
            nonMembers += total - mem;
        }
    }

    if (returnMembers)
        return members;
    else
        return nonMembers;
};

TileClass.prototype.countMembersInRadius = function(cx, cy, radius)
{
    return this.countInRadius(cx, cy, radius, true);
};

TileClass.prototype.countNonMembersInRadius = function(cx, cy, radius)
{
    return this.countInRadius(cx, cy, radius, false);
};
/////////////////////////////////////////////////////////////////////
//  Vector2D
/////////////////////////////////////////////////////////////////////

// TODO: Type errors if v not instanceof Vector classes
// TODO: Possible implement in C++

function Vector2D(x, y)
{
    if (arguments.length == 2)
    {
        this.set(x, y);
    }
    else
    {
        this.set(0, 0);
    }
}

Vector2D.prototype.set = function(x, y)
{
    this.x = x;
    this.y = y;
};

Vector2D.prototype.add = function(v)
{
    return new Vector2D(this.x + v.x, this.y + v.y);
};

Vector2D.prototype.sub = function(v)
{
    return new Vector2D(this.x - v.x, this.y - v.y);
};

Vector2D.prototype.mult = function(f)
{
    return new Vector2D(this.x * f, this.y * f);
};

Vector2D.prototype.div = function(f)
{
    return new Vector2D(this.x / f, this.y / f);
};

Vector2D.prototype.dot = function(v)
{
    return this.x * v.x + this.y * v.y;
};

Vector2D.prototype.lengthSquared = function()
{
    return this.dot(this);
};

Vector2D.prototype.length = function()
{
    return Math.sqrt(this.lengthSquared());
};

Vector2D.prototype.normalize = function()
{
    var mag = this.length();

    this.x /= mag;
    this.y /= mag;
};

/////////////////////////////////////////////////////////////////////
//  Vector3D
/////////////////////////////////////////////////////////////////////

function Vector3D(x, y, z)
{
    if (arguments.length == 3)
    {
        this.set(x, y, z);
    }
    else
    {
        this.set(0, 0, 0);
    }
}

Vector3D.prototype.set = function(x, y, z)
{
    this.x = x;
    this.y = y;
    this.z = z;
};

Vector3D.prototype.add = function(v)
{
    return new Vector3D(this.x + v.x, this.y + v.y, this.z + v.z);
};

Vector3D.prototype.sub = function(v)
{
    return new Vector3D(this.x - v.x, this.y - v.y, this.z - v.z);
};

Vector3D.prototype.mult = function(f)
{
    return new Vector3D(this.x * f, this.y * f, this.z * f);
};

Vector3D.prototype.div = function(f)
{
    return new Vector3D(this.x / f, this.y / f, this.z / f);
};

Vector3D.prototype.dot = function(v)
{
    return this.x * v.x + this.y * v.y + this.z * v.z;
};

Vector3D.prototype.lengthSquared = function()
{
    return this.dot(this);
};

Vector3D.prototype.length = function()
{
    return Math.sqrt(this.lengthSquared());
};

Vector3D.prototype.normalize = function()
{
    var mag = this.length();

    this.x /= mag;
    this.y /= mag;
    this.z /= mag;
};

var settings = {
    Size : 13,
    BaseTerrain: "grass1_spring",
    BaseHeight: 0,
    PlayerData : [ {Civ: "hele"}, {Civ: "hele"}, {Civ: "hele"}, {Civ: "hele"}]
};
InitMapGen(settings);

// terrain textures
const tSand = "desert_dirt_rough";
const tDunes = "desert_sand_dunes_100";
const tFineSand = "desert_sand_smooth";
const tCliff = "desert_cliff_badlands";
const tGrassSand75 = "desert_grass_a";
const tGrassSand50 = "desert_grass_a_sand";
const tGrassSand25 = "desert_grass_a_stones";
const tDirt = "desert_dirt_rough";
const tDirtCracks = "desert_dirt_cracks";
const tShore = "desert_sand_wet";
const tWater = "desert_shore_stones";
const tWaterDeep = "desert_shore_stones_wet";

// gaia entities
const oBerryBush = "gaia/flora_bush_berry";
const oSheep = "gaia/fauna_sheep";
const oDeer = "gaia/fauna_deer";
const oMine = "gaia/geology_stone_desert_small";
const oTree = "gaia/flora_tree_medit_fan_palm";

// decorative props
const aBush = "actor|props/flora/bush_dry_a.xml";
const aDecorativeRock = "actor|geology/gray1.xml";

var tForest = tGrassSand75 + TERRAIN_SEPARATOR + oTree;

// initialize map

log("Initializing map...");

var numPlayers = getNumPlayers();
var mapSize = getMapSize();

// create tile classes

var clPlayer = createTileClass();
var clHill1 = createTileClass();
var clHill2 = createTileClass();
var clHill3 = createTileClass();
var clForest = createTileClass();
var clWater = createTileClass();
var clPatch = createTileClass();
var clRock = createTileClass();
var clFood = createTileClass();
var clBaseResource = createTileClass();

// place players

var playerX = new Array(numPlayers);
var playerY = new Array(numPlayers);
var playerAngle = new Array(numPlayers);

var startAngle = randFloat() * 2 * PI;
for (var i=0; i < numPlayers; i++)
{
    playerAngle[i] = startAngle + i*2*PI/numPlayers;
    playerX[i] = 0.5 + 0.39*cos(playerAngle[i]);
    playerY[i] = 0.5 + 0.39*sin(playerAngle[i]);
}

for (var i=0; i < numPlayers; i++)
{
    log("Creating base for player " + (i + 1) + "...");

    // some constants
    var radius = 20;

    // get the x and y in tiles
    var fx = fractionToTiles(playerX[i]);
    var fy = fractionToTiles(playerY[i]);
    var ix = round(fx);
    var iy = round(fy);

    // calculate size based on the radius
    var size = PI * radius * radius;

    // create the hill
    var placer = new ClumpPlacer(size, 0.9, 0.5, 0, ix, iy);
    createArea(placer, paintClass(clPlayer), null);

    // create the central road patch
    placer = new ClumpPlacer(PI*2*2, 0.6, 0.3, 0.5, ix, iy);
    var painter = new TerrainPainter(tDirt);
    createArea(placer, painter, null);

    // create the TC and citizens
    var civ = getCivCode(i);
    var group = new SimpleGroup(
        [                           // elements (type, count, distance)
            new SimpleObject("structures/"+civ+"_civil_centre", 1,1, 0,0),
            new SimpleObject("units/"+civ+"_support_female_citizen", 3,3, 5,5)
        ],
        true, null, ix, iy
    );
    createObjectGroup(group, i+1);

    // create berry bushes
    var bbAngle = randFloat()*2*PI;
    var bbDist = 10;
    var bbX = round(fx + bbDist * cos(bbAngle));
    var bbY = round(fy + bbDist * sin(bbAngle));
    group = new SimpleGroup(
        [new SimpleObject(oSheep, 5,5, 0,2)],
        true, clBaseResource,   bbX, bbY
    );
    createObjectGroup(group, 0);

    // create mines
    var mAngle = bbAngle;
    while(abs(mAngle - bbAngle) < PI/3) {
        mAngle = randFloat()*2*PI;
    }
    var mDist = 12;
    var mX = round(fx + mDist * cos(mAngle));
    var mY = round(fy + mDist * sin(mAngle));
    group = new SimpleGroup(
        [new SimpleObject(oMine, 3,3, 0,2)],
        true, clBaseResource,   mX, mY
    );
    createObjectGroup(group, 0);

    // create starting straggler trees
    group = new SimpleGroup(
        [new SimpleObject(oTree, 2,2, 6,12)],
        true, null, ix, iy
    );
    createObjectGroup(group, 0, avoidClasses(clBaseResource,1));
}

// create patches
log("Creating sand patches...");
var placer = new ClumpPlacer(30, 0.2, 0.1, 0);
var painter = new LayeredPainter([[tSand, tFineSand], tFineSand], [1]);
createAreas(placer, [painter, paintClass(clPatch)],
    avoidClasses(clPatch, 5),
    (mapSize*mapSize)/600
);

log("Creating dirt patches...");
placer = new ClumpPlacer(10, 0.2, 0.1, 0);
painter = new TerrainPainter([tSand, tDirt]);
createAreas(placer, [painter, paintClass(clPatch)],
    avoidClasses(clPatch, 5),
    (mapSize*mapSize)/600
);

// create the oasis
log("Creating water...");
placer = new ClumpPlacer(1200, 0.6, 0.1, 0, mapSize/2, mapSize/2);
painter = new LayeredPainter([[tSand, tForest], tShore, tWaterDeep], [6,1]);
elevationPainter = new SmoothElevationPainter(ELEVATION_MODIFY, -10, 5);
createArea(placer, [painter, elevationPainter, paintClass(clForest)], null);

// create hills
log("Creating level 1 hills...");
placer = new ClumpPlacer(150, 0.25, 0.1, 0.3);
var terrainPainter = new LayeredPainter(
    [tCliff, tSand],        // terrains
    [1]             // widths
);
var elevationPainter = new SmoothElevationPainter(ELEVATION_MODIFY, 16, 1);
createAreas(placer, [terrainPainter, elevationPainter, paintClass(clHill1)],
    avoidClasses(clForest, 2, clPlayer, 0, clHill1, 16),
    (mapSize*mapSize)/3800, 100
);

log("Creating small level 1 hills...");
placer = new ClumpPlacer(60, 0.25, 0.1, 0.3);
terrainPainter = new LayeredPainter(
    [tCliff, tSand],        // terrains
    [1]             // widths
);
elevationPainter = new SmoothElevationPainter(ELEVATION_MODIFY, 16, 1);
createAreas(placer, [terrainPainter, elevationPainter, paintClass(clHill1)],
    avoidClasses(clForest, 2, clPlayer, 0, clHill1, 3),
    (mapSize*mapSize)/2800, 100
);

log("Creating level 2 hills...");
placer = new ClumpPlacer(60, 0.2, 0.1, 0.9);
terrainPainter = new LayeredPainter(
    [tCliff, tSand],        // terrains
    [1]             // widths
);
elevationPainter = new SmoothElevationPainter(ELEVATION_MODIFY, 16, 1);
createAreas(placer, [terrainPainter, elevationPainter, paintClass(clHill2)],
    [avoidClasses(clHill2, 1), new StayInTileClassConstraint(clHill1, 0)],
    (mapSize*mapSize)/2800, 200
);

log("Creating level 3 hills...");
placer = new ClumpPlacer(25, 0.2, 0.1, 0.9);
terrainPainter = new LayeredPainter(
    [tCliff, tSand],        // terrains
    [1]             // widths
);
elevationPainter = new SmoothElevationPainter(ELEVATION_MODIFY, 16, 1);
createAreas(placer, [terrainPainter, elevationPainter, paintClass(clHill3)],
    [avoidClasses(clHill3, 1), new StayInTileClassConstraint(clHill2, 0)],
    (mapSize*mapSize)/9000, 300
);

// create forests
log("Creating forests...");
placer = new ClumpPlacer(25, 0.15, 0.1, 0.3);
painter = new TerrainPainter([tSand, tForest]);
createAreas(placer, [painter, paintClass(clForest)],
    avoidClasses(clWater, 0, clPlayer, 1, clForest, 20, clHill1, 0),
    (mapSize*mapSize)/4000, 50
);

// create mines
log("Creating mines...");
group = new SimpleGroup([new SimpleObject(oMine, 4,6, 0,2)], true, clRock);
createObjectGroups(group, 0,
    [avoidClasses(clWater, 2, clForest, 2, clPlayer, 0, clRock, 13),
     new BorderTileClassConstraint(clHill1, 0, 4)],
    (mapSize*mapSize)/4000, 100
);

// create decorative rocks for hills
log("Creating decorative rocks...");
group = new SimpleGroup([new SimpleObject(aDecorativeRock, 1,1, 0,0)], true);
createObjectGroups(group, undefined,
    new BorderTileClassConstraint(clHill1, 0, 3),
    (mapSize*mapSize)/2000, 100
);

// create deer
log("Creating deer...");
group = new SimpleGroup([new SimpleObject(oDeer, 5,7, 0,4)], true, clFood);
createObjectGroups(group, 0,
    avoidClasses(clWater, 0, clForest, 0, clPlayer, 0, clHill1, 0, clFood, 25),
    (mapSize*mapSize)/5000, 50
);

// create sheep
log("Creating sheep...");
group = new SimpleGroup([new SimpleObject(oSheep, 1,3, 0,2)], true, clFood);
createObjectGroups(group, 0,
    avoidClasses(clWater, 0, clForest, 0, clPlayer, 0, clHill1, 0, clFood, 15),
    (mapSize*mapSize)/5000, 50
);

// create straggler trees
log("Creating straggler trees...");
group = new SimpleGroup([new SimpleObject(oTree, 1,1, 0,0)], true);
createObjectGroups(group, 0,
    avoidClasses(clWater, 0, clForest, 0, clHill1, 0, clPlayer, 0),
    mapSize*mapSize/1500
);

// create bushes
log("Creating bushes...");
group = new SimpleGroup([new SimpleObject(aBush, 2,3, 0,2)]);
createObjectGroups(group, undefined,
    avoidClasses(clWater, 3, clHill1, 0, clPlayer, 0, clForest, 0),
    mapSize*mapSize/1000
);

// create bushes
log("Creating more decorative rocks...");
group = new SimpleGroup([new SimpleObject(aDecorativeRock, 1,2, 0,2)]);
createObjectGroups(group, undefined,
    avoidClasses(clWater, 3, clHill1, 0, clPlayer, 0, clForest, 0),
    mapSize*mapSize/1000
);

var output = SaveMap();

var endTime = dateNow();

log("Processing time: "+(endTime-startTime)/1000.0+" seconds");