Implementation of A* Pathfinding

[martianxx]

Sorry in advance for this being a long post.

I am making (for my degree) a snake game (you know the classic one that you used to have on mobile phones). However the classic rules of the game ares slightly changed and I am required to implement a computer controlled opponent for the player to play against.

I (having coded most of the rest of the game) have finally come to create my AIController class which can be created as a part of the "snake" class to control a snake.

I have decided to use a basic state machine to control what the computer does. He will go round collecting food until the risk from the extra length is deemed too high at which point he returns to his base (yes in this version i am required to have bases) to drop off his loot.

His navigation around the map I have planned to use the A* path finding algorithm which I had heard about before but never got around to implementing it.

The basic idea I have started with is that I have a start square and a target square and a function that builds a path between the two taking into account walls. (For now it ignores the possibility of hitting the human controlled snake). Anyway, this is what I have so far. It does work, sometimes, but others it gets stuck. I am mainly looking to see if I am (or am not) going about this in the right way especially with regards to the containers I use.

walls_ = pointer to array of position vectors that represent un-walkable locations.

AIPathData = structure made of a Vector3 class and an integer F value;

Vector3 = custom vector class.

void AIController::Update()
{
    if (updateTimerCounter_ == updateTimer_)
    {
        switch (state_)
        {
            case PICKUP:
                if (pathCompleted_)
                {
                    while (!CheckWalls(target_ = Level::GetRandomVector())){}
                    path_ = FindPath(owner_->GetPlayerFront());
                    pathCompleted_ = false;
                }
                Move();
                break;
        }
        updateTimerCounter_ = 0;
    }
    updateTimerCounter_++;
}
void AIController::Move()
{
    int pathSize = path_.size();

    if (path_.size() <= 0)
    {
        pathCompleted_ = true;
        return;
    }

    Vector3 direction = Vector3::Distance(owner_->GetPlayerFront(), path_.front());
    owner_->MoveNodes(direction);
    path_.pop_front();
}
std::list<Vector3> AIController::FindPath(Vector3 start)
{
    std::list<AIPathData> openList; //posible move locations that need to be evaluated
    std::list<Vector3> closedList; //position vectors making up the final path
    int numViableBounds = 0; //the number of bounding cells that are not walls or otherwise invalid
    Vector3 boundingCell; //the position vector of a viable bounding cell
    closedList.push_back(start);

    while (closedList.back() != target_)
    {
        boundingCell = closedList.back() + Vector3::North2D;
        if (CheckVector(boundingCell, closedList))
        {
            openList.push_front(GetPathData(boundingCell));
        }
        boundingCell = closedList.back() + Vector3::South2D;
        if (CheckVector(boundingCell, closedList))
        {
            openList.push_front(GetPathData(boundingCell));
        }
        boundingCell = closedList.back() + Vector3::East2D;
        if (CheckVector(boundingCell, closedList))
        {
            openList.push_front(GetPathData(boundingCell));
        }
        boundingCell = closedList.back() + Vector3::West2D;
        if (CheckVector(boundingCell, closedList))
        {
            openList.push_front(GetPathData(boundingCell));
        }

        Vector3 bestCell = GetBestCell(openList);
        closedList.push_back(bestCell);
        openList = ResetOpenList(openList);
    }

    closedList.pop_front(); //we are already at the start point so remove it from the path

    return closedList;
}
bool AIController::CheckVector(Vector3 cell, std::list<Vector3>& cl)
{
    return CheckWalls(cell) && CheckLists(cell, cl);
}
bool AIController::CheckWalls(Vector3 cell)
{
    for (int i = 0; i < walls_->size(); i++)
    {
        if ((*walls_)[i] == cell)
        {
            return false;
        }
    }
    return true;
}
bool AIController::CheckLists(Vector3 cell, std::list<Vector3>& cl) //as the open list grows this could be come more intensive, for that reason I push all new items onto the front of the vector this means I only need to test the first 4
{
    std::list<Vector3>::iterator i = cl.begin();
    if (cl.size() != 0)
    {
        while (i != cl.end())
        {
            if (*i == cell)
            {
                return false;
            }
            i++;
        }
    }
    return true;
}
AIPathData AIController::GetPathData(Vector3 cell)
{
    Vector3 difference = Vector3::Distance(cell, target_);
    int x = difference.getX();
    int y = difference.getY();

    if (x < 0)
    {
        x*= -1;
    }
    if (y < 0)
    {
        y *= -1;
    }

    AIPathData ret;
    ret.cell = cell;
    ret.fValue = x * 10 + y * 10;

    return ret;
}
Vector3 AIController::GetBestCell(std::list<AIPathData>& ol)
{
    std::list<AIPathData>::iterator j = ol.begin();
    AIPathData bestF = *j;
    AIPathData debug = *j;
    std::cout << "Values:" << std::endl;
    while (j != ol.end())
    {
        std::cout << j->fValue << std::endl;
        AIPathData debug = *j;
        if (j->fValue < bestF.fValue)
            bestF = *j;
        j++;
    }
    std::cout << "Best Value: "<< bestF.fValue << std::endl;
    return bestF.cell;

}
std::list<AIPathData>& AIController::ResetOpenList(std::list<AIPathData>& ol)
{
    while (ol.size() > 0)
    {
        ol.pop_front();
    }

    return ol;
}

So far it works fine as long as there are not too many obstacles (walls) but some times it can get into a position where every surrounding square has a worse value than the one its in resulting in an infinite loop where it constantly moves back and forth between the best and second best squares.

This basically occurs when it gets to a wall and the cell on the left and on the right have the same value so it just picks the first one. However one direction results in the wall ending the other doesn't. This can also make the snake go over every cell until it "realizes" its mistake.

If anyone could shed some light on what might be going wrongs, ways around my problems or alternative strategies I would appreciate it.

Thanks.