#define JSG_MODIFY_ASTAT_SPACE using CommonAI.ZoneClient; using CommonLang; using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; namespace CommonAI.RTS { /// /// 管理空间分割类,十字链表空间管理。 /// public class SpaceDivision : IDisposable { public float SpaceCellW { get; private set; } public float SpaceCellH { get; private set; } public int SpaceXCount { get; private set; } public int SpaceYCount { get; private set; } private SpaceCellNode[,] SpaceMatrix; private bool mNearChanged = true; internal SpaceDivision(float total_w, float total_h, float cellSizeW, float cellSizeH) { this.SpaceCellW = cellSizeW; this.SpaceCellH = cellSizeH; this.SpaceXCount = CMath.roundMod(total_w, SpaceCellW); this.SpaceYCount = CMath.roundMod(total_h, SpaceCellH); this.SpaceMatrix = new SpaceCellNode[SpaceXCount, SpaceYCount]; for (int ix = 0; ix < SpaceXCount; ++ix) { for (int iy = 0; iy < SpaceYCount; ++iy) { this.SpaceMatrix[ix, iy] = new SpaceCellNode(ix, iy); } } int[][] near_table = new int[][] { new int[]{-1,-1}, new int[]{ 0,-1}, new int[]{ 1,-1}, new int[]{-1, 0}, new int[]{ 1, 0}, new int[]{-1, 1}, new int[]{ 0, 1}, new int[]{ 1, 1} }; for (int ix = 0; ix < SpaceXCount; ++ix) { for (int iy = 0; iy < SpaceYCount; ++iy) { SpaceCellNode node = SpaceMatrix[ix, iy]; for (int ni = 0; ni < near_table.Length; ni++) { SpaceCellNode near = GetSpaceCell( ix + near_table[ni][0], iy + near_table[ni][1]); if (near != null && near != node) { node.nears.Add(near); } } } } } public void Dispose() { for (int ix = 0; ix < SpaceXCount; ++ix) { for (int iy = 0; iy < SpaceYCount; ++iy) { SpaceCellNode node = SpaceMatrix[ix, iy]; node.Dispose(); } } } /// /// 实际坐标转换为分割块坐标 /// /// /// /// /// public void ToSpaceBlock(float x, float y, out int cx, out int cy) { cx = (int)(x / SpaceCellW); cy = (int)(y / SpaceCellH); } private void ToSpaceBlock(float x, float y, float r, out int cx1, out int cy1, out int cx2, out int cy2) { cx1 = (int)((x - r) / this.SpaceCellW); cy1 = (int)((y - r) / this.SpaceCellH); cx2 = (int)((x + r) / this.SpaceCellW); cy2 = (int)((y + r) / this.SpaceCellH); cx1 = Math.Max(cx1, 0); cy1 = Math.Max(cy1, 0); cx2 = Math.Min(cx2, this.SpaceXCount - 1); cy2 = Math.Min(cy2, this.SpaceYCount - 1); } private void ToSpaceBlock(float x1, float y1, float x2, float y2, out int cx1, out int cy1, out int cx2, out int cy2) { if (x2 < x1) CUtils.Swap(ref x2, ref x1); if (y2 < y1) CUtils.Swap(ref y2, ref y1); cx1 = (int)(x1 / this.SpaceCellW); cy1 = (int)(y1 / this.SpaceCellH); cx2 = (int)(x2 / this.SpaceCellW); cy2 = (int)(y2 / this.SpaceCellH); cx1 = Math.Max(cx1, 0); cy1 = Math.Max(cy1, 0); cx2 = Math.Min(cx2, this.SpaceXCount - 1); cy2 = Math.Min(cy2, this.SpaceYCount - 1); } public SpaceCellNode GetSpaceCell(int cx, int cy) { if (cx < SpaceXCount && cx >= 0 && cy < SpaceYCount && cy >= 0) { return SpaceMatrix[cx, cy]; } return null; } /// /// 按格取分割块 /// /// /// /// public SpaceCellNode GetSpaceCellNodeByBlock(int cx, int cy) { if (cx < SpaceXCount && cx >= 0 && cy < SpaceYCount && cy >= 0) { return SpaceMatrix[cx, cy]; } return null; } /// /// 按坐标取分割块 /// /// /// /// public SpaceCellNode GetSpaceCellNode(float x, float y) { int cx = (int)(x / SpaceCellW); int cy = (int)(y / SpaceCellH); if (cx < SpaceXCount && cx >= 0 && cy < SpaceYCount && cy >= 0) { return SpaceMatrix[cx, cy]; } return null; } public List ListSpaceCellNodes() { List ret = new List(SpaceXCount * SpaceYCount); for (int ix = 0; ix < SpaceXCount; ++ix) { for (int iy = 0; iy < SpaceYCount; ++iy) { ret.Add(GetSpaceCellNodeByBlock(ix, iy)); } } return ret; } #region _ObjectPositionChanged_ public void NearChange() { mNearChanged = true; } // 更新场景内的分割区域变化信息 public void ClearSpaceNearChanges() { this.mNearChanged = false; for (int ix = 0; ix < SpaceXCount; ++ix) { for (int iy = 0; iy < SpaceYCount; ++iy) { SpaceCellNode node = SpaceMatrix[ix, iy]; node.ClearNearChange(); } } } /// /// 刷新空间分割位置为有改变 /// /// public void NearChange(ObjectCellNode old_cell) { if (old_cell.cell != null) { old_cell.cell.NearChange(); } this.NearChange(); } /// /// 清除空间位置 /// /// public void ClearSpace(ObjectCellNode old_cell) { if (old_cell.cell != null) { old_cell.cell.Remove(old_cell, true); } this.NearChange(); } /// /// 切换单位空间位置 /// public bool SwapSpace(ObjectCellNode obj, float x, float y, bool nearchange) { if (nearchange) mNearChanged = true; SpaceCellNode old_cell = obj.cell; SpaceCellNode new_cell = GetSpaceCellNode(x, y); if (old_cell != new_cell) { if (old_cell != null) { old_cell.Remove(obj, nearchange); } if (new_cell != null) { new_cell.Add(obj, nearchange); } return true; } return false; } public bool IsNearChanged() { return mNearChanged; } /// /// 判断是否附近有位置变化 /// /// /// /// public bool IsNearChanged(float x, float y) { if (this.mNearChanged) { SpaceCellNode node = this.GetSpaceCellNode(x, y); if (node != null) { if (node.IsNearChanged) { return true; } for (int i = node.nears.Count - 1; i >= 0; --i) { if (node.nears[i].IsNearChanged) { return true; } } } } return false; } public bool IsNearChanged(float x, float y, float r) { if (this.mNearChanged) { if (r < this.SpaceCellW && r < this.SpaceCellH) { SpaceCellNode node = this.GetSpaceCellNode(x, y); if (node != null) { if (node.IsNearChanged) return true; for (int i = node.nears.Count - 1; i >= 0; --i) { if (node.nears[i].IsNearChanged) return true; } } } else { #if JSG_MODIFY_ASTAT_SPACE int cx1, cy1, cx2, cy2; this.ToSpaceBlock(x - r, y - r, x + r, y + r, out cx1, out cy1, out cx2, out cy2); #else int cx1 = (int)((x - r) / this.SpaceCellW) - 1; int cy1 = (int)((y - r) / this.SpaceCellH) - 1; int cx2 = (int)((x + r) / this.SpaceCellW) + 1; int cy2 = (int)((y + r) / this.SpaceCellH) + 1; cx1 = Math.Max(cx1, 0); cy1 = Math.Max(cy1, 0); cx2 = Math.Min(cx2, this.SpaceXCount - 1); cy2 = Math.Min(cy2, this.SpaceYCount - 1); #endif for (int cx = cx1; cx <= cx2; ++cx) { for (int cy = cy1; cy <= cy2; ++cy) { SpaceCellNode cn = this.SpaceMatrix[cx, cy]; if (cn.IsNearChanged) return true; } } } } return false; } public bool IsNearChanged(float x1, float y1, float x2, float y2) { if (this.mNearChanged) { if (x2 < x1) CUtils.Swap(ref x2, ref x1); if (y2 < y1) CUtils.Swap(ref y2, ref y1); #if JSG_MODIFY_ASTAT_SPACE int cx1, cy1, cx2, cy2; this.ToSpaceBlock(x1, y1, x2, y2, out cx1, out cy1, out cx2, out cy2); #else int cx1 = (int)(x1 / this.SpaceCellW) - 1; int cy1 = (int)(y1 / this.SpaceCellH) - 1; int cx2 = (int)(x2 / this.SpaceCellW) + 1; int cy2 = (int)(y2 / this.SpaceCellH) + 1; cx1 = Math.Max(cx1, 0); cy1 = Math.Max(cy1, 0); cx2 = Math.Min(cx2, this.SpaceXCount - 1); cy2 = Math.Min(cy2, this.SpaceYCount - 1); #endif for (int cx = cx1; cx <= cx2; ++cx) { for (int cy = cy1; cy <= cy2; ++cy) { SpaceCellNode cn = this.SpaceMatrix[cx, cy]; if (cn.IsNearChanged) return true; } } } return false; } #endregion //---------------------------------------------------------------------------------------------------------------------------- /// /// 获取当前坐标附近的所有单位容量 /// /// /// /// public int GetNearObjectsCapacity(float x, float y) { int ret = 0; SpaceCellNode node = this.GetSpaceCellNode(x, y); if (node != null) { ret += node.Count; for (int i = node.nears.Count - 1; i >= 0; --i) { ret += node.nears[i].Count; } } return Math.Max(ret, 10); } /// /// 遍历单位 /// /// /// 设置为True,立即停止遍历 public delegate void ObjectForEachAction(T obj, ref bool cancel) where T : class; /// /// 获取当前坐标附近的所有单位 /// /// /// /// /// is cancel public bool ForEachNearObjects(float x, float y, ObjectForEachAction indexer) where T : class { SpaceDivision.SpaceCellNode node = GetSpaceCellNode(x, y); if (node != null) { if (node.ForEach(indexer)) { return true; } for (int i = node.nears.Count - 1; i >= 0; --i) { if (node.nears[i].ForEach(indexer)) { return true; } } } return false; } public ZoneItem GetNearPickableItem(ZoneActor owner) { SpaceDivision.SpaceCellNode node = GetSpaceCellNode(owner.X, owner.Y); if (node != null) { var ret = node.GetNearPickableItem(owner); if (ret != null) { return ret; } for (int i = node.nears.Count - 1; i >= 0; --i) { ret = node.nears[i].GetNearPickableItem(owner); if (ret != null) { return ret; } } } return null; } public ZoneItem GetNearPopPanelItem(ZoneActor owner) { SpaceDivision.SpaceCellNode node = GetSpaceCellNode(owner.X, owner.Y); if (node != null) { var ret = node.GetNearPopPanelItem(owner); if (ret != null) { return ret; } for (int i = node.nears.Count - 1; i >= 0; --i) { ret = node.nears[i].GetNearPopPanelItem(owner); if (ret != null) { return ret; } } } return null; } /// /// 获取当前坐标附近的所有单位 /// /// /// /// /// /// is cancel public bool ForEachNearObjects(float x, float y, float r, ObjectForEachAction indexer) where T : class { if (r < SpaceCellW && r < SpaceCellH) { SpaceDivision.SpaceCellNode node = GetSpaceCellNode(x, y); if (node != null) { if (node.ForEach(indexer)) { return true; } for (int i = node.nears.Count - 1; i >= 0; --i) { if (node.nears[i].ForEach(indexer)) { return true; } } } } else { #if JSG_MODIFY_ASTAT_SPACE int cx1, cy1 , cx2 , cy2; this.ToSpaceBlock(x - r, y - r, x + r, y + r, out cx1, out cy1, out cx2, out cy2); #else int cx1 = (int)((x - r) / this.SpaceCellW) - 1; int cy1 = (int)((y - r) / this.SpaceCellH) - 1; int cx2 = (int)((x + r) / this.SpaceCellW) + 1; int cy2 = (int)((y + r) / this.SpaceCellH) + 1; cx1 = Math.Max(cx1, 0); cy1 = Math.Max(cy1, 0); cx2 = Math.Min(cx2, this.SpaceXCount - 1); cy2 = Math.Min(cy2, this.SpaceYCount - 1); #endif for (int cx = cx1; cx <= cx2; ++cx) { for (int cy = cy1; cy <= cy2; ++cy) { SpaceDivision.SpaceCellNode cn = this.SpaceMatrix[cx, cy]; if (cn.ForEach(indexer)) { return true; } } } } return false; } /// /// 获取当前坐标附近的所有单位 /// /// /// /// /// /// /// is cancel public bool ForEachNearObjectsRect(float x1, float y1, float x2, float y2, ObjectForEachAction indexer) where T : class { bool cancel = false; if (x2 < x1) CUtils.Swap(ref x2, ref x1); if (y2 < y1) CUtils.Swap(ref y2, ref y1); #if JSG_MODIFY_ASTAT_SPACE int cx1, cy1, cx2, cy2; this.ToSpaceBlock(x1, y1, x2, y2, out cx1, out cy1, out cx2, out cy2); #else int cx1 = (int)(x1 / this.SpaceCellW) - 1; int cy1 = (int)(y1 / this.SpaceCellH) - 1; int cx2 = (int)(x2 / this.SpaceCellW) + 1; int cy2 = (int)(y2 / this.SpaceCellH) + 1; cx1 = Math.Max(cx1, 0); cy1 = Math.Max(cy1, 0); cx2 = Math.Min(cx2, this.SpaceXCount - 1); cy2 = Math.Min(cy2, this.SpaceYCount - 1); #endif for (int cx = cx1; cx <= cx2; ++cx) { for (int cy = cy1; cy <= cy2; ++cy) { SpaceDivision.SpaceCellNode cn = this.SpaceMatrix[cx, cy]; if (cn.ForEach(indexer)) { return true; } } } return cancel; } //------------------------------------------------------------------------------------------------------------------ /// /// 单位链表结构节点 /// public class ObjectCellNode { public object Object { get { return obj; } } internal readonly object obj; internal SpaceCellNode cell; internal ObjectCellNode next; internal ObjectCellNode prev; internal bool mPosDirty; public ObjectCellNode(object obj) { this.obj = obj; } public void MarkPosDirty(bool dirty) { mPosDirty = dirty; } public ObjectCellNode Next { get { return next; } } public ObjectCellNode Prev { get { return prev; } } public bool PosDirty() { return mPosDirty;} internal void Remove() { if (next != null) { next.prev = this.prev; } if (prev != null) { prev.next = this.next; } this.next = null; this.prev = null; } internal void AddNext(ObjectCellNode next) { this.next = next; next.prev = this; } /// /// /// /// /// /// is canceled public bool ForEach(ObjectForEachAction action) where T : class { bool cancel = false; ObjectCellNode current = this; do { if (current.obj is T) { action((T)current.obj, ref cancel); if (cancel) return cancel; } current = current.next; } while (current != null); return cancel; } public ZoneItem GetNearPickableItem(ZoneActor owner) { var zl = owner.Parent; ZoneItem item = null; ObjectCellNode current = this; do { item = current.obj as ZoneItem; if (item != null && item.Info != null && !item.Info.IsPopPanel && zl.IsCanPickItem(owner, item)) { return item; } current = current.next; } while (current != null); return null; } public ZoneItem GetNearPopPanelItem(ZoneActor owner) { var zl = owner.Parent; ZoneItem item = null; ObjectCellNode current = this; do { item = current.obj as ZoneItem; if (item != null && item.Info != null && item.Info.IsPopPanel) { if (zl.IsCanPickItem(owner, item)) return item; } current = current.next; } while (current != null); return null; } public bool ForEach(ObjectForEachAction action) { bool cancel = false; ObjectCellNode current = this; do { action(current, ref cancel); if (cancel) return cancel; current = current.next; } while (current != null); return cancel; } internal struct Iterator : IEnumerator { public readonly ObjectCellNode mBegin; private bool mStart; private ObjectCellNode index; public Iterator(ObjectCellNode begin) { this.mBegin = begin; this.mStart = false; this.index = null; } public object Current { get { if (index != null) return index.obj; return null; } } public bool MoveNext() { if (!mStart) { index = mBegin; mStart = true; if (index == null) return false; return true; } index = index.next; if (index == null) return false; return true; } public void Reset() { this.mStart = false; } public void Dispose() { } } } //------------------------------------------------------------------------------------------------------------------ /// /// 空间分割节点,十字链表节点 /// public class SpaceCellNode { internal readonly int six; internal readonly int siy; internal readonly List nears = new List(); private ObjectCellNode mHead; private ObjectCellNode mTail; internal SpaceCellNode(int six, int siy) { this.six = six; this.siy = siy; } internal void Dispose() { using(var list = ListObjectPool.AllocAutoRelease()) { foreach (var o in list) { this.Remove(o, false); } } nears.Clear(); } public void NearChange() { IsNearChanged = true; } public void ClearNearChange() { IsNearChanged = false; } public void Add(ObjectCellNode cell, bool nearchange) { if (cell.Next != null || cell.Prev != null) { throw new Exception("obj.mCurCellNode.Next != null || obj.mCurCellNode.Prev != null"); } if (nearchange) IsNearChanged = true; if (Count == 0) { mHead = mTail = cell; } else { mTail.AddNext(cell); mTail = cell; } cell.cell = this; Count++; if (mOnObjectAdded != null) { mOnObjectAdded.Invoke(this, cell.obj); } } public void Remove(ObjectCellNode cell, bool nearchange) { if (nearchange) IsNearChanged = true; Count--; if (Count == 0) { mHead = mTail = null; } else if (mHead == cell) { mHead = mHead.Next; } else if (mTail == cell) { mTail = mTail.Prev; } cell.Remove(); cell.cell = null; if (mOnObjectRemoved != null) { mOnObjectRemoved.Invoke(this, cell.obj); } } public int BX { get { return six; } } public int BY { get { return siy; } } public bool IsNearChanged { get; private set; } public int Count { get; private set; } [Obsolete] public List AsChildList() where T : class { List ret = new List(this.Count); this.ForEach((T o, ref bool c) => { ret.Add(o); }); return ret; } public void AsChildList(List ret) where T : class { this.ForEach((T o, ref bool c) => { ret.Add(o); }); } public void AsNodeList(List ret) { if (mHead != null) { mHead.ForEach((ObjectCellNode o, ref bool cancel)=> { ret.Add(o); }); } } /// /// /// /// /// /// is canceled public bool ForEach(ObjectForEachAction action) where T : class { if (mHead != null) { return mHead.ForEach(action); } return false; } public ZoneItem GetNearPickableItem(ZoneActor owner) { if (mHead != null) { return mHead.GetNearPickableItem(owner); } return null; } public ZoneItem GetNearPopPanelItem(ZoneActor owner) { if (mHead != null) { return mHead.GetNearPopPanelItem(owner); } return null; } public delegate void OnObjectAddedHandler(SpaceCellNode node, object obj); public delegate void OnObjectRemovedHandler(SpaceCellNode node, object obj); private OnObjectAddedHandler mOnObjectAdded; private OnObjectRemovedHandler mOnObjectRemoved; public event OnObjectAddedHandler OnObjectAdded { add { mOnObjectAdded += value; } remove { mOnObjectAdded -= value; } } public event OnObjectRemovedHandler OnObjectRemoved { add { mOnObjectRemoved += value; } remove { mOnObjectRemoved -= value; } } } } }