Witam.
Mam funkcję typu:
template <typename CostF>
vector<Coord> path(Coord a, Coord b, CostF cost)
'cost' to funktor, który zwraca wartość dla dwóch zadanych parametrów i nie może być na stałe wbudowany w funkcję.
Chcę ustawić w pewnej klasie tą funkcję jako friend. Jak to zrobić?
przyznam, ze nie mam czasu teraz odpalic kompilatora.. nie wystarczy w ten sposob?
class X
{
friend template<typename CostF> vector<Coord> path(Coord a, Coord b, CostF cost);
};
a moze problem masz z czyms innym w tej okolicy, tylko zle pytanie zadales? przeczytaj http://www.parashift.com/c++-faq-lite/templates.html punkt [35.16]
Dzięki :D Strona bardzo mi pomogła.
Klase też trzeba było zadeklarować jako template i miałem mnóstwo problemów ze zmianą całego kodu. Na dodatek g++ nie obsługuje słowa export, więc cała implementacja siedzi w .h.
Linijka musi wyglądać tak:
friend std::vector<Coord> astar_path <>(Coord start, Coord end, CostFunction cost);
Właściwie jestem przekonany, że problem wynika ze słabego projektu... Chciałem napisać moduł pathfindera z algorytmem A* - potrzebny mi do wyznaczania ścieżki na mapie 2d, ale żeby była możliwość łatwej modyfikacji do innych celów. W szczególności chcę mieć możliwość wywołania z różną funkcją kosztów, np. z uwzględnieniem poruszania się po przekątnej między kwadratami itp. i to dla różnego formatu map.
Dopiero uczę się c++, na dodatek sam, więc mam problemy z kodowaniem w przystępny sposób.
Kod jest poniżej. Proszę o krytykę.
Czy warto tworzyć nową klasę dla całego tego pathfindera? Miałbym wówczas możliwość tworzenia klas pochodnych z różnymi funkcjami kosztów itp., ale czy to byłby lepszy sposób rozwiązania problemu niż pojedyncza funkcja?
A może zrobić klasę statyczną?
Na razie wygląda to tak:
Plik astar.h:
#ifndef _ASTAR_H
#define _ASTAR_H
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
/**
* Represents single location on the map
*/
struct Coord {
int x, y;
Coord() : x(0), y(0) {}
Coord(int _x, int _y) : x(_x), y(_y) {}; //so it's possible to easily create new coords, like: Coord a(5, 1)
//overloaded operators to determine if two coordinates are the same or different
bool operator==(const Coord &c) const;
bool operator!=(const Coord &c) const;
};
/**
* Nodes for path searching
*
* This contains coordinate on the map, parent tile and proper costs for pathfinder internal use.
* Inherits == and != operators from Coord, as well as x and y.
* Has to be here for reason explained below.
* Can't even make this private...
*/
template <typename CostFunction>
std::vector<Coord> astar_path(Coord start, Coord end, CostFunction cost);
template <typename CostFunction>
class Node: public Coord {
Node *parent;
int F; //total cost rating of the node: F=G+H
int G; //total cost to get to this node from the starting one
int H; //distance from this node to end determined by heuristic
//this may be neccesary too
//bool operator>(const Node<CostFunction> &node) const;
Node() : parent(NULL), F(0), G(0), H(0) {}
Node(Coord pos) : Coord(pos), parent(NULL), F(0), G(0), H(0) {}
Node(int _x, int _y) : Coord(_x, _y), parent(NULL), F(0), G(0), H(0) {}
//test
friend std::vector<Coord> astar_path <>(Coord start, Coord end, CostFunction cost);
public:
//need this to determine which nodes have minimum F cost - must be public, so std algorithm can use it, may set them friend later
bool operator<(const Node &node) const
{
return F < node.F;
}
bool operator>(const Node &node) const
{
return F > node.F;
}
};
/**
* Heuristics function
*
* This one just returns Manhattan distance from one coordinate to another.
*/
int Hfunc(Coord a, Coord b);
/**
* Calculate a path
*
* Calculates a path from coordinate 'start' to coordinate 'end'.
* Returns a stl vector of coordinates, empty if there's no path.
* 'cost' shall be a functor that returns int cost of moving between two Coords given, ie. cost(a, b),
* where a is a starting tile and b is destination. Should return -1 when b is inaccesible.
* This has to be here with all the implementation because C++ is stupid.
*/
template <typename CostFunction>
std::vector<Coord> astar_path(Coord start, Coord end, CostFunction cost) {
//list that stores open nodes - to search
std::list<Node<CostFunction> > open; //TODO: make this a binary heap
//TODO: implement nice binary heap
//list that stores closed nodes - already searched through
std::list<Node<CostFunction> > closed;
//set up starting node
Node<CostFunction> n_start(start);
//set up target node
Node<CostFunction> n_end(end);
//add starting node to open list
open.push_back(n_start); //only one element in the list so it doesn't need sorting yet
Node<CostFunction> n_cur;
while(true) {
//get the lowest F cost node from open list
n_cur = open.front(); //front() returns REFERENCE or whatever
//std::cout << "<";
if (!open.empty()) open.pop_front(); //this causes serious fault when not checked if empty
//one would think error handling would be implemented in std classes
//std::cout << ">";
//put it into closed list
closed.push_back(n_cur);
//get a pointer to this node - this will be child nodes parent node
Node<CostFunction> *p = &closed.back(); //needs to be a pointer to object in list, not its copy
//check for neighbors
//lalala..
//trying this way: iterate through 3x3 field surrounding n_cur position, skipping the center one
for (int i = -1; i <= 1; ++i) for (int j = -1; j <= 1; ++j) {
if (i == 0 && j == 0) continue; //skip the center coordinate
Node<CostFunction> n_new(n_cur.x + i, n_cur.y + j); //the current location
//check if it's inaccesible
//dG is now a cost of passing from n_cur to this cell
int dG = cost(n_cur, n_new);
if (dG == -1) continue; //it is inaccesible
//check if it's in closed list
if (find(closed.begin(), closed.end(), n_new) != closed.end()) {
//it is
//at least it should be with that fancy statement
continue;
}
//is it in open list?
typename std::list<Node<CostFunction> >::iterator i;
if ((i = find(open.begin(), open.end(), n_new)) != open.end()) {
//if it is, we have to check if that path to destination is shorter
//that is, if G of the tile is greater of G of n_cur + dG, we change the tile
if (i -> G > n_cur.G + dG) {
i -> parent = p;
i -> G = n_cur.G + dG;
//list needs sorting now
open.sort();
}
}
//it's not, so add it to open list and sort for change
//first make a valid node out of that
//set up parent
n_new.parent = p;
//calculate F, G and H
n_new.G = n_new.parent -> G + dG;
n_new.H = Hfunc(n_new, n_end);
n_new.F = n_new.H + n_new.G;
open.push_back(n_new);
open.sort();
}
//stop when the current node is the end node or there are no more nodes to search
if (n_cur == end || open.empty()) break;
}
//here we store the path
std::vector<Coord> path;
//see if there is a path
if (n_cur == end) {
//we start from the final node
Node<CostFunction> *i = &n_cur;
//save the current node and get it's parent one till NULL
while (i != NULL) {
Coord step(i -> x, i -> y);
path.push_back(step);
i = i -> parent;
}
}
return path;
}
#endif
astar.cc:
#include "astar.h"
/**
*
*/
bool Coord::operator==(const Coord &c) const
{
return ((x == c.x) && (y == c.y));
}
bool Coord::operator!=(const Coord &c) const
{
return !(*this == c);
}
/*
bool Node::operator<(const Node &node) const
{
return F < node.F;
}
bool Node::operator>(const Node &node) const
{
return F > node.F;
}*/
int Hfunc(Coord a, Coord b)
{
return abs(a.x - b.x) + abs(a.y - b.y);
}
i main.cc:
#include "astar.h"
#include <fstream>
class Map {
public:
Map() : layout(NULL) {}
int get_cost(Coord pos);
char get_char(Coord pos);
void set_char(Coord pos, char c);
friend std::istream &operator>>(std::istream &stream, Map &map);
friend std::ostream &operator<<(std::ostream &stream, const Map &map);
private:
int w, h;
char **layout;
} map;
int Map::get_cost(Coord pos)
{
int x = pos.x;
int y = pos.y;
if (x >= 0 && y >= 0 && x < w && y < h) {
if (layout[x][y] == '#') return -1;
else return 1;
} else return -1;
}
int get_pass(Coord a, Coord b)
{
return map.get_cost(b);
}
void Map::set_char(Coord pos, char c)
{
int x = pos.x;
int y = pos.y;
if (x >= 0 && y >= 0 && x < w && y < h)
layout[x][y] = c;
}
char Map::get_char(Coord pos)
{
return layout[pos.x][pos.y];
}
std::istream &operator>>(std::istream &stream, Map &map)
{
//read in the map dimensions
stream >> map.w >> map.h;
//allocate memory
map.layout = new char*[map.w];
for (int i = 0; i < map.w; map.layout[i++] = new char[map.h]);
//read in data
for (int i = 0; i < map.h && stream.good(); ++i) for (int j = 0; j < map.w && stream.good();) {
char c;
stream >> c;
if (c == '.' || c == '#') map.layout[j++][i] = c;
}
return stream;
}
std::ostream &operator<<(std::ostream &stream, const Map &map)
{
for (int i = 0; i < map.h; ++i) {
for (int j = 0; j < map.w; ++j) {
stream << map.layout[j][i];
}
stream << std::endl;
}
}
int main(int argc, char *argv[])
{
std::ifstream mapfile("map.txt");
mapfile >> map;
Coord a(0, 0);
Coord b(9, 5);
std::vector<Coord> path = astar_path(a, b, get_pass);
//std::cout << path.size() << std::endl;
std::vector<Coord>::iterator i;
for (i = path.begin(); i != path.end(); ++i)
map.set_char(*i, '+');
std::cout << map;
return 0;
}
oczywiscie - w ten sposob tez jest ok, ale doprawy, nie widze powodu dlaczego cala klasa Node mialalby byc template'em.. jedyne co potrzebuje nim byc i znac typ CostFunction to tylko ta jedna friend-metoda..
kompilujesz w g++ ? obejrze to to jak wroce do domu. na bank da sie pojedyncza metode u'template'owic to w sposob bardziej 'lokalny'
/**
* Nodes for path searching
*
* This contains coordinate on the map, parent tile and proper costs for pathfinder internal use.
* Inherits == and != operators from Coord, as well as x and y.
* Has to be here for reason explained below.
* Can't even make this private...
*/
template <typename CostFunction>
std::vector<Coord> astar_path(Coord start, Coord end, CostFunction cost);
template <typename CostFunction>
class Node: public Coord {
Node *parent;
zamien na:
**
* Nodes for path searching
*
* This contains coordinate on the map, parent tile and proper costs for pathfinder internal use.
* Inherits == and != operators from Coord, as well as x and y.
*/
template <typename CostFunction>
class Node: public Coord {
Node *parent;
oraz:
//test
friend std::vector<Coord> astar_path <>(Coord start, Coord end, CostFunction cost);
na:
template<typename CostFunction> friend std::vector<Coord> astar_path (Coord start, Coord end, CostFunction cost);
mowilem ze sie da spokojnie tak zrobic:)
Działa :)
quetzalcoatl napisał(a)
zamien na:
**
* Nodes for path searching
*
* This contains coordinate on the map, parent tile and proper costs for pathfinder internal use.
* Inherits == and != operators from Coord, as well as x and y.
*/
template <typename CostFunction>
class Node: public Coord {
Node *parent;
Usunąłem tylko ten template(pewnie pomyłka), tzn:
class Node: public Coord {
Node *parent;
.
.
.
template<typename CostFunction> friend std::vector<Coord> astar_path(Coord start, Coord end, CostFunction cost);
};
A czy sam pomysł jest dobry? Nie jestem pewien czy wykorzystanie templatów jest tu konieczne.
Zdaje się, że w podobny sposób jest zdefiniowany np. algorytm stl sort(3 parametr to funkcja uzytkownika), ale czy nie lepiej byłoby na przykład napisać małą bazową klasę z wirtualną funkcją cost() i w pochodnych implementować różne algorytmy? Tyle, że tak jak jest w tej chwili można jako argument podać zarówno zwykłą funkcję jak i funktor(np. obiekt Map z overloadowanym operator())...
Dzięki za odpowiedź :)
ups, racja, za malo skasowalem:)
a co do pytania - trudno powiedziec.. kazda opcja ma swoje plusy i minusy. w tym przypadku, chodzi o funkcje, algorytmu itp wiec raczej zostawilbym to na poziomie takim jak masz i nie wdrazal sztucznej hierarchii klas