[C#] How To Make Waypoints Find Their Neighbors Through Script?

Hi! I'm building a pathfinding system inspired by A*. I can't really follow any tutorials because none of them explain anything so I decided to make my own bare bones version.

Currently I'm stuck. How can I make my way points find their neighbors through the script? Right now I've got it setup in a predefined pattern but I'd be interested in moving it to automatically finding its neighbors.

I've tried a couple of solutions but they were too laggy or just flat out didn't work.

Thanks everyone for your help!

 

Curious, If you google Unity A* you get around 100 millions results Have you seen this asset, for example?

 

No I haven't seen the asset. But I'd like to learn how to use the system itself. I know that A* has plenty of resources but most of them just explain the algorithm and not its implementation, especially into Unity. And if they do go that far into depth they still do not explain why they're doing what they're doing when they code it.

My pathfinding system just needs to find the waypoints Northern, Southern, Western, and Eastern neighbors. My game is 4 directional.

 

How is your A* graph setup? Each node should know about its neighbour nodes by default in any (all?) graph setups.

 

I haven't really gone about making it procedurally generate the graph yet. I suppose I should start with that first?

 

Your A* algorithm shouldn't care about building the graph. That's a separate task from the pathfinding.

A* should be take any graph you pass it, usually with some interface that gets neighbour nodes:

Code (csharp):

1.  
2. public interface IAIGraph : IEnumerable<IAINode>
3. {
4.  
5.     //finds neighbours of 'node' and places them in 'coll'
6.     void GetNeighbors(IAINode node, ICollection coll);
7.  
8. }
9.  

As for creating graphs you can have various kinds. Including kinds that you define the nodes and their neighbours staticly.

But if you want a special dynamic graph you'll probably have an 'UpdateGraph' method on the graph that cycles through all the nodes and uses some algorithm to find nearby nodes.

Critical thing is defining what being a "neighbour" is in calculating this. When harcoded a human just makes a judgement call... but in this your program has to make the judgement call. So maybe a neighbour could be defined as:

"A node with in 2 units with no obstruction between them"

OK... now with that definition, you now need to write code that tests the distance between nodes, and if their is an obstruction.

If the test comes back true... then you label them as neighbours in your 'UpdateGraph' method.

DO NOTE, such a process will probably be slow... so you probably won't want to be running it often. Or only run it on localized nodes. Like maybe have an 'UpdateGraphNode(IAINode node)' method that strips that node of all relationships and then re-establishes all relationships for that node. So this way you only update a single node if and only if it's moved for whatever reason.

 

In which case just throw the whole thing in a 2D array.