6
\$\begingroup\$

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

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

// The player target position
private RectangleF target;

public List<PathTile> FindPath(TileEngine tilemap, RectangleF target, RectangleF startPos)
{
    //  Assign Values to variables
    openList = new MinHeap<PathTile>();
    closedList = new HashSet<PathTile>(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<PathTile> 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)
            return null;

        //Finds the tile with the smallest F value in the open list.
        PathTile tempTile = openList.Peek();

        // Adds the PathTile with the smallest F Score into the closed list storing a reference to it's parent
        closedList.Add(new PathTile(tempTile.fScore, tempTile.hScore, tempTile.gScore, tempTile.rect, temp));

        // Sets the PathTile to be stored as the parent to the next smallest value
        temp = tempTile;

        // Removes the PathTile from the open list
        openList.RemoveMin();

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

private void Check(PathTile tile, String direction, RectangleF enemy, TileEngine tileMap)
{
    PathTile tempTile = new PathTile(new RectangleF(tile.rect.X, tile.rect.Y, tile.rect.Width, tile.rect.Height));
    int Hvalue = 0;
    Boolean condition = true;
    if (direction.Equals("Right"))
    {
        tempTile.rect.X = tempTile.rect.X + tempTile.rect.Width;
        condition = tempTile.rect.X < target.X;
    }
    else if (direction.Equals("Left"))
    {
        tempTile.rect.X = tempTile.rect.X - tempTile.rect.Width;
        condition = tempTile.rect.X > target.X;
    }
    else if (direction.Equals("Up"))
    {
        tempTile.rect.Y = tempTile.rect.Y - tempTile.rect.Height;
        condition = tempTile.rect.Y > target.Y;
    }
    else if (direction.Equals("Down"))
    {
        tempTile.rect.Y = tempTile.rect.Y + tempTile.rect.Height;
        condition = tempTile.rect.Y < target.Y;
    }

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

    if (!tileMap.checkTileCollision(tempTile.rect) && !closedList.Contains(tempTile) && tempTile.rect.X > 0 && tempTile.rect.Y > 0)
    {
        //if (!tilemap.CheckEnemyCollisionRecter(tempTile.rect,enemy2))
            openList.Add(new PathTile(Hvalue + (tile.gScore + 1), Hvalue, tile.gScore + 1, tempTile.rect, tile));
    }
}

private int ComputeHValue(RectangleF rec)
{
    int FCount = 0;
    while (true)
    {
        if (rec.X > target.X && rec.X >= (target.X + target.Width))
        {
            rec.X = rec.X - rec.Width;
            FCount++;
        }
        else if (rec.X < target.X && (rec.X + rec.Width <= target.X))
        {
            rec.X = rec.X + rec.Width;
            FCount++;
        }
        if (rec.Y > target.Y && rec.Y >= (target.Y + target.Height))
        {
            rec.Y = rec.Y - rec.Width;
            FCount++;
        }
        else if (rec.Y < target.Y && (rec.Y + rec.Height <= target.Y))
        {
            rec.Y = rec.Y + rec.Width;
            FCount++;
        }
        if (rec.IntersectsWith(target))
            return FCount;
    }
}

}

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. I have to congratulate you for having post a very nice 1st question. Keep giving them just like that :). \$\endgroup\$ – Bruno Costa Jan 31 '16 at 13:13
2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ While I talked about the consistency about var I didn't apply it on my review. But it really is easier when coding from scratch then on the review itself, so I am sorry for that. \$\endgroup\$ – Bruno Costa Jan 31 '16 at 18:02
  • \$\begingroup\$ In the end I would suggest you to not just apply those modifications, but to think deeply about it. There seems to be some pesky steps that you are doing on this algorithm that maybe you could avoid. Look up to the existing A* questions in the related questions div. Or after thinking about it and applying the changes you can always do a follow-up :). \$\endgroup\$ – Bruno Costa Jan 31 '16 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.