-3

i would like some help for my AStar algorithm search, which takes from my point of view far to long. Even though my map is with 500 * 400 coordinates(objectively is my tile graph a bit smaller since I don't took the walls into the TileGraph.) large, I would like to expect the result after a few seconds. The world looks like this, despite the task not being mine

img

I want to search from marked coordinates "Start"(120|180) to "Ziel"(320|220), which currently takes 48 minutes. And sorry for all, who don't speak german, but the text at the picture isn't important.

At first I want to show you, what I've programmed for A*. In General adapted myself to the pseudocode at https://en.wikipedia.org/wiki/A*_search_algorithm .

bool AStarPath::Processing(Node* Start, Node* End)
m_Start = Start;
m_End = End;
for (Node* n : m_SearchRoom->GetAllNodes())
{
    DistanceToStart[n] = std::numeric_limits<float>::infinity();
    CameFrom[n] = nullptr;
}
DistanceToStart[m_Start] = 0;
NotEvaluatedNodes.AddElement(0, m_Start);
while (NotEvaluatedNodes.IsEmpty() == false)
{
    Node* currentNode = NotEvaluatedNodes.GetElement();
    NotEvaluatedNodes.DeleteElement();
    if (currentNode == m_End)
    {
        ReconstructPath();
        return true;
    }
    EvaluatedNodes.insert(currentNode);
    ExamineNeighbours(currentNode);
}
return false;
//End Processing

void AStarPath::ExamineNeighbours(Node* current)
for (Node* neighbour : m_SearchRoom->GetNeighbours(current))
{

    if (std::find(EvaluatedNodes.begin(), EvaluatedNodes.end(), neighbour) != EvaluatedNodes.end())
    {
        continue;
    }

    bool InOpenSet = NotEvaluatedNodes.ContainsElement(neighbour);

    float tentative_g_score = DistanceToStart[current] + DistanceBetween(current, neighbour);

    if (InOpenSet == true && tentative_g_score >= DistanceToStart[neighbour])
    {
        continue;
    }

    CameFrom[neighbour] = current;

    DistanceToStart[neighbour] = tentative_g_score;

    float Valuation = tentative_g_score + DistanceBetween(neighbour, m_End);

    if (InOpenSet == false)
    {
        NotEvaluatedNodes.AddElement(Valuation, neighbour);
    }
    else
    {
        NotEvaluatedNodes.UpdatePriority(neighbour, Valuation);
    }
}

//END ExamineNeighbours

double AStarPath::DistanceBetween(Node* a, Node* b)

return sqrt(pow(m_SearchRoom->GetNodeX(a) - m_SearchRoom->GetNodeX(b), 2) 
    + pow(m_SearchRoom->GetNodeY(a) - m_SearchRoom->GetNodeY(b), 2));
//END DistanceBetween

I'm sorry for the bad formatting, but I don't really know how to work with the code blocks here.

class AStarPath

private:

std::unordered_set<Node*> EvaluatedNodes;


Binary_Heap NotEvaluatedNodes;


std::unordered_map<Node*, float> DistanceToStart;


std::unordered_map<Node*, Node*> CameFrom;

std::vector<Node*> m_path;

TileGraph* m_SearchRoom;

//END Class AStarPath

Anyway, i have thought myself over my problem already and changed some things. Firstly, I implemented a binary heap instead of the std::priority_queue. I used a page at policyalmanac for it, but I'm not permitted to add another link, so I can't really give you the address. It improved the performance, but it still takes quite long as I told at the beginning. Secondly, I used unordered containers (if there are two options), so that the containers don't have to be sorted after the changes. For my EvaluatedNodes I took the std::unordered_set, since from my knowledge it's fastest for std::find, which I use for containment checks. The usage of std::unordered_map is caused by the need of having seperate keys and values. Thirdly, I thought about splitting my map into nodes, which represent multiple coordinates(instead of now where one node represents one coordinate) , but I'm not really sure how to choose them. I thought about setting points at position, that the algorithm decises based on the length and width of the map and add neighbouring coordinates, if there aren't a specific distance or more away from the base node/coordinate and I can reach them only from previous added coordinates. To Check whether there is a ability to walk, I would have used the regular A*, with only the coordinates(converted to A* nodes), which are in these big nodes. Despite this I'm unsure which coordinates I should take for the start and end of this pathfinding. This would probably reduce the number of nodes/coordinates, which are checked, if I only use the coordinates/nodes, which were part of the big nodes.(So that only nodes are used, which where part of the bigger nodes at an upper level)

I'm sorry for my english, but hope that all will be understandable. I'm looking forward to your answers and learning new techniques and ways to handle problems and as well learn about all the hundreds of stupids mistakes I produced. If any important aspect is unclear or if I should add more code/information, feel free to ask.

EDIT: Binary_Heap

class Binary_Heap

private:

std::vector<int> Index;
std::vector<int> m_Valuation;
std::vector<Node*> elements;

int NodesChecked;

int m_NumberOfHeapItems;

void TryToMoveElementUp(int i_pos);

void TryToMoveElementDown(int i_pos);

public:

Binary_Heap(int i_numberOfElements);


void AddElement(int Valuation, Node* element);


void DeleteElement();


Node* GetElement();

bool IsEmpty();

bool ContainsElement(Node* i_node);

void UpdatePriority(Node* i_node, float newValuation);


Binary_Heap::Binary_Heap(int i_numberOfElements)

Index.resize(i_numberOfElements);
elements.resize(i_numberOfElements);
m_Valuation.resize(i_numberOfElements);

NodesChecked = 0;

m_NumberOfHeapItems = 0;

void Binary_Heap::AddElement(int valuation, Node* element)

++NodesChecked;
++m_NumberOfHeapItems;

Index[m_NumberOfHeapItems] = NodesChecked;

m_Valuation[NodesChecked] = valuation;

elements[NodesChecked] = element;

TryToMoveElementUp(m_NumberOfHeapItems);

void Binary_Heap::DeleteElement()

elements[Index[1]] = nullptr;
m_Valuation[Index[1]] = 0;

Index[1] = Index[m_NumberOfHeapItems];
--m_NumberOfHeapItems;

TryToMoveElementDown(1);

bool Binary_Heap::IsEmpty()

return m_NumberOfHeapItems == 0;

Node* Binary_Heap::GetElement()

return elements[Index[1]];

bool Binary_Heap::ContainsElement(Node* i_element)

return std::find(elements.begin(), elements.end(), i_element) != elements.end();

void Binary_Heap::UpdatePriority(Node* i_node, float newValuation)

if (ContainsElement(i_node) == false)
{
    AddElement(newValuation, i_node);
}
else
{
    int treePosition;

    for (int i = 1; i < Index.size(); i++)
    {
        if (elements[Index[i]] == i_node)
        {
            treePosition = i;

            break;
        }
    }

    //Won't influence each other, since only one of them will change the position
    TryToMoveElementUp(treePosition);
    TryToMoveElementDown(treePosition);
}

void Binary_Heap::TryToMoveElementDown(int i_pos)

int nextPosition = i_pos;

while (true)
{
    int currentPosition = nextPosition;

    if (2 * currentPosition + 1 <= m_NumberOfHeapItems)
    {
        if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition]])
        {
            nextPosition = 2 * currentPosition;
        }
        if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition + 1]])
        {
            nextPosition = 2 * currentPosition + 1;
        }
    }
    else
    {
        if (2 * currentPosition <= m_NumberOfHeapItems)
        {
            if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition]])
            {
                nextPosition = 2 * currentPosition;
            }
        }
    }

    if (currentPosition != nextPosition)
    {
        int tmp = Index[currentPosition];
        Index[currentPosition] = Index[nextPosition];
        Index[nextPosition] = tmp;
    }
    else
    {
        break;
    }
}

