Why 3D Grids
- Many agents move in 3D: aerial, underwater, virtual.
- Their tasks are often OMSPP: one start → many goals.
- Delivery drones: one depot → many drop-offs.
- Warehouse drones: one dock → many rack slots.
- Underwater vehicles: one ship → many sampling sites.
- Video games: one flying unit → many targets.
Let’s see how 3D grids affect INC and AGG performance.
3 × 3 × 3 voxels.
Drag to rotate.
Definition
- 3D grid: space split into voxels, each free or an obstacle.
Voxel: a volume pixel (a 3D cell), the usual name in 3D pathfinding. - Up to 26 successors per node, vs 8 on an 8-conn 2D grid.
6 face moves (cost 1), 12 edge diagonals (√2), 8 corner diagonals (√3).
Face, edge and corner neighbors of the center voxel.
Drag to rotate.
- No corner cutting (as on 8-conn 2D grids).
Drag to rotate.
- h: 3D-Octile
- face = number of face moves.
- edge = number of edge diagonals.
- corner = number of corner diagonals.
- h = face + √2 edge + √3 corner.
Drag to rotate.
- The search space grows cubically with distance.
Legend:
4-conn 2D
8-conn 2D
26-conn 3D
BFS on an open grid (no obstacles).
4 Domains, 3 Maps Each
Canonization: for simplicity and consistency, we search only each map’s biggest reachable region.
Every other free voxel becomes an obstacle (random nodes in small sealed regions would give many unreachable pairs).
Plants: real chemical plant layouts, with large and narrow voids around equipment (inside it: unreachable).
plant03 · 84M voxels
plant04 · 155M voxels
plant05 · 175M voxels
Sandstone: rock pores from CT scans, made for flow simulations.
Parker · 64M voxels
Leopard · 64M voxels
Bentheimer · 64M voxels
Warframe: levels of a space combat game: asteroids in open space.
BC1 · 67M voxels
A2 · 89M voxels
FB1 · 168M voxels
Descent: levels of a flying game: rooms and branching tunnels (outside them: unreachable).
levels2 · 106M voxels
level01 · 131M voxels
level11 · 170M voxels
After canonization: the biggest reachable region only.
| Dimensions | Size | Branching Factor | Heuristic Quality | |||||
|---|---|---|---|---|---|---|---|---|
| Map | L | W | H | Voxels | Reachable | % Reachable | ||
| Plants plant03 | 560 | 331 | 453 | 84M | 77M | 92.2% | 25.8 | 0.93 |
| Plants plant04 | 731 | 445 | 477 | 155M | 147M | 94.8% | 25.8 | 0.95 |
| Plants plant05 | 1257 | 457 | 304 | 175M | 167M | 95.7% | 25.9 | 0.95 |
| Sandstone Parker | 400 | 400 | 400 | 64M | 9M | 13.3% | 20.8 | 0.73 |
| Sandstone Leopard | 400 | 400 | 400 | 64M | 13M | 19.8% | 23.1 | 0.80 |
| Sandstone Bentheimer | 400 | 400 | 400 | 64M | 17M | 26.8% | 23.3 | 0.89 |
| Warframe BC1 | 853 | 245 | 321 | 67M | 67M | 99.5% | 25.8 | 0.98 |
| Warframe A2 | 896 | 390 | 255 | 89M | 89M | 99.8% | 25.8 | 0.99 |
| Warframe FB1 | 812 | 358 | 578 | 168M | 168M | 99.7% | 25.9 | 0.99 |
| Descent levels2 | 794 | 541 | 247 | 106M | 6M | 5.8% | 24.9 | 0.87 |
| Descent level01 | 767 | 668 | 256 | 131M | 4M | 3.3% | 24.6 | 0.63 |
| Descent level11 | 676 | 542 | 463 | 170M | 5M | 2.8% | 24.5 | 0.43 |
Instances
- Maps: the 12 study maps.
- Pair: and , a random free voxel pair.
Goal remoteness: ∈ {100, 125, 150, 175, 200} (± 5). - Goals: 200 random free voxels within 20 face moves of .
- Count: 300 instances (12 maps × 5 remoteness bands × 5 pairs).
Algorithms
- INC: Incremental kA*.
- AGG: kA*-MIN (lazy and optimized).
- DIJ: k-Dijkstra.
Informed (guided by ): INC, AGG. Uninformed: DIJ.
Metrics
- Expansion
- Memory
- H-Calcs
- Runtime
Defined in Goal Geometry › Metrics.
By Goal Remoteness
Labels: DIJ/INC expansion ratios.
| Nodes | Ratio to INC | ||||
|---|---|---|---|---|---|
| Remoteness | INC | AGG | DIJ | AGG | DIJ |
| 100 | 35K | 35K | 2.2M | 1.00× | 62× |
| 125 | 127K | 127K | 3.8M | 1.00× | 30× |
| 150 | 142K | 142K | 5.7M | 1.00× | 40× |
| 175 | 180K | 180K | 7.7M | 1.00× | 43× |
| 200 | 150K | 150K | 11M | 1.00× | 70× |
Reasons
Informed search
h guides the search ⇒ the expanded nodes form a thin tube to the goals, growing in length only.
Uninformed search
No h ⇒ the expanded nodes form a ball around , growing in all 3 dimensions.
Drag to rotate.
DIJ / INC (not monotonic)
3 of a band’s 60 instances (mostly Descent; h / c* 0.10–0.97, the rest 0.94) ⇒ 43–66% of its INC expansions ⇒ the ratio jumps from band to band.
Unlike 2D (Goal Geometry)
2D maps: high remoteness ⇒ BFS fills the map ⇒ INC catches up.
3D maps: far larger (4–168M reachable voxels) ⇒ their border caps DIJ’s ball less ⇒ INC does not catch up.
By Domain
Legend: INC, AGG, DIJ.
| Nodes | Ratio to INC | Heuristic Quality | ||||
|---|---|---|---|---|---|---|
| Domain | INC | AGG | DIJ | AGG | DIJ | |
| Plants | 11.9K | 11.9K | 10.3M | 1.00× | 861× | 1.00 |
| Sandstone | 121K | 121K | 1.94M | 1.00× | 16× | 0.86 |
| Warframe | 4.00K | 4.00K | 10.4M | 1.00× | 2,611× | 1.00 |
| Descent | 370K | 370K | 1.29M | 1.00× | 3× | 0.78 |
Reasons
Informed search
Plants, Warframe domains: h ≈ c* ⇒ f rises off the paths ⇒ few nodes beyond them.
Descent domain: tunnels ⇒ h far below c* ⇒ many nodes with f below c*.
Uninformed search
No h ⇒ every node closer than the farthest goal ⇒ millions of nodes in open space.
By Domain and Goal Remoteness
Each point: the median over the domain’s 15 instances in the band.
| DIJ / INC | |||||
|---|---|---|---|---|---|
| Domain | 100 | 125 | 150 | 175 | 200 |
| Plants | 1,796× | 3,064× | 2,882× | 4,547× | 7,206× |
| Warframe | 2,164× | 3,347× | 5,122× | 3,012× | 5,622× |
| Sandstone | 24× | 19× | 20× | 19× | 15× |
| Descent | 39× | 10× | 5× | 7× | 5× |
Reasons
DIJ
Plants, Warframe domains: open space far larger than its ball (≤ 36% of it at 200) ⇒ no border stops it ⇒ ×4.3–5.2 from 100 to 200.
Descent, Sandstone domains: tunnels and pores ⇒ its ball spreads along them only ⇒ ×3.5–4.7.
INC
Plants, Warframe domains: h ≈ c* ⇒ the paths and the goals only ⇒ ×1.3–1.7.
Descent, Sandstone domains: weak h ⇒ detours grow with remoteness ⇒ ×4.4–15.2.
As in 2D (Goal Geometry)
Descent, Sandstone domains: tunnels and pores cap DIJ’s ball, as a 2D map’s border does ⇒ INC catches up.
By Goal Remoteness
Labels: AGG/INC and DIJ/INC memory ratios.
| Slots | Ratio to INC | ||||
|---|---|---|---|---|---|
| Remoteness | INC | AGG | DIJ | AGG | DIJ |
| 100 | 48K | 1.2M | 2.2M | 25× | 47× |
| 125 | 142K | 1.6M | 3.9M | 11× | 28× |
| 150 | 159K | 1.9M | 5.9M | 12× | 37× |
| 175 | 198K | 2.3M | 7.8M | 12× | 40× |
| 200 | 170K | 2.5M | 11M | 15× | 63× |
By Domain
Legend: INC, AGG, DIJ.
| Slots | Ratio to INC | ||||
|---|---|---|---|---|---|
| Domain | INC | AGG | DIJ | AGG | DIJ |
| Plants | 29.6K | 1.75M | 10.5M | 59× | 355× |
| Sandstone | 136K | 1.90M | 1.98M | 14× | 15× |
| Warframe | 21.1K | 1.67M | 10.7M | 79× | 508× |
| Descent | 387K | 2.32M | 1.31M | 6× | 3× |
Reasons
AGG
Every domain: about 11K nodes in OPEN ⇒ an h per active goal for each ⇒ 1.7–2.3M slots.
DIJ
Descent domain: tunnels ⇒ few nodes cheaper than the goals ⇒ fewer slots than AGG.
As in 2D (Goal Geometry)
OPEN’s h-vectors outweigh CLOSED ⇒ AGG’s memory follows its OPEN, not its expansions.
Labels: AGG/INC h-calc ratios.
| H-Calcs | Ratio to INC | ||
|---|---|---|---|
| Remoteness | INC | AGG | AGG |
| 100 | 1.9M | 8.0M | 4.2× |
| 125 | 2.4M | 26M | 10.7× |
| 150 | 2.9M | 29M | 10.3× |
| 175 | 3.3M | 37M | 11.3× |
| 200 | 3.6M | 31M | 8.6× |
By Goal Remoteness
Labels: AGG/INC and DIJ/INC runtime ratios.
| Seconds | Ratio to INC | ||||
|---|---|---|---|---|---|
| Remoteness | INC | AGG | DIJ | AGG | DIJ |
| 100 | 7.87 | 20.29 | 148.46 | 2.6× | 19× |
| 125 | 11.91 | 49.33 | 270.98 | 4.1× | 23× |
| 150 | 13.93 | 54.29 | 418.50 | 3.9× | 30× |
| 175 | 17.00 | 69.22 | 574.98 | 4.1× | 34× |
| 200 | 19.14 | 65.04 | 812.23 | 3.4× | 42× |
By Domain
Legend: INC, AGG, DIJ.
| Seconds | Ratio to INC | ||||
|---|---|---|---|---|---|
| Domain | INC | AGG | DIJ | AGG | DIJ |
| Plants | 6.77 | 22.64 | 778.00 | 3.3× | 115× |
| Sandstone | 12.49 | 38.68 | 125.77 | 3.1× | 10× |
| Warframe | 5.76 | 19.60 | 793.12 | 3.4× | 138× |
| Descent | 30.87 | 125.61 | 83.22 | 4.1× | 3× |
Reasons
AGG
Descent domain: weak h ⇒ only a few times fewer expansions than DIJ ⇒ up to 200 h-calcs per node cost more than they save.