OMSPP - 8 Conns

What Changes When the Grid Gains Diagonals

Setup

Motivation

  1. Moving from 4-connected to 8-connected grids changes the search geometry.
  2. Let’s see how this affects the differences between INC and AGG performance.

Movement Models

Aspect 4-conn 8-conn
Moves 4 cardinal, cost 11 +4+4 diagonal, cost √2
Successors up to 44 up to 88
Heuristic Manhattan Octile
h(n)h(n) Δmax+Δmin\Delta_{\max} + \Delta_{\min} Δmax+(2−1)Δmin\Delta_{\max} + (\sqrt{2}-1)\,\Delta_{\min}
Table 1: Movement Models: 4-Conn vs 8-Conn.
Figure 2: Valid Moves from a Node nn.
Figure 3: Heuristic Example: n=(0,0)n = (0, 0), G=(1,3)G = (1, 3).

No Corner Cutting

  1. Both flanks must be free: a physical agent cannot cut across an obstacle’s corner.
  2. Reachability unchanged: 8-conn reaches the same nodes as 4-conn, just cheaper.
Figure 4: No Corner Cutting.
Map Metrics
Overview

Motivation

  1. Diagonals change the map itself, before any search runs.
  2. These map changes can explain the algorithm metrics that follow.
Figure 5: A* Search: 4-Conn vs 8-Conn.
Legend: expanded, generated.

Metrics

Figure 6: Map Metrics at a Glance.

Setup

  1. Maps: 25 MovingAI maps, 5 per domain.
  2. Pairs: 100100 seeded start-goal pairs (S,G)(S, G) per map, Manhattan distance ≥100\ge 100.
  3. Count: 2,500 pairs overall, 25 maps × 100 pairs per map.
  4. Paired: both models use the same pairs.
  5. Branching factor: measured on whole maps, regardless of the (S,G)(S, G) pairs.
Branching Factor

Mean number of valid moves from a free cell, N4N_4 and N8N_8.
More valid moves ⇒\Rightarrow more successors per expansion ⇒\Rightarrow more work per node.

Legend:
cardinal: both models
diagonal: 8-conn only
invalid (corner rule)

Figure 7: Branching Factor: 4-Conn vs 8-Conn.
Figure 8: Branching Factor by Domain.
Path Cost

Mean optimal cost from SS to GG, c4*c^*_4 and c8*c^*_8.
Same pairs in both models ⇒\Rightarrow the ratio shows how much diagonals shorten paths.

Legend:
4-conn optimal path
8-conn optimal path

Figure 9: Path Cost: 4-Conn vs 8-Conn.
Figure 10: Path Cost by Domain.
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×
Table 2: Path Cost: Obstacles and Valid Diagonals.
Heuristic Quality

Mean h4/c4*h_4 / c^*_4 and h8/c8*h_8 / c^*_8; 11 means a perfect heuristic.
Lower quality ⇒\Rightarrow more expansions for informed search (INC, AGG).

Legend:
4-conn optimal path
8-conn optimal path
dashed: hh (ignores obstacles)

Figure 11: Heuristic Quality: 4-Conn vs 8-Conn.
Figure 12: Heuristic Quality by Domain.
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%
Table 3: Heuristic Quality: Octile vs Manhattan.
Insights
Figure 13: Map Metrics: Insights.
Algorithm Metrics
Overview

Metrics

  1. Expansion
  2. Memory
  3. H-Calcs
  4. Runtime

Defined in Goal Geometry › Metrics.

Setup

  1. Maps: 25 MovingAI maps, 5 per domain.
  2. Pairs: 5 per map, start SS to goal center G0G_0, Manhattan ≥\ge 100.
  3. Goals: 200 cells drawn at random within 20 steps of G0G_0.
    kk ∈ {40, 80, 120, 160, 200}: the first kk of them (nested).
  4. Count: 125 instances overall, 5 domains × 5 maps × 5 pairs.
  5. Algorithms: INC, AGG and DIJ, each under 4-conn and 8-conn.
    Informed (guided by hh): INC, AGG. Uninformed: DIJ (not BFS: 8-conn edge weights are unequal).
  6. Paired: both models solve the same instances.
