[C#] Implementing A* Pathfinding To A Graph - How Do I Begin!?

Hey guys, so I've been posting for a lot of help lately for my pathfinding system. I got a grid to generate, now I just need to implement the actual A* algorithm. I've found plenty of great resources to learn the algorithm itself but I haven't found too many to actually help with implementing it. The only thing I've found is a YouTube series and it isn't too helpful in itself.

I find that right now the hardest thing I'm having trouble with is the fact that I don't really know how to begin. Once I get the ball rolling I can usually figure it out with time but I haven't gotten to that point. I'm using this tutorial. I understand how the algorithm is supposed to go through all of the nodes based on the F cost, but how do I go about generating the H cost? I know it mentioned the Manhattan Block method but how do I go about doing that when it comes to code?

Thanks guys. I really appreciate the help.

 

Code (CSharp):

1. int GenerateHCost()
2.     {
3.  
4.         int hCost;
5.         int hCostY;
6.         int hCostX;
7.  
8.         //x = difference
9.         //y = end node
10.         //z = start node
11.         //x = y - z <-- gives hCost
12.         hCostY = Mathf.RoundToInt(endPos.y - startPos.y);
13.         hCostX = Mathf.RoundToInt(endPos.x - startPos.x);
14.  
15.         hCost = (hCostX + hCostY) * 10;
16.  
17.         return hCost;
18.  
19.     }

I threw this together wondering if this might be what I need to start with. endPos and startPos are just two Vector2's that I'm going to load with the player and enemy node positions from the 2D array.

 

HCost is the heuristic

The heuristic is a guessed distance between 2 nodes (not just start and finish).

You want your heuristic to be fast... preferrably faster than the actual distance which requires a square root. For example you can do the squared distance, or the manhattan distance (named for following a grid distance, like traveling the streets of manhattan).

Code (csharp):

1.  
2. public float ManhattanHeuristic(Vector2 a, Vector2 b)
3. {
4.     return Mathf.Abs(b.x - a.x) + Mathf.Abs(b.y - a.y);
5. }
6.  

Here is an old implementation of A* I did like 10 years ago when I first started programming in Actionscript 3. My copy of the code has been lost, but surprisingly someone forked it into github when googlecode went down.

https://github.com/ToasTyyyyyy/lodgamebox/tree/master/com/lordofduct/engines/ai

In it you can see the 3 generic heuristics I wrote:
https://github.com/ToasTyyyyyy/lodgamebox/blob/master/com/lordofduct/engines/ai/Heuristics.as

Of course other heuristics exist.

Feel free to dig around that library if you want... but do note it was all me just trying to learn, so a lot of it could be rather naive/buggy. But for someone also just learning, it could be helpful to see it from that perspective.



[edit]

HEH, I used that same tutorial when I wrote the one I linked... kek.

 

So would the system i wrote last night no work?

 

no idea, don't know what you wrote

 

I guess I posted it while you were typing your reply.

1. int GenerateHCost()
2. {
3. 
   
4. int hCost;
5. int hCostY;
6. int hCostX;
7. 
   
8. //x = difference
9. //y = end node
10. //z = start node
11. //x = y - z <-- gives hCost
12. hCostY = Mathf.RoundToInt(endPos.y - startPos.y);
13. hCostX = Mathf.RoundToInt(endPos.x - startPos.x);
14. 
    
15. hCost = (hCostX + hCostY) * 10;
16. 
    
17. return hCost;
18. 
    
19. }

Would this be similar to what you wrote? Sorry if this may sound dull, but the vocabulary you used sort of threw me off. I'm not entirely sure what you meant by a heuristic and making it "faster than the actual distance"

 

not exactly, especially since you floor off any decimal value, and I'm not sure why you scale by 10 either...

Furthermore, that method only calculates the hcost between start and end... it needs to take parameters so that it can calculate the hcost between any 2 nodes.

You'll be calculating the heuristic between several nodes as you loop over the grid.

 

The Wikipedia psuedocode implementation is a decent place to start.

https://en.m.wikipedia.org/wiki/A*_search_algorithm

It's also worth reading how and why it works.

 

So if I'm understanding this right, I need to add parameters to my code and have it regenerate the H cost for every node it explores? I'll try to read into your code, hopefully it will bring a new light to me. Thanks!

I'll read that today. Thanks for the tip.