A* algorithm in C# for use in a game

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<PathTile> closedList;

// Closed list using Minheap for O(1) smallest lookup times
private MinHeap<PathTile> 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<PathTile> tempPathList = new List<PathTile>();
        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.

if (!tempTile.rect.IntersectsWith(target))
{
    if (condition)
        Hvalue = tile.hScore - 1;
    else
        Hvalue = tile.hScore + 1;
}

hValue and not Hvalue could be assigned to a ternary expression: hValue = tile.hScore + condition ? -1 : 1

And this is mostly what I could get wrongly about your code. Now let me post the reviewed result.

public class PathFinder
{
    private readonly HashSet<PathTile> _closedList = new HashSet<PathTile>(new PathTileComparer());
    private readonly MinHeap<PathTile> _openList = new MinHeap<PathTile>();

    // The player target position
    private RectangleF target;

    public IEnumerable<PathTile> FindPath(TileEngine tilemap, RectangleF target, RectangleF startPos)
    {
        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 IEnumerable<PathTile> GeneratePath(PathTile tile, RectangleF startPos, TileEngine tileMap)
    {
        PathTile parentTile = tile;
        // Loop until a path to the target is found or the enemy is blocked in
        while (!parentTile.rect.IntersectsWith(target))
        {
            //Checks all adjacent tiles
            CheckAdjacentTiles(parentTile, tileMap);

            // If open list is empty not path has been found
            if (_openList.Count == 0)
                return Enumerable.Empty<PathTile>();

            //Adds the PathTile with the smallest F Score into the closed list
            //This tile becomes the parentTile

            PathTile parentTile = _openList.Peek();
            _closedList.Add(new PathTile(parentTile.fScore, parentTile.hScore, parentTile.gScore, parentTile.rect, parentTile));
            _openList.RemoveMin();
        }

        // If the target has been reached move back up the closed list and return the path
        var tempPathList = new Stack<PathTile>();

        while (parentTile.parent != null)
        {
            tempPathList.Push(parentTile);
            parentTile = parentTile.parent;
        }

        _closedList.Clear();
        _openList.Clear();
        return tempPathList;
    }

    private void CheckAdjacentTiles(PathTile tile, TileEngine tileMap){
        //what you really want to do here is to have a method on PathTile that let's you check if that tile belongs or not to _openList
        //if it does you can add to open list here
        //This is just a try to refactor your check method so it respects a bit more OOP principles.

        var rightTile = new PathTile(new RectangleF(tile.rect.X, tile.rect.Y, tile.rect.Width, tile.rect.Height));
        rightTile.rect.X = rightTile.rect.X + rightTile.rect.Width;
        CheckAdjacentTile(rightTile, tile, tileMap, ()=> rightTile.rect.X < target.X);

        var leftTile = new PathTile(new RectangleF(tile.rect.X, tile.rect.Y, tile.rect.Width, tile.rect.Height));
        leftTile.rect.X = leftTile.rect.X - leftTile.rect.Width;
        CheckAdjacentTile(leftTile, tile, tileMap, ()=> leftTile.rect.X > target.X);

        var downTile = new PathTile(new RectangleF(tile.rect.X, tile.rect.Y, tile.rect.Width, tile.rect.Height));
        downTile.rect.Y = downTile.rect.Y - downTile.rect.Height;
        CheckAdjacentTile(downTile, tile, tileMap, ()=> downTile.rect.Y > target.Y);

        var upTile = new PathTile(new RectangleF(tile.rect.X, tile.rect.Y, tile.rect.Width, tile.rect.Height));
        upTile.rect.Y = upTile.rect.Y + upTile.rect.Height;
        CheckAdjacentTile(upTile, tile, tileMap, ()=> upTile.rect.Y < target.Y);
    }

    private void CheckAdjacentTile(PathTile directionTile, PathTile tile, TileEngine tileMap, Func<bool> incrementshValue){
        var increment = incrementshValue() ? -1 : 1;
        increment = directionTile.rect.IntersectsWith(target) ? -1 : increment;
        int hValue = tile.hScore + increment;

        if (!tileMap.checkTileCollision(directionTile.rect) 
            && !_closedList.Contains(directionTile) 
            && directionTile.rect.X > 0 
            && directionTile.rect.Y > 0)
        {
            _openList.Add(new PathTile(hValue + (tile.gScore + 1), hValue, tile.gScore + 1, directionTile.rect, tile));
        }
    }

    private int ComputehValue(RectangleF rec)
    {
        var hValue = 0;
        while (!rec.IntersectsWith(target))
        {
            if (rec.X > target.X && rec.X >= (target.X + target.Width))
            {
                rec.X = rec.X - rec.Width;
                hValue++;
            }
            else if (rec.X < target.X && (rec.X + rec.Width <= target.X))
            {
                rec.X = rec.X + rec.Width;
                hValue++;
            }
            if (rec.Y > target.Y && rec.Y >= (target.Y + target.Height))
            {
                rec.Y = rec.Y - rec.Width;
                hValue++;
            }
            else if (rec.Y < target.Y && (rec.Y + rec.Height <= target.Y))
            {
                rec.Y = rec.Y + rec.Width;
                hValue++;
            }
        }
        return hValue;
    }
}