Successors
Figure 15: Branching Factor by Outcome: 4-Conn vs 8-Conn.
Wasted: the node was already generated, and the new path gives it no lower gg (no reroute).

Reasons

INC, AGG, DIJ
More neighbors reach a node ⇒\Rightarrow One generates it ⇒\Rightarrow Extras wasted.

Figure 16: Successors Reaching a Node: 4-Conn vs 8-Conn.

DIJ
4-conn: Every step costs 1 ⇒\Rightarrow No cheaper last step ⇒\Rightarrow Never.
8-conn: Pops in gg order ⇒\Rightarrow Needs a cheaper last step ⇒\Rightarrow Rare (0.33%).

Figure 17: A DIJ Reroute in 8-Conn.
Labels: gg (path cost from SS).
Expansion
Figure 18: Expansion: 4-Conn vs 8-Conn.
Labels: AGG/INC and DIJ/INC expansion ratios.

Reasons

INC, AGG, DIJ
Extra successors wasted or rerouted ⇒\Rightarrow No new nodes ⇒\Rightarrow Same expansions.

Figure 19: Successors, Generated and Expanded Nodes: 8-Conn / 4-Conn.

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×
Table 4: Expansion by Number of Goals: Each Model.
Columns 4 and 8 are 4-conn and 8-conn.
Memory
Figure 20: Memory: 4-Conn vs 8-Conn.
1. Labels: AGG/INC and DIJ/INC memory ratios.
2. (*) Crossover point by linear interpolation.

Reasons

INC, DIJ
Same expansions ⇒\Rightarrow Same CLOSED (≥ 97% of memory) ⇒\Rightarrow ~Same Memory (+<2%).

AGG
Peak memory depends more on OPEN than on CLOSED ⇒\Rightarrow OPEN grows in 8-conn ⇒\Rightarrow Memory +4.3%.

Figure 21: CLOSED Share in Peak Memory: 4-Conn vs 8-Conn.
Figure 22: OPEN Size in Peak Memory: 4-Conn vs 8-Conn.

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×
Table 5: Memory by Number of Goals: Each Model.
Columns 4 and 8 are 4-conn and 8-conn.
H-Calcs
Figure 23: H-Calcs: 4-Conn vs 8-Conn.
1. Labels: AGG/INC h-calc ratios at k=40k = 40 and k=200k = 200.
2. The charts are log-scaled for better readability.
3. DIJ computes no hh, so it has no line.

Reasons

INC
Same generated nodes ⇒\Rightarrow More reroutes (2.4×) and a larger OPEN to retarget (1.23×) ⇒\Rightarrow 1.3× h-calcs.

Figure 24: INC H-Calcs by Source: 4-Conn vs 8-Conn.
Bars 4 and 8 are 4-conn and 8-conn.

AGG
hh only when a node is generated ⇒\Rightarrow Same generated nodes ⇒\Rightarrow 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×
Table 6: H-Calcs by Number of Goals: Each Model.
Columns 4 and 8 are 4-conn and 8-conn.
Runtime
Figure 25: Runtime: 4-Conn vs 8-Conn.
1. Labels: AGG/INC and DIJ/INC runtime ratios at k=40k = 40 and k=200k = 200.
2. The top charts are log-scaled for better readability.
3. (*) Crossover point by linear interpolation.

Reasons

INC
Same expansions ⇒\Rightarrow 1.90× successors, 2.4× reroutes, 1.3× h-calcs ⇒\Rightarrow 1.70× slower.

AGG
Same expansions ⇒\Rightarrow 1.90× successors, 2.4× reroutes, 2.2× stale pops (pops that only re-check FF) ⇒\Rightarrow 1.43× slower.

DIJ
Same expansions ⇒\Rightarrow 1.96× successors, 1.57× OPEN (a deeper heap) ⇒\Rightarrow 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×
Table 7: Runtime by Number of Goals.
Columns 4 and 8 are 4-conn and 8-conn.