using System;
using System.IO;
using System.Collections.Generic;
using Oni.Imaging;

namespace Oni.Akira
{
    internal class RoomGridRasterizer
    {
        private const int origin = -2;
        private const float tileSize = 4.0f;
        private const int margin = 3;
        private readonly int xTiles;
        private readonly int zTiles;
        private readonly byte[] data;
        private readonly Vector3 worldOrigin;
        //private readonly List<RoomGridDebugData> debugData;

        private enum RoomGridDebugType : byte
        {
            None,
            SlopedQuad,
            StairQuad,
            Wall,
            DangerQuad,
            ImpassableQuad,
            Floor
        }

        //private class RoomGridDebugData
        //{
        //    public int quadIndex;
        //    public RoomGridDebugType type;
        //    public RoomGridWeight weight;
        //    public short x, y;
        //}

        public RoomGridRasterizer(BoundingBox bbox)
        {
            this.xTiles = (int)(((bbox.Max.X - bbox.Min.X) / tileSize) + (-origin * 2) + 1) + margin * 2;
            this.zTiles = (int)(((bbox.Max.Z - bbox.Min.Z) / tileSize) + (-origin * 2) + 1) + margin * 2;
            this.data = new byte[xTiles * zTiles];
            this.worldOrigin = bbox.Min;
            //this.debugData = new List<RoomGridDebugData>();
        }

        public void Clear(RoomGridWeight weight)
        {
            for (int i = 0; i < xTiles * zTiles; i++)
                data[i] = (byte)weight;
        }

        public int XTiles => xTiles;
        public int ZTiles => ZTiles;

        public float TileSize => tileSize;

        public RoomGridWeight this[int x, int z]
        {
            get { return (RoomGridWeight)data[x + z * xTiles]; }
            set { data[x + z * xTiles] = (byte)value; }
        }

        public void DrawFloor(IEnumerable<Vector3> points)
        {
            foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
                this[point.X, point.Y] = RoomGridWeight.Clear;
        }

        public void DrawDanger(IEnumerable<Vector3> points)
        {
            foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
                this[point.X, point.Y] = RoomGridWeight.Danger;
        }

        public void DrawStairsEntry(IEnumerable<Vector3> points)
        {
            var v0 = points.First();
            var v1 = v0;

            foreach (var v in points)
            {
                if (v.X < v0.X || (v.X == v0.X && v.Z < v0.Z))
                    v0 = v;

                if (v.X > v1.X || (v.X == v1.X && v.Z > v1.Z))
                    v1 = v;
            }

            Point p0 = WorldToGrid(v0);
            Point p1 = WorldToGrid(v1);

            DrawLine(p0, p1, RoomGridWeight.Stairs);

            DrawLine(p0 - Point.UnitY, p1 - Point.UnitY, RoomGridWeight.Clear);
            DrawLine(p0 + Point.UnitY, p1 + Point.UnitY, RoomGridWeight.Clear);
            DrawLine(p0 + Point.UnitX, p1 + Point.UnitX, RoomGridWeight.Clear);
            DrawLine(p0 - Point.UnitX, p1 - Point.UnitX, RoomGridWeight.Clear);

            var pp = points.ToArray();
            Array.Sort(pp, (x, y) => x.Y.CompareTo(y.Y));
            DrawImpassable(pp[0]);
            DrawImpassable(pp[1]);
        }

        public void DrawWall(IEnumerable<Vector3> points)
        {
            var v0 = points.First();
            var v1 = v0;

            foreach (var v in points)
            {
                if (v.X < v0.X || (v.X == v0.X && v.Z < v0.Z))
                    v0 = v;

                if (v.X > v1.X || (v.X == v1.X && v.Z > v1.Z))
                    v1 = v;
            }

            Point p0 = WorldToGrid(v0);
            Point p1 = WorldToGrid(v1);

            DrawLine(p0, p1, RoomGridWeight.Impassable);

            DrawLine(p0 - Point.UnitY, p1 - Point.UnitY, RoomGridWeight.SemiPassable);
            DrawLine(p0 + Point.UnitY, p1 + Point.UnitY, RoomGridWeight.SemiPassable);
            DrawLine(p0 + Point.UnitX, p1 + Point.UnitX, RoomGridWeight.SemiPassable);
            DrawLine(p0 - Point.UnitX, p1 - Point.UnitX, RoomGridWeight.SemiPassable);
        }

        private void DrawLine(Point p0, Point p1, RoomGridWeight weight)
        {
            foreach (Point p in ScanLine(p0, p1))
            {
                if (weight > this[p.X, p.Y])
                {
                    this[p.X, p.Y] = weight;

                    //debugData.Add(new RoomGridDebugData {
                    //    x = (short)p.X,
                    //    y = (short)p.Y,
                    //    weight = weight
                    //});
                }
            }
        }

