Multiple CompareTo

Hello,

Ive run into a situation where I need multiple CompareTo methods. My HexTiles goes through two stages, one calculating the GCost with Dijkstra using a Heap implementing public interface IHeapItem<T> : IComparable<T> . Then I calculate the A* also using the same generic heap class but since the heap is sorted by different things ( FCost and Weight) I need 2 CompareTo methods on the same object. Is there a way I can do this ?

My HexTile object

Code (csharp):

1.  
2.  
3.         public int CompareTo(HexTile nodeToCompare) {
4.             int compare = FCost.CompareTo(nodeToCompare.FCost);
5.             if (compare == 0) {
6.                 compare = HCost.CompareTo(nodeToCompare.HCost);
7.             }
8.             return -compare;
9.         }
10.        
11.         public int CompareTo(HexTile nodeToCompare) {
12.             int compare = Weight.CompareTo(nodeToCompare.Weight);
13.             return -compare;
14.         }
15.  

The heap interface

Code (csharp):

1.  
2.     // Compare items to each other in heap
3.     public interface IHeapItem<T> : IComparable<T>
4.     {
5.         int HeapIndex {
6.             get;
7.             set;
8.         }
9.     }
10.  

 

No, you cannot write two methods with the same name and parameters. I would just name them differently and remove the

IComparable<T>

derivation.

When you want to sort the tiles you usually can pass a compare method or pass an

IComparer<T>

object (at least if you work with

List<T>

).

 

Sice the method has to be on the HexTile object I can't change the signature so I can't overload but im curious what you meant by "you usually can pass a compare method"

Code (csharp):

1.  
2. using UnityEngine;
3. using System.Collections;
4. using System;
5. public class Heap<T> where T : IHeapItem<T> {
6.     T[] items;
7.      //...............ect
8.      if (item.CompareTo(items[swapIndex]) < 0)
9.     //................ect
10. }
11. public interface IHeapItem<T> : IComparable<T> {
12.     int HeapIndex {
13.         get;
14.         set;
15.     }
16. }
17.  

 

can you show me more of the source code (at least the sorting method), so I can give you more advise?

EDIT:
actually I think I can answer you anyways.
you can do it like this:

Code (csharp):

1. public void Sort(Comparison<T> compareMethod)
2. {
3.     // ...
4.     if (compareMethod(item, items[swapIndex]) < 0)
5.     // ...
6. }

or like this:

Code (csharp):

1. public void Sort(IComparer<T> comparer)
2. {
3.     // ...
4.     if (comparer.Compare(item, items[swapIndex]) < 0)
5.     // ...
6. }

 

Sure here is the Heap class, thanks so much for the help

 

Don't implement the comparison on the type that you put in the heap. Implement it as an IComparer that you pass to the heap.

For example... here is my BinaryHeap:
https://github.com/lordofduct/space...puppyUnityFramework/Collections/BinaryHeap.cs

Note that it takes an IComparer:

Code (csharp):

1.  
2.         #region Fields
3.  
4.         private static T[] _zeroArray = new T[0];
5.  
6.         private T[] _heap;
7.         private int _tail;
8.         private IComparer<T> _comparer;
9.  
10.         #endregion
11.  
12.         #region CONSTRUCTOR
13.  
14.         public BinaryHeap()
15.         {
16.             _heap = _zeroArray;
17.             _tail = 0;
18.             _comparer = Comparer<T>.Default;
19.         }
20. //... snip
21.         public BinaryHeap(IComparer<T> comparer)
22.         {
23.             _heap = _zeroArray;
24.             _tail = 0;
25.             _comparer = comparer ?? Comparer<T>.Default;
26.         }
27. //... snip
28.         #endregion
29.  

Then in my Dijkstra I define and use a Dijkstra comparer:
https://github.com/lordofduct/space.../SPPathfinding/Graphs/DijkstraPathResolver.cs

Code (csharp):

1.  
2.         #region Special Types
3.  
4.         private class VertexInfo
5.         {
6.             public T Node;
7.             public VertexInfo Next;
8.             public float Distance;
9.         }
10.  
11.         private class VertexComparer : IComparer<VertexInfo>
12.         {
13.             public readonly static VertexComparer Default = new VertexComparer();
14.  
15.             public int Compare(VertexInfo x, VertexInfo y)
16.             {
17.                 return y.Distance.CompareTo(x.Distance);
18.             }
19.         }
20.  
21.         #endregion
22.  

And in my A* I use a different comparer:
https://github.com/lordofduct/space...ter/SPPathfinding/Graphs/AStarPathResolver.cs

Code (csharp):

1.  
2.         #region Special Types
3.  
4. //...snip
5.  
6.         private class VertexInfo
7.         {
8.             public T Node;
9.             public VertexInfo Next;
10.             public float g;
11.             public float h;
12.             public float f;
13.         }
14.  
15.         private class VertexComparer : IComparer<VertexInfo>
16.         {
17.             public readonly static VertexComparer Default = new VertexComparer();
18.  
19.             public int Compare(VertexInfo x, VertexInfo y)
20.             {
21.                 return y.f.CompareTo(x.f);
22.             }
23.         }
24.  
25.         #endregion
26.  

 

Note that with this. I can search different graphs with different node types implement IGraph<T>:
https://github.com/lordofduct/space....0/blob/master/SPPathfinding/Graphs/IGraph.cs

