2D AI Pathfinding - Without Mesh (?)

Hello,

I have zero experience with AI pathfinding and would like to learn. Currently I haven't found any tutorials etc I understand for 2D. I'm also not using Mesh, and all tutorials I find is about NavMesh and using 3d Physics / Mesh.

I tried already finished scripts, but even if I did manage to make it work - It's hard to grasp and I want to learn myself as I don't like having solutons I barely understand in my game incase I have to tweak it later.

Any advice would be appriciated!

 

Hi @Loff

Google for A* pathfinding.

There are many tutorials and implementations available.

You can use it on rectangular tilemaps and on arbitrary navigation graphs, and in many other ways.

 

Yes, I started from scratch and learnt the very basics of A* pathfinding. The idea of looping through nodes and checking neighbours for the cost of each step (while leaning towards the most likely line towards the target). There are many tutorials on Youtube & Google.

For my game, I had a 2D array in the code (based on the tilemap ground/wall tiles) which I used for the calculations. I'm amazed at how instantly it finds routes through quite complex, large environments - and I'm actually quite proud that I did it without needing to download any assets!

When I first looked at the challenge, like you I was a tad overwhelmed initially, but just stick at it. Once it clicks, you'll suddenly start making real progress.

 

Thanks for the tips. I started following Sebastian Lague's youtube tutorials about A*, and I learned a lot!
I manage to make almost everything work for my game, but I have just one issue I can't solve.
The code between // ---> and // <---- is for 3D space, and I can't manage to make it work for 2D.
I tried Ray2D, Physics2D etc, but I don't know what vars to use in the Physics2D.RayCast from the script below. I have used Physics2D.RayCast before, I just don't know what vars from the script below to use really.
If anyone would give a hand that would be awesome

Spoiler

Code (CSharp):

1.  void CreateGrid()
2.     {
3.         grid = new Node[gridSizeX, gridSizeY];
4.         Vector3 worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x/2 - Vector3.up * gridWorldSize.y/2; //vector forward ?
5.         for (int x = 0; x < gridSizeX; x++) {
6.             for (int y = 0; y < gridSizeY; y++) {
7.                 Vector3 worldPoint = worldBottomLeft + Vector3.right * (x * nodeDiameter + nodeRadius) + Vector3.up * (y * nodeDiameter + nodeRadius);
8.                 bool walkable = !(Physics2D.OverlapCircle(worldPoint, nodeRadius, unwalkableMask));
9.  
10.                 int movementPenalty = 0;
11.  
12.  
13.  
14.  
15.                 // Fix this code from 3D to 2D
16.                 // --->
17.                 Ray ray = new Ray(worldPoint + Vector3.up * 50, Vector3.down);
18.                 RaycastHit hit;
19.  
20.                 if (Physics.Raycast(ray, out hit, 100, walkableMask))
21.                 {
22.                     walkableRegionsDictionary.TryGetValue(hit.collider.gameObject.layer, out movementPenalty);
23.                 }
24.                 // <----
25.  
26.                 if (!walkable)
27.                 {
28.                     movementPenalty += obstacleProximityPenalty;
29.                 }
30.                    
31.  
32.                 grid[x, y] = new Node(walkable, worldPoint, x , y, movementPenalty);
33.             }
34.         }
35.         BlurPenaltyMap(3);
36.     }

 

@Loff

Mavmesh works in 2d as well with NavMeshSurface.
I have a project for 2d tilemap pathfinding, links below in signature
https://github.com/h8man/NavMeshPlus - here how its done
https://github.com/h8man/RedHotSweetPepper - and here is point and click demo