public NavMesh(TerrainTile tile, NavMeshPolygon[] polys, Vector3[] vertices, int[] indices)
 {
     Tile = tile;
     Polygons = polys;
     Vertices = vertices;
     Indices = indices;
 }

        public void Render(TerrainTile tile, TerrainGlobal terrainGlobal, Matrix4 projection, Matrix4 view, Vector3 eyePos)
        {
            var boxparam = tile.GetBoxParam();

            Vector3 eyePosTileCoords = Vector4.Transform(new Vector4(eyePos, 0.0f), tile.InverseModelMatrix).Xyz;

            GL.Enable(EnableCap.CullFace);
            GL.CullFace(CullFaceMode.Front);  // we only want to render back-faces

            tile.HeightTexture.Bind(TextureUnit.Texture0);
            tile.ParamTexture.Bind(TextureUnit.Texture1);
            tile.NormalTexture.Bind(TextureUnit.Texture2);

            this.boundingBoxProgram
                .UseProgram()
                .SetUniform("projection_matrix", projection)
                .SetUniform("model_matrix", tile.ModelMatrix)
                .SetUniform("view_matrix", view)
                .SetUniform("heightTex", 0)
                .SetUniform("paramTex", 1)
                .SetUniform("normalTex", 2)
                .SetUniform("eyePos", eyePos)
                .SetUniform("nEyePos", eyePosTileCoords)
                .SetUniform("boxparam", boxparam);
            this.vertexVBO.Bind(this.boundingBoxProgram.VariableLocation("vertex"));
            this.boxcoordVBO.Bind(this.boundingBoxProgram.VariableLocation("in_boxcoord"));
            this.indexVBO.Bind();
            GL.DrawElements(BeginMode.Triangles, this.indexVBO.Length, DrawElementsType.UnsignedInt, 0);
            Sampler.Unbind(TextureUnit.Texture0);
        }

		public override void Draw()
		{
			if (template == null)
				return;

			var grid = Game.ModData.Manifest.Get<MapGrid>();
			var ts = grid.TileSize;
			var gridType = grid.Type;
			var scale = GetScale();

			var sb = new Rectangle((int)(scale * bounds.X), (int)(scale * bounds.Y), (int)(scale * bounds.Width), (int)(scale * bounds.Height));
			var origin = RenderOrigin + new int2((RenderBounds.Size.Width - sb.Width) / 2 - sb.X, (RenderBounds.Size.Height - sb.Height) / 2 - sb.Y);

			var i = 0;
			for (var y = 0; y < Template.Size.Y; y++)
			{
				for (var x = 0; x < Template.Size.X; x++)
				{
					var tile = new TerrainTile(Template.Id, (byte)(i++));
					var tileInfo = tileset.GetTileInfo(tile);

					// Empty tile
					if (tileInfo == null)
						continue;

					var sprite = worldRenderer.Theater.TileSprite(tile, 0);
					var size = new float2(sprite.Size.X * scale, sprite.Size.Y * scale);

					var u = gridType == MapGridType.Rectangular ? x : (x - y) / 2f;
					var v = gridType == MapGridType.Rectangular ? y : (x + y) / 2f;
					var pos = origin + scale * (new float2(u * ts.Width, (v - 0.5f * tileInfo.Height) * ts.Height) - 0.5f * sprite.Size);
					Game.Renderer.SpriteRenderer.DrawSprite(sprite, pos, worldRenderer.Palette(Palette), size);
				}
			}
		}

        public IEnumerable<PatchDescriptor> GetPatches(TerrainTile tile, Frustum f, Vector3 eyeWorld)
        {
            // create root node
            var root = new QuadTreeNode(tile);

            return root.GetPatches(eyeWorld,f);
        }

        //private Vector3 MinVertex;
        //private Vector3 MaxVertex;
        public QuadTreeNode(QuadTreeNode parent, TerrainTile tile, int tileSize, int depth, bool checkFrustum, Vector2 offset, params Vector4[] v)
        {
            this.tile = tile;
            this.checkFrustum = checkFrustum;
            this.depth = depth;
            this.tileSize = tileSize;
            this.Offset = offset;

            //if (parent != null)
            //{
            //    //TileOffset = parent.TileOffset;
            //}
            //else
            //{
            //    // get tile offset in world space
            //    TileOffset = Vector4.Transform(new Vector4(0f,0f,0f,1f), tile.InverseModelMatrix);
            //}

            for (int i = 0; i < 8; i++)
            {
                vertex[i] = v[i];
            }

            BottomCentre = (vertex[(int)Corner.BottomNearLeft] + vertex[(int)Corner.BottomFarRight]) * 0.5f;
            TopCentre = (vertex[(int)Corner.TopNearLeft] + vertex[(int)Corner.TopFarRight]) * 0.5f;
        }

        public Map(int Width, int Height, string TerrainName)
        {
            width = Width;
            height = Height;
            terrainName = TerrainName;

            System.Random rnd = new System.Random();
            // Create map
            m_Tiles = new TerrainTile[width * height];
            for (int j = 0; j < height; ++j)
            {
                for (int i = 0; i < width; ++i)
                {
                    // For first and last row and first and last collumn set
                    // to non-walkable
                    TerrainTile.Type tile_type = (i > 0 && j % 2 == 0) || (j % 2 == 1 && i < width - 1) ? TerrainTile.Type.REGULAR : TerrainTile.Type.NONE;
                    TerrainTile tile = new TerrainTile(i, j, tile_type);
                    // Set random variant
            //					tile.variant = (byte)rnd.Next(0, 7);
                    tile.variant = 0;

                    m_Tiles[i + j * width] = tile;
                }
            }
            // Set some debug tile
            SetTileTerrainType(GetTile(2, 3), 1);
            SetTileTerrainType(GetTile(13, 6), 1);
            SetTileTerrainType(GetTile(width - 1, height - 1), 1);
        }

        public static byte[] Convert(string json)
        {
            var obj = JsonConvert.DeserializeObject<json_dat>(json);
            var dat = ZlibStream.UncompressBuffer(obj.data);

            Dictionary<short, TerrainTile> tileDict = new Dictionary<short, TerrainTile>();
            for (int i = 0; i < obj.dict.Length; i++)
            {
                var o = obj.dict[i];
                tileDict[(short)i] = new TerrainTile()
                {
                    TileId = o.ground == null ? (short)0xff : XmlDatas.IdToType[o.ground],
                    TileObj = o.objs == null ? null : o.objs[0].id,
                    Name = o.objs == null ? "" : o.objs[0].name ?? "",
                    Terrain = TerrainType.None,
                    Region = o.regions == null ? TileRegion.None : (TileRegion)Enum.Parse(typeof(TileRegion), o.regions[0].id.Replace(' ', '_'))
                };
            }

            var tiles = new TerrainTile[obj.width, obj.height];
            using (NReader rdr = new NReader(new MemoryStream(dat)))
                for (int y = 0; y < obj.height; y++)
                    for (int x = 0; x < obj.width; x++)
                    {
                        tiles[x, y] = tileDict[rdr.ReadInt16()];
                    }
            return Export(tiles);
        }

    List<GameObject> TileArray = new List<GameObject>(); //used for storing the gameobjects themselves.  Whenever updating the tile, be sure to call tile.updateObject() to avoid a desync.

    #endregion Fields

    #region Methods

    //
    //Other Methods
    public static bool CheckPassable(TerrainTile tile)
    {
        var top = tile.topper; //check for toppers or inpassable terrain type.
        var type = tile.terrainType;

        switch (top) {
        case TerrainTileParent.Topper.Tree:
            {
                return false;
            }
        default:
            {
                switch (type) {
                case TerrainTileParent.TerrainType.Empty:
                    {
                        return true;
                    }
                default:
                    {
                        return false;
                    }
                }
            }
        }
    }

 public void HandleTileClick(TerrainTile tile)
 {
     var nextstate = _state.HandleTileClick(tile);
     if (nextstate != null) { // state transition requested
         _state.OnExit();
         _state = nextstate;
     }
 }

 public int CostToTile(TerrainTile tile)
 {
     var idx = TileToIndex(tile);
     if (idx < _distance.Length) {
         return _distance[idx];
     }
     return int.MaxValue;
 }

        public void AddTile(CPos cell, TerrainTile tile)
        {
            map.CustomTerrain[cell] = map.Rules.TileSet.GetTerrainIndex(tile);

            // Terrain tiles define their origin at the topleft
            var s = theater.TileSprite(tile);
            dirty[cell] = new Sprite(s.Sheet, s.Bounds, float2.Zero, s.Channel, s.BlendMode);
        }

 private TerrainTile pickNeighbor(TerrainTile[,] tiles, int row, int col)
 {
     int neighborRow = (row == 0) ? (row + 1) : (row - 1);
     int neighborCol = (col == 0) ? (col + 1) : (col - 1);
     var neighbor =  tiles[neighborRow, neighborCol];
     // TODO: this isn't perfect. maybe use breadth-first search
     return (neighbor.WasTerrainApplied) ? neighbor : pickNeighbor(tiles, neighborRow, neighborCol);
 }

    private void AddInitalTile(int index)
    {
        var tileGameObject = (GameObject)Instantiate(trackPrefab);
        var newTileCoordinates = LocationToCoordinates(0, index);
        tileGameObject.transform.Translate(newTileCoordinates);

        var newTile = new TerrainTile(tileGameObject, 0, index, Direction.Up, index, TerrainTileType.Direct);
        _terrainTiles.Add(newTile);
    }

 static CPos FindEdge(Surface s, CPos p, CVec d, TerrainTile replace)
 {
     for (;;)
     {
         var q = p + d;
         if (!s.Map.Contains(q)) return p;
         if (s.Map.MapTiles.Value[q].Type != replace.Type) return p;
         p = q;
     }
 }

		public void ExportRecastInputMesh(TerrainTile tile, string filename)
		{
			if (File.Exists(filename)) return;			// skip existing files

			var verts = tile.TerrainVertices;
			var indices = tile.TerrainIndices;

			var start = DateTime.Now;
			Console.Write("Writing input file {0}...", filename);

			using (var file = new StreamWriter(filename))
			{
				foreach (var vertex in verts)
				{
					var v = vertex;
					RecastUtil.TransformWoWCoordsToRecastCoords(ref v);
					file.WriteLine("v {0} {1} {2}", v.X, v.Y, v.Z);
				}

				// write faces
				var terrain = tile.Terrain;
				for (var i = 0; i < indices.Length; i += 3)
				{
					// ignore triangles that are completely submerged in a liquid
					var v1 = verts[indices[i]];
					var v2 = verts[indices[i+1]];
					var v3 = verts[indices[i+2]];
					
                    if (terrain.GetLiquidType(v1) != LiquidType.None &&
						terrain.GetLiquidType(v2) != LiquidType.None &&
						terrain.GetLiquidType(v3) != LiquidType.None)
					{
                        var triBottom = float.MaxValue;
				        var triTop = float.MinValue;
				        triBottom = Math.Min(triBottom, v1.Z);
                        triBottom = Math.Min(triBottom, v2.Z);
                        triBottom = Math.Min(triBottom, v3.Z);
				        triTop = Math.Max(triTop, v1.Z);
                        triTop = Math.Max(triTop, v2.Z);
                        triTop = Math.Max(triTop, v3.Z);

					    var triHeightAvg = (triTop - triBottom)*0.5f;
                        var liqHeight = terrain.GetLiquidHeight(v1);
					    var avgTriLiqDepth = liqHeight - triHeightAvg;
                        
                        if (avgTriLiqDepth > 1.0f) continue;
					}

				    //file.WriteLine("f {0} {1} {2}", indices[i] + 1, indices[i + 1] + 1, indices[i + 2] + 1);
					file.WriteLine("f {0} {1} {2}", indices[i + 2] + 1, indices[i + 1] + 1, indices[i] + 1);
				}
			}
			Console.WriteLine("Done. - Exported {0} triangles in: {1:0.000}s",
									indices.Length / 3, (DateTime.Now - start).TotalSeconds);
		}

        public Sprite TileSprite(TerrainTile r)
        {
            Sprite[] template;
            if (!templates.TryGetValue(r.Type, out template))
                return missingTile;

            if (r.Index >= template.Length)
                return missingTile;

            return template[r.Index];
        }

        public static byte[] ConvertMakeWalls(RealmManager manager, string json)
        {
            json_dat obj = JsonConvert.DeserializeObject<json_dat>(json);
            byte[] dat = ZlibStream.UncompressBuffer(obj.data);

            Dictionary<ushort, TerrainTile> tileDict = new Dictionary<ushort, TerrainTile>();
            for (int i = 0; i < obj.dict.Length; i++)
            {
                loc o = obj.dict[i];
                tileDict[(ushort)i] = new TerrainTile
                {
                    TileId = o.ground == null ? (ushort)0xff : manager.GameData.IdToObjectType[o.ground],
                    TileObj = o.objs == null ? null : o.objs[0].id,
                    Name = o.objs == null ? "" : o.objs[0].name ?? "",
                    Terrain = TerrainType.None,
                    Region =
                        o.regions == null
                            ? TileRegion.None
                            : (TileRegion)Enum.Parse(typeof(TileRegion), o.regions[0].id.Replace(' ', '_'))
                };
            }

            TerrainTile[,] tiles = new TerrainTile[obj.width, obj.height];
            using (NReader rdr = new NReader(new MemoryStream(dat)))
                for (int y = 0; y < obj.height; y++)
                    for (int x = 0; x < obj.width; x++)
                    {
                        tiles[x, y] = tileDict[(ushort)rdr.ReadInt16()];
                        tiles[x, y].X = x;
                        tiles[x, y].Y = y;
                    }

            foreach (TerrainTile i in tiles)
            {
                if (i.TileId == 0xff && i.TileObj == null)
                {
                    bool createWall = false;
                    for (int ty = -1; ty <= 1; ty++)
                        for (int tx = -1; tx <= 1; tx++)
                            try
                            {
                                if (tiles[i.X + tx, i.Y + ty].TileId != 0xff)
                                    createWall = true;
                            }
                            catch
                            {
                            }
                    if (createWall)
                        tiles[i.X, i.Y].TileObj = "Grey Wall";
                }
            }

            return WorldMapExporter.Export(tiles);
        }

 private static Bitmap RenderColorBmp(TerrainTile[,] tiles)
 {
     int w = tiles.GetLength(0);
     int h = tiles.GetLength(1);
     Bitmap bmp = new Bitmap(w, h);
     BitmapBuffer buff = new BitmapBuffer(bmp);
     buff.Lock();
     for (int y = 0; y < w; y++)
         for (int x = 0; x < h; x++)
             buff[x, y] = TileTypes.color[tiles[x, y].TileId];
     buff.Unlock();
     return bmp;
 }

 public override void Apply(TerrainTile[,] tiles)
 {
     for (int row = 0; row < tiles.GetLength(0); row++) {
         for (int col = 0; col < tiles.GetLength(1); col++) {
             var tile = tiles[row, col];
             if (!tile.WasTerrainApplied) {
                 var neighbor = pickNeighbor(tiles, row, col);
                 var mat = neighbor.renderer.sharedMaterial;
                 var cost = neighbor.MoveCost;
                 tile.SetTerrain(cost, mat);
             }
         }
       }
 }

    private void AddCoin(TerrainTile tile)
    {
        var coin = (GameObject)Instantiate(coinPrefab);
        coin.transform.Translate(tile.GameObject.transform.position);

        //NOTE: assume obstacle has sime size in all directions
        var halfObstacleSize = coin.collider.bounds.size.x / 2.0f;
        var possibleMoveRange = GlobalConstants.TerrainTileSize / 2.0f - halfObstacleSize;
        var shiftX = Random.Range(-possibleMoveRange, possibleMoveRange);
        var shiftY = Random.Range(-possibleMoveRange, possibleMoveRange);
        coin.transform.Translate(shiftX, 0, shiftY);

        //add as child to tile
        coin.transform.parent = tile.GameObject.transform;
    }