So that way I can use the same implementation of A* for both GridGraph and HexGraph:
https://github.com/lordofduct/space...blob/master/SPPathfinding/Graphs/GridGraph.cs
https://github.com/lordofduct/space.../blob/master/SPPathfinding/Graphs/HexGraph.cs

 

Awesome let me soak this in and will most likely have to ask you more questions. Appreciate the help

 

This stuff is gold but really struggling to understand it. You dont happen to have tutorial on your stuff.

Seeing how you do stuff I realized how much better I can write code. You ok with me tryin to implement some of your stuff it into my own project ?

 

My code exists up on that github for people to explore, for me to share here on unity forums, and all that sort.

Have at it... implement away all you like. My code is on the MIT license, you're free to use it however you like, but there is no guarantee it'll work, and no guarantee I'll support you with it.

With that said... sorry, I don't really 'do' tutorials. But I'm happy to answer some questions in my spare time. Note my partner and I are heads down on our current project, but I get breaks every once in a while to come on here and chat.

I'd love to discuss my why I made the choices I did when implementing A* and Dijkstra in that set of classes.

 

Cool thanks for sharing this repository, I’m going to start small and start with a node interface.

The end goal is to have choice of Pathfinding methods on my hex planet.

I contacted Joel the guy who originally implemented it in c++ and asked for permission to use it and write it over to Unity

So the structure I have is pretty much the same as described here.

I’ll try implement INode into HexTile class and work my way out.

https://github.com/joeld42/hexplanet

Joel is a nice guy and answered any question I had so to Joel

Thanks for the reply, I know I will learn heaps from working through you code.

 

Digging in deeper i can see the reusability of all the interfaces and classes. One thing Im struggling to find is where do you actually compute a graphs neighbor? I can see
INode int GetNeighbours(ICollection<T> buffer); to
IGraph int GetNeighbours(T node, ICollection<T> buffer); to
NodeGraph public int GetNeighbours(T node, ICollection<T> buffer).

Since i have a hex-sphere I thought NodeGraph would be the correct type of graph to implement.
So somehow I would have to get my hexSphere.GetNeighbors to the INode ?

Code below is for contex

Code (csharp):

1.  
2.     public class HexTile : INode<HexTile>
3.     {
4.  
5.         //
6.         // Base properties fields methods and constructor
7.         //
8.         #region CONSTRUCTOR
9.  
10.         /// <summary>
11.         /// Constructor
12.         /// </summary>
13.         /// <param name="position">  The worldspace position of the hex </param>
14.         /// <param name="normal">    The notrmal of this hex            </param>
15.         /// </summary>
16.         public HexTile (Vector3 position, Vector3 normal, TerrainType terrainType)
17.         {
18.             // Initilize values and set defaults
19.             _vertPos = position;
20.             _normal = normal;
21.             _hextri = new List<HexTri> ();
22.             _terrain = terrainType;
23.         }
24.  
25.         #endregion
26.  
27.  
28.         private Vector3 _vertPos;
29.         //World position of this hex;
30.         public Vector3 VertPos {
31.             get {
32.                 return _vertPos;
33.             }
34.             set {
35.                 _vertPos = value;
36.             }
37.         }
38.  
39.         private Vector3 _normal;
40.         //Normal of this hex
41.         public Vector3 Normal {
42.             get {
43.                 return _normal;
44.             }
45.             set {
46.                 _normal = value.normalized;
47.             }
48.         }
49.  
50.         private List<HexTri> _hextri;
51.         //Triangle that share this hex
52.         public List<HexTri> Hextri {
53.             get {
54.                 return _hextri;
55.             }
56.             set {
57.                 _hextri = value;
58.             }
59.         }
60.  
61.         private TerrainType _terrain;
62.         //Terrain type of this hex
63.         public TerrainType Terrain {
64.             get {
65.                 return _terrain;
66.             }
67.             set {
68.                 _terrain = value;
69.             }
70.  
71.         }
72.            
73.        // IMPLEMNET INODE GETNEIGHBOURS HERE
74.  
75.     }
76.  
77.  

Code (csharp):

