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

31

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?

pengguna2499946
sumber
2
Apakah Anda tahu ubin mana yang tidak bisa dilewati atau Anda tahu itu sebagai hasil dari algoritma AStar?
user000user
Bagaimana Anda menyimpan grafik navigasi Anda?
Anko
Jika Anda menyimpan node yang dilalui dalam daftar, Anda mungkin ingin menggunakan tumpukan biner untuk meningkatkan kecepatan.
ChrisC
Jika terlalu lambat saya memiliki serangkaian optimisasi untuk disarankan - atau apakah Anda mencoba untuk menghindari pencarian sama sekali?
Steven
1
Pertanyaan ini mungkin lebih cocok untuk Ilmu Komputer .
Raphael

Jawaban:

45

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.

Steven
sumber
Jika ada agen yang berbeda dengan aturan yang berbeda, tetapi tidak terlalu banyak, ini masih dapat digeneralisasi dengan cukup efisien dengan menggunakan vektor ID, satu per kelas agen.
MSalters
4
+1 Untuk mengetahui bahwa masalah ini kemungkinan adalah area yang dicegah (bukan hanya ubin yang tidak bisa dilewati), dan bahwa masalah seperti ini dapat diselesaikan dengan lebih mudah dengan perhitungan waktu muat awal.
Slipp D. Thompson
Isi banjir atau BFS setiap area.
wolfdawn
ID Pulau tidak harus statis. Ada algoritma sederhana yang cocok jika ada kebutuhan untuk dapat bergabung dengan dua pulau yang terpisah, tetapi tidak dapat membagi pulau setelahnya. Halaman 8 hingga 20 dalam slide ini menjelaskan algoritma tertentu: cs.columbia.edu/~bert/courses/3137/Lecture22.pdf
kasperd
@kasperd tentu saja tidak ada yang mencegah id pulau dihitung ulang, digabung saat runtime. Intinya adalah bahwa id pulau memungkinkan Anda untuk mengkonfirmasi jika ada jalur antara dua node dengan cepat tanpa melakukan pencarian astar.
Steven
26

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.

mklingen
sumber
13
Saya ingin menunjukkan bahwa mengubah mekanisme gim Anda tergantung pada kecepatan CPU (ya, pencarian rute adalah gim mekanik) mungkin berubah menjadi ide yang buruk karena dapat membuat gim ini sangat tidak dapat diprediksi dan dalam beberapa kasus bahkan tidak dapat dimainkan di komputer 10 tahun dari sekarang. Jadi saya lebih suka merekomendasikan untuk membatasi A * dengan membatasi set terbuka daripada oleh waktu CPU.
Philipp
@ Pilip. Dimodifikasi jawaban untuk mencerminkan ini.
mklingen
1
Perhatikan bahwa Anda dapat menentukan (cukup efisien, O (node)) untuk grafik yang diberikan jarak maksimum antara dua node. Ini adalah masalah jalur terpanjang , dan ini memberi Anda batas atas yang benar untuk jumlah node yang akan diperiksa.
MSalters
2
@MSalters Bagaimana Anda melakukan ini di O (n)? Dan apa yang 'cukup efisien'? Jika ini hanya untuk pasangan node, bukankah Anda hanya menduplikasi pekerjaan?
Steven
Menurut Wikipedia, masalah jalur terpanjang adalah NP-hard, sayangnya.
Desty
21
  1. 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.

