Better automatic navigation algorithm?

I'm wiring up a UI-heavy game for controller navigation using Unity's EventSystem. The Automatic Navigation is great, when it works, which is about half the time. Common failures:

- two objects are overlapping so it skips the too-close object and moves to a further neighbor

- a small object beside a large offset object skips over the large object to a further neighbor

These cases are so so obviously wrong that I've been tempted to rewrite the algorithm myself. Maybe I'm not the first? Are there any known better (or more customizable) replacements to unity's automatic Selectable navigation?

 

In case it wasn't clear, most of my menus include dynamic content so hard-coding neighbors is rarely an option. Here's an example of a situation where I can't really imagine how this would be the desired outcome:



They all have center pivots and non-overlapping bounds, longer buttons are dynamically generated and laid out by a scrolling grid. Fixed by moving the smaller button left so it lines up with the bigger ones - I don't even know how I would have fixed this using explicit links.

Other things that it seems like a good algorithm might handle: overlapping cards in a hand, items of different sizes in a GridLayoutGroup, items that are completely obscured behind an opaque Image, items inside a CanvasGroup whose alpha is 0, items completely outside a Mask2d.

 

Yes its is downright AWFUL, im looking for a better one, did u ever find one?

 

I would be interested in that too!

 

Nah, I ended up overriding the Button class to manually set some directions while Unity automatically sets the others, then I overrode the GridLayoutGroup to manually set all 4 directions on child Selectables. Hacky, but these two classes plus rearranging some UI elements solved most of my problems.

Code (CSharp):

