Bagaimana saya bisa membuat A * selesai lebih cepat ketika tujuan tidak bisa dilewati?

Saya membuat game 2D berbasis ubin sederhana, yang menggunakan algoritma pathfinding A * ("A star"). Saya sudah bekerja dengan baik, tetapi saya memiliki masalah kinerja dengan pencarian. Sederhananya, ketika saya mengklik ubin yang tidak bisa dilewati, algoritme tampaknya menelusuri seluruh peta untuk menemukan rute ke ubin yang tidak bisa dilewati — bahkan jika saya berdiri di sebelahnya.

Bagaimana saya bisa menghindari ini? Saya kira saya bisa mengurangi pathfinding ke area layar, tapi mungkin saya kehilangan sesuatu yang jelas di sini?

Beberapa gagasan untuk menghindari pencarian yang menghasilkan jalur yang gagal sama sekali:

ID Pulau

Salah satu cara termurah untuk menyelesaikan pencarian A * secara lebih cepat adalah dengan tidak melakukan pencarian sama sekali. Jika area tersebut benar-benar tidak mungkin dilewati oleh semua agen, banjir memenuhi setiap area dengan ID Pulau yang unik pada muatan (atau dalam pipa). Ketika merintis jalan, periksa apakah ID Pulau asal jalur cocok dengan ID Pulau tujuan. Jika mereka tidak cocok tidak ada gunanya melakukan pencarian - kedua titik berada di pulau yang berbeda dan tidak terhubung. Ini hanya membantu jika ada simpul yang benar-benar tidak bisa dilewati untuk semua agen.

Batasi batas atas

Saya membatasi batas atas jumlah maksimum node yang dapat dicari. Ini membantu pencarian yang tidak dapat dilewati untuk berjalan selamanya, tetapi itu berarti beberapa pencarian yang lumayan lama dapat hilang. Nomor ini perlu disetel, dan itu tidak benar-benar menyelesaikan masalah, tetapi mengurangi biaya yang terkait dengan pencarian panjang.

Jika yang Anda temukan adalah terlalu lama maka teknik-teknik berikut berguna:

Jadikan Asinkron & Batasi Iterasi

Biarkan pencarian berjalan di utas terpisah atau sedikit setiap frame sehingga permainan tidak berhenti menunggu pencarian. Tampilkan animasi karakter menggaruk kepala atau menginjak-injak kaki, atau apa pun yang sesuai sambil menunggu pencarian berakhir. Untuk melakukan ini secara efektif, saya akan menjaga Negara pencarian sebagai objek terpisah dan memungkinkan beberapa negara ada. Ketika jalur diminta, ambil objek status bebas dan tambahkan ke antrian objek status aktif. Dalam pembaruan penelusuran jalan Anda, tarik item aktif dari depan antrian dan jalankan A * hingga A. selesai atau B. beberapa batas iterasi dijalankan. Jika selesai, masukkan kembali objek state ke daftar objek state bebas. Jika belum selesai, letakkan di akhir 'pencarian aktif' dan pindah ke yang berikutnya.

Pilih Struktur Data yang Tepat

Pastikan Anda menggunakan struktur data yang tepat. Inilah cara kerja StateObject saya. Semua node saya sudah dialokasikan sebelumnya ke nomor yang terbatas - misalnya 1024 atau 2048 - untuk alasan kinerja. Saya menggunakan kumpulan node yang mempercepat alokasi node dan juga memungkinkan saya untuk menyimpan indeks, bukan pointer dalam struktur data saya yang u16s (atau u8 jika saya memiliki 255 max node, yang saya lakukan pada beberapa game). Untuk pathfinding saya, saya menggunakan antrian prioritas untuk daftar terbuka, menyimpan pointer ke objek Node. Ini diimplementasikan sebagai tumpukan biner, dan saya mengurutkan nilai floating point sebagai bilangan bulat karena selalu positif dan platform saya memiliki perbandingan floating point yang lambat. Saya menggunakan hashtable untuk peta tertutup saya untuk melacak node yang saya kunjungi. Ini menyimpan NodeID, bukan Node, untuk menghemat ukuran cache.

Cache What You Can

