Jump to content
• Advertisement

# How do i reduce number of nodes in a graph?

This topic is 4235 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

##### Share on other sites
Advertisement
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

##### 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

##### Share on other sites
Can't you use the same method to create both a dense and a sparse graph?

#### Share this 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

##### 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

##### 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

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
Rutin
24
2. 2
3. 3
JoeJ
20
4. 4
5. 5
• Advertisement

• 9
• 46
• 41
• 23
• 13
• ### Forum Statistics

• Total Topics
631746
• Total Posts
3002022
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!