1. using UnityEngine;
2. using UnityEngine.EventSystems;
3. using UnityEngine.UI;
4.  
5. public class NWButton : Button {
6.  
7.     // partially override the automatic navigation by setting just some of these
8.     public Selectable selectOverrideOnUp;
9.     public Selectable selectOverrideOnDown;
10.     public Selectable selectOverrideOnLeft;
11.     public Selectable selectOverrideOnRight;
12.  
13.     /// <summary>
14.     /// Leave navigation on Automatic then override just one or some directions with explicit targets.
15.     /// </summary>
16.     public override Selectable FindSelectableOnUp() {
17.         return selectOverrideOnUp != null && selectOverrideOnUp.gameObject.activeSelf
18.             ? selectOverrideOnUp : base.FindSelectableOnUp();
19.     }
20.     public override Selectable FindSelectableOnDown() {
21.         return selectOverrideOnDown != null && selectOverrideOnDown.gameObject.activeSelf
22.             ? selectOverrideOnDown : base.FindSelectableOnDown();
23.     }
24.     public override Selectable FindSelectableOnLeft() {
25.         return selectOverrideOnLeft != null && selectOverrideOnLeft.gameObject.activeSelf
26.             ? selectOverrideOnLeft : base.FindSelectableOnLeft();
27.     }
28.     public override Selectable FindSelectableOnRight() {
29.         return selectOverrideOnRight != null && selectOverrideOnRight.gameObject.activeSelf
30.             ? selectOverrideOnRight : base.FindSelectableOnRight();
31.     }
32. }

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using UnityEngine;
5. using UnityEngine.EventSystems;
6. using UnityEngine.UI;
7.  
8. public class NWGridLayoutGroup : GridLayoutGroup {
9.     // for cards or buttons, manually connect left, right, up and down navigation neighbors
10.     // this crap is the Unity way, without it saving and prefab's gonna get screwed up
11.     [SerializeField]
12.     protected bool m_setSelectableNavigation = false;
13.     public bool setSelectableNavigation {
14.         get => m_setSelectableNavigation;
15.         set => SetProperty(ref m_setSelectableNavigation, value);
16.     }
17.    
18.     // all the topmost / leftmost / etc items will all link to this one Selectable if provided
19.     [SerializeField]
20.     protected Selectable m_navigationUp = null;
21.     public Selectable navigationUp {
22.         get => m_navigationUp;
23.         set => SetProperty(ref m_navigationUp, value);
24.     }
25.    
26.     [SerializeField]
27.     protected Selectable m_navigationDown = null;
28.     public Selectable navigationDown {
29.         get => m_navigationDown;
30.         set => SetProperty(ref m_navigationDown, value);
31.     }
32.    
33.     [SerializeField]
34.     protected Selectable m_navigationLeft = null;
35.     public Selectable navigationLeft {
36.         get => m_navigationLeft;
37.         set => SetProperty(ref m_navigationLeft, value);
38.     }
39.    
40.     [SerializeField]
41.     protected Selectable m_navigationRight = null;
42.     public Selectable navigationRight {
43.         get => m_navigationRight;
44.         set => SetProperty(ref m_navigationRight, value);
45.     }
46.    
47.     private readonly Dictionary<Selectable, Vector2Int> childrenByGrid = new Dictionary<Selectable, Vector2Int>();
48.  
49.     /// <summary>
50.     /// Return the selectable in the given index slot, or navigationAbove / navigationRight etc, or null.
51.     /// </summary>
52.     private Selectable GetAdjacentSelectable(int positionX, int positionY) {
53.         if (positionX < 0) return navigationLeft;
54.         if (positionY < 0) return navigationUp;
55.  
56.         bool xFound = false;
57.         foreach (Selectable child in childrenByGrid.Keys) {
58.             Vector2Int otherPosition = childrenByGrid[child];
59.             if (otherPosition.x != positionX) continue;
60.             xFound = true;
61.             if (otherPosition.y != positionY) continue;
62.             return child;
63.         }
64.  
65.         if (xFound) {
66.             // found a child to the left or right, so we must be exiting to whatever is below
67.             return navigationDown;
68.         } else {
69.             return navigationRight;
70.         }
71.     }
72.    
73.     /// <summary>
74.     /// Set the navigation for every Selectable in this grid, if setSelectableNavigation is enabled.
75.     /// </summary>
76.     private void SetNavigation() {
77.         if (!setSelectableNavigation) return;
78.        
79.         foreach (RectTransform child in rectChildren) {
80.             Selectable selectable = child.GetComponentInChildren<Selectable>(true);
81.             if (selectable == null) {
82.                 Debug.LogError("NWGridLayoutGroup doing selectableNavigation with no selectable " + child.GetPath());
83.                 continue;
84.             }
85.             if (!childrenByGrid.ContainsKey(selectable)) {
86.                 Debug.LogError("NWGridLayoutGroup doing childrenByGrid missing selectable " + child.GetPath());
87.                 continue;
88.             }
89.            
90.             Vector2Int position = childrenByGrid.GetSafe(selectable);
91.  
92.             Navigation navigation = selectable.navigation;
93.             navigation.mode = Navigation.Mode.Explicit;
94.             navigation.selectOnUp = GetAdjacentSelectable(position.x, position.y - 1);
95.             navigation.selectOnDown = GetAdjacentSelectable(position.x, position.y + 1);
96.             navigation.selectOnLeft = GetAdjacentSelectable(position.x - 1, position.y);
97.             navigation.selectOnRight = GetAdjacentSelectable(position.x + 1, position.y);
98.             selectable.navigation = navigation;
99.         }
100.        
101.         // keep this empty until the next layout update
102.         childrenByGrid.Clear();
103.     }
104.    
105.     // copied from GridLayoutGroup with small changes
106.    
107.  
108.     /// <summary>
109.     /// Called by the layout system
110.     /// Also see ILayoutElement
111.     /// </summary>
112.     public override void SetLayoutHorizontal()
113.     {
114.         // only prep done here
115.         SetCellsAlongAxis(0);
116.     }
117.  
118.     /// <summary>
119.     /// Called by the layout system
120.     /// Also see ILayoutElement
121.     /// </summary>
122.     public override void SetLayoutVertical()
123.     {
124.         // actual positioning done here
125.         SetCellsAlongAxis(1);
126.     }
127.  
128.     private void SetCellsAlongAxis(int axis)
129.     {
130.         // Normally a Layout Controller should only set horizontal values when invoked for the horizontal axis
131.         // and only vertical values when invoked for the vertical axis.
132.         // However, in this case we set both the horizontal and vertical position when invoked for the vertical axis.
133.         // Since we only set the horizontal position and not the size, it shouldn't affect children's layout,
134.         // and thus shouldn't break the rule that all horizontal layout must be calculated before all vertical layout.
135.         var rectChildrenCount = rectChildren.Count;
136.         if (axis == 0)
137.         {
138.             // Only set the sizes when invoked for horizontal axis, not the positions.
139.  
140.             for (int i = 0; i < rectChildrenCount; i++)
141.             {
142.                 RectTransform rect = rectChildren[i];
143.  
144.                 m_Tracker.Add(this, rect,
145.                     DrivenTransformProperties.Anchors |
146.                     DrivenTransformProperties.AnchoredPosition |
147.                     DrivenTransformProperties.SizeDelta);
148.  
149.                 rect.anchorMin = Vector2.up;
150.                 rect.anchorMax = Vector2.up;
151.                 rect.sizeDelta = cellSize;
152.             }
153.             return;
154.         }
155.  
156.         float width = rectTransform.rect.size.x;
157.         float height = rectTransform.rect.size.y;
158.  
159.         int cellCountX = 1;
160.         int cellCountY = 1;
161.         if (m_Constraint == Constraint.FixedColumnCount)
162.         {
163.             cellCountX = m_ConstraintCount;
164.  
165.             if (rectChildrenCount > cellCountX)
166.                 cellCountY = rectChildrenCount / cellCountX + (rectChildrenCount % cellCountX > 0 ? 1 : 0);
167.         }
168.         else if (m_Constraint == Constraint.FixedRowCount)
169.         {
170.             cellCountY = m_ConstraintCount;
171.  
172.             if (rectChildrenCount > cellCountY)
173.                 cellCountX = rectChildrenCount / cellCountY + (rectChildrenCount % cellCountY > 0 ? 1 : 0);
174.         }
175.         else
176.         {
177.             if (cellSize.x + spacing.x <= 0)
178.                 cellCountX = int.MaxValue;
179.             else
180.                 cellCountX = Mathf.Max(1, Mathf.FloorToInt((width - padding.horizontal + spacing.x + 0.001f) / (cellSize.x + spacing.x)));
181.  
182.             if (cellSize.y + spacing.y <= 0)
183.                 cellCountY = int.MaxValue;
184.             else
185.                 cellCountY = Mathf.Max(1, Mathf.FloorToInt((height - padding.vertical + spacing.y + 0.001f) / (cellSize.y + spacing.y)));
186.         }
187.  
188.         int cornerX = (int)startCorner % 2;
189.         int cornerY = (int)startCorner / 2;
190.  
191.         int cellsPerMainAxis, actualCellCountX, actualCellCountY;
192.         if (startAxis == Axis.Horizontal)
193.         {
194.             cellsPerMainAxis = cellCountX;
195.             actualCellCountX = Mathf.Clamp(cellCountX, 1, rectChildrenCount);
196.             actualCellCountY = Mathf.Clamp(cellCountY, 1, Mathf.CeilToInt(rectChildrenCount / (float)cellsPerMainAxis));
197.         }
198.         else
199.         {
200.             cellsPerMainAxis = cellCountY;
201.             actualCellCountY = Mathf.Clamp(cellCountY, 1, rectChildrenCount);
202.             actualCellCountX = Mathf.Clamp(cellCountX, 1, Mathf.CeilToInt(rectChildrenCount / (float)cellsPerMainAxis));
203.         }
204.  
205.         Vector2 requiredSpace = new Vector2(
206.             actualCellCountX * cellSize.x + (actualCellCountX - 1) * spacing.x,
207.             actualCellCountY * cellSize.y + (actualCellCountY - 1) * spacing.y
208.         );
209.         Vector2 startOffset = new Vector2(
210.             GetStartOffset(0, requiredSpace.x),
211.             GetStartOffset(1, requiredSpace.y)
212.         );
213.        
214.        
215.         // sarah added
216.         if (setSelectableNavigation) {
217.             childrenByGrid.Clear();
218.         }
219.  
220.         for (int i = 0; i < rectChildrenCount; i++)
221.         {
222.             int positionX;
223.             int positionY;
224.             if (startAxis == Axis.Horizontal)
225.             {
226.                 positionX = i % cellsPerMainAxis;
227.                 positionY = i / cellsPerMainAxis;
228.             }
229.             else
230.             {
231.                 positionX = i / cellsPerMainAxis;
232.                 positionY = i % cellsPerMainAxis;
233.             }
234.  
235.             if (cornerX == 1)
236.                 positionX = actualCellCountX - 1 - positionX;
237.             if (cornerY == 1)
238.                 positionY = actualCellCountY - 1 - positionY;
239.  
240.             SetChildAlongAxis(rectChildren[i], 0, startOffset.x + (cellSize[0] + spacing[0]) * positionX, cellSize[0]);
241.             SetChildAlongAxis(rectChildren[i], 1, startOffset.y + (cellSize[1] + spacing[1]) * positionY, cellSize[1]);
242.            
243.             // sarah added
244.             if (setSelectableNavigation) {
245.                 Selectable childSelectable = rectChildren[i].GetComponentInChildren<Selectable>(true);
246.                 if (childSelectable == null) {
247.                     Debug.LogError("NWGridLayoutGroup with selectableNavigation but child has no Selectable " + rectChildren[i].GetPath());
248.                 } else {
249.                     childrenByGrid.AddSafe(childSelectable, new Vector2Int(positionX, positionY));
250.                     // Debug.Log("==== recording child at " + new Vector2Int(positionX, positionY) + ": " + childSelectable.GetPath());
251.                 }
252.             }
253.         }
254.        
255.         // sarah added
256.         // SetLayoutVertical is called after SetLayoutHorizontal so this is the last part of the layout update
257.         SetNavigation();
258.     }
259. }
260.  

 

