Küp Yüzeyinde Bir Yıldız Yol Bulma Algoritması Sezgisel

Question

Bir küpün yüzeyinde oynayan bir snake game yapıyorum. Şu anda Dijkstra'nın yol bulma için algoritmasını kullanıyor. Set ve öncelik sıra veri yapıları ile optimizasyonlara rağmen, hala biraz yavaş. Yılan bir yiyecek maddesi yediğinde ve yeni bir tane aramaya başladığında gecikmeyi farkediyorsunuz.

Bunun yerine A * kullanmaya çalışıyorum ama iyi bir buluşsal bulamıyorum. 4 yön hareketi olan düz bir ızgarada, Manhattan mesafesini kullanırdım. İyi bir nedenden ötürü işe yaramayan 3D Manhattan mesafesini abs(dx) + abs(dy) + abs(dz) kullanmayı denedim: yılana, oyun dünyası olağandışı bir sarmalayıcı özellikleri olan 6 grids (corresponding to the faces of the cube).

Kodda, her kare bir grid[15][15] 2D dizisinde saklanır. Her yüzü saklamak için 6 dizi vardır. Dolayısıyla, her bir karenin 2B dizisindeki ofseti tanımlamak ve hangi diziyi belirtmek için (arrayX, arrayY, d) üçlüsü vardır. Ayrıca, her bir kare, uzamsal konumunu açıklayan bir (x, y, z) üçlüsüne sahiptir. İşte

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

A * için kütüphane kod:: İşte

pathfinding olur oyun kodunun alandır

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60 uygun, kısa ve öz sezgisel bunun için ne

oyun Dünyası?

Answer 1

Bunu çözmenin bir yolu, bir besin maddesini alır almaz tüm yol haritasını yapmak yerine, yılanın bir sonraki gıda maddesine sahip olan tarafa doğru hareket etmesini ve daha sonra bu tarafta olmasını sağlamaktır. Gıda maddesini almak için temel bir 2D ızgara A * algoritması kullanın. Başka bir deyişle:

yılan küp yeni tarafa bir gıda maddesini veya hamle kapar zaman

, aşağıdakileri yapın: gıda maddesini geçerli küp tarafında ise

• , bir yol bulmak 2D Manhattan uzaklığı sezgisel
• ile A * algoritmasını kullanarak, gıda öğesi küpün bitişik tarafındaysa, aynı yol bulma algoritmasını kullanarak küpün kenarını geçerli tarafa ve hedef tarafa sınırlayan bir yol bulun. .
• Yiyecek maddesi küpün diğer tarafındaysa, aynı yol bulma algoritmasına sahip geçerli tarafın yolunu bulun.

Bu en kısa genel yolu garanti değil, ama genellikle kısa yoluna yakın olmalıdır ve birden çok aşamadan içine pathfinding böler ve her bir aşama için daha verimli bir algoritma kullanır çünkü daha hızlı olmalıdır.