(I'm not quite sure if this is the right forum, since I'm not sure if to use A* or similar) Hi there. It's been quite a while that I once implemented such a search algorithm, so I'd like to ask if it would be the best option or whether anyone sees a better approach for the following scenario: Know MS Visio? There are boxes and diamonds drawn to display a flowchart, each of them having 4 X'es as connectors on their outlines. You can connect objects to each other, the connections are drawn as paths consisting of connected axis-aligned lines, ie. only horizontal and vertical lines allowed. I want to do something similar, and I have to find the shortest connection to draw between 2 objects with this hor/ver limitation, and, of course, not collide with other objects. I thought of implementing a path finding algorithm like A*, and in addition to actual movement, introducing a cost for "turning", ie. altering the drawing direction from vertical to horizontal line, and assigning this turning-cost an especially high value in order to have the algorithm produce a path which is shortest, but has as few as possible turns, since I want a tidy flowchart not full of a zig zag mess ;-) This is what came to my mind right now, but before I waste time on implementing this, maybe someone here has done such a task before and knows a better and maybe even easier way. Thanks in advance, unshaven

Yup, A* with extra cost for turning looks like the right approach to me. Notice that you need to consider "position (4,5) going horizontally" and "position (4,5) going vertically" as different nodes. The transition between those nodes is the one that gets the turning penalty. At least, that's how I would do it.

You could overlay your set of interconnected symbolic objects/structures (boxes diamonds...) and mark out the occupied squares (more than one per object) as unpassable (the objects connector points being outside these).

You would run A* and try to find a path. Path after path of additional connections gets added (the square marked as impassible). If it was too long (3 lefts to make a right...) you might be able to have the entire layout self-spread (expand the choke points by 1 dimension to let a path thru).

You may need a special crossover object for allowance for a path to occupy another paths square if they cross at 90 degrees (or 45??)...

If the program is fast enuf it might be possible to have it reorder the paths generated repeatedly and find a more compact set of paths (lessen the need of self spread) -- maybe even emply a GA type solution to mutate the path order ????

There is a JAVA demo in the SUN SDK that has a bunch of boxes connected by springs that funds equilibrium entrophy states for the interconnected boxes -- it could be modified (algorithm)maybe to have your tool shift placements and adjust itself to better placements...