find neighboring nodes A *

Unity Engine
1

I’m trying to implement the A * algorithm to find the nodes closest to a given node, I used the same function as I did to make a maze. In practice you see if neighboring nodes are walkable. I came up with this. How could I do?

void AddNears(Cell currentCell)
    {


        int currentRow = (currentCell.current / xSize) + 1;
        int eastLimited = currentCell.current % xSize;
        int westLimited = currentCell.current % xSize;
        int southLimited = xSize - 1;
        int northLimited = currentCell.current / xSize;



        //East
        if (eastLimited != xSize - 1)
        {
            if (cells[currentCell.current + 1].isVisited == false)
                neighboringCell.Add(cells[currentCell.current + 1]);

        }
        //West
        if (westLimited != 0)
        {
            if (cells[currentCell.current - 1].isVisited == false)
                neighboringCell.Add(cells[currentCell.current - 1]);
           
        }
        //South
        if (currentCell.current > southLimited)
        {
            if (cells[currentCell.current - xSize].isVisited == false)
                neighboringCell.Add(cells[currentCell.current - xSize]);
           
        }
        //North
        if (northLimited != ySize - 1)
        {
            if (cells[currentCell.current + xSize].isVisited == false)
                neighboringCell.Add(cells[currentCell.current + xSize]);
           
        }
    }
2

So A* is an algorithm that should be able to traverse any graph of nodes.

The graph is what hands back the ‘neighbours’. A* is independent of this.

So how are you representing this graph?

Personally I would probably create some object identity for the graph… probably with some interface so that I can easily change the sorts of graphs I have. Here’s an example with a square grid graph (which appears to be what you’re doing).

public interface INode
{
    float Weight { get;set; }
}

public interface IGraph
{
    IEnumerable<INode> GetAllNodes();
    IEnumerable<INode> GetNeighbours(INode node);
    float Distance(INode a, INode b);
}

public class GridGraph : IGraph
{

    private int _w;
    private int _h;
    private INode[] _nodes;

    public GridGraph(int w, int h)
    {
        _w = w;
        _h = h;
        _nodes = new INode[_w * _h];
    }

    public INode this[int i, int j]
    {
        get
        {
            if (i < 0 || i >= _w) throw new System.IndexOutOfRangeException();
            if (j < 0 || j >= _h) throw new System.IndexOutOfRangeException();
            return _nodes[j * _w + i];
        }
        set
        {
            if (i < 0 || i >= _w) throw new System.IndexOutOfRangeException();
            if (j < 0 || j >= _h) throw new System.IndexOutOfRangeException();
            _nodes[j * _w + i] = value;
        }
    }

    public IEnumerable<INode> GetAllNodes()
    {
        return _nodes;
    }

    public IEnumerable<INode> GetNeighbours(INode node)
    {
        var index = System.Array.IndexOf(_nodes, node);
        if(index < 0) yield break;

        int i = index % _w;
        int j = index / _w;
        if(j > 0) yield return this[i, j-1];
        if(i < _w - 1) yield return this[i+1,j];
        if(j < _h - 1) yield return this[i,j + 1];
        if(i > 0) yield return this[i-1, j];
    }

    public float Distance(INode a, INode b)
    {
        throw new System.NotImplementedException();
    }

}
1 Like
3

do you think my method right?

4

Well you didn’t share all the code, there are several variables in that example that are scoped outside the function. I have no idea who can access them, and how their state is maintained. This makes me especially concerned that neighboringCell is possibly bloated or at least compromised.

Furthermore this appears to just ‘AddNears’, there’s no logic beyond that.

And I find it rather adhoc and unable to grow or expand.

5

I personally prefer to have the nodes aware of their own neighbours, and traverse the graph this way.

Of course when building the nodes you have to pass the neighbours in from somewhere. So you often need a graph of some sort anyway.

6

If you just want to find the node closest to a given node, why are you using pathfinding? Do you also want to find the closest path to given node? if not; just calculate the distance between the nodes and compare it will be faster

7

I should calculate if the distance between the current node and its neighbors is equal to 1?

8

No but, you say you want to “find the nodes closest to a given node”. If all the nodes have a position; (x,y) or (x,y,z) in 3D then if you compare the distance of your node with all the rest the smallest result will yield the closest nodes! This is a bad implementation if you have many nodes but that could be easily fixed with a tree structure. (octree or quadtree for example in the 3D case.) I just dont see why you use pathfinding thats all.