読者です 読者をやめる 読者になる 読者になる

Python3.5.2でRPGを制作する ~ダイクストラアルゴリズムが快速になったよ編~

python プログラミング

ダイクストラアルゴリズムの速度が遅い原因が分かった。私が大変、大変参考にしている

http://notame.hatenablog.com/entry/dijkstras-algorithm-sample

のブログ様曰く、

-このアルゴリズムでポイントとなる点は、調べるセルに既にスコアが入っていた場合の処理です。スコアが入っていた場合、これから入れるべきスコアの方が低かった*2場合のみ、値を更新しセルの連結も変更します。そのようにすることで、すべてのセルに対する最短距離が求まっていくわけですね。

「セルの連結..俺確かリストで表現してたよな。どこに書いてたっけ?」

いや、その処理やってねえ!

そしてそして、興奮も冷めやらぬうちに処理を記述してみると!

めっちゃ早い!検証するとかそんなレベルじゃ無く、一瞬で終わるようになった!

試しにMAPを15 * 50にしてみると、やはり一瞬で終わるようになった。いやあ快適だ。もう半分諦めていたので、素晴らしい日になった!

ただ、限界は有るようで、128 * 128とかのサイズにするとカクつくようになった(それでも体感的には神速なんだけどね~;;

ただ、これはアルゴリズムの限界な気がする。A*法とかだともっと早いのかな?今後、機会があれば挑戦してみたいと思う。

ううむ。うきうき気分で祝杯を上げている(濃いカルピスで

続いてはゲーム内経済の導入に挑戦したい。といっても、NPCが動いてくれているので、後は肉付けしていくだけなんだけどね。

明日も頑張ろー!