How do i reduce number of nodes in a graph?
Author
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 :)
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.
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.
Author
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
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
Author
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
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
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