Ketika Anda pertama kali mengunjungi sebuah node dan menghitung jarak ke tujuan, cache itu di node yang disimpan di Object Negara. Jika Anda mengunjungi kembali simpul tersebut gunakan hasil cache bukannya menghitungnya lagi. Dalam kasus saya ini membantu tidak harus melakukan root kuadrat pada node yang telah ditinjau. Anda mungkin menemukan ada nilai-nilai lain yang dapat Anda prakalkulasi dan cache.

Area lebih lanjut yang dapat Anda selidiki: gunakan pencarian jalur dua arah untuk mencari dari kedua ujungnya. Saya belum melakukan ini tetapi karena orang lain telah mencatat ini mungkin membantu, tetapi bukan tanpa peringatan itu. Hal lain dalam daftar saya untuk dicoba adalah pencarian jalan hierarkis, atau pencarian jalur pengelompokan. Ada deskripsi menarik dalam dokumentasi HavokAI Here yang menjelaskan konsep pengelompokan mereka, yang berbeda dari implementasi HPA * yang dijelaskan di sini .

Semoga beruntung, dan beri tahu kami apa yang Anda temukan.

AStar adalah algoritma perencanaan yang lengkap , artinya jika ada jalur ke node, AStar dijamin akan menemukannya. Akibatnya, ia harus memeriksa setiap jalur keluar dari simpul awal sebelum dapat memutuskan bahwa simpul tujuan tidak dapat dijangkau. Ini sangat tidak diinginkan ketika Anda memiliki terlalu banyak node.

Cara untuk mengurangi ini:

• Jika Anda mengetahui apriori bahwa suatu simpul tidak dapat dijangkau (mis. Ia tidak memiliki tetangga atau ditandai UnPassable), kembalilah No Pathtanpa pernah memanggil AStar.

• Batasi jumlah node yang akan diperluas AStar sebelum diakhiri. Periksa set terbuka. Jika terlalu besar, akhiri dan kembali No Path. Namun, ini akan membatasi kelengkapan AStar; sehingga hanya dapat merencanakan jalur dengan panjang maksimal.

• Batasi waktu yang dibutuhkan AStar untuk menemukan jalan. Jika kehabisan waktu, keluar dan kembali No Path. Ini membatasi kelengkapan seperti strategi sebelumnya, tetapi timbangan dengan kecepatan komputer. Perhatikan bahwa untuk banyak permainan ini tidak diinginkan, karena pemain dengan komputer yang lebih cepat atau lebih lambat akan mengalami permainan secara berbeda.

4. Jalankan pencarian A * ganda dari node target secara terbalik juga pada saat yang sama dalam loop yang sama dan batalkan kedua pencarian segera setelah satu ditemukan tidak dapat dipecahkan

Jika target hanya memiliki 6 petak yang dapat diakses di sekitarnya dan sumber asli memiliki 1002 petak yang dapat diakses, pencarian akan berhenti pada 6 (dua) iterasi.

Segera setelah satu pencarian menemukan node lain yang dikunjungi, Anda juga dapat membatasi ruang lingkup pencarian untuk node lain yang dikunjungi dan menyelesaikan lebih cepat.

Assuming the issue is the destination is unreachable. And that the navigation mesh isn't dynamic. The easiest way to do this is have a much sparser navigation graph (sparse enough that a full run through is relatively quick) and only use the detailed graph if the pathing is possible.

Use multiple algorithms with different characteristics

A* has some fine characteristics. In particular, it always finds the shortest path, if one exist. Unfortunately, you have found some bad characteristics as well. In this case, it must exhaustively search for all possible paths before admitting no solution exists.

The "flaw" you are discovering in A* is that it is unaware of topology. You may have a 2-D world, but it doesn't know this. For all it knows, in the far corner of your world is a staircase which brings it right under the world to its destination.

Consider creating a second algorithm which is aware of topology. As a first pass, you might fill the world with "nodes" every 10 or 100 spaces, and then maintain a graph of connectivity between these nodes. This algorithm would pathfind by finding accessable nodes near the start and end, then trying to find a path between them on the graph, if one exists.

One easy way to do this would be to assign each tile to a node. It is trivial to show that you only need to assign one node to each tile (you can never have access to two nodes which are not connected in the graph). Then the graph edges are defined to be anywhere two tiles with different nodes are adjacent.

This graph has a disadvantage: it does not find the optimum path. It merely finds a path. However, it has now shown you that A* can find an optimum path.

