A Star



  • Hey,

    ich versuche aktuell A Star zu implementieren. Allerdings scheine ich den Algorithmus noch nicht zu 100% verstanden zu haben. Meine aktuelle Implementation funkioniert hin und wieder perfekt, aber scheitert dann plötzlich bei der Wegfindung, obwohl man einen möglichen Weg mit dem bloßen Auge erkennen kann. Auch Endlosschleifen kommen leider vor.

    Mir ist es wichtig, dass der Algorithmus einen Weg findet oder mir definitiv sagt, dass es keinen gibt.

    Ich glaube, dass der Fehler in Zeile 170 oder 174 liegt. Ich habe mich an folgendes Tutorial gehalten: http://wiki.gamegardens.com/Path_Finding_Tutorial

    Dort steht nämlich folgendes (fett markiert):

    create the open list of nodes, initially containing only our starting node
    create the closed list of nodes, initially empty
    while (we have not reached our goal) {
    consider the best node in the open list (the node with the lowest f value)
    if (this node is the goal) {
    then we're done
    }
    else {
    move the current node to the closed list and consider all of its neighbors
    for (each neighbor) {
    if (this neighbor is in the closed list and our current g value is lower) {
    update the neighbor with the new, lower, g value
    change the neighbor's parent to our current node

    }
    else if (this neighbor is in the open list and our current g value is lower) {
    update the neighbor with the new, lower, g value
    change the neighbor's parent to our current node

    }
    else this neighbor is not in either the open or closed list {
    add the neighbor to the open list and set its g value
    }
    }
    }
    }

    Was damit genau gemeint ist, ist mir nicht klar, weshalb ich es "irgendwie" gemacht habe. Zu finden in Zeile 170 und 174.

    Hier ist mein aktueller Ansatz als vollständiges Beispiel:

    #include <iostream>
    #include <cassert>
    #include <vector>
    #include <cmath>
    #include <algorithm>
    #include <ctime>
    //#include <Windows.h>
    
    const size_t TILES_X = 30;
    const size_t TILES_Y = 20;
    
    class TileMap
    {
    private:
    	char tiles[TILES_X][TILES_Y];
    
    public:
    	TileMap()
    	{
    		for (size_t x = 0; x < TILES_X; ++x)
    		{
    			for (size_t y = 0; y < TILES_Y; ++y)
    			{
    				tiles[x][y] = '.';
    			}
    		}
    	}
    
    	char getTile(size_t x, size_t y) const
    	{
    		assert(inBounds(x, y));
    
    		return tiles[x][y];
    	}
    
    	void setTile(size_t x, size_t y, char val)
    	{
    		assert(inBounds(x, y));
    
    		tiles[x][y] = val;
    	}
    
    	bool inBounds(long x, long y) const
    	{
    		return (x >= 0 && x < TILES_X) && (y >= 0 && y < TILES_Y);
    	}
    
    	void print()
    	{
    		for (size_t y = 0; y < TILES_Y; ++y)
    		{
    			for (size_t x = 0; x < TILES_X; ++x)
    			{
    				std::cout << getTile(x, y);
    			}
    
    			std::cout << "\n";
    		}
    	}
    };
    
    class AStar
    {
    	private:
    		TileMap& map;
    
    	public:
    		AStar(TileMap& map_) 
    			: map(map_)
    		{
    		}
    
    		void calculate(size_t startX, size_t startY, size_t endX, size_t endY, long max = 0)
    		{
    			struct Node
    			{
    				size_t x;
    				size_t y;
    				size_t steps;
    				size_t distance;
    				size_t total;
    
    				Node(size_t x_, size_t y_, size_t distance_, size_t steps_ = 0)
    					: x(x_), y(y_), distance(distance_), steps(steps_), total(steps_ + distance_)
    				{
    				}
    
    				bool operator<(const Node& rhs) const
    				{
    					return total > rhs.total;
    				}
    			};
    
    			std::vector<Node> openNodes;
    			std::vector<Node> closedNodes;
    			std::vector<Node> path;
    
    			openNodes.push_back(Node(startX, startY, hDistance(startX, startY, endX, endY)));
    
    			long counter = 0;
    			while (!openNodes.empty())
    			{
    				std::sort(openNodes.begin(), openNodes.end());
    
    				Node current = *(openNodes.end() - 1);
    
    				if (max != 0)
    				{
    					if (++counter > max)
    					{
    						map.setTile(startX, startY, 'S');
    
    						map.setTile(endX, endY, 'E');
    
    						std::cout << "No path\n";
    						return;
    					}
    				}
    
    				openNodes.pop_back();
    
    				path.push_back(current);
    
    				if (current.x == endX && current.y == endY)
    				{
    					for (std::vector<Node>::iterator it = path.begin(); it != path.end(); ++it)
    					{
    						map.setTile(it->x, it->y, '-');
    					}
    
    					map.setTile(startX, startY, 'S');
    					map.setTile(endX, endY, 'E');
    
    					return;
    				}
    				else
    				{
    					closedNodes.push_back(current);
    
    					for (int x = -1; x < 2; ++x)
    					{
    						for (int y = -1; y < 2; ++y)
    						{
    							int posX = current.x + x;
    							int posY = current.y + y;
    
    							bool inClosedList = false;
    
    							for (std::vector<Node>::iterator it = closedNodes.begin(); it != closedNodes.end(); ++it)
    							{
    								if (it->x == posX && it->y == posY)
    								{
    									inClosedList = true;
    									break;
    								}
    							}
    
    							bool inOpenList = false;
    							for (std::vector<Node>::iterator it = openNodes.begin(); it != openNodes.end(); ++it)
    							{
    								if (it->x == posX && it->y == posY)
    								{
    									inOpenList = true;
    									break;
    								}
    							}
    
    							if (inClosedList && current.total > hDistance(posX, posY, endX, endY) + current.steps + 1)
    							{
    								current = Node(posX, posY, hDistance(posX, posY, endX, endY), current.steps + 1);
    							}
    							else if (inOpenList && current.total > hDistance(posX, posY, endX, endY) + current.steps + 1)
    							{
    								current = Node(posX, posY, hDistance(posX, posY, endX, endY), current.steps + 1);
    							}
    							else
    							{
    								if (map.inBounds(posX, posY) && map.getTile(posX, posY) != '#')
    								{
    									openNodes.push_back(Node(posX, posY, hDistance(posX, posY, endX, endY), current.steps + 1));
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    
    		double sq(long x)
    		{
    			return x *x;
    		}
    
    		size_t hDistance(long x1, long y1, long x2, long y2)
    		{
    			return std::abs(x1 - x2) + std::abs(y1 - y2); // Manhattan distance
    
    			//return std::sqrt(sq((x1 - x2)) + sq((y1 - y2))); // Euclidean distance
    		}
    };
    
    int main()
    {
    	srand(time(NULL));
    
    	TileMap map;
    
    	AStar astar(map);
    
    	for (size_t x = 0; x < TILES_X; ++x)
    	{
    		for (size_t y = 0; y < TILES_Y; ++y)
    		{
    			char c = '.';
    
    			if (rand() % 5 == 0)
    			{
    				c = '#';
    			}
    
    			map.setTile(x, y, c);
    		}
    	}
    
    	astar.calculate(rand() % TILES_X, rand() % TILES_Y, rand() % TILES_X, rand() % TILES_Y, 1000);
    
    	map.print();
    }
    

    Würde mich über Tipps sehr freuen. Möchte diesen eigentlich recht einfachen Algorithmus ganz gerne realisiert bekommen.

    Viele Grüße und noch ein schönes Wochenende



  • Nur als Anmerkung: Falls es dir nicht um das Implementieren selbst, sondern nur um das Resultat geht, könntest du auch Boost.Graph anschauen, dort ist auch ein A* umgesetzt.


Log in to reply