context: #region Copyright & License Information
  /*
   * Copyright 2007-2015 The OpenRA Developers (see AUTHORS)
   * This file is part of OpenRA, which is free software. It is made
   * available to you under the terms of the GNU General Public License
   * as published by the Free Software Foundation. For more information,
   * see COPYING.
   */
  #endregion
  
  using System;
  using System.Collections.Generic;
  using System.Drawing;
  using System.Linq;
  
  namespace OpenRA.Traits
  {
  	public enum SubCell { Invalid = int.MinValue, Any = int.MinValue / 2, FullCell = 0, First = 1 }
  
  	public class ActorMapInfo : ITraitInfo
  	{
  		[Desc("Size of partition bins (cells)")]
  		public readonly int BinSize = 10;
  
  		public object Create(ActorInitializer init) { return new ActorMap(init.World, this); }
  	}
  
  	public class ActorMap : ITick
  	{
  		class InfluenceNode
  		{
  			public InfluenceNode Next;
  			public SubCell SubCell;
  			public Actor Actor;
  		}
  
  		class Bin
  		{
  			public readonly List<Actor> Actors = new List<Actor>();
  			public readonly List<ProximityTrigger> ProximityTriggers = new List<ProximityTrigger>();
  		}
  
  		class CellTrigger
  		{
  			public readonly int Id;
  			public readonly CPos[] Footprint;
  			public bool Dirty;
  
  			Action<Actor> onActorEntered;
  			Action<Actor> onActorExited;
  
  			IEnumerable<Actor> currentActors = Enumerable.Empty<Actor>();
  
  			public CellTrigger(int id, CPos[] footprint, Action<Actor> onActorEntered, Action<Actor> onActorExited)
  			{
  				Id = id;
  				Footprint = footprint;
  
  				this.onActorEntered = onActorEntered;
  				this.onActorExited = onActorExited;
  
  				// Notify any actors that are initially inside the trigger zone
  				Dirty = true;
  			}
  
  			public void Tick(ActorMap am)
  			{
  				if (!Dirty)
  					return;
  
  				var oldActors = currentActors;
  				currentActors = Footprint.SelectMany(c => am.GetUnitsAt(c)).ToList();
  
  				var entered = currentActors.Except(oldActors);
  				var exited = oldActors.Except(currentActors);
  
  				if (onActorEntered != null)
  					foreach (var a in entered)
  						onActorEntered(a);
  
  				if (onActorExited != null)
  					foreach (var a in exited)
  						onActorExited(a);
  
  				Dirty = false;
  			}
  		}
  
  		class ProximityTrigger : IDisposable
  		{
  			public readonly int Id;
  			public WPos Position { get; private set; }
  			public WRange Range { get; private set; }
  
  			public WPos TopLeft { get; private set; }
  			public WPos BottomRight { get; private set; }
  
  			public bool Dirty;
  
  			Action<Actor> onActorEntered;
  			Action<Actor> onActorExited;
  
  			IEnumerable<Actor> currentActors = Enumerable.Empty<Actor>();
  
  			public ProximityTrigger(int id, WPos pos, WRange range, Action<Actor> onActorEntered, Action<Actor> onActorExited)
  			{
  				Id = id;
  
  				this.onActorEntered = onActorEntered;
  				this.onActorExited = onActorExited;
  
  				Update(pos, range);
  			}
  
  			public void Update(WPos newPos, WRange newRange)
  			{
  				Position = newPos;
  				Range = newRange;
  
  				var offset = new WVec(newRange, newRange, WRange.Zero);
  				TopLeft = newPos - offset;
  				BottomRight = newPos + offset;
  
  				Dirty = true;
  			}
  
  			public void Tick(ActorMap am)
  			{
  				if (!Dirty)
  					return;
  
  				var oldActors = currentActors;
  				var delta = new WVec(Range, Range, WRange.Zero);
  				currentActors = am.ActorsInBox(Position - delta, Position + delta)
  					.Where(a => (a.CenterPosition - Position).HorizontalLengthSquared < Range.Range * Range.Range)
  					.ToList();
  
  				var entered = currentActors.Except(oldActors);
  				var exited = oldActors.Except(currentActors);
  
  				if (onActorEntered != null)
  					foreach (var a in entered)
  						onActorEntered(a);
  
  				if (onActorExited != null)
  					foreach (var a in exited)
  						onActorExited(a);
  
  				Dirty = false;
  			}
  
  			public void Dispose()
  			{
  				if (onActorExited != null)
  					foreach (var a in currentActors)
  						onActorExited(a);
  			}
  		}
  
  		readonly ActorMapInfo info;
  		readonly Map map;
  		readonly Dictionary<int, CellTrigger> cellTriggers = new Dictionary<int, CellTrigger>();
  		readonly Dictionary<CPos, List<CellTrigger>> cellTriggerInfluence = new Dictionary<CPos, List<CellTrigger>>();
  		readonly Dictionary<int, ProximityTrigger> proximityTriggers = new Dictionary<int, ProximityTrigger>();
  		int nextTriggerId;
  
  		readonly CellLayer<InfluenceNode> influence;
  
  		readonly Bin[] bins;
  		readonly int rows, cols;
  
  		// Position updates are done in one pass
  		// to ensure consistency during a tick
  		readonly HashSet<Actor> addActorPosition = new HashSet<Actor>();
  		readonly HashSet<Actor> removeActorPosition = new HashSet<Actor>();
  		readonly Predicate<Actor> actorShouldBeRemoved;
  
  		public ActorMap(World world, ActorMapInfo info)
  		{
  			this.info = info;
  			map = world.Map;
  			influence = new CellLayer<InfluenceNode>(world.Map);
  
  			cols = CellCoordToBinIndex(world.Map.MapSize.X) + 1;
  			rows = CellCoordToBinIndex(world.Map.MapSize.Y) + 1;
  			bins = new Bin[rows * cols];
  			for (var row = 0; row < rows; row++)
  				for (var col = 0; col < cols; col++)
  					bins[row * cols + col] = new Bin();
  
  			// Cache this delegate so it does not have to be allocated repeatedly.
  			actorShouldBeRemoved = removeActorPosition.Contains;
  		}
  
  		public IEnumerable<Actor> GetUnitsAt(CPos a)
  		{
  			if (!map.Contains(a))
  				yield break;
  
  			for (var i = influence[a]; i != null; i = i.Next)
  				if (!i.Actor.Destroyed)
  					yield return i.Actor;
  		}
  
  		public IEnumerable<Actor> GetUnitsAt(CPos a, SubCell sub)
  		{
  			if (!map.Contains(a))
  				yield break;
  
  
gt: 			for (var i = influence[a]; i != null; i = i.Next)