A* pathfinding for waveguides about siepic_ebeam_pdk HOT 10 CLOSED

Why are you trying to implement A* algorithm? To find Optimal waveguide Path?
If yes, then What criteria are you using to constrict the movement?

from siepic_ebeam_pdk.

The idea is to have the user click on the waveguide start, and the waveguide end, and have the software figure out where to route the waveguide and bends, so that it doesn't bump into anything.

from siepic_ebeam_pdk.

Just a quick question. What pya function are you using to check if a point is already taken on the grid? I mean is there an inbuilt function for such operation?

from siepic_ebeam_pdk.

I haven't started this yet. But this would require much more than the pya functions.

from siepic_ebeam_pdk.

I have implemented A* algorithm before in two projects. So, I am well aware of the approach and heuristics and I can make it work in klayout but I am not sure how to check whether a block in the grid space is taken or not. I will skim read through the documentation but if you find any information on this, please let me know.

from siepic_ebeam_pdk.

I imagined making a graph based on the Verification routines. Part of this is creating a list of components in an array database including pins and position information.
One could do a full grid, but it would be computationally inefficient. It would be nicer to do a sparse Graph.

The other challenge is how to do it for multiple waveguides.

Lukas Chrostowski
Associate Professor, ECE
University of British Columbia
604-822-8507
http://www.mina.ubc.ca/lukasc
http://siepic.ubc.ca

On Nov 28, 2015, at 6:40 AM, Jaspreet Jhoja [email protected] wrote:

I have implemented A* algorithm before in two projects. So, I am well aware of the approach and heuristics and I can make it work in klayout but I am not sure how to check whether a block in the grid space is taken or not. I will skim read through the documentation but if you find any information on this, please let me know.

—
Reply to this email directly or view it on GitHub.

from siepic_ebeam_pdk.

Yes, I agree. I just want to compile a list of blocks which are already
taken. Heuristics will automatically generate nodes which will get
investigated from the grid. Use of open and closed lists avoid the
possibility of dense graphs.

On Sat, Nov 28, 2015 at 10:26 PM, Lukas Chrostowski <
[email protected]> wrote:

I imagined making a graph based on the Verification routines. Part of this
is creating a list of components in an array database including pins and
position information.
One could do a full grid, but it would be computationally inefficient. It
would be nicer to do a sparse Graph.

The other challenge is how to do it for multiple waveguides.

Lukas Chrostowski
Associate Professor, ECE
University of British Columbia
604-822-8507
http://www.mina.ubc.ca/lukasc
http://siepic.ubc.ca

On Nov 28, 2015, at 6:40 AM, Jaspreet Jhoja [email protected]
wrote:

I have implemented A* algorithm before in two projects. So, I am well
aware of the approach and heuristics and I can make it work in klayout but
I am not sure how to check whether a block in the grid space is taken or
not. I will skim read through the documentation but if you find any
information on this, please let me know.

—
Reply to this email directly or view it on GitHub.

—
Reply to this email directly or view it on GitHub
https://github.com/lukasc-ubc/SiEPIC_EBeam_PDK/issues/20#issuecomment-160341637
.

from siepic_ebeam_pdk.

Hello Dr. Chrostowski,

I have added the A*algorithm script to the Github and have sent you a pull
request.

regards,
Jaspreet Jhoja

On Sun, Nov 29, 2015 at 7:07 AM, Jaspreet Jhoja [email protected]
wrote:

Yes, I agree. I just want to compile a list of blocks which are already
taken. Heuristics will automatically generate nodes which will get
investigated from the grid. Use of open and closed lists avoid the
possibility of dense graphs.

On Sat, Nov 28, 2015 at 10:26 PM, Lukas Chrostowski <
[email protected]> wrote:

I imagined making a graph based on the Verification routines. Part of
this is creating a list of components in an array database including pins
and position information.
One could do a full grid, but it would be computationally inefficient. It
would be nicer to do a sparse Graph.