thanks a lot. thats pretty much the route i already took too. im glad its possible though.

 

I've been looking for a way to solve this problem and stumbled on this... Are 'GetSafe', 'AddSafe', and 'GetPath' extension functions you wrote, or part of some package I don't have?

Thanks for your work in this, it's really astounding that Unity just doesn't give us a good way of handling automatic navigation between dynamically added grids of buttons without overriding stuff.

 

Oh yeah they're just my own helper extensions I should have stripped:

Code (CSharp):

1. public static TValue GetSafe<TKey, TValue>(this IDictionary<TKey, TValue> dict, TKey key, TValue defaultValue = default) {
2.     if (key == null || dict == null) return defaultValue;
3.     if (!dict.ContainsKey(key)) return defaultValue;
4.     return dict[key];
5. }
6.  
7. public static void AddSafe<TKey, TValue>(this IDictionary<TKey, TValue> dict, TKey key, TValue value) {
8.     if (dict == null || key == null) return;
9.     dict.Add(key, value);
10. }
11.  
12. public static string GetPath(this Component component) {
13.     try {
14.         if (component == null || component.gameObject == null) return "";
15.         return component.transform.GetPath() + "/" + component.GetType().ToString();
16.     } catch (Exception e) {
17.         return "[path undetermined, error " + e + "]";
18.     }
19. }
20.  
21. public static string GetPath(this Transform current) {
22.     if (current == null) {
23.         return "NULL";
24.     }
25.     if (current.parent == null) {
26.         return "/" + current.name;
27.     }
28.     return current.parent.GetPath() + "/" + current.name;
29. }
30.  
31.  

 

I improved the navigation code, at least for my use case, by treating selectables as rects and measuring the distance in between them instead of points on their centers.

I had to modify the Selectable.cs file, which means editing the UI Package.

The final code and the specific changes done to the file can be seen here https://gist.github.com/forestrf/00d4ac645241a8a9de43114341f29ff0/revisions

It has problems when the quads intersect too much, in that case it should go back to using the center of the rects for that pair of selectables.

 

I know it is a bit late answer, but for anyone for who have any issue with ui navigation and they looking for for solution, I would recommend "uGUI Directed Navigation": https://assetstore.unity.com/packages/tools/gui/ugui-directed-navigation-245630