[.net] A* optimization in C#

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.

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.

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.



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;
}




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

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.

How big is your map? 32x32 tiles or 10000x10000. This will play an important part in the answers you get.

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.

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.

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.

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.

how to equate a better path without the open list?

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.