1.  
2.     public class HexSphere
3.     {
4.         /// <summary>
5.         /// HexSphere Constructor
6.         /// </summary>
7.         /// <typeparam int subd_level = 2  > number of times to subdivide      </typeparam>
8.         /// <typeparam int raduis = 10    > the raduis of the hex sphere      </typeparam>
9.         public HexSphere (int subd_level, float raduis)
10.         {    
11.             // Set sphere raduis
12.             _planetRadius = raduis;
13.  
14.             // Build the level 0
15.             BuildLevel0 ();
16.  
17.             // Subdivide until desired level
18.             while (_subdLevel < subd_level) {
19.                 Subdivide (/*trandom, twatery*/);
20.             }
21.  
22.             // Project to spherical shape if we're at level 0
23.             if (subd_level == 0) {
24.                 ProjectToSphere ();
25.             }
26.  
27.         }
28.  
29.  
30.         private int _subdLevel = 0;
31.         // Tracking number of subdivisions. Read only
32.         public int SubdLevel {                                
33.             get{ return _subdLevel; }
34.         }
35.  
36.         private float _planetRadius;
37.         // The sphere raduis. Read only
38.         public float PlanetRadius {                              
39.             get{ return _planetRadius; }
40.         }
41.  
42.         private List<HexTile> _hexes = new List<HexTile> ();
43.         // Data for the hexes. Read only
44.         public List<HexTile> Hexes {                            
45.             get{ return _hexes; }
46.         }
47.  
48.         private List<HexTri> _hexdual = new List<HexTri> ();
49.         // Data for the triangle mesh. Read only
50.         public List<HexTri> Hexdual {                            
51.             get{ return _hexdual; }
52.         }
53.  
54.         public Dictionary<TerrainType, int> _weights = new Dictionary<TerrainType, int>();
55.  
56.  
57.         /// <summary>
58.         /// Builds the level0.
59.         /// </summary>
60.         public void BuildLevel0 ()
61.         {    
62.  
63.             // Hard code an icosahedron (20 sided die) for HexTile
64.             HexTile hexTile = new HexTile (new Vector3 (0.723606f, 0.0f, 1.17082f), new Vector3 (0.723606f, 0.0f, 1.17082f), TerrainType.Terrain_WATER);
65.             _hexes.Add (hexTile);
66.             hexTile = new HexTile (new Vector3 (0.0f, 1.17082f, 0.723606f), new Vector3 (0.0f, 1.17082f, 0.723606f),TerrainType.Terrain_FOREST);
67.             //hexTile.Terrain = GetRandomTerrain();
68.             _hexes.Add (hexTile);
69.             hexTile = new HexTile (new Vector3 (-0.723606f, 0.0f, 1.17082f), new Vector3 (-0.723606f, 0.0f, 1.17082f),TerrainType.Terrain_GRASSLAND);
70.             //hexTile.Terrain = GetRandomTerrain();
71.             _hexes.Add (hexTile);
72.             hexTile = new HexTile (new Vector3 (0.0f, -1.17082f, 0.723606f), new Vector3 (0.0f, -1.17082f, 0.723606f),TerrainType.Terrain_DESERT);
73.             //hexTile.Terrain = GetRandomTerrain();
74.             _hexes.Add (hexTile);
75.             hexTile = new HexTile (new Vector3 (0.723606f, 0.0f, -1.17082f), new Vector3 (0.723606f, 0.0f, -1.17082f),TerrainType.Terrain_WATER);
76.             //hexTile.Terrain = GetRandomTerrain();
77.             _hexes.Add (hexTile);
78.             hexTile = new HexTile (new Vector3 (0.0f, -1.17082f, -0.723606f), new Vector3 (0.0f, -1.17082f, -0.723606f),TerrainType.Terrain_FOREST);
79.             //hexTile.Terrain = GetRandomTerrain();
80.             _hexes.Add (hexTile);
81.             hexTile = new HexTile (new Vector3 (-0.723606f, 0.0f, -1.17082f), new Vector3 (-0.723606f, 0.0f, -1.17082f),TerrainType.Terrain_GRASSLAND);
82.             //hexTile.Terrain = GetRandomTerrain();
83.             _hexes.Add (hexTile);
84.             hexTile = new HexTile (new Vector3 (0.0f, 1.17082f, -0.723606f), new Vector3 (0.0f, 1.17082f, -0.723606f),TerrainType.Terrain_DESERT);
85.             //hexTile.Terrain = GetRandomTerrain();
86.             _hexes.Add (hexTile);
87.             hexTile = new HexTile (new Vector3 (1.17082f, -0.723606f, 0.0f), new Vector3 (1.17082f, -0.723606f, 0.0f),TerrainType.Terrain_MOUNTAIN);
88.             //hexTile.Terrain = GetRandomTerrain();
89.             _hexes.Add (hexTile);
90.             hexTile = new HexTile (new Vector3 (1.17082f, 0.723606f, 0.0f), new Vector3 (1.17082f, 0.723606f, 0.0f),TerrainType.Terrain_MOUNTAIN);
91.             //hexTile.Terrain = GetRandomTerrain();
92.             _hexes.Add (hexTile);
93.             hexTile = new HexTile (new Vector3 (-1.17082f, 0.723606f, 0.0f), new Vector3 (-1.17082f, 0.723606f, 0.0f),TerrainType.Terrain_FOREST);
94.             //hexTile.Terrain = GetRandomTerrain();
95.             _hexes.Add (hexTile);
96.             hexTile = new HexTile (new Vector3 (-1.17082f, -0.723606f, 0.0f), new Vector3 (-1.17082f, -0.723606f, 0.0f),TerrainType.Terrain_WATER);
97.             //hexTile.Terrain = GetRandomTerrain();
98.             _hexes.Add (hexTile);
99.  
100.  
101.             // Hard code an icosahedron (20 sided die) for HexTri
102.             HexTri hexTri = new HexTri (5, 11, 6);                    
103.             _hexdual.Add (hexTri);
104.             hexTri = new HexTri (1, 2, 0);
105.             _hexdual.Add (hexTri);
106.             hexTri = new HexTri (0, 2, 3);
107.             _hexdual.Add (hexTri);
108.             hexTri = new HexTri (5, 6, 4);
109.             _hexdual.Add (hexTri);
110.             hexTri = new HexTri (4, 6, 7);
111.             _hexdual.Add (hexTri);
112.             hexTri = new HexTri (9, 1, 0);
113.             _hexdual.Add (hexTri);
114.             hexTri = new HexTri (10, 2, 1);
115.             _hexdual.Add (hexTri);
116.             hexTri = new HexTri (2, 10, 11);
117.             _hexdual.Add (hexTri);
118.             hexTri = new HexTri (11, 3, 2);
119.             _hexdual.Add (hexTri);
120.             hexTri = new HexTri (8, 9, 0);
121.             _hexdual.Add (hexTri);
122.             hexTri = new HexTri (0, 3, 8);
123.             _hexdual.Add (hexTri);
124.             hexTri = new HexTri (11, 10, 6);
125.             _hexdual.Add (hexTri);
126.             hexTri = new HexTri (4, 7, 9);
127.             _hexdual.Add (hexTri);
128.             hexTri = new HexTri (9, 8, 4);
129.             _hexdual.Add (hexTri);
130.             hexTri = new HexTri (7, 6, 10);
131.             _hexdual.Add (hexTri);
132.             hexTri = new HexTri (1, 9, 7);
133.             _hexdual.Add (hexTri);
134.             hexTri = new HexTri (10, 1, 7);
135.             _hexdual.Add (hexTri);
136.             hexTri = new HexTri (5, 4, 8);
137.             _hexdual.Add (hexTri);
138.             hexTri = new HexTri (3, 11, 5);
139.             _hexdual.Add (hexTri);
140.             hexTri = new HexTri (8, 3, 5);
141.             _hexdual.Add (hexTri);
142.  
143.         }
144.         // BuildLevel0
145.        
146.        
147.         public void GetNeighbors (int tileNdx, ref List<int> nbrs)
148.         {
149.  
150.             //
151.             // Clear list
152.             nbrs.Clear ();
153.  
154.             //
155.             // Check neighbors logic
156.             for (int ti = 0; ti < _hexes [tileNdx].Hextri.Count; ti++) {
157.  
158.                 // HEX A
159.                 if (_hexes [tileNdx].Hextri [ti].HexA != tileNdx && nbrs.IndexOf (_hexes [tileNdx].Hextri [ti].HexA) == -1) {
160.                     nbrs.Add (_hexes [tileNdx].Hextri [ti].HexA);
161.                 }
162.  
163.                 // HEX B
164.                 if (_hexes [tileNdx].Hextri [ti].HexB != tileNdx && nbrs.IndexOf (_hexes [tileNdx].Hextri [ti].HexB) == -1) {
165.                     nbrs.Add (_hexes [tileNdx].Hextri [ti].HexB);
166.                 }
167.  
168.                 // HEX C
169.                 if (_hexes [tileNdx].Hextri [ti].HexC != tileNdx && nbrs.IndexOf (_hexes [tileNdx].Hextri [ti].HexC) == -1) {
170.                     nbrs.Add (_hexes [tileNdx].Hextri [ti].HexC);
171.                 }
172.  
173.             }
174.  
175.         }
176.  
177.  
178.  

 

Actually looking further into the code I see a LinkedNodeGraph class. Since I have 5-6 neighbours is this a better option to use over a heap in the NodeGraph Class ?

I also see that I should not implement INode interface on my HexTile just add my node to the LinkedNodeGraph .. I think

 

A HexGraph exists.

And here is the GetNeighbours from it:
https://github.com/lordofduct/space.../master/SPPathfinding/Graphs/HexGraph.cs#L149

Note, it's a flat hex graph. 'nominalWidth' has to do with the fact that on a 2d hex graph, the height has the same number of tiles as rows. But the width, has 2 different number of nodes depending on the row you're on.

Note how the first row has 1 more node than the second row.

'nominalWidth' is the larger of these two.

Not sure how this would apply to a SphereHexGraph. Though if you need a SphereHexGraph... you should implement one rather than trying to make one of the other Linked graphs to work. The linked ones are slower and take up more memory... but exist for more obtuse graphs (non-grid like).

That's the usefulness of the IGraph interface. You can implement any graph of your likings with the necessary functions. And the path resolver's will use it. Because the path resolvers are built around the idea that all graphs have this set of functions for it to use.

Your custom 'SpherHexGraph' just needs a Count property, and a GetNeightbours function that returns the neighbours of a given node. (2 versions exist, an enumerated one, and one that fills a collection... to save on GC).

This is known as decoupling.

The path resolver doesn't care about the graph or the nodes. The path resolver just does it's job on anything shaped like an 'IGraph'.

And even then we ALSO decouple the path resolver by having them implement 'IPathResolver'. This way you can write a portion of code that is like "I have this random IPathResolver, I also have this random IGraph... I can calculate a path in it and never really care what sort of graph it is, or what algorithm it used".

So say you wrote some AI logic that did pathfinding.

You'd hand it a graph and a pathresolver. And write logic around that. But if down the line you were like "heck, my ai is changing to a new graph type... oh, no need to tweak the code of the ai. It just works!"

 

INode is only used by NodeGraph. Only nodes that go into a nodegraph need to implement INode.

NodeGraph is for the most obtuse/arbitrary of graphs.

So... the reason I call these graphs is because A* and Dijkstra and what all really come from 'graph theory':
https://en.wikipedia.org/wiki/Graph_theory

A graph is a mathematical concept. And doesn't necessarily have to represent a physical map like representation.

It really just represents a branching set of 'things'. Those 'things' could be anything. A graph could for instance represent the abstract concept of a conversational tree for instance. One conversational statement, a 'node', may lead to another, and so on. But 2 different nodes may lead to the same, and another node may loop back around to a previous node after so many steps.

You could represent this conversation tree... or "dialogue tree"... as a graph. And you could apply things like A* or Dijkstra to it.

This would you to create AI that is having a conversation with motive and skill.

So like... the motivation is "AI wants to get to this topic represented at node X" (your target node in A*). And your skill is "The AI's ability to effectively communicate as represented by the cost to get from node A -> B".

Now with this... you can then calculate the most effective conversation an AI should use to get to it's desired out come.

...

And by introducing play choice at each node. Where the player moves the conversation in the graph. The AI can recalculate it's A* path through the conversation to try and get it "back on topic of it's motivated target discussion".

You then end up with what "feels" like a rudimentary conversation with a being that seems to have personality... or at least... has desires. It wants to talk about "cheese", so it's always looking for ways to move the topic towards "cheese".

...

Thing is... this can't be represented as some 'grid graph', or 'hex graph'... it's an abstract multi-dimensional graphs with one way edges (A leads to B, but B does not lead to A).

So the overly generic 'NodeGraph' represents this. It's just a collection you throw INodes into, and those INodes are what report back what neighbours it might have.

...

I should go through and document these graphs.

I just haven't had the time.

Busy busy!

 

Thanks heaps for taking the time to explain it to me I know your are busy. Ok I will start by writing hexSphereGraph to see how I get on. Thanks again, Ill post progress on here

 

Iv started to implement HexSphereGraph. When I build my hexSphere all the hex indicies are return into a list and all the triangle neighbor are tracked , so it relatively easy to get my neighbors.

Here is where im struggling:

1) I dont u understand the 2 versions of GetNeightbours in the IGraph (an enumerated one, and one that fills a collection... to save on GC). I want to ask a more specific question but my knolage gap is so large I cant even do that.

