Sign in to follow this  
Volvic

Creating a Graph Data Structure

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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:

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.

Share this post


Link to post
Share on other sites
A more abstracted version, allowing for non-NESW connections, would be:
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this