Ex falso sequitur quodlibet

Pathfinding & decisions · 2 / 10

Dijkstra’s Algorithm

累積コストから最短経路や到達範囲を求める。

Compare in motion

Interactive model

広がる到達範囲

Synchronized comparison
AReference
移動コストを考慮しない範囲

移動コストを考慮しない範囲

BDijkstra’s Algorithm100%
最短距離や移動可能範囲を求められる

最短距離や移動可能範囲を求められる

Loading demo…

Scrub to pause and inspect. At 0%, B matches A; at 100%, B shows the effect. The scene repeats every 8 seconds.

Look for: 累積コスト順に広げる → 近い領域から明らかになる。

This model simplifies the technique to show its use case and effect. Operation counts describe the model; they are not performance measurements.

Read the storyboard

例: 広がる到達範囲

  1. 1. Start

    出発点だけが既知

  2. 2. Change

    累積コスト順に広げる

  3. 3. Result

    近い領域から明らかになる

最短距離や移動可能範囲を求められる。時間変化を示す模式図です。実際の描画結果や処理速度を再現したものではありません。

How it works

  1. 1. Input

    地図と出発点

  2. 2. Process

    累積コスト順に展開

  3. 3. Result

    最短距離の分布

A schematic of Dijkstra’s Algorithm. It shows the relationship between input, process, and result; exact values and rendering depend on the implementation.

Further reading

Red Blob Games — A* Introduction ↗

A general reference for this subcategory.