2) Why in HexGraph did you implement IList or in LinkedNodeGraph ICollection.

Here is what i done so far, it a stab at implementing the public IEnumerable<T> GetNeighbours (int index) from IGraph.
Im using a list to check I dont return the same hex (pseudo hex) and I feel there has got to be a better way to do this.
The syntax for the hex is a bit long but I kept it explicit for debugging.

Code (csharp):

1.  
2. using System;
3. using System.Collections;
4. using System.Collections.Generic;
5. using UnityEngine;
6.  
7. using LB.HexSphereBuild;
8.  
9. namespace LB.Pathfinding
10. {
11.    
12.     public class HexSphereGraph<T> : IGraph<T>
13.         where T :  HexTile
14.     {
15.         #region Fields
16.  
17.         private List<T> _hexes;
18.         private List<int> _foundNeighbours = new List<int> ();
19.  
20.         #endregion
21.  
22.  
23.         #region Constructor
24.  
25.         public HexSphereGraph (List<T> hexes)
26.         {
27.             _hexes = hexes;
28.                
29.         }
30.  
31.         #endregion
32.  
33.  
34.         #region Methods
35.  
36.         public IEnumerable<T> GetNeighbours (int index)
37.         {
38.             // Check bounds
39.             if (index < 0 || index == _hexes.Count)
40.                 yield break;
41.  
42.  
43.             // Track Found neighbours indicies
44.             _foundNeighbours.Clear ();
45.  
46.  
47.             // Loop over all triangle in this Hex and match neighbours
48.             for (int ti = 0; ti < _hexes [index].Hextri.Count; ti++) {
49.  
50.  
51.                 // HEX A
52.                 if (_hexes [index].Hextri [ti].HexA != index &&
53.                     _foundNeighbours.IndexOf (_hexes [index].Hextri [ti].HexA) == -1) {
54.                     _foundNeighbours.Add (_hexes [index].Hextri [ti].HexA);
55.                     yield return _hexes [_hexes [index].Hextri [ti].HexA];
56.                 }
57.  
58.  
59.                 // HEX B
60.                 if (_hexes [index].Hextri [ti].HexB != index &&
61.                     _foundNeighbours.IndexOf (_hexes [index].Hextri [ti].HexB) == -1) {
62.                     _foundNeighbours.Add (_hexes [index].Hextri [ti].HexB);
63.                     yield return  _hexes [_hexes [index].Hextri [ti].HexB];
64.                 }
65.  
66.  
67.                 // HEX C
68.                 if (_hexes [index].Hextri [ti].HexC != index &&
69.                     _foundNeighbours.IndexOf (_hexes [index].Hextri [ti].HexC) == -1) {
70.                     _foundNeighbours.Add (_hexes [index].Hextri [ti].HexC);
71.                     yield return  _hexes [_hexes [index].Hextri [ti].HexC];
72.                 }
73.  
74.             }
75.         }
76.  
77.         #endregion
78.  
79.         #region IGraph Interface
80.  
81.         int IGraph<T>.Count {
82.             get { return _hexes.Count; }
83.         }
84.  
85.         #endregion
86.  
87.     }
88.  
89. }
90.  
91.  
92.  
93.  

 

