path.cs

A star 算法求解最短路径问题

using System;
using System.Collections;

namespace Path_UProject
{
	/// <summary>
	/// This class implements A*
	/// </summary>
	public class Path : IComparable
	{
		public Path(int gi, int gj)
		{
			p = new ArrayList();
			this.gi=gi;
			this.gj=gj;
		}

		public ArrayList p;
		public int gi;
		public int gj;

		public int CompareTo(Object rhs)
		{
			Path p = (Path) rhs;
			if (this.F()<p.F())
				return -1;
			else if(this.F()>p.F())
				return 1;
			else
				return 0;
		}

		public void AddNode(int i, int j)
		{
            Node n = new Node();
			n.i=i;
			n.j=j;

			p.Add(n);
		}

		public void Extend(ref ArrayList ar, ref int[,] map)
		{
			Node n = (Node)p[p.Count-1];

			Path p1 = new Path(gi,gj);
			Path p2 = new Path(gi,gj);
			Path p3 = new Path(gi,gj);
			Path p4 = new Path(gi,gj);

			p1.p = (ArrayList)this.p.Clone();
			p2.p = (ArrayList)this.p.Clone();
			p3.p = (ArrayList)this.p.Clone();
			p4.p = (ArrayList)this.p.Clone();

			int i=n.i,j=n.j;

			if(n.i>=1)
			{
				Node nn = new Node();
				i--;
				if((map[i,j]!=1))
				{
					nn.i=i;
					nn.j=j;
					p1.p.Add(nn);
					ar.Add(p1);
				}
				i++;
			}

			if(p.Count>=2)
			{
				for(int co=0;co<=p.Count-2;co++)
				{
					Node otl = (Node)p[co];
					i--;
					if((otl.i==i)&&(otl.j==j))
					{
						ar.RemoveAt(ar.Count-1);
					}
					i++;
				}
			}

			if(n.i<=8)
			{
				Node nn = new Node();
				i++;
				if(map[i,j]!=1)
				{
					nn.i=i;
					nn.j=j;
					p2.p.Add(nn);
					ar.Add(p2);
				}
				i--;
			}

			if(p.Count>=2)
			{
				for(int co=0;co<=p.Count-2;co++)
				{
					Node otl = (Node)p[co];
					i++;
					if((otl.i==i)&&(otl.j==j))
					{
						ar.RemoveAt(ar.Count-1);
					}
					i--;
				}
			}
			
			if(n.j>=1)
			{
				Node nn = new Node();
				j--;
				if(map[i,j]!=1)
				{
					nn.i=i;
					nn.j=j;
					p3.p.Add(nn);
					ar.Add(p3);
				}
				j++;
			}

			if(p.Count>=2)
			{
				for(int co=0;co<=p.Count-2;co++)
				{
					Node otl = (Node)p[co];
					j--;
					if((otl.i==i)&&(otl.j==j))
					{
						ar.RemoveAt(ar.Count-1);
					}
					j++;
				}
			}

			if(n.j<=8)
			{
				Node nn = new Node();
				j++;
				if(map[i,j]!=1)
				{
					nn.i=i;
					nn.j=j;
					p4.p.Add(nn);
					ar.Add(p4);
				}
				j--;
			}
			if(p.Count>=2)
			{
				for(int co=0;co<=p.Count-2;co++)
				{
					Node otl = (Node)p[co];
					j++;
					if((otl.i==i)&&(otl.j==j))
					{
						ar.RemoveAt(ar.Count-1);
					}
					i--;
				}
			}

		}

		public int F()
		{
			Node n = (Node)p[p.Count-1];
			return (int)(p.Count+(Math.Abs(gi-n.i)+Math.Abs(gj-n.j))*1);
		}

		public bool Finished()
		{
            Node n = (Node)p[p.Count-1];
			if ((n.i==gi)&&(n.j==gj))
				return true;
			else
				return false;
		}

		public void ReplaceTheBetter(ref ArrayList ar)
		{
			for (int i=0; i<=ar.Count-2; i++)
			{
				Path p1=(Path)ar[i];
				for (int j=i+1; j<=ar.Count-1; j++)
				{
					Path p2=(Path)ar[j];

//					for (int k1=1; k1<=p1.p.Count-1; k1++)
//					{
						Node n1 = (Node)p1.p[p1.p.Count-1];
						for (int k2=0; k2<=p2.p.Count-1; k2++)
						{
							Node n2 = (Node)p2.p[k2];

							if ((n1.i==n2.i)&&(n1.j==n2.j))
							{
								if (p1.p.Count-1>=k2)
								{
									ar.RemoveAt(i);
									return;
								}
								else if (p1.p.Count-1<k2)
								{
									ar.RemoveAt(j);
									return;
								}
							}

						}
//					}
				}
			}
		
		}

	}
}