Motivation
- Moving from 4-connected to 8-connected grids changes the search geometry.
- Let’s see how this affects the differences between INC and AGG performance.
Legend: expanded, generated.
Movement Models
| Aspect | 4-conn | 8-conn |
|---|---|---|
| Moves | 4 cardinal, cost | diagonal, cost √2 |
| Successors | up to | up to |
| Heuristic | Manhattan | Octile |
No Corner Cutting
- Both flanks must be free: a physical agent cannot cut across an obstacle’s corner.
- Reachability unchanged: 8-conn reaches the same nodes as 4-conn, just cheaper.
Motivation
- Diagonals change the map itself, before any search runs.
- These map changes can explain the algorithm metrics that follow.
Legend: expanded, generated.
Metrics
Setup
- Maps: 25 MovingAI maps, 5 per domain.
- Pairs: seeded start-goal pairs per map, Manhattan distance .
- Count: 2,500 pairs overall, 25 maps × 100 pairs per map.
- Paired: both models use the same pairs.
- Branching factor: measured on whole maps, regardless of the pairs.
Mean number of valid moves from a free cell, and .
More valid moves more successors per expansion more work per node.
Legend:
cardinal: both models
diagonal: 8-conn only
invalid (corner rule)
Mean optimal cost from to , and .
Same pairs in both models the ratio shows how much diagonals shorten paths.
Legend:
4-conn optimal path
8-conn optimal path
1. Domains are ordered by the 8-conn / 4-conn ratio.
2. The chart is log-scaled for better readability.
| Path Cost | |||
|---|---|---|---|
| Domain | Obstacles | Valid Diagonals | 8-conn / 4-conn |
| Cities | 24% | 98% | 0.83× |
| Games | 60% | 93% | 0.84× |
| Rooms | 10% | 89% | 0.85× |
| Random | 20% | 52% | 0.86× |
| Mazes | 14% | 80% | 0.89× |
| All | 26% | 83% | 0.86× |
Mean and ; means a perfect heuristic.
Lower quality more expansions for informed search (INC, AGG).
Legend:
4-conn optimal path
8-conn optimal path
dashed: (ignores obstacles)
| Heuristic Quality | Octile Quality per Pair | ||||
|---|---|---|---|---|---|
| Domain | Manhattan | Octile | Worse | Equal | Better |
| Mazes | 0.26 | 0.24 | 65% | 5% | 30% |
| Random | 0.97 | 0.93 | 68% | 16% | 16% |
| Rooms | 0.83 | 0.81 | 57% | 2% | 40% |
| Games | 0.81 | 0.81 | 41% | 14% | 44% |
| Cities | 0.94 | 0.93 | 37% | 31% | 32% |
| All | 0.76 | 0.75 | 54% | 14% | 32% |
Metrics
- Expansion
- Memory
- H-Calcs
- Runtime
Defined in Goal Geometry › Metrics.
Setup
- Maps: 25 MovingAI maps, 5 per domain.
- Pairs: 5 per map, start to goal center , Manhattan 100.
- Goals: 200 cells drawn at random within 20 steps of .
∈ {40, 80, 120, 160, 200}: the first of them (nested). - Count: 125 instances overall, 5 domains × 5 maps × 5 pairs.
- Algorithms: INC, AGG and DIJ, each under 4-conn and 8-conn.
Informed (guided by ): INC, AGG. Uninformed: DIJ (not BFS: 8-conn edge weights are unequal). - Paired: both models solve the same instances.
Wasted: the node was already generated, and the new path gives it no lower (no reroute).
Reasons
INC, AGG, DIJ
More neighbors reach a node One generates it Extras wasted.
DIJ
4-conn: Every step costs 1 No cheaper last step Never.
8-conn: Pops in order Needs a cheaper last step Rare (0.33%).
Labels: (path cost from ).
Labels: AGG/INC and DIJ/INC expansion ratios.
Reasons
INC, AGG, DIJ
Extra successors wasted or rerouted No new nodes Same expansions.
By Number of Goals
| Nodes | Ratio to INC | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| INC | AGG | DIJ | 4-Conn | 8-Conn | ||||||
| k | 4 | 8 | 4 | 8 | 4 | 8 | AGG | DIJ | AGG | DIJ |
| 40 | 40.9K | 41.7K | 40.9K | 41.7K | 161K | 164K | 1.00× | 3.94× | 1.00× | 3.93× |
| 80 | 42.4K | 42.3K | 42.4K | 42.3K | 161K | 164K | 1.00× | 3.80× | 1.00× | 3.88× |
| 120 | 42.9K | 42.5K | 42.9K | 42.5K | 161K | 164K | 1.00× | 3.76× | 1.00× | 3.86× |
| 160 | 43.2K | 42.6K | 43.2K | 42.7K | 161K | 164K | 1.00× | 3.74× | 1.00× | 3.85× |
| 200 | 43.3K | 42.7K | 43.3K | 42.8K | 161K | 164K | 1.00× | 3.73× | 1.00× | 3.84× |
Columns 4 and 8 are 4-conn and 8-conn.
1. Labels: AGG/INC and DIJ/INC memory ratios.
2. (*) Crossover point by linear interpolation.
Reasons
INC, DIJ
Same expansions Same CLOSED (≥ 97% of memory) ~Same Memory (+<2%).
AGG
Peak memory depends more on OPEN than on CLOSED OPEN grows in 8-conn Memory +4.3%.
By Number of Goals
| Slots | Ratio to INC | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| INC | AGG | DIJ | 4-Conn | 8-Conn | ||||||
| k | 4 | 8 | 4 | 8 | 4 | 8 | AGG | DIJ | AGG | DIJ |
| 40 | 41.7K | 42.7K | 66.2K | 70.9K | 162K | 164K | 1.59× | 3.87× | 1.66× | 3.84× |
| 80 | 43.3K | 43.4K | 99.9K | 106K | 162K | 165K | 2.31× | 3.73× | 2.45× | 3.80× |
| 120 | 43.8K | 43.6K | 136K | 143K | 162K | 165K | 3.09× | 3.69× | 3.28× | 3.78× |
| 160 | 44.1K | 43.7K | 174K | 180K | 162K | 165K | 3.95× | 3.67× | 4.11× | 3.77× |
| 200 | 44.2K | 43.8K | 212K | 217K | 162K | 165K | 4.80× | 3.66× | 4.96× | 3.76× |
Columns 4 and 8 are 4-conn and 8-conn.
1. Labels: AGG/INC h-calc ratios at and .
2. The charts are log-scaled for better readability.
3. DIJ computes no , so it has no line.
Reasons
INC
Same generated nodes More reroutes (2.4×) and a larger OPEN to retarget (1.23×) 1.3× h-calcs.
Bars 4 and 8 are 4-conn and 8-conn.
AGG
only when a node is generated Same generated nodes Flat h-calcs.
By Number of Goals
| H-Calcs | AGG/INC Ratio | |||||
|---|---|---|---|---|---|---|
| INC | AGG | 4-Conn | 8-Conn | |||
| k | 4 | 8 | 4 | 8 | ||
| 40 | 80.8K | 106K | 1.59M | 1.63M | 19.62× | 15.46× |
| 80 | 107K | 136K | 3.26M | 3.31M | 30.60× | 24.32× |
| 120 | 129K | 163K | 4.95M | 4.99M | 38.51× | 30.51× |
| 160 | 149K | 189K | 6.64M | 6.67M | 44.57× | 35.37× |
| 200 | 168K | 212K | 8.33M | 8.36M | 49.54× | 39.39× |
Columns 4 and 8 are 4-conn and 8-conn.
1. Labels: AGG/INC and DIJ/INC runtime ratios at and .
2. The top charts are log-scaled for better readability.
3. (*) Crossover point by linear interpolation.
Reasons
INC
Same expansions 1.90× successors, 2.4× reroutes, 1.3× h-calcs 1.70× slower.
AGG
Same expansions 1.90× successors, 2.4× reroutes, 2.2× stale pops (pops that only re-check ) 1.43× slower.
DIJ
Same expansions 1.96× successors, 1.57× OPEN (a deeper heap) 1.27× slower.
By Number of Goals
| Seconds | Ratio to INC | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| INC | AGG | DIJ | 4-Conn | 8-Conn | ||||||
| k | 4 | 8 | 4 | 8 | 4 | 8 | AGG | DIJ | AGG | DIJ |
| 40 | 2.26 | 4.07 | 7.80 | 11.28 | 11.54 | 14.62 | 3.45× | 5.10× | 2.77× | 3.60× |
| 80 | 2.54 | 4.35 | 13.62 | 19.10 | 11.60 | 14.72 | 5.36× | 4.57× | 4.39× | 3.38× |
| 120 | 2.72 | 4.58 | 19.21 | 27.11 | 11.57 | 14.77 | 7.06× | 4.25× | 5.91× | 3.22× |
| 160 | 2.88 | 4.79 | 25.08 | 35.68 | 11.52 | 14.62 | 8.71× | 4.00× | 7.45× | 3.05× |
| 200 | 3.02 | 4.98 | 30.52 | 44.28 | 11.39 | 14.59 | 10.11× | 3.77× | 8.89× | 2.93× |
Columns 4 and 8 are 4-conn and 8-conn.