So create an enumerable creates garbage on the heap that will need to be cleaned up. Since a pathfinder may run the pathfinding algorithm rather frequently, and you probably will have several agents on screen calculating their own paths. This garbage will pile up.

Unity uses an older version of mono (they're currently revamping it now in the newest versions of unity). This old version of mono has a naive garbage collector. It's slow, and unity has to pause itself while the collector runs. So sometimes it causes your game to stutter.

By having a version of the function that takes in an ICollection<T>, the pathresolver can create a single collection (a list), and recycle it every time it calls 'GetNeighbours'. It just clears the collection every time it calls it, and then passes it in to the graph to be filled with the new block of neighbours.

This way only one list every exists.

It's similar to how 'Physics.RaycastNonAlloc' takes in an array:
https://docs.unity3d.com/ScriptReference/Physics.RaycastNonAlloc.html

Or GameObject.GetComponents has a version that takes in a List:
https://docs.unity3d.com/ScriptReference/GameObject.GetComponents.html

Note how RaycastNonAlloc returns a count of how many raycasts was found. It nice to know the count of the collection from the method that filled it. This is useful if you didn't empty the collection first, or if the collection you passed hashes like objects (like a HashSet).

HexGraph is a linear collection (it is made of rows and columns). This means the list can be indexed. Indexing is always a nice feature to have since it gives fast access to the list.

Though pathresolver doesn't care if it's indexed, and never accesses it as such. But you might need to use the HexGraph elsewhere as an indexed list. Say you need to change information about a specific node, or some other thing. Well, being able to acccess it by index can be super helpful.

LinkedNodeGraph on the other hand is a branching multidimensional set. This means that it is non-linear and can't be easily indexed. So there's no way to access it by index. So it doesn't implement IList (which represents indexed collections), and just implements the more generic ICollection.

Note that GetNeighbours exists purely for the benefit of a IPathResolver. The rest of the collection stuff is for you to fill and mutate the graph. But GetNeighbours is what is used by a IPathResolver to calculate paths.

And the IPathResolver methods don't access the collection as an indexed list.

Instead it receives starting nodes (as T), goal nodes (as T), and it requests from the graph for neighbours of a node by handing it the current node it is at (a T).

The means you implement these function:

Code (csharp):

1.  
2. IEnumerable<T> GetNeighbours(T node);
3. int GetNeighbours(T node, ICollection<T> buffer);

Note that they take in 'T node' as parameters, not an index.

So you're going to want to take in a node, get the index that node is at, and then get the neighbours of that index via your GetNeighbours(int index) method.

Yeah, you shouldn't be doing this.

1) if you need to use a set to check likeness... use a HashSet, it doesn't allow duplicates or nulls. And it's an O(1) to test if it contains a specific object. Rather than the O(n) performance List has for contains.

