概要
「ゴール駆動型エージェントの実装（概念編）」の続編です。
こちらでは、前回書いた概念を元に、実際にサンプルプロジェクトで実装した内容を解説していこうと思います。
※ 前回も書きましたが、あくまで書籍を読んで実際に自分が実装したものの解説です。そのため、理論など勘違い・間違いを含んでいる可能性が多分にあるため、あくまで実装の一例として御覧ください。
はじめに
さて、実際に実装について書いていく前に、イメージしやすくするための前提を書こうと思います。
※ まずはコードから読みたいよ！ って人は下に書いてある実装解説から読んでください。
ゴール駆動型はStateパターンに似ている
実際に実装してみて感じたのは、いわゆるデザインパターンで言うところの「Stateパターン」にとても似ているな、ということ。
Stateパターンてなんぞ？ という人はWikipediaなどを参考にしてもらいたいですが、ざっくり言うと、「State（状態）」をひとつのクラスとして定義し、そのインスタンスを差し替えることで状態による振る舞いの違いを表現する、というものです。
個人的なイメージはカートリッジを差し替えるとプログラムが変わる、みたいな感じですね。
（Aというカートリッジを挿すと、Aボタンはジャンプだけど、Bというカートリッジを挿すと同じAボタンでもしゃがむ、とか変化する）
「ゴール」が持つメソッドは3つ
どのあたりが似ていると感じたかと言うと、StateパターンではEnter、Execute、Exitという3つのメソッドを実装し、「とある状態に入ったとき」「とある状態にある間中」「とある状態から抜けるとき」を表します。
新しい状態クラスを作って、それぞれのメソッドをオーバーライドすることで状態が変化する際と「とある状態にある間中」に実行される内容を柔軟に切り替える／実行することができます。
そして、ゴール駆動型のGoalクラスも似たような3つのメソッドを持ちます。
- Activate
- Process
- Terminate
の3つです。
基本的なイメージはそれぞれEnter、Execute、Exitと同様です。
ただ一点異なる点としては、Stateパターンの場合はEnterが呼ばれるのは状態が変化した際の1度きりなのに対し、ゴール駆動型ではActivateが（ゴールによっては）何度も呼ばれる可能性がある、という点です。
Activate
アクティブ化。ゴールが非アクティブ状態から実行された場合に起動される。前提処理やサブゴールのプランニングなど、ゴール実行開始時に必要な処理を行います。
Process
ゴールのメイン処理。
例えば「プレイヤーに近づく」というゴールの場合、ゲームループ中に毎フレームごとにProcessは実行され、その都度、プレイヤーの位置の補足と追従を実行したり、といったことを行います。
Terminate
ゴール「終了」時の後処理。あくまで終了時で、ゴールが成功したか失敗したかに関わらず、必ず実行されます。
Activate時に準備した内容を破棄したりなど、後処理が必要な場合にオーバーライドします。
ゴールは「失敗」することがある
Stateパターンの「状態」は、まさに状態そのものでそれに失敗も成功もありません。
状態が変化したら振る舞いがどうなるか、だけを定義します。
一方、ゴール駆動型のGoalクラスでは、内容は振る舞いを定義していますが、目的は振る舞いではなく、あくまでゴールに到達することです。
つまり、ゴールに向かうために取った行動が「振る舞い」として見えているに過ぎません。
そして大事な点として、ゴールは「失敗する」可能性がある、ということです。
具体例を上げてみると、「とある地点まで移動する」というゴールがあったとしましょう。
なにもない真っ平らな状態なら失敗することはありません。しかし、ほぼすべてのゲームにおいてそんな状況はあり得ません。
実際のゲームであれば道があったり、壁があったり障害物があったり。
なにかしら「とある地点」までの間に、到達不可能になる要因があるものです。
さて、実際にAIに「この地点まで行け」とゴールを設定して、一歩を踏み出したとしましょう。
最初は順調にその地点に向かって歩いています。
ところが途中で扉が閉まるなどして、どうやっても目的地にたどり着けないことが検知された場合どうでしょうか。
もはやそのゴールは達成不可能です。
これが「失敗することもある」ということの理由です。
図にすると下のようなイメージです。
ゴールを階層的に定義したイメージ図
（図での）最終ゴールである「直接攻撃」に失敗した場合は、その前の「プレイヤーに近づく」に戻る
失敗したら再プランニング
個人的な感想を書くと、ゴール駆動型の実装を読んだときに「なんてよくできているんだ」と思いました。
ゴールは失敗する前提になっていて、対象のゴールが失敗したら、より上位のゴール（親ゴール）に処理が戻されます。（思い出してください。ゴールはサブゴールの集合です）
そして親ゴールでもし再プランニングすることができるならここで再プランニングされます。
（例えば目的地まで移動するゴールが失敗した場合は、別の候補から別の目的地を決める、など）
もし親ゴールが再プランニングできない場合はさらに親ゴールに処理が戻ります。
そしてこのゴールの失敗の連鎖が続き、ルートゴールまで戻されると、ルートゴールは（前回書いたように）Brainクラスが担当しています。
Brainクラスは現在のAIの置かれている状況を把握し、プランナークラスからプランをもらってゴールを決定している中枢的存在です。
つまりここまで処理が戻る、ということはAIの状況になにかしらの変化が起きたことを意味しています。
結果として、Brainクラスは現在の状況からさらに最適なゴールを見つけ出すために動き出します。
これを繰り返すことで、まるでAIを、人が操作しているかのように柔軟な挙動を取らせることができる、というわけなのです。
前述の図を用いて表すと、例えばプレイヤーに直接攻撃が失敗した場合、遠距離攻撃を模索する、というような場合は以下のようになります。
ゴールは常に評価、更新される
先ほどからゴールの失敗やプランニング、という言葉を何度も使いましたが、これらはいつ、どこで行われるのでしょうか？
答えを先に書いてしまうと、「毎フレーム」です。
このあたりもStateパターンと似ていると思っている部分ですが、各ゴールは毎フレームごとに評価されます。
そのメソッドが前述したProcessメソッドです。
Processメソッドは毎フレーム（UnityのUpdateメソッドとほぼ同じタイミング）で呼び出され、常にゴールの状態を評価します。
そして「ゴールが失敗した」と判断すると、ゴールを「失敗状態」にし、親に処理を戻します。
そして次のループ処理の中で親ゴールが評価され、その後は前述のフローを辿って行く、という流れです。
ゴールは常に変化する
さて、感の言い方であればピンときたかもしれませんが、ゴールが常に評価される、ということは場合によってはゴールが突然変わる場合もありえます。
というか、なにかしらゲームをやっていることを想像してもらえば分かると思いますが、人の操作は常に変化していきます。
アクションゲームであれば、突然出てきた敵を迎撃するために立ち止まる、という選択を取るかもしれません。
RPGなどのコマンド式のゲームであっても、次のターンにはこうしようと思っていたが敵からの思わぬ攻撃のためにやむなく回復を優先した、なんてこともあるでしょう。
つまり、ゴールは常に変化し、状況に応じて柔軟に変化しなければならない、ということです。
むしろ柔軟に変化しないならそれはAIとは呼べませんね。
こうした、ゴールベースで行動を定義し、かつファジーな判断でリアルタイムにゴールを変更していくことで、AIはまるで生きているかのように振る舞うことができるのです。
また、ゴール自体が差し替えられずとも、現在実行しているゴールに差し込まれる形で別のゴールが設定されることもあります。
ゴールは状態を持つ
上で「失敗状態にし」と書きましたが、ゴールも「状態」を持ちます。
Stateパターンに似ていると書いたのに、ゴール自体にも「状態」があると書くと混乱するかもしれませんが、今目的としているゴールがどんな状態か、が確認できることはとても有用です。（Stateパターンの状態とは意味が異なるので注意してください）
前述のように、ゴールが達成困難になった場合は「失敗」と見なす必要があり、そうした「状態」が必要になってきます。
ゴールが持つ状態は4つ
ゴールクラスは inactive, active, completed, failed の4つの状態を持ちます。
inactive
非アクティブ状態。まだゴールが開始されていない状態です。
もし非アクティブ状態のゴールが「実行されるべき」状態となった場合は、前述の Activate メソッドを呼び出し、アクティブな状態に変化させます。
active
前述の inactive から、現在処理中を示すアクティブな状態へ変化したものが active です。
ゴール未達でかつ、まだ達成できる見込みがある場合は常に active 状態となります。
completed
完了状態。ゴールしたことを親ゴールに伝えます。
failed
ゴール失敗。前述の例で言えば「目的地に到達不可能になった状態」ですね。
失敗した場合は親ゴールにそれが伝わり、ゴールを再プランニングします。（前述の通りです）
実装解説
さて、だいぶ長々と前提について書きましたが、ここからは実際のコードを参考に、今回の実装内容を解説していきたいと思います。
ゴールクラスを実装する
まずはコードを見てもらったほうが早いと思うので、コードから。
namespace AI
{
<summary>
</summary>
public enum Status
{
Inactive,
Active,
Completed,
Failed,
}
<summary>
</summary>
public interface IGoal
{
bool IsInactive { get; }
bool IsActive { get; }
bool IsCompleted { get; }
bool HasFailed { get; }
void Activate();
Status Process();
void Terminate();
void AddSubgoal(IGoal subgoal);
}
<summary>
</summary>
public class Goal<T> : IGoal where T : AIBase
{
protected T _owner;
<summary>
</summary>
public bool IsInactive { get { return _status == Status.Inactive; } }
<summary>
</summary>
public bool IsActive { get { return _status == Status.Active; } }
<summary>
</summary>
public bool IsCompleted { get { return _status == Status.Completed; } }
<summary>
</summary>
public bool HasFailed { get { return _status == Status.Failed; } }
<summary>
</summary>
internal Status _status = Status.Inactive;
public Goal(T owner)
{
_owner = owner;
}
<summary>
</summary>
internal void ActivateIfInactive()
{
if (IsInactive)
{
Activate();
}
}
<summary>
</summary>
protected void ReactivateIfFailed()
{
if (HasFailed)
{
_status = Status.Inactive;
}
}
<summary>
</summary>
public virtual void Activate()
{
Debug.Log("Start " + this);
_status = Status.Active;
}
public virtual Status Process()
{
ActivateIfInactive();
return _status;
}
<summary>
</summary>
public virtual void Terminate()
{
}
public virtual void AddSubgoal(IGoal subgoal)
{
}
}
}
ゴールの基底クラスです。
ベースとなる処理と、状態のプロパティのみ宣言しています。（つまりなにもしないゴール）
各ゴールについてはこれを継承して、実際の処理を記述していきます。
次に、サブゴールをまとめる親ゴールです。
CompositeGoal
サブゴールを束ねるゴールもまた、Goalクラスを継承したものになっています。
名称からも分かる通り、このゴールは「Compositeパターン」を利用して実装しています。
どんなものかをWikipediaから引用させてもらうと、
Composite パターン（コンポジット・パターン）とは、GoF(Gang of Four; 4人のギャングたち)によって定義された デザインパターンの1つである。「構造に関するパターン」に属する。Composite パターンを用いるとディレクトリとファイルなどのような、木構造を伴う再帰的なデータ構造を表すことができる。
ということになります。ファイルとフォルダ、というのは分かりやすい例でしょう。
Compositeパターンを簡単なクラス図にすると以下のようになります。
namespace AI
{
<summary>
</summary>
public class CompositeGoal<T> : Goal<T> where T : AIBase
{
<summary>
</summary>
protected List<IGoal> _subgoals = new List<IGoal>();
public CompositeGoal(T owner) : base(owner) { }
#region Override
public override Status Process()
{
ActivateIfInactive();
return ProcessSubgoals();
}
<summary>
</summary>
<param name="subgoal"></param>
public override void AddSubgoal(IGoal subgoal)
{
if (_subgoals.Contains(subgoal))
{
return;
}
_subgoals.Add(subgoal);
}
#endregion
<summary>
</summary>
protected void RemoveAllSubgoals()
{
foreach (var goal in _subgoals)
{
goal.Terminate();
}
_subgoals.Clear();
}
<summary>
</summary>
<returns></returns>
internal virtual Status ProcessSubgoals()
{
while (_subgoals.Count > 0 &&
(_subgoals[0].IsCompleted || _subgoals[0].HasFailed))
{
_subgoals[0].Terminate();
_subgoals.RemoveAt(0);
}
if (_subgoals.Count == 0)
{
_status = Status.Completed;
return _status;
}
var firstGoal = _subgoals[0];
var subgoalStatus = firstGoal.Process();
if ((subgoalStatus == Status.Completed) &&
_subgoals.Count > 1)
{
_status = Status.Active;
return _status;
}
return _status;
}
}
}
サブゴールを束ねるゴールの定義は以上です。
基本的な処理はサブゴールを評価し、それが完了しているのか失敗しているのかのチェックと、サブゴールすべてが完了したら完了状態になる、というだけのシンプルなものです。
実際の挙動に関しては、目的に応じてこれらふたつのゴールのどちらかを継承してゴール派生クラスを作成していきます。（例えば、目的地に行くゴールであればGoalクラスを継承して、Processメソッド内で移動処理を記述する、という具合です）
全体を統括するBrainクラス
前回書いた通り、Brainクラスは全体のゴールを統括する役割を持っています。が、継承元はCompositeGoalです。
namespace AI
{
<summary>
</summary>
public class Brain<T> : CompositeGoal<T> where T : AIBase
{
private IPlanner _planner;
private PlanBase _currentPlan;
private List<Memory> _shortMemories = new List<Memory>();
private List<Memory> _longMemories = new List<Memory>();
<summary>
</summary>
private List<Memory> AllMemories
{
get
{
List<Memory> allMemories = new List<Memory>();
allMemories.AddRange(_shortMemories);
allMemories.AddRange(_longMemories);
return allMemories;
}
}
#region Constructor
public Brain(T owner) : base(owner)
{
NOTE
_planner = new CharaPlanner(owner);
}
#endregion
#region Public members
<summary>
</summary>
<param name="planObject"></param>
public void Memorize(PlanObject planObject)
{
if (HasMemory(planObject))
{
return;
}
_shortMemories.Add(MakeMemory(planObject));
}
<summary>
</summary>
public void MemoryControl()
{
var targets = from m in _shortMemories
where m.Target != null
select m;
var newList = targets.ToList();
_shortMemories = newList;
}
#endregion
#region Private members
<summary>
</summary>
<returns></returns>
PlanBase EvaluatePlans()
{
List<PlanBase> plans = EnumeratePlans();
return _planner.Evaluate(plans);
}
<summary>
</summary>
<returns></returns>
List<PlanBase> EnumeratePlans()
{
var plans = new List<PlanBase>();
foreach (var m in AllMemories)
{
plans.Add(m.Plan);
}
return plans;
}
<summary>
</summary>
<param name="plan"></param>
<returns></returns>
IGoal GetGoalByPlan(PlanBase plan)
{
switch (plan.GoalType)
{
case GoalType.Wander:
{
return new GoalWander<T>(_owner);
}
case GoalType.GetEnergy:
case GoalType.GetPower:
{
var memory = FindMemory(plan);
return new GoalGetItem<T>(_owner, memory.Target);
}
case GoalType.Attack:
{
var memory = FindMemory(plan);
return new GoalAttackTarget<T>(_owner, memory.Target);
}
}
return new Goal<T>(_owner);
}
<summary>
</summary>
<param name="newPlan"></param>
void ChangePlan(PlanBase newPlan)
{
Debug.Log("Change plan to " + newPlan);
_currentPlan = newPlan;
RemoveAllSubgoals();
var goal = GetGoalByPlan(newPlan);
AddSubgoal(goal);
}
<summary>
</summary>
Memory MakeMemory(PlanObject planObject)
{
var memory = new Memory(planObject);
return memory;
}
<summary>
</summary>
Memory FindMemory(PlanBase plan)
{
return AllMemories.Find(m => m.Plan == plan);
}
<summary>
</summary>
bool HasMemory(PlanObject planObject)
{
var memory = AllMemories.Find(m => m.Plan == planObject.Plan);
return memory != null;
}
<summary>
</summary>
bool HasMemory(Memory memory)
{
var storeMem = AllMemories.Find(m => m == memory);
return storeMem != null;
}
#endregion
#region Override Goal class
public override void Activate()
{
base.Activate();
RemoveAllSubgoals();
var memory = new Memory();
memory.Plan = new PlanWander();
_longMemories.Add(memory);
}
public override Status Process()
{
ActivateIfInactive();
PlanBase selectedPlan = EvaluatePlans();
bool needsChangePlan = (selectedPlan != null) && (_currentPlan != selectedPlan);
if (needsChangePlan)
{
ChangePlan(selectedPlan);
}
return ProcessSubgoals();
}
public override void Terminate()
{
base.Terminate();
}
#endregion
}
}
Brainクラスはその名の通り、AIの挙動を決定する大事な役割を担います。
保持しているAIBase（Owner）の情報と、現在記憶している状態を元に、行動すべき内容を決定します。
短期記憶と長期記憶
プランニング対象となるオブジェクトに関しては記憶に蓄えられます。
また、人間と同様に「長期記憶」と「短期記憶」に分けて保持しておくことで、一定時間経過したら忘れてしまう、という挙動や、忘れることなく必ず実行させる、ということが可能になります。
短期記憶させるものとしては、例えば回復アイテムの位置を覚えさせておいたり、武器の場所を覚えさせておいたり、といったことが考えられます。
当然AIは自分の判断において行動するため、「見つけた」タイミングでそれらのアイテムを取りに行くとは限りません。
そのため、いったん記憶に留めておいてから、必要になったタイミングでそれを取り出し、その場所に向かうことで自然な動きを実現している、というわけです。
長期記憶に適しているものとしては、例えば陣取りゲームなどの場合は最重要ゴールは「陣地を取る」ということです。
こうしたことを「忘れて」しまっては困るので、直近でやるべきゴールがない場合に自動的に選択され、かつ消去されないように長期記憶に留めておくなどするといいでしょう。
記憶にとどめる処理自体は、AIがなにか記憶に留めておくべきものを「見つけた」ときに記憶されます。
見つける方法は様々です。今回のサンプルでは単に、isTriggerなコライダを用いて、記憶可能オブジェクトが検知エリア内に入った場合にそれを保持するようにしています。
今回はコライダを設定していますが、例えば視覚を表現するようにキャラクターの目の前のオブジェクトだけを対象としたり、あるいは「音」に反応するようにしてもいいと思います。
要は「外界を認識するセンサー」をエージェントに実装し、それらが「知覚」したときに記憶に留めることをすれば、より自然な形で記憶に留めさせることができます。
サンプルではSphereColliderでセンサーを表現
プランを選択する「プランナー」
そして実際に「どのプランを選択するか」については「プランナー」クラスを設けています。
プランナークラスに判断を任せることで、あとから性格を変えたりといったことが容易になるようにしています。
ということで、プランナークラスを見てみましょう。
PlannerBase
PlannerBaseクラスはIPlannerインターフェースを実装し、プランナーのベースとなる処理を実装しています。
プランの実際の評価については派生クラスに任せています。
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
namespace AI
{
<summary>
</summary>
interface IPlanner
{
float EvaluatePlan(PlanBase plan);
PlanBase Evaluate(List<PlanBase> plans);
}
<summary>
</summary>
public class PlannerBase<T> : IPlanner where T : AIBase
{
protected T _owner;
#region Constructor
public PlannerBase(T owner)
{
_owner = owner;
}
#endregion
<summary>
</summary>
<param name="plans"></param>
<returns></returns>
public virtual PlanBase Evaluate(List<PlanBase> plans)
{
float maxValue = 0f;
PlanBase selectedPlan = null;
foreach (var plan in plans)
{
float value = EvaluatePlan(plan);
if (maxValue <= value)
{
maxValue = value;
selectedPlan = plan;
}
}
return selectedPlan;
}
<summary>
</summary>
<param name="plan"></param>
<returns></returns>
public virtual float EvaluatePlan(PlanBase plan)
{
return 0f;
}
}
}
大事なポイントはEvalute(List<PlanBase> plans)メソッドです。
プランナーはプランリストを受け取り、その中からオーナーのパラメータを元に「最適」となるプランを選択します。
最適なプランの選択は派生クラスの評価のロジックに任されています。
CharaPlanner
using UnityEngine;
using System.Collections;
namespace AI
{
public class CharaPlanner : PlannerBase<AIBase>
{
#region Constructor
public CharaPlanner(AIBase owner) : base(owner) { }
#endregion
<summary>
</summary>
public override float EvaluatePlan(PlanBase plan)
{
float value = 0f;
if (plan.GoalType == GoalType.Attack)
{
if (_owner.AttackPower == 0.0f)
{
return 0f;
}
value += Mathf.Pow(_owner.Energy, 2f);
value += Mathf.Pow(_owner.AttackPower, 1.5f);
return value;
}
foreach (var reward in plan.RewardProspects)
{
switch (reward.RewardType)
{
case RewardType.Enegy:
value += Mathf.Pow(1f - _owner.Energy, 2f) * reward.Value;
break;
case RewardType.Power:
value += Mathf.Pow(1f - _owner.AttackPower, 3f) * reward.Value;
break;
}
}
return value;
}
}
}
今回のサンプルではキャラクターはひとりしかいないため、CharaPlannerのみの実装です。
これを複数種類実装して、それぞれのキャラクターごとに変えることで、キャラごとの性格を変える、といったことも可能です。
CharaPlannerはシンプルにEvaluatePlan(PlanBase plan)メソッドをオーバーライドして、プランごとの評価部分を実装しています。
プラン選択の要はこのメソッドです。
見てもらうと分かる通り、各プランに設定された「報酬」を元に、2次関数の形で報酬を評価しています。
当然これを3次関数にしたり、あるいはまったく別のロジックを入れることによって、柔軟に、選択するプランに変化を与えることが可能になります。
（例えば、上のサンプルで言えばエネルギーの評価値を上げておくことで、ひたすらエネルギー回収に向かうAIにする、といった具合です）
前回の記事で「ファジーに判断する」と書いたのがまさにこの部分です。
いったんすべてのプランを評価し、その中で「一番評価の高かった（つまりAIにとって最適の）プラン」を選択することで、AIがまるで人が操作しているかのような「状況を判断して行動している」様子を表現している、というわけです。
評価は報酬から計算する
さて、最後は報酬とプラン選択のロジックについて少し深掘りして終わりにしたいと思います。
（さすがにすべてのクラス、実装を解説するには長くなりすぎるので）
前述の通り、プランは報酬を計算して最終的に選択されます。報酬自体はただの数値的なパラメータです。
（例えばこれを手に入れたらライフがこれだけ回復する、とか、これを手に入れたらエネルギーがこれだけ充填される、など）
こうしたパラメータを元に、オーナーの状態（例えばライフが少なくてピンチ！ など）に応じて、適切なプランが選択されるようにロジックを組めば、AIがさも人が操作しているかのような錯覚を生み出すことができます。
ではその計算ロジックはどうしたらいいでしょうか。
正直なところ、答えはありません。というより、キャラクターに取らせたい行動に応じて最適解が変わってきます。
このあたりの調整はゲームの面白さを左右する部分にもなるので大変、でも楽しい部分ではないでしょうか。
とはいえこれでは解説にならないので、今回実装したものを解説すると、2次関数として実装しています。
具体的には以下の部分です。
value += Mathf.Pow(1f - _owner.Energy, 2f) * reward.Value;
1からオーナーのパラメータを引いたものを二乗したものに、報酬の値を掛け算して求めています。
これはつまり、オーナーのエネルギーが最大（1が最大）の場合、報酬見込み値は0になります。（1 - 1 = 0です）
逆に、オーナーのエネルギーが減ってくると2次関数的に見込みが増加します。
実際に値を入れてみると分かりやすいと思います。
pow(1 - 0.9, 2) = 0.1 * 0.1 = 0.01
pow(1 - 0.5, 2) = 0.5 * 0.5 = 0.25
pow(1 - 0.1, 2) = 0.9 * 0.9 = 0.81
という具合です。
※ シェーダもそうですが、0～1で表現するとこうも値が扱いやすくなるのはほんとすごいなと思ってます。
小数点の2次関数とすることで、以下のように充足度が減るにつれて、その報酬見込みが顕著に上昇していくようになります。
またこれらの式を工夫することで、最初は興味がない事柄に対しても、途中から急激に興味を示す、というようなことが可能になります。
まとめ
さて、いかがだったでしょうか。
AIが作れるようになると、ゲームの幅がとても広がります。
そしてゲームに限らず、ゲームAIの理論を組み合わせてサービスの向上を図ることもできるのではないかなと思っています。
今回は「ゴール駆動型」のAIの紹介・解説でしたが、参考にした書籍「実例で学ぶ ゲームAIプログラミング」では様々なAIについて解説されています。
例えば、
などなど、組み合わせることでより多様なAIを作れる内容が盛り沢山です。
経路探索などはUnityではNavMeshなどで手軽に実装できますが、理論を知っておくと色々と応用が効くのでおすすめです。
A*ではありませんが、過去にダイクストラのアルゴリズムについても記事を書いたので、興味がある人は読んてみてください。
qiita.com
