CODEWITHSUNDEEP
algorithmgraphgraph-algorithmpath-finding
Nikita
Nikita

Reputation: 337

How to optimize a large graph for pathfinding algorithms?

I develop a small program where an user can create a simple diagrams with abstract blocks connected by lines, for example, flow charts or structural diagrams. One of the clause of the statement of work is that lines have to get around other blocks\lines and don't intersect them while moving.

Illustration

enter image description here

I tried to use pathfinding algorithms like A* or Lee's algorithm for it and consider a workspace (a window with diagram elements) like a graph - one pixel is one graph node. However, moving of blocks\lines causes the significant time delay (for example, pathfinding in the workspace with size 500x500 takes about 320-360 ms). It seems like the graph is too big for those algorithms.

Could you please tell me how to reduce the number of nodes with regard to this case? Maybe is there a way to speed up those algorithms or use something other for it?!

Upvotes: 1

Views: 352

Answers (1)

btilly
btilly

Reputation: 46507

Don't think of this as a graph theory problem, think of it as a physics problem.

Visualize it as follows. Each block has a specified force pulling it towards the last place that it was put. Line segments, blocks, and the edge of the graph repel each other with an inverse square law (except that the end of the line you are drawing doesn't repel blocks in front of it). Under sufficient stress, a line segment can be broken into smaller line segments that have a pull towards returning to being a straight line.

The dynamics are complicated, but the number of entities is the number of objects you see on screen, not the number of pixels it is drawn on. Therefore you'll be able to do updates relatively quickly.

You'll need to play with the dynamics a bit to get a good experience, but this should be a more tractable approach.

Upvotes: 3

Related Questions