mercredi 12 juillet 2017

vector is faster than list in list fastest operations

I wrote a simply A* algorithm for my game:

Navigation.hpp

#pragma once

#include <SFML\Graphics.hpp>
#include <algorithm>
#include <iostream>

#include <vector>
#include <list>
#include <set>

using namespace std;

class Field;

//Comparer using by set to allow priority
struct FieldComparer
{
    bool operator()(const Field *, const Field *) const;
};

using FieldSet = set<Field*, FieldComparer>;
using FieldContainer = vector<Field*>; ///////////////////////////faster than list ?!

//Contains info about field, buildings builded on it and type of terrain
class Field
{
private:
    sf::Vector2i mapPosition{ 0, 0 };

    unsigned hCost{ 0 }; //to goal
    unsigned gCost{ 0 }; //to start

    Field *  parent;

    bool     isWalkable { true };
    bool     isPathPart { false };
public:
    void SetParent(Field&);
    Field * GetParent() const;

    unsigned GetFCost() const; //sum of hCost and gCost
    unsigned GetHCost() const;
    unsigned GetGCost() const;

    bool     IsWalkable() const;
    bool     IsPathPart() const;

    void SetHCost(unsigned);
    void SetGCost(unsigned);

    void SetWalkable(bool);
    void SetAsPartOfPath(bool);

    sf::Vector2i GetMapPosition() const;

    //compares positions
    bool operator == (const Field& other);

    Field(sf::Vector2i mapPosition, bool isWalkable) 
        : mapPosition(mapPosition), isWalkable(isWalkable) {}
};

//Contains fields and describes them
class Map
{
private:
    sf::Vector2u mapSize;
    Field *** fields; //two dimensional array of fields gives the fastest access
public:

    sf::Vector2u GetMapSize() const;
    Field *** GetFields();

    Map(sf::Vector2u);
    Map() {}
};

//Searching patch after giving a specified map
class PathFinder
{
private:
    //Calculate score between two fields
    unsigned CalcScore(Field&, Field&) const;

    //Get neighbours of field in specified map
    FieldContainer GetNeighbours(Field&, Map&) const;
public:

    //Find path that have the lowest cost, from a to b in map
    FieldContainer FindPath(Map&, Field&, Field&);

    //Reconstruct path using pointers to parent
    FieldContainer ReconstructPath(Field*, Field*) const;
};

Navigation.cpp

#include "Navigation.hpp"

#pragma region Field

    void Field::SetParent(Field & parent) { this->parent = &parent; }
    Field * Field::GetParent() const { return parent; }

    unsigned Field::GetFCost() const { return hCost + gCost; }
    unsigned Field::GetHCost() const { return hCost; }
    unsigned Field::GetGCost() const { return gCost; }

    bool Field::IsWalkable()   const { return isWalkable; }
    bool Field::IsPathPart()   const { return isPathPart; }

    void Field::SetHCost(unsigned value) { hCost = value; }
    void Field::SetGCost(unsigned value) { gCost = value; }

    void Field::SetWalkable(bool isWalkable)     { this->isWalkable = isWalkable; }
    void Field::SetAsPartOfPath(bool isPathPart) { this->isPathPart = isPathPart; }

    sf::Vector2i Field::GetMapPosition() const { return mapPosition; }
    bool Field::operator == (const Field& other)
    {
        return this->mapPosition == other.GetMapPosition();
    }

#pragma endregion Field

#pragma region Map

    sf::Vector2u Map::GetMapSize() const { return mapSize; }
    Field *** Map::GetFields() { return fields; }
    Map::Map(sf::Vector2u mapSize) : mapSize(mapSize)
    {
        //initialize map
        fields = new Field**[mapSize.x];

        //initialize all fields
        for (unsigned x = 0; x < mapSize.x; x++)
        {
            fields[x] = new Field*[mapSize.y];

            for (unsigned y = 0; y < mapSize.y; y++)
            {
                fields[x][y] = new Field({static_cast<int>(x), static_cast<int>(y)}, 
                { 
                    (!(y == 3 && x >= 1) || (x == 5 && y < 4))              
                });
            }
        }
    }

#pragma endregion Map