Stephane Hockenhull
sumber
2
Ada lebih banyak untuk menerapkan pencarian A-star dua arah daripada yang tersirat oleh pernyataan Anda, termasuk memverifikasi bahwa heuristik tetap diterima dalam keadaan ini. (Tautan: homepages.dcc.ufmg.br/
~ chaimo/public/ENIA11.pdf
4
@StephaneHockenhull: Setelah menerapkan Bidirectional A- * pada peta medan dengan biaya asimetris, saya yakinkan Anda bahwa mengabaikan bla-bla akademik akan menghasilkan pemilihan jalur yang salah dan perhitungan biaya yang salah.
Pieter Geerkens
1
@ MoingDuck: Jumlah total node tidak berubah, dan setiap node hanya akan dikunjungi sekali, jadi kasus terburuk dari peta yang terbelah dua persis identik dengan A- * searah.
Pieter Geerkens
1
@PieterGeerkens: Dalam A * klasik, hanya setengah dari simpul yang dapat dijangkau, dan dengan demikian dikunjungi. Jika peta terbelah dua persis, maka ketika Anda mencari dua arah, Anda menyentuh (hampir) setiap node. Pasti kasus tepi
Mooing Duck
1
@MooingDuck: I mis-spoke; the worst cases are different graphs, but have the same behaviour - worst case for unidirectional is a completely isolated goal-node, requiring that all nodes be visited.
Pieter Geerkens
12

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.

ClassicThunder
sumber
6
This is good. By grouping tiles into "regions" and first checking if the region your tile is in can be connected to the region the other tile is in, you can throw away negatives much faster.
Konerak
2
Correct - generally falls under HPA*
Steven
@Steven Thanks I was sure I wasn't the first person to think of such an approach but didn't know what it was called. Makes taking advantage of preexisting research much easier.
ClassicThunder
3

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.

Cort Ammon - Reinstate Monica
sumber
I have reason to believe algorithms like those for Google Maps operate in a similar (though more advanced) manner.
Cort Ammon - Reinstate Monica
Wrong. A* is very much aware of topology, via the choice of admissable heuristic.
MSalters
Re Google, at my previous job we analyzed the performance of Google Maps and found that it couldn't have been A*. We believe they use ArcFlags or other similar algorithms that rely on map preprocessing.
MSalters
@MSalters: That's an interesting fine line to draw. I argue A* is unaware of topology because it only concerns itself with nearest neighbors. I would argue that it is more fair to word that the algorithm generating the admissible heuristic is aware of the topology, rather than A* itself. Consider a case where there is a diamond. A* takes one path for a bit, before backing up to try the other side of the diamond. There is no way to notify A* that the only "exit" from that branch is through an already visited node (saving computation) with the heuristic.
Cort Ammon - Reinstate Monica
1
Can't speak for Google Maps, but Bing Map uses Parallel Bidirectional A-star with Landmarks and Triangle Inequality (ALT), with pre-computed distances from (and to) a small number of landmarks and every node.
Pieter Geerkens
2

Some more ideas in addition to the answers above:

  1. 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.

  2. 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*.

user55564
sumber
1

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.

Madmenyo
sumber
This is exactly what I was suggesting with an area ID in my answer.
Steven
You could also reduce the amount of CPU/time used if your map is dynamic, but doesn't change often. I.e. you could re-calculate area IDs whenever a locked door is unlocked or locked. Since that usually happens in response to a player's actions, you'd at least exclude locked areas of a dungeon.
uliwitness
1

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.

Superbest
sumber
0

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.

aaaaaaaaaaaa
sumber
This is even slower if the unreachable tiles outnumber the reachable tiles
Mooing Duck
1
@MooingDuck The connected unreachable tiles you mean. This is a solution that works with pretty much any sane map design, and it is very easy to implement. I'm not going to suggest anything fancier without better knowledge of the exact problem, like how the A* implementation can be so slow that visiting all the tiles is actually a problem.
aaaaaaaaaaaa
0

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.

ent
sumber
The point was to be faster than regular A*.
Heckel
0

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');
Kromster says support Monica
sumber
0

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.

wolfdawn
sumber
I'm not sure I understand this part "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" Can you explain how did you come to the 10k number please?
Kromster says support Monica
What exactly do you mean by "lazy BFS that prefers nodes closer to the target"? Do you mean Dijkstra, plain BFS, or one with a heuristic (well you've recreated A* here, or how do you select the next best node out of an open set)? That log|V| in A*'s complexity really comes from maintaining that open-set, or the size of the fringe, and for grid maps it's extremely small - about log(sqrt(|V|)) using your notation. The log|V| only shows up in hyper-connected graphs. This is an example where naive application of worst-case complexity gives an incorrect conclusion.
congusbongus
@congusbongus This is exactly what I mean. Do not use a vanilla implementation of A*
wolfdawn
@KromStern Assuming you use the vanilla implementation of A* for a tile based game, you get V * logV complexity, V being the number of tiles, for a grid of 32 by 32 it's 1024. logV, being well approximately the number of bits needed to represent 1024 which is 10. So you end up running for a longer time needlessly. Of course, if you specialize the implementation to take advantage of the fact you are running on a grid of tiles, you overcome this limitation which is exactly what I was referring to
wolfdawn