My really inefficient getter method

[kittik]

I have successfully implemented the Dijkstra algorithm to allow pathfinding on a Hexagonal grid, however, I am using a function at the very end to pass the next node in a path.

To do this, I am checking every single node, which is causing lag and is really sloppy. How can I better go about passing the next node in the chain than the below code?

public HexID PathToHexagon(int x, int z)
    {
        HexID nextHex = null;
        for(int i = 0; i < everyHexagon.Count; i++)
        {
            if(everyHexagon[i].idX == x)
            {
                if(everyHexagon[i].idZ == z)
                {
                    nextHex = everyHexagon[i];
                    break;
                }
            }
        }

        return nextHex;
    }

everyHexagon is stored in a List of Hex components and is added to when the grid is generated.

Thanks for the support.

[Malleck666]

public HexID PathToHexagon(int x, int z){
    HexID nextHex = everyHexagon.Find( hex => hex.idX == x && hex.idZ == z);
    return nextHex;
}

Something like that?

[kittik]

Thank you @Malleck666 that’s really helped ^^

[Malleck666]

@kittik

Thank you @Malleck666 that’s really helped ^^

No problem. Note that I missed out the return in my answer. I will amend that.

[lordofduct]

Honestly, Malleck666’s example is effectively the same exact algorithm. So will perform roughly the same… and technically will be even slower since it requires creating the delegate and iterating and calling said delegate.

First and foremost, you should be storing your HexGraph in a manner that can easily be accessed by index.

For example here is a HexGraph:

We can number the rows as following:

Note that the even rows are of length N, and the odd rows of length N - 1 (in this case 15 and 14 respectively).

I will refer to this row length as ‘nominal width’.

There’s a few basic formulas to convert this to a 1d array (or List) if we numbered the indices starting in the upper left and working right, and down.

The length of any 2 rows is (nominalWidth * 2 - 1), and from this we can work out the total length as Ceil(doubleWidth * rowCount / 2).

From any given row and rowIndex we can work out the index in the array as:
if even row = doubleWidth * row / 2 + rowIndex
if odd row = doubleWidth * (row - 1) / 2 + nominalWidth + rowIndex

And lastly there are 6 neighbours:
index - nominalWidth
index - nominalWidth + 1
index - 1
index + 1
index + nominalWidth - 1
index + nominalWidth

