A* pathfinding movement range

Hi all. I've just implemented A* pathfinding for my project and it works great. I can click my unit and get them to navigate to any point on my tile map. I am just having a little trouble with limiting the movement range of my units.

I figure it's something like the code below. Start with the tile the unit is on, then iterate through its neighbours, add them to the moveableArea list, then iterate through the moveableArea list again to find their neighbours, and then limit the amount of iterations based on a formula using the Units max movement distance.

But I can't quite figure out how to do it properly - all my attempts end up half-baked:




So I've removed all failed coding attempts, and the below script currently just returns EVERY tile on the board. I would really appreciate any help possible.

Thanks very much for your time!

map.tiles is a list of ALL tiles in the scene.
Neighbour is just a custom class that holds some extra data I need.
Neighbour.id is the position of the neighbouring tile in map.tiles

Code (csharp):

1.  
2. //The final list of tiles the unit can move to
3. List<Tile> moveableArea = new List<Tile>();
4.  
5. void GetMoveableArea(Unit unit)
6. {
7.     // The distance the unit can move is based on its speed stat
8.     int distance = unit.speed.level;
9.  
10.     //Add the first tile to the search area
11.     moveableArea.Add(map.tiles[unit.tilePosition]);
12.  
13.     for (int i = 0; i < moveableArea.Count; i++)
14.     {
15.         for (int n = 0; n < 4; n++)
16.         {
17.             Neighbour neighbour = moveableArea[i].neighbours[n];
18.    
19.             // If the neighbour is not a null tile, its walkable,
20.             // and its not already in our moveable area
21.             if (!neighbour.nullTile && neighbour.walkable &&
22.                 !moveableArea.Contains(map.tiles[neighbour.id]))
23.             {
24.                  // Use the neighbours ID to get the tile
25.                  moveableArea.Add(map.tiles[neighbour.id]);
26.             }
27.         }
28.     }
29. }

 

You don't want to add things to a list while you are iterating over it. In this case, that's

moveableArea

. That will, in almost all cases, cause some unexpected behavior, as you can tell.

The code is a bit unclear to me. But what you are describing seems like it should just be a simple recursive function. I threw together some pseudocode REAL quick, maybe it can help out.

Code (CSharp):

1. List<Tile> tiles = new List<Tile>(startTile);
2.  
3. // iterate over tiles. Find neighbors for those tiles, then iterate over those neighbors. This is the recursive part.
4. List neighbors = FindNeighbors(tile, moveableArea);
5. moveableArea.Add(neighbors);
6.  
7. // In the end your recursive function would return a list of all collected tiles
8.  
9.  
10. // FindNeighbors
11. List<Tile> FindNeighbors(Tile tile, List<tiles> moveableArea)
12. {
13.     // return a list containing the neighbors of "tile"
14.     // but filter out the ones that are already contained in "moveableArea"
15. }

 

How are you returning neighbors? how does tileName.neighbour[x] return a tile?

 

I like to try something very simple to troubleshoot first. Something like the following code with Debug.Log statements throughout to see where the problem is

Code (CSharp):

1.     void GetMoveableArea(Unit unit)
2.     {
3.         int distance = unit.speed.level;
4.         Tile occupiedTile = map.tiles[unit.tilePosition];
5.  
6.         moveableArea.Clear();
7.  
8.         MADD(occupiedTile);
9.  
10.         foreach (Tile n in occupiedTile.neighbours)
11.             MADD(n);
12.     }
13.  
14.     void MADD(Tile t)
15.     {
16.         if (!moveableArea.Contains(t))
17.             moveableArea.Add(t);
18.     }

 

Hey EdGunther, thanks a lot for taking the time to respond!

I managed to get a bit of help from Reddit, who reminded me that A* uses a cost system for figuring out paths. So all I had to do was measure the movement cost from my origin tile to each of the neighbours, and then simply add any tiles that were under a specific cost amount. Got it working great now!

 

Hey! Don't know if you still remember but, how did you get the movement cost from the neighbors? Did you use the pathfinding? Could you link the reddit post?
Because what I did was calculate the manhattan distance between them. However, some of them go outside of not walkable zones