Modifing AStar algorithm to connect gates in logic scheme

Question

I've been working on a logic scheme simulator for a while now. The whole thing is pretty much working but there's an issue that I can't seem to solve.

Connections in a logic scheme should be vertical and horizontal. They should avoid logic gates and have as few turns as possible (avoiding the staircase effect). Connections can also intersect but they can never overlap.

I used AStar algorithm to find the shortest and the nicest path between two logic gates. The heuristics for pathfinding is Manhattan distance while the cost between the two nodes is a dimension of a single square on the canvas.

The whole issue arises between two conditions. "Min turns" and "no overlap". I solved "min turns" issue by punishing the algorithm with double the normal cost when it tries to make a turn. That causes the algorithm to postpone all turns to the latest possible moment which causes my next picture.

My condition of no overlapping is forbidding the second input from connecting to the second free input of the AND gate (note: simulator is made for Android and the number of inputs is variable, that's why inputs are close to each other). A situation like this is bound to happen sooner or later but I would like to make it as late as possible.

I have tried to:

• introdue "int turnNumber" to count how many turns have been made so far and punish paths that make too many turns. (algorithm takes too long to complete, sometimes very very long)
• calculate Manhattan distance from the start to the end. Divide that number by two and then remove the "double cost" punishment from nodes whose heuristics are near that middle. (for some situations algorithm fell into infinite loop)

Are there any ideas on how to redistribute turns in the middle so as many as possible connections can be made between logic gates while still satisfying the "min turn" condition?

In case you'd like to see the code: https://gist.github.com/linaran/c8c493bb54cfca764aeb

Note: The canvas that I'm working with isn't bounded. EDIT: method for calculating cost and heuristics are -- "calculateCost" and "manhattan"

Answer 1

1. You wrote that you already tried swap start/end position

• but my guts tell me if you compute path from In to Out
• then the turn is near Output which is in most cases OK because most Gates has single output.

2. Anyway I would change your turn cost policy a bit:

• let P0,P1 be the path endpoints
• let Pm=(P0+P1)/2 be the mid point
• so you want the turn be as close to the mid point as it can be
• so change turn cost tc to be dependent to the distance from Pm
• tc(x,y)=const0+const1*|(x,y)-Pm|
• that should do the trick (but I didn't test this so handle with prejudice)
• it could create some weird patterns so try euclidean and manhatan distances
• and chose the one with better results
• 

3. Another approach is

• fill the map from both start and end points at once
• And stop when they meet
• you need to distinguish between costs from start and end point
• so either use negative for star and positive values for end point origin
• or allocate ranges for the two (range should be larger then map size xs*ys in cells/pixels)
• or add some flag value to the cost inside map cell

4. you can mix 1. and 2. together

• so compute Pm
• find nearest free point to Pm and let it be P2
• and solve path P0->P2 and P1->P2
• so the turns will be near P2 which is near Pm which is desired

[notes]

• the 3th approach is the most robust one and should lead to desired results