        private void FillPolygon(IEnumerable<Vector3> points, RoomGridWeight weight)
        {
            foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList()))
            {
                if (weight > this[point.X, point.Y])
                    this[point.X, point.Y] = weight;
            }
        }

        public void DrawImpassable(IEnumerable<Vector3> points)
        {
            FillPolygon(points, RoomGridWeight.Impassable);
        }

        public void DrawImpassable(Vector3 position)
        {
            var point = WorldToGrid(position);
            int x = point.X;
            int y = point.Y;

            DrawTile(x, y, RoomGridWeight.Impassable);

            DrawTile(x - 1, y, RoomGridWeight.SemiPassable);
            DrawTile(x + 1, y, RoomGridWeight.SemiPassable);
            DrawTile(x, y - 1, RoomGridWeight.SemiPassable);
            DrawTile(x, y + 1, RoomGridWeight.SemiPassable);
            DrawTile(x - 1, y - 1, RoomGridWeight.SemiPassable);
            DrawTile(x + 1, y - 1, RoomGridWeight.SemiPassable);
            DrawTile(x + 1, y + 1, RoomGridWeight.SemiPassable);
            DrawTile(x - 1, y + 1, RoomGridWeight.SemiPassable);
        }

        private void DrawTile(int x, int y, RoomGridWeight weight)
        {
            if (0 <= x && x < xTiles && 0 <= y && y < zTiles)
            {
                if (weight > this[x, y])
                    this[x, y] = weight;
            }
        }

        public void AddBorders()
        {
            AddBorder(RoomGridWeight.Danger, RoomGridWeight.Clear, RoomGridWeight.Border4);
            AddBorder(RoomGridWeight.Border4, RoomGridWeight.Clear, RoomGridWeight.Border3);
            AddBorder(RoomGridWeight.Border3, RoomGridWeight.Clear, RoomGridWeight.Border2);
            AddBorder(RoomGridWeight.Border2, RoomGridWeight.Clear, RoomGridWeight.Border1);
            AddBorder(RoomGridWeight.SemiPassable, RoomGridWeight.Clear, RoomGridWeight.NearWall);
        }

        private void AddBorder(RoomGridWeight aroundOf, RoomGridWeight onlyIf, RoomGridWeight border)
        {
            for (int z = 0; z < zTiles; z++)
            {
                for (int x = 0; x < xTiles; x++)
                {
                    if (this[x, z] != aroundOf)
                        continue;

                    if (x - 1 >= 0 && this[x - 1, z] == onlyIf)
                        this[x - 1, z] = border;

                    if (x + 1 < xTiles && this[x + 1, z] == onlyIf)
                        this[x + 1, z] = border;

                    if (z - 1 >= 0 && this[x, z - 1] == onlyIf)
                        this[x, z - 1] = border;

                    if (z + 1 < zTiles && this[x, z + 1] == onlyIf)
                        this[x, z + 1] = border;
                }
            }
        }

        private Point WorldToGrid(Vector3 world)
        {
            return new Point(
                FMath.TruncateToInt32((world.X - worldOrigin.X) / tileSize) - origin + margin,
                FMath.TruncateToInt32((world.Z - worldOrigin.Z) / tileSize) - origin + margin);
        }

        public RoomGrid GetGrid()
        {
            int gridXTiles = xTiles - 2 * margin;
            int gridZTiles = zTiles - 2 * margin;

            var gridData = new byte[gridXTiles * gridZTiles];

            for (int z = margin; z < zTiles - margin; z++)
            {
                for (int x = margin; x < xTiles - margin; x++)
                    gridData[(x - margin) + (z - margin) * gridXTiles] = data[x + z * xTiles];
            }

            //var debugStream = new MemoryStream(debugData.Count * 16);

            //using (var writer = new BinaryWriter(debugStream))
            //{
            //    foreach (var data in debugData)
            //    {
            //        writer.WriteByte((byte)data.type);
            //        writer.WriteByte(0);
            //        writer.Write(data.x);
            //        writer.Write(data.y);
            //        writer.WriteInt16(0);
            //        writer.Write(data.quadIndex);
            //        writer.Write((int)data.weight);
            //    }
            //}

            return new RoomGrid(gridXTiles, gridZTiles, gridData, null);
        }

        private IEnumerable<Point> ScanLine(Point p0, Point p1)
        {
            return ScanLine(p0.X, p0.Y, p1.X, p1.Y);
        }

        private IEnumerable<Point> ScanLine(int x0, int y0, int x1, int y1)
        {
            int dx = (x0 < x1) ? x1 - x0 : x0 - x1;
            int dy = (y0 < y1) ? y1 - y0 : y0 - y1;
            int sx = (x0 < x1) ? 1 : -1;
            int sy = (y0 < y1) ? 1 : -1;
            int err = dx - dy;

            while (true)
            {
                if (0 <= x0 && x0 < xTiles && 0 <= y0 && y0 < zTiles)
                    yield return new Point(x0, y0);

                if (x0 == x1 && y0 == y1)
                    break;

                int derr = 2 * err;

                if (derr > -dy)
                {
                    err = err - dy;
                    x0 = x0 + sx;
                }

                if (derr < dx)
                {
                    err = err + dx;
                    y0 = y0 + sy;
                }
            }
        }

        private IEnumerable<Vector2> ScanLine(Vector2 p0, Vector2 p1)
        {
            return ScanLine(p0.X, p0.Y, p1.X, p1.Y);
        }

        private IEnumerable<Vector2> ScanLine(float x0, float y0, float x1, float y1)
        {
            float dx = (x0 < x1) ? x1 - x0 : x0 - x1;
            float dy = (y0 < y1) ? y1 - y0 : y0 - y1;
            float sx = (x0 < x1) ? 1 : -1;
            float sy = (y0 < y1) ? 1 : -1;
            float err = dx - dy;

            while (true)
            {
                if (0 <= x0 && x0 < xTiles && 0 <= y0 && y0 < zTiles)
                    yield return new Vector2(x0, y0);

                if (x0 == x1 && y0 == y1)
                    break;

                float derr = 2 * err;

                if (derr > -dy)
                {
                    err = err - dy;
                    x0 = x0 + sx;
                }

                if (derr < dx)
                {
                    err = err + dx;
                    y0 = y0 + sy;
                }
            }
        }

        private IEnumerable<Point> ScanPolygon(IList<Point> points)
        {
            var activeEdgeList = new List<Edge>();
            var activeEdgeTable = new List<List<Edge>>();
            int minY = BuildActiveEdgeTable(points, activeEdgeTable);

            for (int y = 0; y < activeEdgeTable.Count; y++)
            {
                for (int i = 0; i < activeEdgeTable[y].Count; i++)
                    activeEdgeList.Add(activeEdgeTable[y][i]);

                for (int i = 0; i < activeEdgeList.Count; i++)
                {
                    if (activeEdgeList[i].maxY <= y + minY)
                    {
                        activeEdgeList.RemoveAt(i);
                        i--;
                    }
                }

                activeEdgeList.Sort((a, b) => (a.currentX == b.currentX ? a.slopeRecip.CompareTo(b.slopeRecip) : a.currentX.CompareTo(b.currentX)));

                for (int i = 0; i < activeEdgeList.Count; i += 2)
                {
                    int yLine = minY + y;

                    if (0 <= yLine && yLine < zTiles)
                    {
                        int xStart = Math.Max(0, (int)Math.Ceiling(activeEdgeList[i].currentX));
                        int xEnd = Math.Min(xTiles - 1, (int)activeEdgeList[i + 1].currentX);

                        for (int x = xStart; x <= xEnd; x++)
                            yield return new Point(x, yLine);
                    }
                }

                for (int i = 0; i < activeEdgeList.Count; i++)
                    activeEdgeList[i].Next();
            }
        }

        private class Edge
        {
            public float maxY;
            public float currentX;
            public float slopeRecip;

            public Edge(Point current, Point next)
            {
                maxY = Math.Max(current.Y, next.Y);
                slopeRecip = (current.X - next.X) / (float)(current.Y - next.Y);

                if (current.Y == maxY)
                    currentX = next.X;
                else
                    currentX = current.X;
            }

            public void Next()
            {
                currentX += slopeRecip;
            }
        }

        private static int BuildActiveEdgeTable(IList<Point> points, List<List<Edge>> activeEdgeTable)
        {
            activeEdgeTable.Clear();

            int minY = points.Min(p => p.Y);
            int maxY = points.Max(p => p.Y);

            for (int i = minY; i <= maxY; i++)
                activeEdgeTable.Add(new List<Edge>());

            for (int i = 0; i < points.Count; i++)
            {
                Point current = points[i];
                Point next = points[(i + 1) % points.Count];

                if (current.Y == next.Y)
                    continue;

                var e = new Edge(current, next);

                if (current.Y == e.maxY)
                    activeEdgeTable[next.Y - minY].Add(e);
                else
                    activeEdgeTable[current.Y - minY].Add(e);
            }

            return minY;
        }
    }
}