using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using V3.Objects;
using Rectangle = Microsoft.Xna.Framework.Rectangle;
namespace V3
{
public sealed class Node
{
///
/// Represents the Rectangle if a Quad gets split
///
private Node mRt; // The rectangle on the right top
private Node mLt; // The rectangle on the left top
private Node mRb; // The rectangle on the right bottom
private Node mLb; // The rectangle on the left bottom
private readonly Node mParent; // the parent of a node
private Rectangle mRectangle;
private readonly int mPositionX; // X position of the current rectangle
private readonly int mPositionY; // Y position of the current rectangle
private readonly int mSizeX; // length of the current rectangle
private readonly int mSizeY; // width of the current rectangle
private readonly int mCenterX; // center of the current rectangle
private readonly int mCenterY;
private int mCount;
private Rectangle mCreatureRectangle;
private MovementDirection mMovementDirectionItem2;
private MovementState mMovementStateItem;
private MovementState mMovementStateItem2;
///
/// The list of each node where the objects in each rectangle are saved
///
private List mObjectList = new List();
private int Count => ObjectCount();
///
/// initialize the Node
///
/// the current Rectangle/size of the Node
/// the parent of the node
public Node(Rectangle currentRectangle, Node p)
{
mParent = p;
mRectangle = currentRectangle;
mPositionY = mRectangle.Y;
mPositionX = mRectangle.X;
mSizeX = mRectangle.Width;
mSizeY = mRectangle.Height;
mCenterY = mRectangle.Y + mRectangle.Height / 2;
mCenterX = mRectangle.X + mRectangle.Width / 2;
}
///
/// divided the rectangle in 4 small rectangles locaded in it self
///
private void CreateSubnodes()
{
if (mLt == null)
{
mLt = new Node(new Rectangle(mPositionX - 1, mPositionY - 1, mSizeX / 2 + 2, mSizeY / 2 + 2),
this);
mRt = new Node(new Rectangle(mPositionX + mSizeX / 2, mPositionY - 1, mSizeX / 2 + 1, mSizeY / 2 + 2),
this);
mLb = new Node(new Rectangle(mPositionX - 1, mPositionY + mSizeY / 2, mSizeX / 2 + 2, mSizeY / 2 + 1),
this);
mRb = new Node( new Rectangle(mPositionX + mSizeX / 2, mPositionY + mSizeY / 2, mSizeX / 2 + 1, mSizeY / 2 + 1),
this);
}
}
///
/// This method is looking in which rectangle the object is located.
/// At first it checks in which part (right top, left top...) of the rectangle the object is
/// and if its posibible the rectangle gets split in for new rectangles the same is happening again.
///
/// Type of Creature including their position.
public void AddtoSubNode(IGameObject item)
{
mCreatureRectangle = item.BoundaryRectangle;
if (mRectangle.Contains(mCreatureRectangle))
{
if (mCreatureRectangle.Right < mCenterX && (mCreatureRectangle.Y + mCreatureRectangle.Height) < mCenterY)
{
CreateSubnodes(); // splits subnode in more subnodes
mLt.AddtoSubNode(item);
}
else if (mCreatureRectangle.X > mCenterX && (mCreatureRectangle.Y + mCreatureRectangle.Height) < mCenterY)
{
CreateSubnodes();
mRt.AddtoSubNode(item);
}
else if (mCreatureRectangle.Right < mCenterX && mCreatureRectangle.Y > mCenterY)
{
CreateSubnodes();
mLb.AddtoSubNode(item);
}
else if (mCreatureRectangle.X > mCenterX && mCreatureRectangle.Y > mCenterY)
{
CreateSubnodes();
mRb.AddtoSubNode(item);
}
else
{
mObjectList.Add(item); // the object gets added to the objectlist of the current node/subnode
//CheckCollission(mObjectList);
mCount++;
if (mCount == 8)
{
CheckCollission(mObjectList);
}
else if (mCount > 8)
{
mCount = 0;
}
}
}
}
///
/// checks if the Objects in the same Quad are intersecting
///
/// list with the objects in the same quad
//void CheckCollission(List objectList)
void CheckCollission(List objectList)
{
// if (mParent != null)
// {
// mList2 = mParent.mObjectList;
// }
foreach (var obj in objectList)
{
foreach (var obj2 in objectList)
{
if (Equals(obj, obj2))
{
continue;
}
if (obj.BoundaryRectangle.Intersects(obj2.BoundaryRectangle))
//if (obj.BoundaryRectangle.X < obj2.BoundaryRectangle.X + obj2.BoundaryRectangle.Width &&
//obj.BoundaryRectangle.X + obj.BoundaryRectangle.Width > obj2.BoundaryRectangle.X &&
//obj.BoundaryRectangle.Y < obj2.BoundaryRectangle.Y + obj2.BoundaryRectangle.Height &&
//obj.BoundaryRectangle.Height + obj.BoundaryRectangle.Y > obj2.BoundaryRectangle.Y)
{
if (!(obj is ICreature)) return;
if (!(obj2 is ICreature)) return;
ICreature creature = (ICreature)obj;
mMovementStateItem = creature.MovementState;
ICreature creature2 = (ICreature)obj2;
mMovementStateItem2 = creature2.MovementState;
if (mMovementStateItem != MovementState.Dying && (mMovementStateItem2 != MovementState.Dying))
{
HandleCollision(obj, obj2);
}
}
}
}
//if (mParent != null)
//{
// foreach (var obj in mList2)
// {
// foreach (var obj2 in objectList)
// {
// if (obj == obj2)
// {
// continue;
// }
// if (obj.BoundaryRectangle.Intersects(obj2.BoundaryRectangle))
// //if (obj.BoundaryRectangle.X < obj2.BoundaryRectangle.X + obj2.BoundaryRectangle.Width &&
// // obj.BoundaryRectangle.X + obj.BoundaryRectangle.Width > obj2.BoundaryRectangle.X &&
// // obj.BoundaryRectangle.Y < obj2.BoundaryRectangle.Y + obj2.BoundaryRectangle.Height &&
// // obj.BoundaryRectangle.Height + obj.BoundaryRectangle.Y > obj2.BoundaryRectangle.Y)
// {
// if (!(obj is ICreature)) return;
// if (!(obj2 is ICreature)) return;
// //if (obj.GetType() != typeof(ICreature)) return;
// ICreature creature = (ICreature)obj;
// mMovementStateItem = creature.MovementState;
// ICreature creature2 = (ICreature)obj2;
// mMovementStateItem2 = creature2.MovementState;
// if (mMovementStateItem != MovementState.Dying && (mMovementStateItem2 != MovementState.Dying))
// {
// HandleCollision(obj, obj2);
// }
// //mCollision = true;
// }
// }
// }
//}
}
///
/// If collsion is detected the object gets moved away so there is no collision anymore
///
/// the object which collid with another object
/// the other object
//void HandleCollision(AbstractCreature item, AbstractCreature item2)
void HandleCollision(IGameObject item, IGameObject item2)
{
ICreature creature = (ICreature)item;
ICreature creature2 = (ICreature)item2;
mMovementDirectionItem2 = creature2.MovementDirection;
if (mMovementDirectionItem2 == MovementDirection.S)
{
creature.Position = new Vector2(item.Position.X + 1, item.Position.Y);
}
if (mMovementDirectionItem2 == MovementDirection.N)
{
creature.Position = new Vector2(item.Position.X + 1, item.Position.Y);
}
else if (mMovementDirectionItem2 == MovementDirection.O)
{
creature.Position = new Vector2(item.Position.X, item.Position.Y + 1);
}
else if (mMovementDirectionItem2 == MovementDirection.W)
{
creature.Position = new Vector2(item.Position.X, item.Position.Y + 1);
}
else if (mMovementDirectionItem2 == MovementDirection.SO)
{
creature.Position = new Vector2(item.Position.X - 1, item.Position.Y);
}
else if (mMovementDirectionItem2 == MovementDirection.NO)
{
creature.Position = new Vector2(item.Position.X + 1, item.Position.Y - 1);
}
else if (mMovementDirectionItem2 == MovementDirection.NW)
{
creature.Position = new Vector2(item.Position.X - 1, item.Position.Y + 1);
}
else if (mMovementDirectionItem2 == MovementDirection.SW)
{
creature.Position = new Vector2(item.Position.X + 1, item.Position.Y);
}
else
{
creature.Position = new Vector2(item.Position.X + 1, item.Position.Y + 1);
}
}
///
/// Clears the QuadTree of all objects, including any objects living in its children.
///
public void Clear()
{
// Clear out the children, if we have any
if (mLt != null)
{
mLt.Clear();
mRt.Clear();
mLb.Clear();
mRb.Clear();
}
// Clear any objects at this level
if (mObjectList != null)
{
mObjectList.Clear();
mObjectList = null;
}
// Set the children to null
mLt = null;
mRt = null;
mLb = null;
mRb = null;
}
///
/// Get the total for all objects in this QuadTree, including children.
///
/// The number of objects contained within this QuadTree and its children.
private int ObjectCount()
{
int count = 0;
// Add the objects at this level
if (mObjectList != null) count += mObjectList.Count;
// Add the objects that are contained in the children
if (mLt != null)
{
count += mLt.ObjectCount();
count += mRt.ObjectCount();
count += mLb.ObjectCount();
count += mRb.ObjectCount();
}
return count;
}
///
/// Deletes an item from this QuadTree. If the object is removed causes this Quad to have no objects in its children,
/// it's children will be removed as well.
///
///
public void Delete(IGameObject item)
{
if (mObjectList.Contains(item))
{
mObjectList.Remove(item);
}
// If we didn't find the object in this tree, try to delete from its children
else if (mLt != null)
{
mLt.Delete(item);
mRt.Delete(item);
mLb.Delete(item);
mRb.Delete(item);
}
// If all the children are empty, delete all the children
if (mLt?.Count == 0 &&
mRt.Count == 0 &&
mLb.Count == 0 &&
mRb.Count == 0)
{
mLt = null;
mRt = null;
mLb = null;
mRb = null;
}
}
///
/// If the Object isnt in his old Rectangle anymore it have to move
/// the object to the parent(s) Rectangle until it fits, and optionally going back down into children
///
/// Actuell Creature
private void Move(IGameObject item)
{
if (mParent != null && mParent.mRectangle.Contains(item.BoundaryRectangle))
{
mParent.AddtoSubNode(item);
}
else if (mParent == null)
{
AddtoSubNode(item);
}
else
{
mParent.Move(item);
}
}
///
/// If four Subnodes are empty the get deleted
///
private void RemoveEmptyNodes()
{
// If all the children are empty, delete all the children
if (mLt?.Count == 0 &&
mRt.Count == 0 &&
mLb.Count == 0 &&
mRb.Count == 0)
{
mLt = null;
mRt = null;
mLb = null;
mRb = null;
}
mLt?.RemoveEmptyNodes();
mRt?.RemoveEmptyNodes();
mLb?.RemoveEmptyNodes();
mRb?.RemoveEmptyNodes();
}
///
/// Gibt einem alle Argumente die Innerhalb des rectangles sind zurück in der Liste objectInRecList
///
/// Der Bereich aus dem man alle Objecte haben möchte
/// Die Liste, in der alle Objekte enthalten sind, die sich im gefragten Rectangle aufhalten
///
public List GetObjectsInRectangle(Rectangle rectangle, List objectInRecList)
{
if (rectangle.Intersects(mRectangle))
{
if (mObjectList != null)
{
foreach (var obj in mObjectList)
{
if (obj.GetSelf() != null)
{
objectInRecList.Add(obj);
}
}
}
if (mLt != null)
{
mLt.GetObjectsInRectangle(rectangle, objectInRecList);
mRt.GetObjectsInRectangle(rectangle, objectInRecList);
mLb.GetObjectsInRectangle(rectangle, objectInRecList);
mRb.GetObjectsInRectangle(rectangle, objectInRecList);
}
}
return objectInRecList;
}
///
/// Updates the position of the object in the Quadtree. If they changed their position
/// they get deleted and added again at the correct position.
///
public void Update1()
{
List copyList = new List(mObjectList);
//CheckCollission(mObjectList);
foreach (IGameObject obj in copyList)
{
if (!(obj is ICreature))
continue;
Delete(obj);
if (mRectangle.Contains(obj.BoundaryRectangle))
{
AddtoSubNode(obj);
}
// if Creature isnt there anymore -> move
else
{
Move(obj);
break;
}
}
mLt?.Update1();
mRt?.Update1();
mRb?.Update1();
mLb?.Update1();
RemoveEmptyNodes();
}
///
/// Makes the Quadtree visible
///
/// to draw the Rectangles
///
public void DrawQuadtree(SpriteBatch spriteBatch, Texture2D texture)
{
//spriteBatch.Draw(mQuadtree.Texture, mRectangle, Color.Black);
spriteBatch.Draw(texture, new Rectangle(mPositionX, mPositionY, mSizeX, 2), Color.Black);
spriteBatch.Draw(texture, new Rectangle(mPositionX, mPositionY, 2, mSizeY), Color.Black);
spriteBatch.Draw(texture, new Rectangle(mPositionX + mSizeX, mPositionY, 2, mSizeY), Color.Black);
spriteBatch.Draw(texture, new Rectangle(mPositionX, mPositionY + mSizeY, mSizeX, 2), Color.Black);
mLt?.DrawQuadtree(spriteBatch, texture);
mRt?.DrawQuadtree(spriteBatch, texture);
mLb?.DrawQuadtree(spriteBatch, texture);
mRb?.DrawQuadtree(spriteBatch, texture);
// Draws the rectangle of each Creature
//foreach (var obj in mObjectList)
//{
// spriteBatch.Draw(mQuadtree.Texture, new Rectangle(obj.BoundaryRectangle.X, obj.BoundaryRectangle.Y, obj.BoundaryRectangle.Width, 5), Color.Red);
// spriteBatch.Draw(mQuadtree.Texture, new Rectangle(obj.BoundaryRectangle.X, obj.BoundaryRectangle.Y, 5, obj.BoundaryRectangle.Height), Color.Red);
// spriteBatch.Draw(mQuadtree.Texture, new Rectangle(obj.BoundaryRectangle.X + obj.BoundaryRectangle.Width, obj.BoundaryRectangle.Y, 5, obj.BoundaryRectangle.Height), Color.Red);
// spriteBatch.Draw(mQuadtree.Texture, new Rectangle(obj.BoundaryRectangle.X, obj.BoundaryRectangle.Y + obj.BoundaryRectangle.Height, obj.BoundaryRectangle.Width, 5), Color.Red);
//}
}
}
}