It also provides a heuristic to improve your underestimates needed to make A* function, because you now know more about your landscape. You are less likely to have to fully explore a dead end before finding out that you needed to step back to go forward.

Some more ideas in addition to the answers above:

6. Cache results of A* search. Save the path data from cell A to cell B and reuse if possible. This is more applicable in static maps and you will have to do more work with dynamic maps.

7. Cache the neighbours of each cell. A* implementation need to expand each node and add its neighbours to the open set to search. If this neighbours is calculated each time rather than cached then it could dramatically slow down the search. And if you havnt already done so, use a priority queue for A*.

If your map is static you can just have each separate section have there own code and check this first before running A*. This can be done upon map creation or even coded in the map.

Impassable tiles should have a flag and when moving to a tile like that you could opt not to run A* or pick a tile next to it that is reachable.

If you have dynamic maps that change frequently you are pretty much out of luck. You have to way your decision making your algorithm stop before completion or do checks on sections get closed off frequently.

How can I make A* more quickly conclude that a node is impassable?

Profile your Node.IsPassable() function, figure out the slowest parts, speed them up.

When deciding whether a node is passable, put the most likely situations at the top, so that most of the time the function returns right away without bothering to check the more obscure possibilities.

But this is for making it faster to check a single node. You can profile to see how much time is spent on querying nodes, but sounds like your problem is that too many nodes are being checked.

when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile

If the destination tile itself is impassable, the algorithm shouldn't check any tiles at all. Before even starting to do pathfinding, it should query the destination tile to check if it's possible, and if not, return a no path result.

If you mean that the destination itself is passable, but is encircled by impassable tiles, such that there is no path, then it is normal for A* to check the whole map. How else would it know there's no path?

If the latter is the case, you can speed it up by doing a bidirectional search - that way the search starting from the destination can quickly find that there is no path and stop the search. See this example, surround the destination with walls and compare bidirectional vs. single direction.

Do the path-finding backwards.

If only your map doesn't have big continuous areas of unreachable tiles then this will work. Rather than searching the entire reachable map, the path-finding will only search the enclosed unreachable area.

If the areas that the player are connected (no teleports etc.) and the unreachable areas are generally not very well connected, you can simply do the A* starting from the node you want to reach. That way you can still find any possible route to the destination and A* will stop searching quickly for unreachable areas.

when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile — even if I'm standing next to it.

Other answers are great, but I have to point at the obvious - You should not run the pathfinding to an impassable tile at all.

This should be an early exit from the algo:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');

To check for the longest distance in a graph between two nodes:

(assuming all edges have the same weight)

1. Run BFS from any vertex v.
2. Use the results to select a vertex furthest away from v, we'll call it d.
3. Run BFS from u.
4. Find the vertex furthest away from u,we'll call it w.
5. The distance between u and w is the longest distance in the graph.

Proof:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)

• Lets say the distance between y and x is greater!
• Then according to this D2 + R < D3
• Then D2 < R + D3
• Then the distance between v and x is greater than that of v and u?
• Then u wouldn't have been picked in the first phase.

Credit to prof. Shlomi Rubinstein

If you are using weighted edges, you can accomplish the same thing in polynomial time by running Dijkstra instead of BFS to find the furthest vertex.

Please note I'm assuming it's a connected graph. I am also assuming it's undirected.

A* is not really useful for a simple 2d tile based game because if I understand correctly, assuming the creatures move in 4 directions, BFS will achieve the same results. Even if creatures can move in 8 directions, lazy BFS that prefers nodes closer to the target will still achieve the same results. A* is a modification Dijkstra which is far more computationally expensive then using BFS.

BFS = O(|V|) supposedly O(|V| + |E|) but not really in the case of a top down map. A* = O(|V|log|V|)

If we have a map with just 32 x 32 tiles, BFS will cost at most 1024 and a true A* could cost you a whopping 10,000. This is the difference between 0.5 seconds and 5 seconds, possibly more if you take the cache into account. So make sure your A* behaves like a lazy BFS that prefers tiles that are closer to the desired target.

A* is useful for navigation maps were the cost of edges is important in the decision making process. In a simple overhead tile based games, the cost of edges is probably not an important consideration. Event if it is, (different tiles cost differently), you can run a modified version of BFS that postpones and penalizes paths that pass through tiles that slow the character down.

So yeah BFS > A* in many cases when it comes to tiles.