How to optimize a large graph for pathfinding algorithms?

Question

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

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?!

one pixel is one graph node - this is your problem. There must be a way to make it less granular. I don't quite understand your problem so I can't say exactly how. — BlueRaja - Danny Pflughoeft
– BlueRaja - Danny Pflughoeft, Commented Oct 2, 2018 at 6:45
@BlueRaja-DannyPflughoeft As far as I know, I can't make the grid (the graph of workspace is considered as a grid here) more granular because the minimum size of a obstacle is 1x1 (part of line between blocks) — Nikita
– Nikita, Commented Oct 2, 2018 at 7:30
Can the blocks intersect? Correct me if I'm wrong but there might be much simpler solution to your problem. If blocks can't intersect and user moves one block then the path he created by moving the block could be a line connecting two blocks. Else try, there are some tools predefined for this purpose mentioned here - stackoverflow.com/questions/2459919/… — lukaszberwid
– lukaszberwid, Commented Oct 2, 2018 at 11:13
This sort of question could do with example image(s), even if they're just quick sketches in MS Paint. — m69 ''snarky and unwelcoming''
– m69 ''snarky and unwelcoming'', Commented Oct 2, 2018 at 18:49

btilly · Accepted Answer · 2018-10-02 21:23:57Z

3

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.

answered Oct 2, 2018 at 21:23

btilly

47.8k3 gold badges70 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to optimize a large graph for pathfinding algorithms?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related