MicroPather is a path finder and A* solver (astar or a-star) written in platform independent C++ that can be easily integrated into existing code. MicroPather focuses on being a path finding engine for video games but is a generic A* solver.
326
stars
71
forks
source link
Reusing graph while blocking previously found paths #18
I'm planning on trying MicroPather out as part of a circuit board autorouter. On a PCB, a given area can only be used by a single trace. So I would like to be able to use a single graph that represents the PCB, and run MicroPather multiple times on it, once for each required trace. Each time a trace is found, I would then need to remove the nodes used by that trace from the graph.
For performance, I would like to avoid having a second representation of the PCB where I keep track of which areas have been used in previous traces, since, I think, that would require me to generate a new graph and nodes for each trace.
Can MicroPather be used in this way?
I've done some successful experiments with MicroPather for my stripboard autorouter, so I'll probably try it first, even if I do have to regenerate the graph from a separate representation for each trace.
I'm planning on trying MicroPather out as part of a circuit board autorouter. On a PCB, a given area can only be used by a single trace. So I would like to be able to use a single graph that represents the PCB, and run MicroPather multiple times on it, once for each required trace. Each time a trace is found, I would then need to remove the nodes used by that trace from the graph.
For performance, I would like to avoid having a second representation of the PCB where I keep track of which areas have been used in previous traces, since, I think, that would require me to generate a new graph and nodes for each trace.
Can MicroPather be used in this way?
I've done some successful experiments with MicroPather for my stripboard autorouter, so I'll probably try it first, even if I do have to regenerate the graph from a separate representation for each trace.