A* algorithm in C# for use in a game

I recently started up again on a 2D game engine I have been working on over the last couple of years. I managed to implement a version of the a* algorithm that seems to work fine for my game, but it seems to be having a dramatic impact on my games performance when I have multiple enemies using it.

Currently I am calling a* only if there is an obstacle between the player and the enemy, and then every frame while there is still a collision between enemy and player. Could you please take a look at my code and let me know if you can see anything obvious that might be slowing it down

```
public class PathFinder
{
// Open list using HashSet for O(1) coontains lookup times
private HashSet closedList;

// Closed list using Minheap for O(1) smallest lookup times
private MinHeap openList;

// The player target position
private RectangleF target;

public List FindPath(TileEngine tilemap, RectangleF target, RectangleF startPos)
{
// Assign Values to variables
openList = new MinHeap();
closedList = new HashSet(new PathTileComparer());
this.target = target;

// Compute the F-Value of the starting position and create a new PathTile Object
int HValue = ComputeHValue(startPos);
PathTile p = new PathTile(HValue, HValue, 0, startPos, null);

// Add the path tile to the
openList.Add(p);

// Begin the search for the shortest path and return a list containing the Path Tiles or null
return GeneratePath(p, startPos,tilemap);
}

private List GeneratePath(PathTile tile, RectangleF startPos, TileEngine tileMap)
{
PathTile temp = tile;
// Loop until a path to the target is found or the enemy is blocked in
while (true)
{
//Checks all adjacent tiles
Check(temp, "Right", startPos, tileMap);
Check(temp, "Left", startPos, tileMap);
Check(temp, "Up", startPos, tileMap);
Check(temp, "Down", startPos, tileMap);

// If open list is empty not path has been found
if (openList.Count == 0

In general you did a good job but there are somethings that can be improved, either for correctness and/or performance and others for readability/quality.

Let's start with the ComputeHValue

int FCount = 0;
while (true)
{
    Check(temp, "Right", startPos, tileMap);
    //...

    //...
    if (rec.IntersectsWith(target))
        return FCount;
}

Your variable does not follow the naming conventions and I don't know what the F stands for.
Maybe it really is the name used on this algorithm pseudo-code, but if it's not change it to count. It also would make sense to call it something along the lines of the method name like hValue.

Can we always increment hValue in the while? If so you can only have 1 increment instruction, although I won't be including it on my review,
because I don't know if it can.

Your while loop could evaluate !rec.IntersectsWith(target) condition removing the if from it.

Like I told you I don't know the purpouse of the algorithm but normally I would be expecting Y coordinate to be related to heigth.
This is the kind of place that you can put some comments on your code to help understand it.

rec.Y = rec.Y + rec.Height; //not rec.Width

// Open list using HashSet for O(1) coontains lookup times
private HashSet closedList;

// Closed list using Minheap for O(1) smallest lookup times
private MinHeap openList;

Are the comments swaped here (shouldn't be Closed List on the first and Open List on the later)?
I think if you know the data structures those kind of comments may not really be useful.
You could also prefix your fields with _

Furthermore you are always creating new instances of those variables in your FindPath method, maybe they could be declared inside the method itself.
Other alternative, that I like more, is to create them on the constructor, and empty them with Clear, so you don't have to pass them to other methods.

Your GeneratePath might be where you made most mistakes and is really in need of some reviewing, let's do it.

while (true)
{
    //Checks all adjacent tiles
    Check(temp, "Right", startPos, tileMap);
    //...
    closedList.Add(new PathTile(tempTile.fScore, tempTile.hScore, tempTile.gScore, tempTile.rect, temp));
    //...
    // If the target has been reached move back up the closed list and return the path
    if (temp.rect.IntersectsWith(target))
    {
        List tempPathList = new List();
        PathTile t = temp;
        tempPathList.Add(t);

        while (t.parent != null)
        {
            t = t.parent;
            tempPathList.Insert(0, t);
        }

        closedList.Clear();
        openList = null;
        return tempPathList;
    }
}

First of all the same while concept that I described earlier for ComputeHValue could also be applied here.

The calling of the Check method 4 times, in this while loop, may be one of the reasons for your code slowness, there probably are better ways
to get the same behaviour with still undertandable code, that I'll include on my final result.

You are using t, temp, tempTile all to represent a PathTile, I think we can reduce a little bit the number of variables and the naming also.

Can't we just add tempTile to the closedList? We could reuse the object, unless there is some kind of problem with using the same object.
But it doesn't seem the case since you are creating an instance of PathTile to insert into your list. So I would go with it.

The comments present on the while body add too much noise to the code. I would prefer to have a 4 line comment block to give a nice explanation
about it instead of doing per line basis.

Then you are inserting values in the list always at the beggining.
When you insert an item to the beggining of a list you have to shift all existing elements to right, making Insert an O(n) operation.
What you really wanted to use here was a Stack

You can also remove some redudant code when you are adding the items if you change the order of the while body statements.

Also I should have mentioned earlier that you can use varto abreviate declarations.
This may be a little personal choice but I think what matters the most in the end is to be consistent.
And if you are trying to be consistent you have 2 options:

• You use var everywhere (int and string being allowed exceptions in some circunstances)

• You don't use var at all and don't ever create anonymous types (on LINQ Select extension for example)

Ah and after all you are using the Clear method here, so my previous point was spot on, I guess.

And finally your Check method. I'll greatly modify it with GeneratePath, but I thought I could also include something about it on my review.

Check, Check what? You should name your methods so it allows you to have a glimpse of what it really does, if it's not enough they should have XML documentation.

You never use enemy parameter on this method, remove it, since it doesn't seem to have a porpuse.

``

StackExchange Code Review Q#118426, answer score: 2