Download this FREE eBook and learn all you need to get started with Windows Nano Server, including deployment options, remote management
and troubleshooting tips and tricks
private List<AStarNode> FindPathNoReduction(Point start, Point dest)
{
List<AStarNode> ptd = new List<AStarNode>();
start.Offset(-(this.Map.X), -(this.Map.Y));
dest.Offset(-(this.Map.X), -(this.Map.Y));
int destx = dest.X;
int desty = dest.Y;
int left = this.Map.Bounds.Left;
int top = this.Map.Bounds.Top;
int right = this.Map.Bounds.Right;
int bottom = this.Map.Bounds.Bottom;
int width = this.Map.Width;
int height = this.Map.Height;
UInt16[,] collisiondata = this.Map.CollisionData;
float factor = 1;
AStarNode[,] nodegrid = new AStarNode[this.Map.Width, this.Map.Height];
AStarNode endnode = new AStarNode(dest.X, dest.Y, false, false, null, 0, 0);
AStarNode startnode = new AStarNode(start.X, start.Y, false, true, null, 0, this.Heuristic.Calculate(destx, desty, start.X, start.Y) * factor);
PriorityQueueB<AStarNode> openQueue = new PriorityQueueB<AStarNode>(new AStarNodeComparer());
openQueue.Push(startnode);
float newg = 0;
int cx = 0;
int cy = 0;
AStarNode node;
int vxvy;
AStarNode cnode;
while (true)
{
if (openQueue.Count == 0)
break;
node = openQueue.Pop();
//CHeck to see if we have reached the destination
if (node.X == endnode.X && node.Y == endnode.Y)
{
//set score
this.Score = node.F;
//BUILD PATH USING REFRENCED PARENTS
ptd.Add(node);
node.X += this.Map.X;
node.Y += this.Map.Y;
if (node.Parent != null)
{
do
{
ptd.Add(node = node.Parent);
node.X += this.Map.X;
node.Y += this.Map.Y;
if (node.Parent == null)
break;
} while (true);
}
//return the final path
ptd.Reverse();
//Put the offset back in and move to path
return ptd;
}
else
{
// look for adjacent blocks that we attach to and add them to open
for (int vy = -1; vy < 2; vy++)
{
for (int vx = -1; vx < 2; vx++)
{
if (vx == 0 && vy == 0) continue; //continue if we are on the current node
cx = node.X + vx; cy = node.Y + vy;
vxvy = vx * vy;
//check for map edge
if (cy < 0 || cy > height - 1 || cx < 0 || cx > width - 1) continue;
//check for walkability and small diagonal gaps that cant be passed
if ((collisiondata[cx, cy] & 1) > 0) continue;
if (vxvy != 0 && ((collisiondata[node.X, cy] & 1) > 0)
&& ((collisiondata[cx, node.Y] & 1) > 0)) continue;
newg = node.G + SCORE[Math.Abs(vxvy)];
cnode = nodegrid[cx, cy];
if (cnode == null)
{
cnode = new AStarNode(cx, cy, false, false, node, newg, this.Heuristic.Calculate(destx, desty, cx, cy) * factor);
nodegrid[cx, cy] = cnode;
}
else
{
if (cnode.G > newg)
{
cnode.IsClosed = false;
cnode.G = newg;
cnode.Parent = node;
}
else continue;
}
if (!cnode.IsOpen)
{
cnode.IsOpen = true;
openQueue.Push(cnode);
}
}
}
node.IsOpen = false; node.IsClosed = true;
}
}
return ptd;
}
public class PriorityQueueB<T> : IPriorityQueue<T>
{
#region Variables Declaration
protected List<T> InnerList = new List<T>();
protected IComparer<T> mComparer;
#endregion
#region Contructors
public PriorityQueueB()
{
mComparer = Comparer<T>.Default;
}
public PriorityQueueB(IComparer<T> comparer)
{
mComparer = comparer;
}
public PriorityQueueB(IComparer<T> comparer, int capacity)
{
mComparer = comparer;
InnerList.Capacity = capacity;
}
#endregion
#region Methods
protected void SwitchElements(int i, int j)
{
T h = InnerList[i];
InnerList[i] = InnerList[j];
InnerList[j] = h;
}
protected virtual int OnCompare(int i, int j)
{
return mComparer.Compare(InnerList[i], InnerList[j]);
}
/// <summary>
/// Push an object onto the PQ
/// </summary>
/// <param name="O">The new object</param>
/// <returns>The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.</returns>
public int Push(T item)
{
int p = InnerList.Count, p2;
InnerList.Add(item); // E[p] = O
do
{
if (p == 0)
break;
p2 = (p - 1) / 2;
if (OnCompare(p, p2) < 0)
{
SwitchElements(p, p2);
p = p2;
}
else
break;
} while (true);
return p;
}
/// <summary>
/// Get the smallest object and remove it.
/// </summary>
/// <returns>The smallest object</returns>
public T Pop()
{
T result = InnerList[0];
int p = 0, p1, p2, pn;
InnerList[0] = InnerList[InnerList.Count - 1];
InnerList.RemoveAt(InnerList.Count - 1);
do
{
pn = p;
p1 = 2 * p + 1;
p2 = 2 * p + 2;
if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner
p = p1;
if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
p = p2;
if (p == pn)
break;
SwitchElements(p, pn);
} while (true);
return result;
}
/// <summary>
/// Notify the PQ that the object at position i has changed
/// and the PQ needs to restore order.
/// Since you dont have access to any indexes (except by using the
/// explicit IList.this) you should not call this function without knowing exactly
/// what you do.
/// </summary>
/// <param name="i">The index of the changed object.</param>
public void Update(int i)
{
int p = i, pn;
int p1, p2;
do // aufsteigen
{
if (p == 0)
break;
p2 = (p - 1) / 2;
if (OnCompare(p, p2) < 0)
{
SwitchElements(p, p2);
p = p2;
}
else
break;
} while (true);
if (p < i)
return;
do // absteigen
{
pn = p;
p1 = 2 * p + 1;
p2 = 2 * p + 2;
if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner
p = p1;
if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
p = p2;
if (p == pn)
break;
SwitchElements(p, pn);
} while (true);
}
/// <summary>
/// Get the smallest object without removing it.
/// </summary>
/// <returns>The smallest object</returns>
public T Peek()
{
if (InnerList.Count > 0)
return InnerList[0];
return default(T);
}
public void Clear()
{
InnerList.Clear();
}
public int Count
{
get { return InnerList.Count; }
}
public void RemoveLocation(T item)
{
int index = -1;
for (int i = 0; i < InnerList.Count; i++)
{
if (mComparer.Compare(InnerList[i], item) == 0)
index = i;
}
if (index != -1)
InnerList.RemoveAt(index);
}
public T this[int index]
{
get { return InnerList[index]; }
set
{
InnerList[index] = value;
Update(index);
}
}
#endregion
}
If you are experiencing a similar issue, please ask a related question
Join the community of 500,000 technology professionals and ask your questions.