#pragma region PathFinder

    bool FieldComparer::operator()(const Field * l, const Field * r) const
    {
        return l->GetFCost() <  r->GetFCost() ||   //another field has smaller fcost
               l->GetFCost() == r->GetFCost() &&   //or fcost equals, and checked field is nearer to goal than current field
               l->GetHCost() <  r->GetHCost();

    }

    unsigned PathFinder::CalcScore(Field & a, Field & b) const
    {
        sf::Vector2u dst
        {
            static_cast<unsigned>(abs(b.GetMapPosition().x - a.GetMapPosition().x)),
            static_cast<unsigned>(abs(b.GetMapPosition().y - a.GetMapPosition().y))
        };

        return (dst.x > dst.y ? 14 * dst.y + 10 * (dst.x - dst.y) :
                                14 * dst.x + 10 * (dst.y - dst.x));
    }

    FieldContainer PathFinder::GetNeighbours(Field & f, Map & m) const
    {
        FieldContainer neighbours{};

        //cout << "checking neighbours for field: { " << f.GetMapPosition().x << ", " << f.GetMapPosition().y << " }\n";
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                int xPos = f.GetMapPosition().x + x;
                int yPos = f.GetMapPosition().y + y;

                if (x == 0 && y == 0) //dont check the same field
                    continue;

                //check that field is in the map
                bool isInTheMap = (xPos >= 0 && yPos >= 0 && xPos < m.GetMapSize().x && yPos < m.GetMapSize().y);

                if (isInTheMap)
                {
                    neighbours.push_back(m.GetFields()[xPos][yPos]);
                }
            }
        }

        return neighbours;
    }

    FieldContainer PathFinder::FindPath(Map& map, Field& a, Field& b)
    {
        FieldSet open = {};   //not expanded fields
        FieldSet closed = {}; //expanded fields

        a.SetHCost(CalcScore(a, b)); //calculate h cost for start field, gcost equals 0
        open.insert(&a);             //add start field to open vector

        while (!open.empty()) //while we have unexpanded fields in open set
        {
            Field * current = *open.begin(); //set current field

            //if current checked field is our goal field
            if (*current == b)
            {
                return
                    ReconstructPath(&a, current); //return reversed path
            }

            closed.insert(current); //end of checking current field, add it to closed vector...
            open.erase(open.find(current)); //set solution

            //get neighbours of current field
            for (auto f : GetNeighbours(*current, map))
            {
                //continue if f is unavailable
                if (closed.find(f) != closed.end() || !f->IsWalkable())
                {
                    continue;
                }

                //calculate tentative g cost, based on current cost and direction changed
                unsigned tentativeGCost = current->GetGCost() + (current->GetMapPosition().x != f->GetMapPosition().x && current->GetMapPosition().y != f->GetMapPosition().y ? 14 : 10);

                bool fieldIsNotInOpenSet = open.find(f) == open.end();
                if (tentativeGCost < f->GetGCost() || fieldIsNotInOpenSet)
                {
                    f->SetGCost(tentativeGCost);
                    f->SetHCost(CalcScore(*f, b));
                    f->SetParent(*current);

                    if (fieldIsNotInOpenSet)
                    {
                        open.insert(f);
                    }
                }
            }
        }
        return {}; //no path anaviable
    }

    FieldContainer PathFinder::ReconstructPath(Field * a, Field * current) const
    {
        FieldContainer totalPath { current };

        while (!(current == a))
        {
            totalPath.push_back(current);
            current->SetAsPartOfPath(true);
            current = current->GetParent();
        }

        std::reverse(totalPath.begin(), totalPath.end()); //reverse the path
        return totalPath;
    }

#pragma endregion PathFinder

...and I am wondering why when I use std::list instead of std::vector, time of execute path finding algorithm equals or is bigger than in std::vector, because there are only adding operations for FieldContainer.

I was checking execution times 10 times in a loop using std::chrono high resolution timer:

#include "MapDrawer.h"
#include <iostream>

#include "Navigation.hpp"
//clock
#include <chrono>

typedef std::chrono::high_resolution_clock ChronoClock;

using namespace sf;

bool pathFound = false;

FieldContainer path;
Map gameMap;

const sf::Vector2f mapSize { 300, 300 };

void Test()
{
    for (int i = 0; i < 10; i++)
    {
        gameMap = { static_cast<sf::Vector2u>(mapSize) };
        PathFinder pathFinder{};

        auto t1 = ChronoClock::now();

        path = pathFinder.FindPath(gameMap, *gameMap.GetFields()[0][0], *gameMap.GetFields()[(int)(mapSize.x - 1)][(int)(mapSize.y - 1)]);

        auto t2 = ChronoClock::now();

        std::cout << "Delta: " << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << " milliseconds\n";
    }
}


void MapDrawer::draw(RenderTarget &target, RenderStates states) const
{
    if (!pathFound)
    {
        Test();
        pathFound = true;
    }
    ////////////////
}

Results in ms (DEBUG)

map size        container       time (average)
  50x50           list               13,8
  50x50          vector              12,4
 150x150          list               54,0
 150x150         vector              41,9
 300x300          list              109,9
 300x300         vector             100,8

Result in ms (RELEASE)

map size        container       time (average)
 500x500          list               9,3
 500x500         vector              7,4
1500x1500         list              23,9
1500x1500        vector             23,7

So it looks like the vector is more fast than list, but why, since list should be faster in adding operations?

Btw. is that algorithm fast? If no, then what I could change to increase the speed?

Thanks.

Aucun commentaire:

Enregistrer un commentaire