Optimizing an A* algorithm

I am currently using an implementation of the A* algorithm described here.

Currently, when I run my algorithm, my IDE lags horribly and the .exe generated also lags terribly. Using the CPU analyzer, I narrowed down the culprit using around 95% of the available CPU to my PathFind method. I'm not entirely sure where to start with optimizing the algorithm or making it less taxing on the system.

```
public struct Grid
{
public Rectangle Size;
public byte[,] Weight;
///
/// Creates a grid for pathfinding, if weight is 0 is inaccessible, non-zero indicates accessible
///
///
///
///
///
///
public Grid(int posX, int posY, int width, int height, byte defaultValue = 0)
{
Size = new Rectangle(posX, posY, width, height);
Weight = new byte[width, height];

for(int i = 0; i PathFind(Point start, Point end)
{
//Nodes that have already been analyzed and have a path from start to them
List closedSet = new List();

//Nodes that have been identified as a neighbor of an analyzed node, but not fully analyzed
List openSet = new List { start };

//A dictionary identifying the optimal origin point to each node. This is used to back track from the end to find the optimal path
Dictionary cameFrom = new Dictionary();
//A dictionary indicating how far ceach analyzed node is from the start
Dictionary currentDistance = new Dictionary();
//A dictionary indicating how far it is expected to reach the end, if the path travels through the specified node
Dictionary predictedDistance = new Dictionary();

//Initialize the start node w/ dist of 0, and an est. distance of ydist + xdist, optimal path in a square grid that doesn't allow for diagonal movement
currentDistance.Add(start, 0);
predictedDistance.Add(start, 0 + Math.Abs(start.X - end.X) + Math.Abs(start.Y - end.Y));

//If there are unanalyzed nod

Without looking too closely at your actual algorithm, I can tell you're using the wrong data-structures.

• closedSet should to be a set. closedSet.Contains(neighbor) should be O(1) but right now it's O(n)

-
openSet needs to be a priority queue. Dequeueing and adding items should be O(log n), but right now they're O(n log n) and O(n) (respectively).

(Shameless plug: I have a C# priority queue implementation specifically optimized for pathfinding on Github)

-
Creating a custom Node data structure to represent the graph (instead of using a bunch of dictionaries/arrays) will give a slight speed boost, and more importantly make your code a lot cleaner.

Other stylistic notes:

• Keep your brace-style consistent. Inconsistent braces make the code harder to read.

-
The line

if(!closedSet.Contains(neighbor) || tempCurrentDistance < currentDistance[neighbor])

is unnecessary, you check the negation of that a few lines above.

• It's debatable whether throwing an exception on "no path found" is the best solution. Exceptions should be for things that wouldn't occur during a normal execution of the program, and not having any path between two points is a common occurrence is many applications.

[Edit] Once you've done all the above, if it is still too slow for you there are various other algorithmic optimizations you can apply, such as altering tie-breaking behavior or using an incremental/suboptimal algorithm. These tend to be overkill for student projects, though.

You should also run your code through a profiler to find the hot-spots, at the very least for the experience. I recommend dotTrace, which is free for students.

StackExchange Code Review Q#138094, answer score: 29