2) A hexgraph should only have 6 neighbours. And those neighbours should be unique. You shouldn't have to check if you already selected a neighbour. If I grab the neighbour to my left, and then the one to my right... there's no reason the one on my right is the same as the one on my left. That just shouldn't happen.

If it has... that means you filled your graph in a weird manner. And just let it ride. The graph shouldn't care about that. You messed up filling it... maybe you intended to fill it that way. The resolver will deal with this on its own.

 

Thanks again for your reply, I read over your answers a several times and continues on with the HexSphereGraph.

I used HashSet for my neighbors check, My hexSphere is more of a pseudo hexSphere as implemented in the hex sphere white paper

/// HexTile - A Hextile is a single hex (or sometimes pentagon)
/// in the hex tiled planet. It is a single vertex of the mesh

/// HexTri - A Hextri is an element of the dual of the (mostly) hex tiling
/// This is basically our triangle mesh that we draw hexes on.

(image green is mesh yellow is pseudo hex)


I worked through all your graph example and manage to assemble my hexSphere graph. Not quite working and have some questions to fill my lack of knowledge. I asked the questions in my code below tagging a comment with @LackOfKnowledge. Not rush I know you are busy Ill keep trying to understand it in the mean time.

Thanks Healps

Code (csharp):

1.  
2. using System;
3. using System.Collections;
4. using System.Collections.Generic;
5. using UnityEngine;
6.  
7. using Lightbringer.HexSphereBuild;
8.  
9. namespace Lightbringer.Pathfinding
10. {
11.    
12.     public class HexSphereGraph<T> : IGraph<T>, IList<T>
13.         where T :  HexTile
14.     {
15.        
16.         #region Fields
17.  
18.         private T[] _data;
19.         private HashSet<T> _foundNeighbours = new  HashSet<T> ();
20.         private IEqualityComparer<T> _comparer;
21.  
22.         #endregion
23.  
24.  
25.         #region Constructor
26.  
27.         public HexSphereGraph (List<T> hexes, int numElements)
28.         {
29.             // @LackOfKnowledge,has to be a better way to get list into array
30.             T[] _data = new T[numElements];
31.             _data = hexes.GetRange(0, numElements).ToArray();
32.             // @LackOfKnowledge, what is the default comparer for a generic is it memory location?
33.             _comparer = EqualityComparer<T>.Default;
34.         }
35.  
36.         #endregion
37.  
38.  
39.         #region IList Interface
40.  
41.         public T this[int index]
42.         {
43.             get
44.             {
45.                 return _data[index];
46.             }
47.  
48.             set
49.             {
50.                 _data[index] = value;
51.             }
52.         }
53.  
54.         public int Count
55.         {
56.             get
57.             {
58.                 return _data.Length;
59.             }
60.         }
61.  
62.         // @LackOfKnowledge. Is this the collection to the IEnumerable to the IList ?
63.         // Im not exactly sure how all this is strung together?
64.         bool ICollection<T>.IsReadOnly
65.         {
66.             get
67.             {
68.                 return false;
69.             }
70.         }
71.  
72.  
73.         public int IndexOf(T item)
74.         {
75.             for(int i = 0; i < _data.Length; i++)
76.             {
77.                 if (_comparer.Equals(_data[i], item)) return i;
78.             }
79.             return -1;
80.         }
81.  
82.         public void Clear()
83.         {
84.             Array.Clear(_data, 0, _data.Length);
85.         }
86.  
87.         public bool Contains(T item)
88.         {
89.             for(int i = 0; i < _data.Length; i++)
90.             {
91.                 if (_comparer.Equals(_data[i], item)) return true;
92.             }
93.             return false;
94.         }
95.  
96.         public void CopyTo(T[] array, int arrayIndex)
97.         {
98.             System.Array.Copy(_data, 0, array, arrayIndex, _data.Length);
99.         }
100.  
101.         public bool Remove(T item)
102.         {
103.             if (item == null) return false;
104.  
105.             bool result = false;
106.             for (int i = 0; i < _data.Length; i++)
107.             {
108.                 if (_comparer.Equals(_data[i], item))
109.                 {
110.                     result = true;
111.                     _data[i] = default(T);
112.                 }
113.             }
114.             return result;
115.         }
116.  
117.         public void RemoveAt(int index)
118.         {
119.             _data[index] = default(T);// @LackOfKnowledge, need to understanding on default(T)
120.         }
121.  
122.         // @LackOfKnowledge, Not sure what this is for, is this suppose to add T
123.         // at an index in the collection ?
124.         //
125.         void IList<T>.Insert(int index, T item)
126.         {
127.             throw new System.NotSupportedException();
128.         }
129.         // @LackOfKnowledge , Not sure what this is for, is this suppose to add T
130.         // at into the collection the IEnumerable used and the IList usese ?
131.         // If so do I need to implement this as im using .Add in buffer.Add line 207
132.         // Also using at line 165 but this is on the HashSet<T>
133.         void ICollection<T>.Add(T item)
134.         {
135.             throw new System.NotSupportedException();
136.         }
137.  
138.         #endregion
139.  
140.  
141.         #region IGraph Interface
142.  
143.         int IGraph<T>.Count {
144.             get { return _data.Length; }
145.         }
146.  
147.         public IEnumerable<T> GetNeighbours(T node)
148.         {
149.             if (node == null) throw new ArgumentNullException("node");
150.  
151.             // Check bounds
152.             int index = this.IndexOf(node);      
153.  
154.             if (index < 0 || index == _data.Length)
155.                 yield break;
156.  
157.  
158.             // Track Found neighbours indicies
159.             _foundNeighbours.Clear ();
160.  
161.  
162.             // Loop over all triangle in this Hex and match neighbours
163.             for (int ti = 0; ti < _data [index].Hextri.Count; ti++) {
164.  
165.  
166.                 // HEX A
167.                 if (_data [index].Hextri [ti].HexA != index &&
168.                     _foundNeighbours.Contains (_data [_data [index].Hextri [ti].HexA]) == false) {
169.                     _foundNeighbours.Add (_data [_data [index].Hextri [ti].HexA]);
170.                     yield return _data [_data [index].Hextri [ti].HexA];
171.                 }
172.  
173.  
174.                 // HEX B
175.                 if (_data [index].Hextri [ti].HexB != index &&
176.                     _foundNeighbours.Contains (_data[_data [index].Hextri [ti].HexB]) == false) {
177.                     _foundNeighbours.Add ( _data[_data [index].Hextri [ti].HexB]);
178.                     yield return  _data[_data [index].Hextri [ti].HexB];
179.                 }
180.  
181.  
182.                 // HEX C
183.                 if (_data [index].Hextri [ti].HexC != index &&
184.                     _foundNeighbours.Contains (_data [_data [index].Hextri [ti].HexC]) == false) {
185.                     _foundNeighbours.Add (_data [_data [index].Hextri [ti].HexC]);
186.                     yield return  _data [_data [index].Hextri [ti].HexC];
187.                 }
188.  
189.             }
190.  
191.         }
192.  
193.         public int GetNeighbours(T node, ICollection<T> buffer)
194.         {
195.            
196.             if (node == null) throw new ArgumentNullException("node");
197.             if (buffer == null) throw new ArgumentNullException("buffer");
198.             int index = this.IndexOf(node);
199.  
200.             // For returning the number of neighbours
201.             int cnt = buffer.Count;
202.  
203.  
204.  
205.             // Loop over all triangle in this Hex and match neighbours
206.             for (int ti = 0; ti < _data [index].Hextri.Count; ti++) {
207.  
208.  
209.                 // HEX A
210.                 if (_data [index].Hextri [ti].HexA != index &&
211.                     buffer.Contains (_data [_data [index].Hextri [ti].HexA]) == false) {
212.                     buffer.Add (_data [_data [index].Hextri [ti].HexA]);
213.                 }
214.  
215.  
216.                 // HEX B
217.                 if (_data [index].Hextri [ti].HexB != index &&
218.                     buffer.Contains (_data[_data [index].Hextri [ti].HexB]) == false) {
219.                     buffer.Add ( _data[_data [index].Hextri [ti].HexB]);
220.                 }
221.  
222.  
223.                 // HEX C
224.                 if (_data [index].Hextri [ti].HexC != index &&
225.                     buffer.Contains (_data [_data [index].Hextri [ti].HexC]) == false) {
226.                     buffer.Add (_data [_data [index].Hextri [ti].HexC]);
227.                 }
228.  
229.             }
230.             return buffer.Count - cnt;
231.         }
232.            
233.         #endregion
234.  
235.         //@LackOfKnowledge, how the IEnumerable Interface is implemented is
236.         // still a bit confusing, I think my general understanfing of how
237.         // IEnumerator<T> work is lacking
238.         #region IEnumerable Interface
239.  
240.         //@LackOfKnowledge Creating the struct Emunerator handle?
241.         public Enumerator GetEnumerator()
242.         {
243.             return new Enumerator(this);
244.         }
245.         //@LackOfKnowledge,this syntax is confusing to me is this needed for the
246.         // IEnumerable Interface
247.         IEnumerator IEnumerable.GetEnumerator()
248.         {
249.             return new Enumerator(this);
250.         }
251.         //@LackOfKnowledge, this syntax is confusing is it returing the Emumerator
252.         // from the struct constructor?
253.         IEnumerator<T> IEnumerable<T>.GetEnumerator()
254.         {
255.             return new Enumerator(this);
256.         }
257.  
258.         //@LackOfKnowledge, looks like a handle to private _data and
259.         // what will be used to ittitate over _data?
260.         public struct Enumerator : IEnumerator<T>
261.         {
262.  
263.             private T[] _graph;
264.             private int _index;
265.             private T _current; //@LackOfKnowledge cant track how this is found or tracked
266.  
267.             public Enumerator(HexSphereGraph<T> graph)
268.             {
269.                 if (graph == null) throw new ArgumentNullException("graph");
270.                 _graph = graph._data;
271.                 _index = 0;
272.                 _current = default(T);
273.             }
274.             //@LackOfKnowledge ?
275.             public T Current
276.             {
277.                 get
278.                 {
279.                     return _current;
280.                 }
281.             }
282.             //@LackOfKnowledge ?
283.             object IEnumerator.Current
284.             {
285.                 get
286.                 {
287.                     return _current;
288.                 }
289.             }
290.  
291.             public void Dispose()
292.             {
293.                 _graph = null;
294.                 _index = 0;
295.                 _current = default(T);//@LackOfKnowledge,
296.             }
297.  
298.             public bool MoveNext()
299.             {
300.                 if (_graph == null) return false;
301.                 if (_index >= _graph.Length) return false;
302.  
303.                 _current = _graph[_index];
304.                 _index++;
305.                 return true;
306.             }
307.  
308.             public void Reset()
309.             {
310.                 _index = 0;
311.                 _current = default(T);
312.             }
313.         }
314.  
315.         #endregion
316.  
317.     }
318.  
319. }
320.  
321.  
322.  
323.  
324.  

 

