Wikipedia Algoritma pathfinding A * membutuhkan banyak waktu

Saya telah berhasil mengimplementasikan A * pathfinding di C # tetapi sangat lambat, dan saya tidak mengerti mengapa. Saya bahkan mencoba untuk tidak menyortir daftar openNodes tetapi masih sama.

Peta ini 80x80, dan ada 10-11 node.

Saya mengambil pseudocode dari sini Wikipedia

Dan ini adalah implementasi saya:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; // a) We refer to this as the current square.)

            if (current == mEnd)
            {
                while (current != null)
                {
                    solutionNodes.Add(current);
                    current = current.Parent;
                }

                return solutionNodes;
            }

            openNodes.Remove(current);
            closedNodes.Add(current); // b) Switch it to the closed list.

            List<PGNode> neighborNodes = current.GetNeighborNodes();
            double cost = 0;
            bool isCostBetter = false;

            for (int i = 0; i < neighborNodes.Count; i++)
            {
                PGNode neighbor = neighborNodes[i];
                cost = current.G + 10;
                isCostBetter = false;

                if (neighbor.Passable == false || closedNodes.Contains(neighbor))
                    continue; // If it is not walkable or if it is on the closed list, ignore it.

                if (openNodes.Contains(neighbor) == false)
                {
                    openNodes.Add(neighbor); // If it isn’t on the open list, add it to the open list.
                    isCostBetter = true;
                }
                else if (cost < neighbor.G)
                {
                    isCostBetter = true;
                }

                if (isCostBetter)
                {
                    neighbor.Parent = current; //  Make the current square the parent of this square. 
                    neighbor.G = cost;
                    neighbor.H = GetManhattanHeuristic(current, neighbor);
                }
            }
        }

        return null;
    }

Inilah heuristik yang saya gunakan:

    private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
    {
        return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
    }

Apa yang saya lakukan salah? Ini sepanjang hari saya terus mencari kode yang sama.

Saya melihat tiga hal, satu salah, dua mencurigakan.

1) Anda sedang mengurutkan pada setiap iterasi. Jangan. Baik gunakan antrian prioritas, atau paling tidak lakukan pencarian linier untuk menemukan minimum. Anda sebenarnya tidak perlu seluruh daftar untuk disortir setiap saat!

2) openNodes.Contains () mungkin lambat (tidak yakin tentang spesifikasi Daftar C #, tapi saya yakin itu melakukan pencarian linear). Anda dapat menambahkan flag ke setiap node dan melakukan ini di O (1).

3) GetNeighborNodes () bisa lambat.

Selain poin yang sudah dibuat bahwa Anda harus menggunakan tumpukan prioritas, Anda telah salah memahami heuristik. Kamu punya

if (isCostBetter)
{
    ...
    neighbor.H = GetManhattanHeuristic (saat ini, tetangga);
}

if (openNodes.Contains (neighbor) == false)
{
    neighbor.H = GetHeuristic (tetangga, mEnd);
    ...
}

Dan sebagai titik minor lebih lanjut, Anda dapat menyederhanakan A * dengan memfilter simpul yang tidak dapat dilewati GetNeighbourNodes().

Meta-jawaban: Anda tidak boleh hanya menghabiskan waktu sehari menatap kode mencari masalah kinerja. Lima menit dengan profiler akan menunjukkan dengan tepat di mana letak hambatannya. Anda dapat mengunduh jejak gratis sebagian besar profiler dan menghubungkannya ke aplikasi Anda dalam beberapa menit.

Tidak jelas apa yang Anda bandingkan ketika Anda membandingkan F dari node yang berbeda. Apakah F properti didefinisikan sebagai G + H? Harus. (Kata-kata kasar: Ini adalah contoh mengapa prinsip akses seragam adalah omong kosong.)

Lebih penting lagi, Anda menyortir ulang node setiap frame. A * panggilan untuk penggunaan antrian prioritas , yang memungkinkan efisien - O (lg n) - diurutkan penyisipan elemen tunggal, dan satu set, yang memungkinkan pemeriksaan cepat untuk node tertutup. Saat Anda telah menulis algoritme, Anda memiliki penyisipan + O (n lg n), yang menaikkan run-time ke proporsi yang tidak berguna.

(Anda mungkin mendapatkan O (n) penyisipan + urutkan jika C # memiliki algoritma penyortiran yang baik. Itu masih terlalu banyak. Gunakan antrian prioritas nyata.)

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

• Pada satu ekstrim, jika h (n) adalah 0, maka hanya g (n) yang berperan, dan A * berubah menjadi algoritma Dijkstra, yang dijamin untuk menemukan jalur terpendek.
• Jika h (n) selalu lebih rendah dari (atau sama dengan) biaya pindah dari n ke tujuan, maka A * dijamin untuk menemukan jalur terpendek. Semakin rendah h (n), semakin banyak simpul A * mengembang, membuatnya lebih lambat.
• Jika h (n) persis sama dengan biaya bergerak dari n ke tujuan, maka A * hanya akan mengikuti jalur terbaik dan tidak pernah memperluas apa pun, membuatnya sangat cepat. Meskipun Anda tidak dapat membuat ini terjadi dalam semua kasus, Anda dapat membuatnya tepat dalam beberapa kasus khusus. Sangat menyenangkan mengetahui bahwa dengan informasi yang sempurna, A * akan berperilaku sempurna.
• Jika h (n) kadang-kadang lebih besar daripada biaya bergerak dari n ke tujuan, maka A * tidak dijamin untuk menemukan jalur terpendek, tetapi dapat berjalan lebih cepat.
• Di sisi lain, jika h (n) sangat tinggi relatif terhadap g (n), maka hanya h (n) yang berperan, dan A * berubah menjadi Best-First-Search.

Anda menggunakan 'jarak manhatten'. Ini hampir selalu heuristik yang buruk. Selain itu, dari melihat info itu dari halaman tertaut, Anda dapat menebak bahwa heuristik Anda lebih rendah dari biaya sebenarnya.

Selain jawaban teratas lainnya (yang tidak diragukan lagi lebih penting daripada saran ini), optimasi lain adalah mengubah 'daftar' yang tertutup menjadi semacam tabel hash. Anda tidak perlu menjadi koleksi yang dipesan, hanya untuk dapat dengan cepat menambah nilai dan melihat dengan cepat apakah ada dalam koleksi.

Biaya Anda dan Heuristik Anda perlu memiliki hubungan. Ini harus menjadi petunjuk bahwa H dihitung di dua tempat yang berbeda tetapi tidak pernah diakses.