A*アルゴリズムのActionscript 3.0インスタンス
2031 ワード
【実例提示】
ステップごとの効果を見るために、毎秒のフレーム数を6に設定し、物体の移動速度を遅くします.効果は上記の通りです.本来A*アルゴリズムのコアアルゴリズムは複雑ではありませんが、実現されたコードは想像以上に多く、細部を一つ一つテストできず、DEMOを置いて、後で使います.また、各段階をデバッグしてみましょう.実は電子書籍にA*の例がありますが、コードを叩いたときに気づいたのですが、カップは......!
A*アルゴリズムの資料については、参考にすることができます
A*寻路初探GameDev.net( http://data.gameres.com/message.asp?TopicID=25439 )
【A*メソッドまとめ】
パスの中でどの四角形を通るかを選択する鍵は、次の式です.
F = G + H
ここで,*G=始点Aから,生成された経路に沿ってメッシュ上の指定された格子に移動する移動には費用がかかる.*H=メッシュ上のその格子から終点Bへの移動の見積り移動に費やす.これはよく啓発的と呼ばれ、少し迷うかもしれません.そう呼ばれたのは推測にすぎないからだ.道の長さを事前に知ることはできません.道にはいろいろな障害(壁、水など)があるかもしれません.本稿ではHを計算する方法は1つしか提供されていませんが、ネット上で他の多くの方法を見つけることができます.
各ステップの操作を一緒に書きましょう.
1、オープンリストに開始格を追加します.2,次の作業を繰り返す:a)オープンリストでF値が最も低い格子を探す.現在のグリッドと呼ばれています.b)リストを閉じるまで切り替える.c)隣接する8格子のそれぞれに対して?*パスできない場合、またはリストを閉じている場合は省略します.逆に次のようになります.*オープンリストにない場合は、追加します.現在のグリッドをこのグリッドの親ノードとします.このグリッドのF,G,およびH値を記録します.*すでにオープンリストにある場合は、G値を参照して新しいパスがより良いかどうかを確認します.より低いG値は、より良いパスを意味します.もしそうであれば、このグリッドの親ノードを現在のグリッドに変更し、このグリッドのGとF値を再計算します.オープンリストをF値で並べ替える場合は、変更後にオープンリストを並べ替える必要がある場合があります.(プログラムではこの手順を省略します)
d)停止し、*がオープンリストにターゲットグリッドを追加すると、パスが見つかったり、*がターゲットグリッドが見つからなかったりして、オープンリストが空になります.この場合、パスは存在しません. 3.パスを保存します.ターゲット・グリッドから開始し、各グリッドの親ノードに沿って開始グリッドに戻るまで移動します.これがあなたの道です.
【ダミーコード】
基本的にA*のアルゴリズムは次の疑似コードに集中していますが、具体的に実現するには多くの工夫が必要です.
参考資料:
『ゲーム中の人工知能』
GameRes http://gameres.com/
「ActionScript 3.0ゲーム開発例」という本は、A*アルゴリズムについての説明が非常にいい加減で、長い間読んでいましたが、仕方がありませんでした.しかし、コードの例はいいですね.
ステップごとの効果を見るために、毎秒のフレーム数を6に設定し、物体の移動速度を遅くします.効果は上記の通りです.本来A*アルゴリズムのコアアルゴリズムは複雑ではありませんが、実現されたコードは想像以上に多く、細部を一つ一つテストできず、DEMOを置いて、後で使います.また、各段階をデバッグしてみましょう.実は電子書籍にA*の例がありますが、コードを叩いたときに気づいたのですが、カップは......!
A*アルゴリズムの資料については、参考にすることができます
A*寻路初探GameDev.net( http://data.gameres.com/message.asp?TopicID=25439 )
【A*メソッドまとめ】
パスの中でどの四角形を通るかを選択する鍵は、次の式です.
F = G + H
ここで,*G=始点Aから,生成された経路に沿ってメッシュ上の指定された格子に移動する移動には費用がかかる.*H=メッシュ上のその格子から終点Bへの移動の見積り移動に費やす.これはよく啓発的と呼ばれ、少し迷うかもしれません.そう呼ばれたのは推測にすぎないからだ.道の長さを事前に知ることはできません.道にはいろいろな障害(壁、水など)があるかもしれません.本稿ではHを計算する方法は1つしか提供されていませんが、ネット上で他の多くの方法を見つけることができます.
各ステップの操作を一緒に書きましょう.
1、オープンリストに開始格を追加します.2,次の作業を繰り返す:a)オープンリストでF値が最も低い格子を探す.現在のグリッドと呼ばれています.b)リストを閉じるまで切り替える.c)隣接する8格子のそれぞれに対して?*パスできない場合、またはリストを閉じている場合は省略します.逆に次のようになります.*オープンリストにない場合は、追加します.現在のグリッドをこのグリッドの親ノードとします.このグリッドのF,G,およびH値を記録します.*すでにオープンリストにある場合は、G値を参照して新しいパスがより良いかどうかを確認します.より低いG値は、より良いパスを意味します.もしそうであれば、このグリッドの親ノードを現在のグリッドに変更し、このグリッドのGとF値を再計算します.オープンリストをF値で並べ替える場合は、変更後にオープンリストを並べ替える必要がある場合があります.(プログラムではこの手順を省略します)
d)停止し、*がオープンリストにターゲットグリッドを追加すると、パスが見つかったり、*がターゲットグリッドが見つからなかったりして、オープンリストが空になります.この場合、パスは存在しません. 3.パスを保存します.ターゲット・グリッドから開始し、各グリッドの親ノードに沿って開始グリッドに戻るまで移動します.これがあなたの道です.
【ダミーコード】
基本的にA*のアルゴリズムは次の疑似コードに集中していますが、具体的に実現するには多くの工夫が必要です.
openlist
while openlist {
=openlist
if == then
else
closelist
for
if openlist
and
and closed List
and
openlist
}
参考資料:
『ゲーム中の人工知能』
GameRes http://gameres.com/
「ActionScript 3.0ゲーム開発例」という本は、A*アルゴリズムについての説明が非常にいい加減で、長い間読んでいましたが、仕方がありませんでした.しかし、コードの例はいいですね.