Sign in to follow this  
Lesan

[.net] A* optimization in C#

Recommended Posts

Hello.
I'm currently using this code as my pathfinding algorithm for an RTS. However, I find it too slow.
What would you recommend me to optimize it? I'm looking both for general ideas or articles (like grouping nearby tiles into one for pathfinding purposes?) and for specific optimization pertaining to the code (using classes slows it down? using generic lists slows it down?

Thank you in advance.

[source lang="csharp"]
private List<Tile> FindPath(Creature c, Tile targetTile)
{
List<Tile> open = new List<Tile>(); // A* open list
List<Tile> closed = new List<Tile>(); // A* closed list
Tile targetFound = null;
if (targetTile.BlocksMovement) return null;

// The heuristics used is 10 times horizontal distance to target + 10 times vertical distance to target
// Setting the cost of the starting tile to 0
Map[c.TileX][c.TileY].Pathfinding_G = 0;
Map[c.TileX][c.TileY].Pathfinding_H = Math.Abs(targetTile.X - c.TileX) * 10 + Math.Abs(targetTile.Y - c.TileY) * 10;
Map[c.TileX][c.TileY].Pathfinding_F = Map[c.TileX][c.TileY].Pathfinding_G + Map[c.TileX][c.TileY].Pathfinding_H;
Map[c.TileX][c.TileY].Pathfinding_Parent = null;
open.Add(Map[c.TileX][c.TileY]);

while (open.Count != 0)
{
// Choosing the tile with lowest "F" value (cost + heuristics)
int lowestF = Int32.MaxValue;
Tile currentTile = null;
foreach (Tile t in open)
{
if (t.Pathfinding_F < lowestF)
{
lowestF = t.Pathfinding_F;
currentTile = t;
}
}
// End if target is found
if (currentTile == targetTile)
{
targetFound = targetTile;
break;
}

// Determines the cost to all adjacent tiles and if it is smaller than the existing one, overwrites
foreach (Tile adjacent in currentTile.Neighbours)
{
if (closed.Contains(adjacent)) continue;
// If this is the first time we ran into the tile, we reset its cost to maximum and calculate the heuristic.
if (!open.Contains(adjacent))
{
adjacent.Pathfinding_G = Int32.MaxValue;
adjacent.Pathfinding_H = Math.Abs(targetTile.X - adjacent.X) * 10 + Math.Abs(targetTile.Y - adjacent.Y) * 10;
adjacent.Pathfinding_F = adjacent.Pathfinding_G + adjacent.Pathfinding_H;
open.Add(adjacent);
}
int Gfromhere = currentTile.Pathfinding_G + 10;
if (Math.Abs(currentTile.X - adjacent.X) + Math.Abs(currentTile.Y - adjacent.Y) == 2) Gfromhere += 4;
if (Gfromhere < adjacent.Pathfinding_G)
{
adjacent.Pathfinding_G = Gfromhere;
adjacent.Pathfinding_F = adjacent.Pathfinding_G + adjacent.Pathfinding_H;
adjacent.Pathfinding_Parent = currentTile;
}
}
open.Remove(currentTile);
closed.Add(currentTile);
}

// Backtracking to form a path
if (targetFound == null)
return null;
else
{
List<Tile> res = new List<Tile>();
while (targetFound.Pathfinding_Parent != null)
{
res.Insert(0, targetFound);
targetFound = targetFound.Pathfinding_Parent;
}
return res;
}
}
[/source]

Share this post


Link to post
Share on other sites
No need to multiply by 10 on the heuristic if distance is your only influencer.

An open and a closed list? Isn't the closed list sufficient?

Since you're doing a lot of contains on the lists, a HashSet or even Dictionary (with a null value) would be a more suitable structure.

I'd make sure that currentTile.Neighbors is relatively efficient.

Not optimizing related, but it's odd that your map contains the pathfinding heuristics and parent tile and stuff; it will make it hard to parallelize this.

After that... run the profiler; see where things are called more than they should, see where the hot spots are.

Share this post


Link to post
Share on other sites
I have never seen an A* algorithm that only uses a closed list.....how to equate a better path without the open list? The only thing that jumps out to be are the below; 1)creating objects inside a loop (more of a memory footprint thing than speed. Allocating a bunch of memory instead of reusing the same piece...there is no guarantee when garbage collection will run) 2)Constantly doing a contains on the list of objects, even changing it to contain reference ints in another list would be faster than an object check. I think more details about your map may be required as well. How big is your map? 32x32 tiles or 10000x10000. This will play an important part in the answers you get.

