Sign in to follow this  

How do i reduce number of nodes in a graph?

This topic is 4017 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! I have a graph for which my units navigate along in my game, its pretty dense so i would like to generate a coarser version of this graph. Are there any good algorithms/code for reducing graphs? I've thought a lot upon this, but can't figure out a really good algorithm. And google doesn't answer me either. Thanks for any help, T :)

Share this post


Link to post
Share on other sites
You're going to be a lot more specific.

Start with telling us what your graph represents - is it suitable waypoints? Level Geometry? A regular square grid?

Also tell us how you are generating the graph.

Share this post


Link to post
Share on other sites
Each node in the graph has a position, and a list of neighbour nodes, which can be safely reached from that node.

They are walkable paths in a landscape, and is used for navigation. I.e an A* routine finds the shortest path between two positions in the landscape by pathing through the graph.

Now the landscape is really huge, and I really need a less dense graph for longer searches, unless i want to search some 100.000 nodes. (and i dont ;)

/Thanks, T



Share this post


Link to post
Share on other sites
The routine that creates the dense (original) graph cannot auto-generate nodes that far apart. That routine does several tests to make sure a character can walk
across the landscape without getting stuck on a slope or an obsticle of some kind between two of its node points. It would be to hard to rewrite it to work for longer distances.

It would be best if it could just reduce the original graph, for a far search and the do smaller searches in the dense graph as characters pass nodes.

:)

/T

Share this post


Link to post
Share on other sites
With a smart algorithm and a bit of preprocessing searching a shortest path between random points in a 100k node grid is less than 1ms on a modern computer: smart algorithm

For reducing the graph you could just delete nodes and adjust the adjacent edges in a way that retains connectivity. Do you store any kind of length for edges in your graph? You probably need it for the reduced graph.

Share this post


Link to post
Share on other sites
An idea: split your map into 'cells' on a grid, one 'meganode' per cell, as long as all the nodes in one cell are interconnected (they usually will be). Connect adjacent meganodes if there is a route between any nodes within the two cells. If a cell contains multiple 'groups', give it more than one 'meganode' (one for each interconnected cluster, with the node placed at the 'average' location of all nodes in the cluster) and treat each one the same.

Then, for long distance pathfinding, find the shortest route in the sparse map to find which cells the route passes through, and then find the shortest route in the subset of the dense map that contains only those cells.

Share this post


Link to post
Share on other sites

This topic is 4017 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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