A*算法实践

参考了 http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html

代码比较简单，也没有对选取opens里最小的元素进行速度优化，比如用heap

close状态直接记录在了cells数组里，好像更方便

List<DataCell> opens = new List<DataCell>(); //开放列表


DataCell start = cells[15];
DataCell end = cells[99];
start.color = Color.Gold;
end.color = Color.Lime;
opens.Add(start);
for (int i = 0; i < 100; i++)//把所有h初始化掉

{
cells[i].h = (int)Math.Sqrt((cells[i].x - end.x) * (cells[i].x - end.x) + (cells[i].y - end.y) * (cells[i].y - end.y));
}

while (opens.Count > 0)
{
int minindex = 0;
for (int i = 1; i < opens.Count; i++)//找出最小f的节点

{
    if (opens[i].f < opens[minindex].f)
    {
    minindex = i;
    }
}
opens[minindex].fin = true;
int cellid = opens[minindex].id;
int hplus = opens[minindex].f;
if (opens[minindex].id == end.id)//到达目标，退出

{
    int pid = cells[cellid].parent;
    while (pid != 0)
    {
    cells[pid].color = Color.Red;
    pid = cells[pid].parent;
    }
    break;
}
opens.Remove(opens[minindex]);
for (int i = -1; i < 2; i++) //对周围的8各节点进行扫描

{
    for (int j = -1; j < 2; j++)
    {
    if (i == 0 && j == 0)
    {
     continue;
    }
    if (cellid + j * 10 < 0 || cellid + j * 10 >= 100)
    {
     continue;
    }
    if ((cellid % 10) == 0 && i == -1)
    {
     continue;
    }
    if ((cellid % 10) == 9 && i == 1)
    {
     continue;
    }
    if (!cells[cellid + j * 10 + i].fin && !cells[cellid + j * 10 + i].disable)
    {
     int sid = cellid + j * 10 + i;
     int tempg = (int)Math.Sqrt((cells[sid].x - cells[cellid].x) * (cells[sid].x - cells[cellid].x) + (cells[sid].y - cells[cellid].y) * (cells[sid].y - cells[cellid].y));
     int tempf = tempg + cells[sid].h + hplus;
     if (cells[sid].f == 0 || cells[sid].f > tempf)
     {
        cells[sid].g = tempg;
        cells[sid].f = tempf;
        cells[sid].parent = cellid;
     }
     if (!opens.Contains(cells[sid]))
     {
        opens.Add(cells[sid]);
     }
    }
    }
}