Here you can see my implement all of this into its own collection:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace com.spacepuppy.Graphs
{
    public class HexGraph<T> : IGraph<T>, IList<T>
    {

        #region Fields

        private int _rowCount;
        private int _nominalWidth;
        private int _doubleWidth;
        private T[] _data;
        private IEqualityComparer<T> _comparer;

        #endregion

        #region CONSTRUCTOR

        public HexGraph(int rowCount, int nominalWidth)
        {
            _rowCount = rowCount;
            _nominalWidth = nominalWidth;
            _doubleWidth = _nominalWidth + _nominalWidth - 1;
            int cnt = (int)Math.Ceiling((double)_doubleWidth * (double)rowCount / 2d);
            _data = new T[Math.Max(cnt, 0)];
            _comparer = EqualityComparer<T>.Default;
        }

        public HexGraph(int rowCount, int nominalWidth, IEqualityComparer<T> comparer)
        {
            _rowCount = rowCount;
            _nominalWidth = nominalWidth;
            _doubleWidth = _nominalWidth + _nominalWidth - 1;
            int cnt = (int)Math.Ceiling((double)_doubleWidth * (double)rowCount / 2d);
            _data = new T[Math.Max(cnt, 0)];
            _comparer = comparer ?? EqualityComparer<T>.Default;
        }

        #endregion

        #region Properties

        public int RowCount
        {
            get { return _rowCount; }
        }

        public int NominalWidth
        {
            get { return _nominalWidth; }
        }

        public T this[int row, int index]
        {
            get
            {
                if (row % 2 == 0)
                {
                    //if even row
                    return _data[(_doubleWidth * row / 2) + index];
                }
                else
                {
                    //if odd row
                    return _data[(_doubleWidth * (row - 1) / 2) + _nominalWidth + index];
                }
            }
            set
            {
                if (row % 2 == 0)
                {
                    //if even row
                    _data[(_doubleWidth * row / 2) + index] = value;
                }
                else
                {
                    //if odd row
                    _data[(_doubleWidth * (row - 1) / 2) + _nominalWidth + index] = value;
                }
            }
        }

        #endregion

        #region Methods

        public IEnumerable<T> GetNeighbours(int row, int index)
        {
            if (row % 2 == 0)
            {
                //if even row
                return this.GetNeighbours((_doubleWidth * row / 2) + index);
            }
            else
            {
                //if odd row
                return this.GetNeighbours((_doubleWidth * (row - 1) / 2) + _nominalWidth + index);
            }
        }

        public int GetNeighbours(int row, int index, ICollection<T> buffer)
        {
            if (row % 2 == 0)
            {
                //if even row
                return this.GetNeighbours((_doubleWidth * row / 2) + index, buffer);
            }
            else
            {
                //if odd row
                return this.GetNeighbours((_doubleWidth * (row - 1) / 2) + _nominalWidth + index, buffer);
            }
        }

        public IEnumerable<T> GetNeighbours(int index)
        {
            if (index < 0 || index >= _data.Length) yield break;

            int row = index / _doubleWidth;
            int rowIndex = index % _doubleWidth;
            if (rowIndex >= _nominalWidth)
            {
                row++;
                rowIndex -= _nominalWidth;
            }
            int rowWidth = (row % 2 == 0) ? _nominalWidth : _nominalWidth - 1;

            int low = _nominalWidth - 1;
            int high = _nominalWidth;
            int i;

            i = index - high;
            if (i >= 0) yield return _data[i];
            i = index - low;
            if (i >= 0) yield return _data[i];
            if (rowIndex > 0) yield return _data[index - 1];
            if (rowIndex < rowWidth - 1) yield return _data[index + 1];
            i = index + low;
            if (i < _data.Length) yield return _data[i];
            i = index + high;
            if (i < _data.Length) yield return _data[i];
        }

        public int GetNeighbours(int index, ICollection<T> buffer)
        {
            if (buffer == null) throw new ArgumentNullException("buffer");
            if (index < 0 || index >= _data.Length) return 0;

            int row = index / _doubleWidth;
            int rowIndex = index % _doubleWidth;
            if (rowIndex >= _nominalWidth)
            {
                row++;
                rowIndex -= _nominalWidth;
            }
            int rowWidth = (row % 2 == 0) ? _nominalWidth : _nominalWidth - 1;

            int low = _nominalWidth - 1;
            int high = _nominalWidth;
            int i;
            int cnt = 0;

            i = index - high;
            if (i >= 0)
            {
                cnt++;
                buffer.Add(_data[i]);
            }
            i = index - low;
            if (i >= 0)
            {
                cnt++;
                buffer.Add(_data[i]);
            }
            if (rowIndex > 0)
            {
                cnt++;
                buffer.Add(_data[index - 1]);
            }
            if (rowIndex < rowWidth - 1)
            {
                cnt++;
                buffer.Add(_data[index + 1]);
            }
            i = index + low;
            if (i < _data.Length)
            {
                cnt++;
                buffer.Add(_data[i]);
            }
            i = index + high;
            if (i < _data.Length)
            {
                cnt++;
                buffer.Add(_data[i]);
            }

            return cnt;
        }

        private void GetCoords(int index, out int row, out int rowIndex)
        {
            row = index / _doubleWidth;
            rowIndex = index % _doubleWidth;
            if (rowIndex >= _nominalWidth)
            {
                row++;
                rowIndex -= _nominalWidth;
            }
        }

        #endregion

        #region IList Interface

        public T this[int index]
        {
            get
            {
                return _data[index];
            }

            set
            {
                _data[index] = value;
            }
        }

        public int Count
        {
            get
            {
                return _data.Length;
            }
        }

        bool ICollection<T>.IsReadOnly
        {
            get
            {
                return false;
            }
        }


        public int IndexOf(T item)
        {
            for (int i = 0; i < _data.Length; i++)
            {
                if (_comparer.Equals(_data[i], item)) return i;
            }
            return -1;
        }

        public void Clear()
        {
            Array.Clear(_data, 0, _data.Length);
        }

        public bool Contains(T item)
        {
            for (int i = 0; i < _data.Length; i++)
            {
                if (_comparer.Equals(_data[i], item)) return true;
            }
            return false;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            System.Array.Copy(_data, 0, array, arrayIndex, _data.Length);
        }

        public bool Remove(T item)
        {
            if (item == null) return false;

            bool result = false;
            for (int i = 0; i < _data.Length; i++)
            {
                if (_comparer.Equals(_data[i], item))
                {
                    result = true;
                    _data[i] = default(T);
                }
            }
            return result;
        }

        public void RemoveAt(int index)
        {
            _data[index] = default(T);
        }

        void IList<T>.Insert(int index, T item)
        {
            throw new System.NotSupportedException();
        }

        void ICollection<T>.Add(T item)
        {
            throw new System.NotSupportedException();
        }

        #endregion

        #region IGraph Interface

        int IGraph<T>.Count
        {
            get { return _data.Length; }
        }

        public IEnumerable<T> GetNeighbours(T node)
        {
            if (node == null) throw new ArgumentNullException("node");

            int index = this.IndexOf(node);
            if (index < 0) return Enumerable.Empty<T>();
           
            return this.GetNeighbours(index);
        }

        public int GetNeighbours(T node, ICollection<T> buffer)
        {
            if (buffer == null) throw new ArgumentNullException("buffer");

            int index = this.IndexOf(node);
            if (index < 0) return 0;
           
            return this.GetNeighbours(index, buffer);
        }

        #endregion

        #region IEnumerable Interface

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return new Enumerator(this);
        }

        public struct Enumerator : IEnumerator<T>
        {

            private T[] _graph;
            private int _index;
            private T _current;

            public Enumerator(HexGraph<T> graph)
            {
                if (graph == null) throw new ArgumentNullException("graph");
                _graph = graph._data;
                _index = 0;
                _current = default(T);
            }

            public T Current
            {
                get
                {
                    return _current;
                }
            }

            object IEnumerator.Current
            {
                get
                {
                    return _current;
                }
            }

            public void Dispose()
            {
                _graph = null;
                _index = 0;
                _current = default(T);
            }

            public bool MoveNext()
            {
                if (_graph == null) return false;
                if (_index >= _graph.Length) return false;

                _current = _graph[_index];
                _index++;
                return true;
            }

            public void Reset()
            {
                _index = 0;
                _current = default(T);
            }
        }

        #endregion

    }
}

