Creating a Graph Data Structure
Hi guys i am wanting to create a graph data structure in c++ and link the edges to the nodes. so the graph looks like:
I want to create this graph so i can then implement a A* pathfinding algorithm. I have never created a graph data structure before so any help would be muchly appreciated.
A waypoint (i.e. nodes of the graph) is suitable to provide information for each point of interest in your dungeon. Obviously points of interest are most of those marked by the green dots in your image. Necessary data for each waypoint is what waypoints can be reached directly.
Another data perhaps necessary is the grid location of the waypoint. Looking furthur, informations of the length of the way (i.e. edges of the graphs) from one waypoint to the next may be of interest if the shortest way should be found. The length can be calculated from the grid location stored with waypoints. More advanced information for the way would be an additional walkability value for determining a maximum speed if using that way.
Until now waypoints like 14 and 21 need not necessarily be given. However, they become of interest if used e.g. to steer animations, since they allow to determine a change in direction of movement. However, for a pure path finding they are not needed.
Another aspect is whether ways may also be unidirectional, i.e. they lead from waypoint A to waypoint B but not the other way (e.g. a trap door).
Whether waypoints and/or ways are explicitely modeled by an own class depends on the amount of information inherent, and the amount of redundancy a solution will have. One possibility would be the following:
This (incomplete) solution allows to have unidirectional ways since each Waypoint stores only how to reach its possible neighbours, but not the way back. If a way back would be possible than the particular neighboured Waypoint must have set its _waypoints[oppositeDirection] to the original Waypoint.
Another data perhaps necessary is the grid location of the waypoint. Looking furthur, informations of the length of the way (i.e. edges of the graphs) from one waypoint to the next may be of interest if the shortest way should be found. The length can be calculated from the grid location stored with waypoints. More advanced information for the way would be an additional walkability value for determining a maximum speed if using that way.
Until now waypoints like 14 and 21 need not necessarily be given. However, they become of interest if used e.g. to steer animations, since they allow to determine a change in direction of movement. However, for a pure path finding they are not needed.
Another aspect is whether ways may also be unidirectional, i.e. they lead from waypoint A to waypoint B but not the other way (e.g. a trap door).
Whether waypoints and/or ways are explicitely modeled by an own class depends on the amount of information inherent, and the amount of redundancy a solution will have. One possibility would be the following:
typedef enum Direction_t { NORTH, EAST, SOUTH, WEST}class Waypoint {public: Waypoint* next(Direction_t inDirection) { return _waypoints[inDirection]; } float costs(Direction_t inDirection) const { float result = INFINITY; Waypoint* neighbour = next(inDirection); if(neighbour) { // the following assumes pure horizontal or vertical direction result = _walkability[inDirection] * ( ::abs(_x-neighbour->_x) + ::abs(_y-neighbour->_y) ); } return result; }private: // points to the next Waypoint indexed by a Direction_t; nil if no Waypoint in that direction Waypoint* _neighbours[4]; // a value for each neighboured Waypoint float _walkability[4]; // grid location int32_t _x, _y;};
This (incomplete) solution allows to have unidirectional ways since each Waypoint stores only how to reach its possible neighbours, but not the way back. If a way back would be possible than the particular neighboured Waypoint must have set its _waypoints[oppositeDirection] to the original Waypoint.
A more abstracted version, allowing for non-NESW connections, would be:
... i.e. a waypoint is just a list of connections to other waypoints and a location.
You're probably also going to want to read the connection information in from a (text) file.
struct Waypoint { struct Connection { Waypoint* target; float value }; std::vector<Connection> neighbours; // grid location; could be a point int32_t _x, _y;};
... i.e. a waypoint is just a list of connections to other waypoints and a location.
You're probably also going to want to read the connection information in from a (text) file.
I made a graph/map data struct in one of my classes at school and it worked out quite well.
Create a Vertex Class
Each Vertex has a list of connection lines
Each connection line has a Vertex it connects to
Then all you have to do is traverse through these vertecies to find a path.
I recommend you make your graph be templated. This way you can have whatever data stored at each vertex and whatever data stored at each connection.
Luck,
J
Create a Vertex Class
Each Vertex has a list of connection lines
Each connection line has a Vertex it connects to
Then all you have to do is traverse through these vertecies to find a path.
I recommend you make your graph be templated. This way you can have whatever data stored at each vertex and whatever data stored at each connection.
Luck,
J
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement