整理硬盘的时候，发现我早些年写的A星寻路算法。特放上来，待有缘人拿去，无递归噢，性能那是杠杠的。
码上伺候
public class Node
{
public int X
{
get;
set;
} public int Y
{
get;
set;
} public int G
{
get;
set;
} public int H
{
get;
set;
} public int F
{
get;
set;
} public Node parentNode
{
get;
set;
} public Node(int x, int y, Node parent)
{
this.X = x;
this.Y = y;
this.parentNode = parent;
}
}
Node
public class AStar
{
private int[,] map;
private List<Node> openList;
private List<Node> closeList;
private const int COST_STRAIGHT = ;
private const int COST_DIAGONAL = ;
private int row;
private int column; public AStar(int[,] map, int row, int column)
{
this.map = map;
this.row = row;
this.column = column;
openList = new List<Node>();
closeList = new List<Node>();
} //查找坐标
public int Search(int x1, int y1, int x2, int y2)
{
if (x1 < || x1 >= row || x2 < || x2 >= row || y1 < || y1 >= column || y2 < || y2 >= column)
{
return -;
} if (map[x1,y1] == || map[x2,y2] == )
{
return -;
} Node start = new Node(x1, y1, null);
Node end = new Node(x2, y2, null);
openList.Add(start);
List<Node> resultList = Search(start, end);
if (resultList.Count == )
{
return ;
} foreach (Node node in resultList)
{
map[node.X,node.Y] = -;
} return ;
} private List<Node> Search(Node start, Node end)
{
List<Node> result = new List<Node>();
bool isFind = false;
Node node = null;
openList.Sort(new NodeComparator()); while (openList.Count > )
{
node = openList[];
if (node.X == end.X && node.Y == end.Y)
{
isFind = true;
break;
}
//上
if ((node.Y - ) >= )
{
CheckPath(node.X, node.Y - , node, end, COST_STRAIGHT);
}
//下
if ((node.Y + ) < column)
{
CheckPath(node.X, node.Y + , node, end, COST_STRAIGHT);
}
//左
if ((node.X - ) >= )
{
CheckPath(node.X - , node.Y, node, end, COST_STRAIGHT);
}
//右
if ((node.X + ) < row)
{
CheckPath(node.X + , node.Y, node, end, COST_STRAIGHT);
}
//左上
if ((node.X - ) >= && (node.Y - ) >= )
{
CheckPath(node.X - , node.Y - , node, end, COST_DIAGONAL);
}
//左下
if ((node.X - ) >= && (node.Y + ) < column)
{
CheckPath(node.X - , node.Y + , node, end, COST_DIAGONAL);
}
//右上
if ((node.X + ) < row && (node.Y - ) >= )
{
CheckPath(node.X + , node.Y - , node, end, COST_DIAGONAL);
}
//右下
if ((node.X + ) < row && (node.Y + ) < column)
{
CheckPath(node.X + , node.Y + , node, end, COST_DIAGONAL);
} openList.Remove(node);
closeList.Add(node);
}
if (isFind) {
GetPath(result, node);
} return result;
} private bool CheckPath(int x, int y, Node parentNode, Node end, int cost)
{
Node node = new Node(x, y, parentNode);
if (map[x,y] == )
{
closeList.Add(node);
return false;
}
if (IsListContains(closeList, x, y) != -)
{
return false;
}
int index = -;
if ((index = IsListContains(openList, x, y)) != -)
{
if ((parentNode.G + cost) < openList[index].G)
{
node.parentNode = parentNode;
CountG(node, cost);
CountF(node);
openList[index] = node;
}
}
else {
node.parentNode = parentNode;
Count(node, end, cost);
openList.Add(node);
} return true;
} private int IsListContains(List<Node> list, int x, int y)
{
int i = ;
foreach (Node node in list)
{
if (node.X == x && node.Y == y)
{
return i;
}
i += ;
} return -;
} private void GetPath(List<Node> list, Node node)
{
while (node.parentNode != null)
{
list.Add(node);
node = node.parentNode;
} list.Add(node); } private void Count(Node node, Node end, int cost)
{
CountG(node, cost);
CountH(node, end);
CountF(end);
} private void CountG(Node node, int cost)
{
if (node.parentNode == null)
{
node.G = cost;
}
else
node.G = node.parentNode.G + cost;
} private void CountH(Node node, Node end)
{
node.H = Math.Abs(node.X - end.X) + Math.Abs(node.Y - end.Y);
} private void CountF(Node node)
{
node.F = node.G + node.H;
}
}
AStar
class Program
{
delegate void FuncDelegate(); static void Measure(FuncDelegate func, string funcName)
{
Stopwatch sw = new Stopwatch();
sw.Start();
func();
sw.Stop();
Console.WriteLine(" {0} used {1} ms", funcName, sw.ElapsedMilliseconds);
} static void DrawTheMap(int[,] map)
{
for (int x = ; x < ; x++)
{
for (int y = ; y < ; y++)
{
if (map[x, y] == )
{
Console.Write("□");
}
else if (map[x, y] == )
{
Console.Write("■");
}
else if (map[x, y] == -)
{
Console.Write("※");
}
}
Console.WriteLine("");
}
} static void AstarAlgorim()
{
int[,] map = new int[,] {
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
}; AStar star = new AStar(map, , );
int flag = star.Search(, , , );
if (flag == -)
{
Console.WriteLine("传输数据有误!");
}
else if (flag == )
{
Console.WriteLine("没有找到!");
}
else
{
DrawTheMap(map);
}
} static void Main(string[] args)
{
Measure(AstarAlgorim, "A星寻路"); Console.ReadLine();
}
}
Program