The other challenge is how to do it for multiple waveguides.

Lukas Chrostowski
Associate Professor, ECE
University of British Columbia
604-822-8507
http://www.mina.ubc.ca/lukasc
http://siepic.ubc.ca

On Nov 28, 2015, at 6:40 AM, Jaspreet Jhoja [email protected]
wrote:

I have implemented A* algorithm before in two projects. So, I am well
aware of the approach and heuristics and I can make it work in klayout but
I am not sure how to check whether a block in the grid space is taken or
not. I will skim read through the documentation but if you find any
information on this, please let me know.

—
Reply to this email directly or view it on GitHub.

—
Reply to this email directly or view it on GitHub
https://github.com/lukasc-ubc/SiEPIC_EBeam_PDK/issues/20#issuecomment-160341637
.

from siepic_ebeam_pdk.

Cool. I’m trying to get shapely working, but not having much luck…

Lukas Chrostowski, P.Eng., Associate Professor
Program Director, NSERC Silicon Electronic-Photonic Integrated Circuits (SiEPIC) Program http://www.siepic.ubc.ca/
"Silicon Photonics Design" textbook is now available http://www.cambridge.org/us/academic/subjects/engineering/electronic-optoelectronic-devices-and-nanotechnology/silicon-photonics-design-devices-systems.
course on edX http://bit.ly/UBCxPhot – Silicon Photonics Design, Fabrication and Data Analysis

University of British Columbia
Electrical and Computer Engineering http://www.ece.ubc.ca/,
4039-2332 Main Mall, Kaiser Building
Vancouver, B.C., Canada, V6T-1Z4
Office: Room 4039 Kaiser Building
Work: 604-822-8507
http://www.mina.ubc.ca/lukasc http://www.mina.ubc.ca/lukasc

http://bit.ly/SiPbook http://bit.ly/SiPbook http://bit.ly/UBCxPhot

On Dec 3, 2015, at 7:58 AM, Jaspreet Jhoja [email protected] wrote:

Hello Dr. Chrostowski,

I have added the A*algorithm script to the Github and have sent you a pull
request.

regards,
Jaspreet Jhoja

On Sun, Nov 29, 2015 at 7:07 AM, Jaspreet Jhoja [email protected]
wrote:

Yes, I agree. I just want to compile a list of blocks which are already
taken. Heuristics will automatically generate nodes which will get
investigated from the grid. Use of open and closed lists avoid the
possibility of dense graphs.

On Sat, Nov 28, 2015 at 10:26 PM, Lukas Chrostowski <
[email protected]> wrote:

I imagined making a graph based on the Verification routines. Part of
this is creating a list of components in an array database including pins
and position information.
One could do a full grid, but it would be computationally inefficient. It
would be nicer to do a sparse Graph.

The other challenge is how to do it for multiple waveguides.

Lukas Chrostowski
Associate Professor, ECE
University of British Columbia
604-822-8507
http://www.mina.ubc.ca/lukasc
http://siepic.ubc.ca

On Nov 28, 2015, at 6:40 AM, Jaspreet Jhoja [email protected]
wrote:

I have implemented A* algorithm before in two projects. So, I am well
aware of the approach and heuristics and I can make it work in klayout but
I am not sure how to check whether a block in the grid space is taken or
not. I will skim read through the documentation but if you find any
information on this, please let me know.

—
Reply to this email directly or view it on GitHub.

—
Reply to this email directly or view it on GitHub
https://github.com/lukasc-ubc/SiEPIC_EBeam_PDK/issues/20#issuecomment-160341637
.

—
Reply to this email directly or view it on GitHub https://github.com/lukasc-ubc/SiEPIC_EBeam_PDK/issues/20#issuecomment-161688693.

from siepic_ebeam_pdk.

moving to SiEPIC-Tools

from siepic_ebeam_pdk.