Just a quick question, I have my graph working and ready to run it through the AStarPathResolver. I see the constructor requires a IHeuristic<T> heuristic. Do i need to create a heuristics graph similar to my HexSphereGraph ?

public AStarPathResolver(IGraph<T> graph, IHeuristic<T> heuristic)

 

IHeuristic is what gets the weight of a node, and the estimated distance between 2 nodes.

In the IHeuristic code file I have an implementation that bases it off of the 'Transform' position, which works if your nodes are Transforms:
https://github.com/lordofduct/space...lob/master/SPPathfinding/Graphs/IHeuristic.cs

If that won't work for your nodes. You need to define some heuristic for your graph. A way to calculate (quickly) an estimated distance between 2 nodes.

If you have a way to look up index, the heuristic could be the index difference between 2 nodes. Or you can do point to point distance on a sphere.

Whatever you choose is up to you.

 

Got it , did a rough arch length and it seems to be working. Thanks heaps for all your patience and help

 

Sorry last question, what is the purpose of the ISteppingPathResolver.

 

Stepping path resolver is for if you want to break the resolution up over several frames.

Since resolving a path on a large grid my take a long time, and you might have something in the setup that requires accessing the unity api (like the position of the transform for the heuristic). You can't just thread the thing.

So instead you can start up a coroutine and 'step' the resolver instead.

 