void Binary_Heap::TryToMoveElementUp(int i_pos)

int treePosition = i_pos;

while (treePosition != 1)
{
    if (m_Valuation[Index[treePosition]] <= m_Valuation[Index[treePosition / 2]])
    {
        int tmp = Index[treePosition / 2];

        Index[treePosition / 2] = Index[treePosition];

        Index[treePosition] = tmp;

        treePosition = treePosition / 2;
    }
    else
    {
        break;
    }
}
Community
  • 1
  • 1
JohTa
  • 1
  • 2
  • 2
    I am not sure this is suited for SO but, 48 minutes for a A* on a graph with 20k nodes?! Either you are running this on a very very very [...] very old computer, either you have a strong issue in your implementation. Even if you'd go through the whole set of nodes each time you'd had to check for something, it would not take 48 minutes! You should profile your program to check where it is taking time, because with the current you provide no one will be able to help you (especially you did not provide your Binary_Heap implementation). – Holt Jun 06 '16 at 19:33
  • Why is it that hardly anyone posts exactly what optimizations they used when they built their application? If you're timing an unoptimized or a "debug build", please retest by timing a release, optimized version. There are far too many posts on SO where we get "why is my program slow" questions, and as soon as it is requested to turn optimizations on, the problem of slowness goes away. – PaulMcKenzie Jun 06 '16 at 19:44
  • I have used this(http://www.policyalmanac.org/games/binaryHeaps.htm). The Computer isnt as old. I will edit my Post with the binary heap, just have to make the code not look like work in process(especially the variable names) – JohTa Jun 06 '16 at 19:49
  • @PaulMcKenzie: I still have the results in mind of change from priority_queue to Binary_Heap, the others I add later: with priority queue it took for 200 iterations(changed the while in to a for loop) about 45seconds and with Binary_Heap 34seconds. – JohTa Jun 06 '16 at 19:57
  • @JohTa Changing data structures is fine, but the point I'm making is that you should never time debug or unoptimized builds. It's a waste of time -- always time release, optimized builds. – PaulMcKenzie Jun 06 '16 at 20:01
  • 1
    This should be moved to code review. – Colin Basnett Jun 06 '16 at 20:15
  • 1
    @ColinBasnett Ok, then I'm sorry. – JohTa Jun 06 '16 at 20:21
  • @PaulMcKenzie I will keep that in mind. Haven't bothered with debug or release mode, but atleast the creation of the world is only a 1/3 long in comparision to debug build. I have to check tomorrow the actual pahtfinding.time. Thank you ! – JohTa Jun 06 '16 at 20:25
  • 2
    @ColinBasnett Code review has some pretty strict requirements. This is going to take a lot of clean-up before it will be met with anything but a barrage of downvotes and a hold. JohTa, do yourself a favour and give this a read before reposting: http://codereview.stackexchange.com/help/how-to-ask – user4581301 Jun 06 '16 at 20:51
  • I edited the image link format so it is viewable and try to get rid of the double line-ing in your code but after spot compile errors I stop as it is pointless to do for such. Where are your `{ }` for functions? For example first line of code `bool AStarPath::Processing(Node* Start, Node* End) m_Start = Start;` should be `bool AStarPath::Processing(Node* Start, Node* End) { m_Start = Start;` or you got some weird compiler allowing this? Also if node approach is slow for this why not use [2D map A* approach](http://stackoverflow.com/a/23779490/2521214) instead? – Spektre Jun 07 '16 at 06:55
  • The text says "Drive the c't racer in the fewest possible steps from 'Start' to 'Zeil' without hitting any of the walls." ('Ziel' is German for 'target' or 'destination'). (It may be "shortest course" rather than "fewest steps") – Martin Bonner supports Monica Jun 07 '16 at 14:30
  • @MartinBonner: As I told, the c't challenge isn't mine, so that the text doesn't matter. I'm using AStar to get a Path for the actual pathfinding to lead them around the shortest path. I've now decided to improve the heuristics and not just use the euclidean distance instead I'm trying to guess the length of the path around the wall, so that the algorithm has to check less nodes. – JohTa Jun 08 '16 at 19:45
  • @Spekte: Well, thanks anyway. It looked strange with the curly brackets, so that I've removed them. Doesn't seem to be the best idea. – JohTa Jun 08 '16 at 19:46

1 Answers1

1

This line introduces major inefficiency, as it needs to iterate over all the nodes in the queue, in each iteration.

bool InOpenSet = NotEvaluatedNodes.ContainsElement(neighbour);

Try using a more efficient data structure, e.g. the unordered_set you use for EvaluatedNodes. Whenever you push or pop a node from the heap, modify the set accordingly to always contain only the nodes in the heap.

pepo
  • 669
  • 4
  • 7