Hi Andrew,I've been pecking away at QAutorouter little by little recently. For the Simple Router plugin, I've been building some experimental versions of the router based on the A* path finding algorithm using a Manhattan-length heuristic, and I have decided to stick with that approach for path finding.
Short term work focuses on developing both an A*-optimized open-set (priority queue) and closed-set container for both optimizing execution speed and memory consumption. My my initial runs, I observed that A* can gobble memory at an extraordinary rate if special care is not taken. In addition, in particular the sorted open-set container must be very fast particularly on the sorted insert. Anyway, I've got a handle on it.
Once A* is in the bag, that's a significant chunk of the work completed, and then I can start focusing on solving the higher level routing problems.
For a V1 release, I am of the mind to switch to building the routing algorithm into the main executable rather that going with the originally planned plug-in model, just to simplify the implementation, and get to "market" as quickly as possible.
I wish I had more time to work on it, it is a fun and challenging project...sigh...we do what we can.
--Mike On 06/23/2014 09:50 AM, 'Andrew Lynch' via N8VEM-S100 wrote:
Hi This is my nightmare come true. Some of you will recall my concerns earlier about our almost complete dependence on FreeRouter and my calls for another autorouting solution. It looks like the time for QAutorouter may have arrived at last. As soon as I get back tonight I will remove the FreeRouting files on the wiki. If the copyrights are in question we have to move away from FreeRouting. Fortunately KiCAD is still usable without FreeRouting. Thanks and have a nice day! Andrew Lynch