Hey lordofduct,

Ive had a grand time playing around with your repo creating some interesting things. I did want to ask you about your
LinkedNodeGraph template. As far as I can tell it only supports a node having one neighbor or linked node but then I found CountNeighbours(T node). Can a node have multiple links?

Thank so much for your time

 

Yeah, it can have multiple links.

The neighbours are stored as a linked list.

Note the add code, specifically the part I put comments:

Code (csharp):

1.  
2. public void Add(T node, T neighbour, bool oneway = false)
3. {
4.     if (node == null) throw new ArgumentNullException("node");
5.     if (neighbour == null) throw new ArgumentNullException("neighbour");
6.  
7.     NeighbourInfo info = null;
8. //here we check if node already is an entry
9.     if(_entries.TryGetValue(node, out info) && info != null)
10.     {
11. //if it is an entry that means it already has neighbours
12.         while(info != null)
13.         {
14. //loop over the neighbours and check if 'neighbour' is already paired
15.             if (_entries.Comparer.Equals(info.Value, neighbour))
16.             {
17. //it was already added, break now and exit
18.                 break;
19.             }
20.             else if (info.Next == null)
21.             {
22. //otherwise we reached the end of the linked list, insert the new neighbour
23.                 info.Next = new NeighbourInfo()
24.                 {
25.                     Value = neighbour
26.                 };
27.                 break;
28.             }
29.             else
30.             {
31. //otherwise we still haven't found the end of the linked list, keep stepping over the members of the linked list
32.                 info = info.Next;
33.             }
34.         }
35.     }
36.     else
37.     {
38. //node was never a member yet, so this is the first neighbour association. Begin a new linked list
39.         _entries[node] = new NeighbourInfo()
40.         {
41.             Value = neighbour
42.         };
43.     }
44.  
45.     if(!oneway)
46.     {
47.         this.Add(neighbour, node, true);
48.     }
49.     else if(!_entries.ContainsKey(neighbour))
50.     {
51.         _entries.Add(neighbour, null);
52.     }
53. }
54.  

 

Ahh ok, thanks so much for the help !!