[lordofduct]

Note the above stuff I covered is intended to be used in an abstracted implementation of Dijkstra (or other algorithm like A*).

Example of that following:

First the definition of a graph, IGraph:

    public interface IGraph<T> : IEnumerable<T>
    {

        int Count { get; }

        IEnumerable<T> GetNeighbours(T node);
        int GetNeighbours(T node, ICollection<T> buffer);

    }

spacepuppy-unity-framework/SpacepuppyBase/Graphs/IGraph.cs at master · lordofduct/spacepuppy-unity-framework · GitHub

And a definition of a heuristic for checking distance:

    public interface IHeuristic<T>
    {
        float Weight(T n);
        float Distance(T x, T y);
    }

spacepuppy-unity-framework/SpacepuppyBase/Graphs/IHeuristic.cs at master · lordofduct/spacepuppy-unity-framework · GitHub

And this is all used by IPathResolver (like Dijkstra):

    public interface IPathResolver<T>
    {

        T Start { get; set; }
        T Goal { get; set; }

        IList<T> Reduce();
        int Reduce(IList<T> path);

    }

spacepuppy-unity-framework/SpacepuppyBase/Graphs/IPathResolver.cs at master · lordofduct/spacepuppy-unity-framework · GitHub

And for an example of Dijkstra, here is the Dijkstra implementation of IPathResolver:
spacepuppy-unity-framework/SpacepuppyBase/Graphs/DijkstraPathResolver.cs at master · lordofduct/spacepuppy-unity-framework · GitHub

Note DijkstraPathResolver is ambiguous of the graph. You could pass in any sort of graph like a…

GridGraph - a 2d grid of nodes:
spacepuppy-unity-framework/SpacepuppyBase/Graphs/GridGraph.cs at master · lordofduct/spacepuppy-unity-framework · GitHub

LinkedNodeGraph - an arbitrary linking of nodes, like that of an abstract graph you’d work on in Graph Theory:
spacepuppy-unity-framework/SpacepuppyBase/Graphs/LinkedNodeGraph.cs at master · lordofduct/spacepuppy-unity-framework · GitHub

Or the aforementioned HexGraph example I gave in the previous post.

All Dijkstra cares about is being able to get a list of all neighbours for a given node, and how to measure the distance (heuristic) between 2 nodes, as well as a given nodes weight (if any). That’s it.

[Malleck666]

@lordofduct

Honestly, Malleck666’s example is effectively the same exact algorithm. So will perform roughly the same… and technically will be even slower since it requires creating the delegate and iterating and calling said delegate.

First and foremost, you should be storing your HexGraph in a manner that can easily be accessed by index.

For example here is a HexGraph:

We can number the rows as following:

Note that the even rows are of length N, and the odd rows of length N - 1 (in this case 15 and 14 respectively).

I will refer to this row length as ‘nominal width’.

There’s a few basic formulas to convert this to a 1d array (or List) if we numbered the indices starting in the upper left and working right, and down.

The length of any 2 rows is (nominalWidth * 2 - 1), and from this we can work out the total length as Ceil(doubleWidth * rowCount / 2).

