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 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(); } 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 points) { foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList())) this[point.X, point.Y] = RoomGridWeight.Clear; } public void DrawDanger(IEnumerable points) { foreach (var point in ScanPolygon(points.Select(v => WorldToGrid(v)).ToList())) this[point.X, point.Y] = RoomGridWeight.Danger; } public void DrawStairsEntry(IEnumerable 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 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 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 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 ScanLine(Point p0, Point p1) { return ScanLine(p0.X, p0.Y, p1.X, p1.Y); } private IEnumerable 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 ScanLine(Vector2 p0, Vector2 p1) { return ScanLine(p0.X, p0.Y, p1.X, p1.Y); } private IEnumerable 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 ScanPolygon(IList points) { var activeEdgeList = new List(); var activeEdgeTable = new List>(); 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 points, List> 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()); 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; } } }