So my game uses a tile grid for movement, with my own probably not great implementation of Astar. My main problem is that there’s a problem when two of my tiles have the same h, g, and f costs, this is due to my game having battlers block the tile they’re currently on. For instance, sometimes I’ll begin pathfinding and it’ll eventually lead to a dead end, due to it seeing a tile that will eventually lead to a block as fine. If anyone has any idea of a way to fix this, I’ll attach my pathfinding code below. Tiles are connected to each adjacent tile in a list on the tile itself. I would life if the solution wouldn’t mean I’d have to tear down the whole thing, but if it’s necessary, I guess it can’t be helped. Thank you.
public void BuildRoute(Tile finalDestination)
{
Tile checkedTile = hostTile;
pathway.Clear();
List<int> fCostList = new List<int>();
List<int> hCostList = new List<int>();
while (finalDestination.partOfPath == false)
{
for(int i = 0; i < checkedTile.adjacentTiles.Count; i++)
{
if(checkedTile.adjacentTiles[i].blocked == false && checkedTile.adjacentTiles[i].partOfPath == false)
{
checkedTile.adjacentTiles[i].FindAstarNumbers(hostTile, finalDestination);
fCostList.Add(checkedTile.adjacentTiles[i].fCost);
hCostList.Add(checkedTile.adjacentTiles[i].hCost);
}
}
for(int i = 0; i < checkedTile.adjacentTiles.Count; i++)
{
if(checkedTile.adjacentTiles[i].hCost == hCostList.Min() && checkedTile.adjacentTiles[i].fCost == fCostList.Min() && checkedTile.adjacentTiles[i].partOfPath == false)
{
pathway.Add(checkedTile.adjacentTiles[i]);
checkedTile = checkedTile.adjacentTiles[i];
checkedTile.partOfPath = true;
if(isEnemy == false)
{
checkedTile.HighlightAltBlue(); //This just highlights the tile they're going for.
}
}
}
fCostList.Clear();
hCostList.Clear();
}
}
Please don’t take the following negatively, we all have been beginners at some point you just need to find right learning resources that work for you and keep working.
What you wrote looks nothing like A*, you will have to go back to the tutorial you used or find a different tutorial and write it mostly from scratch. You might be able to reuse H function calculation and the way you store adjacent tiles. I guess you wrote that by purely looking at the visualization of A* without looking at code of example implementations. Algorithm visualizations are great as additional material to help understand how algorithm works especially if you are not very comfortable with reading complex code, but they should not be treated as only material. Visualizations often ignore or handwave around important implementation details, that might not be very obvious unless you are very experienced with similar type of algorithms or algorithms and data structures in general.
For a beginner I would also advice taking a look other simpler path finding algorithms first like BFS and Dijkstra. I personally find A* in context of game development slightly overrated to the point where many people are not aware that alternative exist. Which can sometimes depending on specifics of your game be not only simpler and more beginner friendly to code but also perform better. It has come even to the point where many tutorials addressed at beginners try to teach A*, but since proper A* depends on some non trivial data structures and very careful implementation which would be difficult to explain in beginner tutorial so they cut the corners. So you end up with worst parts of everything: more complicated code, worse limitations (because faster performance if implemented correctly often comes at the cost of working in specific conditions or not generating related useful to have information), worse performance (because you skipped corners and implemented simplified version). What’s the point of writing more complex algorithm badly, if simplifications mean that it performs worse than if you implemented simpler algorithm properly. If you want to learn build up your skills with simpler stuff first which you can implement with less corner cutting.
Some notes on common path finding algorithms, their strengths and weaknesses.
-
BFS - Works only when all the edges have some length. Great if you are working with a grid like many games do (assuming you are fine with diagonal moves having same length as vertical/horizontal or no diagonal moves). Simplest to implement, unlike following doesn’t require a heap/priority queue or some kind of sorted list data structure. Finds shortest path not only between pair of points, but also from single point to everywhere on map, or even list of few nodes to everywhere in map. No changes required if you are working with arbitrary graphs.
-
Dijkstra’s algorithm Similar to BFS, but replacing regular queue with priority queue. Unlike BFS supports arbitrary (positive) edge lengths not just plain grid with all distances being 1. Just like BFS can find shortest path from single point to everywhere in map in single run not just pair of points. Works with arbitrary graphs.
-
A* Can be consider a Dijkstra’s algorithm with additional additional heuristics to avoid visiting whole graph in common cases. Ideal map for A* is one with large open areas, few dead ends and obstacles which can be avoided by going slightly sideways. Which is what many real world environments look like. Although with maps like that you have to consider whether something like dumb strategy of going in straight line towards target and moving slightly sideways if there is an obstacle might also work (especially for game with hoards of enemies), or if the environments contain some dead ends and it is more important for enemies not to get stuck maybe a you might want a navmesh. One drawback for A* is that unlike previous algorithms it only works for pair of points, it can’t find shortest path from single point to everywhere on map. If you feel like you need to run A* multiple times in a row with one common endpoint consider replacing that with single run of previously mentioned algorithms. Good example of this tower defense games, instead of running A* for each enemy it’s sufficient to run BFS or Dijkstra’s algorithm once. It is also common to be interested in questions like which X on map is closest to Y. One more limitation of A* is that it depends on the heuristic for estimating distance to target. This is fine for graphs that repesent 2d or 3d map, but it maybe hard or impossible to come up with valid heuristics for graphs that represent more abstract problems. One more tricky detail to properly take advantage of A* is that since one of main benefits of it is potentially not having to process all the nodes, you need to avoid processing all the nodes in graph (for each run). The naive thing to do is at the start of algorithm creating new or resetting existing arrays for storing state like whether node was already processed and currently best known distance to each node, but this means that you are processing all the nodes which defeats the whole point of A*. Properly avoiding it might mean reusing structures between runs and carefully tracking which nodes were dirtied during current run so that only those can be restored to clean state, which is error prone and results in ugly looking interfaces. Due to the nature of how modern computers work (with branch predictions and multi layer cache ) simply wiping the whole arrays at start may still be very fast and beneficial if it allows you to avoid later processing every node in the more branch and random memory access heavy phase of path finding algorithm. But that goes into the territory where you need to make actual benchmarks, with specific implementation, size and structure of map, pattern of how often you call the path finding between which points. With the best choice varying depending on all those details.
1 Like
Thank you, I probably knew my implementation was a bit of a patchwork version of the concepts of A*. You were completely right, I focused much more on the concept itself instead of the actual code and way things should be working, I also hadn’t seen anything about BFS or Dijkstra’s. The only pathfinding info I found early on was about A*, which led me to assume that it was the most beginner friendly and fitting. I’ll definitely be looking at BFS as that seems to be a perfect fit. Just for clarification, the game I’m working on is a Fire Emblem-esque trpg, I realize I should’ve included that in my initial post, if that changes any of your advice let me know, but what you have supplied already is incredibly helpful! Thank you!
How big a world? 20x20 tiles? 50x50? You could probably brute force a search of that scale and never notice the penalty, as long as you cached the results and didn’t bang on it every frame for every unit.
Just pick a pathing solution, make sure you implement it right, and if you wrap it up behind your own nice “front” class to hide what the details are, you can trivially change it out in the future without having to hack up your entire game.
1 Like
Now I’ve been trying to implement a BFS pathfinding method, but I fear I’ve messed up somewhere obvious, when adding adjacent tiles to a search list, I get a problem where I can’t quite get the game to ignore already searched or searching tiles, I think it’s probably just a minor coding error, but I can’t see what I’m doing wrong.
public void BuildRoute(Tile finalDestination)
{
candidate = hostTile;
Tile checkedNeighbor;
pathway.Clear();
searching.Clear();
searched.Clear();
int safetyLimit = 100000; //These are used to keep the while loop from going forever, making me force close unity whenever I screw up.
int safety = 0; //The grid is quite small, only 3 x 4 at the moment. So these numbers are above the amount of loops needed.
searching.Add(hostTile);
while(searching.Contains(finalDestination) == false)
{
if(safety == safetyLimit)
{
break;
}
candidate = searching[0];
for(int i = 0; i < candidate.adjacentTiles.Count; i++)
{
checkedNeighbor = candidate.adjacentTiles[i];
if(checkedNeighbor.blocked == false && searched.Contains(checkedNeighbor) == false && searching.Contains(checkedNeighbor) == false)
{
searching.Add(checkedNeighbor);
checkedNeighbor.tileCameFrom = candidate;
searching.Remove(candidate);
searched.Add(candidate);
}
}
safety++;
}
}
You are removing candidate from searching only when you find an unvisited neighbor. Not only it results in potentially adding it to “searched” list multiple times, it also means that you don’t remove it from front of searching if there no unvisited neighbors. So once you reach a dead end your loop will keep repeatedly try to process it. Changing state from searching to searched should happen independently of the state of neighbors.
By the way C# standard library has proper queue available Queue<T> Class (System.Collections.Generic) | Microsoft Learn , so you don’t have to misuse list as a bad version of queue.
2 Likes