Share this post


Link to post
Share on other sites
Instead of keeping a closed list, keep an array of booleans the same size as your map. Instead of pushing down then searching this closed list to see if a specific tile is closed, just check the array in that position: closedList[y][x].

You could avoid clearing that list every pathfind by instead storing the closedList as an array of integers. Instead of flagging each tile as closed with a boolean, set it to a certain value which changes for each pathfind request.

[code]

private static int PATHFIND_CLOSED_VALUE = int.MIN_VALUE;
private static int[][] closedList = null;

public Path pathfind(Position start, Position end) {
// If you ever reach the max value, which is highly unlikely,
// you will need to reset the closed value
if (PATHFIND_CLOSED_VALUE == int.MAX_VALUE) {
PATHFIND_CLOSED_VALUE = int.MIN_VALUE;
closedList = null;

}

if (closedList == null) {

closedList = new int...
}

...
// Checking to see if a cell is closed
var isClosed = closedList[y][x] == PATHFIND_CLOSED_VALUE;
...
// Setting a cell closed
closedList[y][x] = PATHFIND_CLOSED_VALUE;

PATHFIND_CLOSED_VALUE += 1;
}

[/code]


This code is not at all thread safe, but I'm guessing you're probably not concerned with that.

Share this post


Link to post
Share on other sites
One implementation detail: instead of implementing your open set as a list, you may want to use a sorted container or a priority queue container (preferably the latter, but last I checked the .NET standard library didn't have one); either would probably speed up the process of finding the next element.

Most algorithmic improvements to game pathfinding usually involve using different algorithms instead of or to augment raw A*. One of the most effective is to use hierarchical pathfinding to first build a rough path from point A to B and then using A* to smooth out the rough path.

Share this post


Link to post
Share on other sites
[quote name='XXChester' timestamp='1318950872' post='4873939']
How big is your map? 32x32 tiles or 10000x10000. This will play an important part in the answers you get.
[/quote]

For very large maps there are other things you can do to improve pathfinding performance.

For one, you can keep a separate grid the same size as the tile map that indicates which regions are contiguous. This can be used to know immediately before you even waste time trying to find a path from one point to the other, whether or not there even is a path between the two cells.

Another thing you can do is create pregenerated paths and store these along with the map. So you could pregenerate paths from each doorway in a dungeon to every other doorway in a dungeon. then, if you can determine that the path is going from one room to another, you can on-the-fly calculate a path from the player to the correct door, then use the pregenerated path from that door to the next door. After you've reached the end of that pregen path, then finish with on-the-fly pathing to the final destination cell.

Share this post


Link to post
Share on other sites
Another option that is sometimes used to speed up an A* implementation (but cannot be used for all game types) is to do an initial blind fill of the pieces costs on the map load. Than you do not always have to calculate them, but as you said you are writing an RTS this is most likely not an option for you.

Share this post


Link to post
Share on other sites
[quote]
Instead of keeping a closed list, keep an array of booleans the same size as your map. Instead of pushing down then searching this closed list to see if a specific tile is closed, just check the array in that position: closedList[y][x].
[/quote]

Ah yes, this is (usually) better than my recommendation for the closed list fixes.

[quote]
how to equate a better path without the open list?
[/quote]

It's been some time since I had to implement the thing (and this implementation looks a bit different from what I remember it to be), but since you automatically take the non-closed neighbor with the best heuristic, you're usually (depending on how accurate your heuristic is) going to get the best path the first time out.

Share this post


Link to post
Share on other sites
[quote name='Telastyn' timestamp='1318952667' post='4873952']
[quote]
how to equate a better path without the open list?
[/quote]

It's been some time since I had to implement the thing (and this implementation looks a bit different from what I remember it to be), but since you automatically take the non-closed neighbor with the best heuristic, you're usually (depending on how accurate your heuristic is) going to get the best path the first time out.
[/quote]

Hmm I will have to think this one through. I am still new to the AI scene and haven't heard about an implementation without an open list but it may very well be possible. I seem to remember my first implementation without the open list and I had to implement it for when the algorithm hit a dead end or something.

That's interesting though, like I said I will have to look into it.
Thanks.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this