From any given row and rowIndex we can work out the index in the array as:
if even row = doubleWidth * row / 2 + rowIndex
if odd row = doubleWidth * (row - 1) / 2 + nominalWidth + rowIndex

And lastly there are 6 neighbours:
index - nominalWidth
index - nominalWidth + 1
index - 1
index + 1
index + nominalWidth - 1
index + nominalWidth

Here you can see my implement all of this into its own collection:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace com.spacepuppy.Graphs
{
    public class HexGraph<T> : IGraph<T>, IList<T>
    {

        #region Fields

        private int _rowCount;
        private int _nominalWidth;
        private int _doubleWidth;
        private T[] _data;
        private IEqualityComparer<T> _comparer;

        #endregion

        #region CONSTRUCTOR

        public HexGraph(int rowCount, int nominalWidth)
        {
            _rowCount = rowCount;
            _nominalWidth = nominalWidth;
            _doubleWidth = _nominalWidth + _nominalWidth - 1;
            int cnt = (int)Math.Ceiling((double)_doubleWidth * (double)rowCount / 2d);
            _data = new T[Math.Max(cnt, 0)];
            _comparer = EqualityComparer<T>.Default;
        }

        public HexGraph(int rowCount, int nominalWidth, IEqualityComparer<T> comparer)
        {
            _rowCount = rowCount;
            _nominalWidth = nominalWidth;
            _doubleWidth = _nominalWidth + _nominalWidth - 1;
            int cnt = (int)Math.Ceiling((double)_doubleWidth * (double)rowCount / 2d);
            _data = new T[Math.Max(cnt, 0)];
            _comparer = comparer ?? EqualityComparer<T>.Default;
        }

        #endregion

        #region Properties

        public int RowCount
        {
            get { return _rowCount; }
        }

        public int NominalWidth
        {
            get { return _nominalWidth; }
        }

        public T this[int row, int index]
        {
            get
            {
                if (row % 2 == 0)
                {
                    //if even row
                    return _data[(_doubleWidth * row / 2) + index];
                }
                else
                {
                    //if odd row
                    return _data[(_doubleWidth * (row - 1) / 2) + _nominalWidth + index];
                }
            }
            set
            {
                if (row % 2 == 0)
                {
                    //if even row
                    _data[(_doubleWidth * row / 2) + index] = value;
                }
                else
                {
                    //if odd row
                    _data[(_doubleWidth * (row - 1) / 2) + _nominalWidth + index] = value;
                }
            }
        }

        #endregion

        #region Methods

        public IEnumerable<T> GetNeighbours(int row, int index)
        {
            if (row % 2 == 0)
            {
                //if even row
                return this.GetNeighbours((_doubleWidth * row / 2) + index);
            }
            else
            {
                //if odd row
                return this.GetNeighbours((_doubleWidth * (row - 1) / 2) + _nominalWidth + index);
            }
        }

        public int GetNeighbours(int row, int index, ICollection<T> buffer)
        {
            if (row % 2 == 0)
            {
                //if even row
                return this.GetNeighbours((_doubleWidth * row / 2) + index, buffer);
            }
            else
            {
                //if odd row
                return this.GetNeighbours((_doubleWidth * (row - 1) / 2) + _nominalWidth + index, buffer);
            }
        }

        public IEnumerable<T> GetNeighbours(int index)
        {
            if (index < 0 || index >= _data.Length) yield break;

            int row = index / _doubleWidth;
            int rowIndex = index % _doubleWidth;
            if (rowIndex >= _nominalWidth)
            {
                row++;
                rowIndex -= _nominalWidth;
            }
            int rowWidth = (row % 2 == 0) ? _nominalWidth : _nominalWidth - 1;

            int low = _nominalWidth - 1;
            int high = _nominalWidth;
            int i;

            i = index - high;
            if (i >= 0) yield return _data[i];
            i = index - low;
            if (i >= 0) yield return _data[i];
            if (rowIndex > 0) yield return _data[index - 1];
            if (rowIndex < rowWidth - 1) yield return _data[index + 1];
            i = index + low;
            if (i < _data.Length) yield return _data[i];
            i = index + high;
            if (i < _data.Length) yield return _data[i];
        }

        public int GetNeighbours(int index, ICollection<T> buffer)
        {
            if (buffer == null) throw new ArgumentNullException("buffer");
            if (index < 0 || index >= _data.Length) return 0;

            int row = index / _doubleWidth;
            int rowIndex = index % _doubleWidth;
            if (rowIndex >= _nominalWidth)
            {
                row++;
                rowIndex -= _nominalWidth;
            }
            int rowWidth = (row % 2 == 0) ? _nominalWidth : _nominalWidth - 1;

            int low = _nominalWidth - 1;
            int high = _nominalWidth;
            int i;
            int cnt = 0;

            i = index - high;
            if (i >= 0)
            {
                cnt++;
                buffer.Add(_data[i]);
            }
            i = index - low;
            if (i >= 0)
            {
                cnt++;
                buffer.Add(_data[i]);
            }
            if (rowIndex > 0)
            {
                cnt++;
                buffer.Add(_data[index - 1]);
            }
            if (rowIndex < rowWidth - 1)
            {
                cnt++;
                buffer.Add(_data[index + 1]);
            }
            i = index + low;
            if (i < _data.Length)
            {
                cnt++;
                buffer.Add(_data[i]);
            }
            i = index + high;
            if (i < _data.Length)
            {
                cnt++;
                buffer.Add(_data[i]);
            }

            return cnt;
        }

        private void GetCoords(int index, out int row, out int rowIndex)
        {
            row = index / _doubleWidth;
            rowIndex = index % _doubleWidth;
            if (rowIndex >= _nominalWidth)
            {
                row++;
                rowIndex -= _nominalWidth;
            }
        }

        #endregion

        #region IList Interface

        public T this[int index]
        {
            get
            {
                return _data[index];
            }

            set
            {
                _data[index] = value;
            }
        }

        public int Count
        {
            get
            {
                return _data.Length;
            }
        }

        bool ICollection<T>.IsReadOnly
        {
            get
            {
                return false;
            }
        }


        public int IndexOf(T item)
        {
            for (int i = 0; i < _data.Length; i++)
            {
                if (_comparer.Equals(_data[i], item)) return i;
            }
            return -1;
        }

        public void Clear()
        {
            Array.Clear(_data, 0, _data.Length);
        }

        public bool Contains(T item)
        {
            for (int i = 0; i < _data.Length; i++)
            {
                if (_comparer.Equals(_data[i], item)) return true;
            }
            return false;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            System.Array.Copy(_data, 0, array, arrayIndex, _data.Length);
        }

        public bool Remove(T item)
        {
            if (item == null) return false;

            bool result = false;
            for (int i = 0; i < _data.Length; i++)
            {
                if (_comparer.Equals(_data[i], item))
                {
                    result = true;
                    _data[i] = default(T);
                }
            }
            return result;
        }

        public void RemoveAt(int index)
        {
            _data[index] = default(T);
        }

        void IList<T>.Insert(int index, T item)
        {
            throw new System.NotSupportedException();
        }

        void ICollection<T>.Add(T item)
        {
            throw new System.NotSupportedException();
        }

        #endregion

        #region IGraph Interface

        int IGraph<T>.Count
        {
            get { return _data.Length; }
        }

        public IEnumerable<T> GetNeighbours(T node)
        {
            if (node == null) throw new ArgumentNullException("node");

            int index = this.IndexOf(node);
            if (index < 0) return Enumerable.Empty<T>();
          
            return this.GetNeighbours(index);
        }

        public int GetNeighbours(T node, ICollection<T> buffer)
        {
            if (buffer == null) throw new ArgumentNullException("buffer");

            int index = this.IndexOf(node);
            if (index < 0) return 0;
          
            return this.GetNeighbours(index, buffer);
        }

        #endregion

        #region IEnumerable Interface

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return new Enumerator(this);
        }

        public struct Enumerator : IEnumerator<T>
        {

            private T[] _graph;
            private int _index;
            private T _current;

            public Enumerator(HexGraph<T> graph)
            {
                if (graph == null) throw new ArgumentNullException("graph");
                _graph = graph._data;
                _index = 0;
                _current = default(T);
            }

            public T Current
            {
                get
                {
                    return _current;
                }
            }

            object IEnumerator.Current
            {
                get
                {
                    return _current;
                }
            }

            public void Dispose()
            {
                _graph = null;
                _index = 0;
                _current = default(T);
            }

            public bool MoveNext()
            {
                if (_graph == null) return false;
                if (_index >= _graph.Length) return false;

                _current = _graph[_index];
                _index++;
                return true;
            }

            public void Reset()
            {
                _index = 0;
                _current = default(T);
            }
        }

        #endregion

    }
}

@lordofduct , great solution and close to something I have used myself for a hex grid setup. I am aware my solution is functionally similar to the original as I thought the OP was looking for a “tidier” solution I am sure the OP appreciates this much information from you, however!

[kittik]

Thank you also @lordofduct . Your solution and explaination is really detailed! I will impliment this and let you know how I get on