python - 在python中将meshgrid点转换为邻接矩阵

Question

我正在将网格点（2D 迷宫）转换为邻接矩阵，稍后我将使用它来查找给定坐标之间的最短路径。请查看我的代码：

import numpy as np
import numpy.matlib #for matrices

def cutblocks(xv,yv,allBlocks):
    x_new,y_new = np.copy(xv), np.copy(yv)
    ori_x,ori_y = xv[0][0], yv[0][0]
    for block in allBlocks:
        block = sorted(block)
        block_xmin = np.min((block[0][0], block[2][0]))
        block_xmax = np.max((block[0][0], block[2][0]))
        block_ymin = np.min((block[0][1], block[1][1]))
        block_ymax = np.max((block[0][1], block[1][1]))

        rx_min, rx_max = int((block_xmin-ori_x)/stepSize)+1, int((block_xmax-ori_x)/stepSize)+1
        ry_min, ry_max = int((block_ymin-ori_y)/stepSize)+1, int((block_ymax-ori_y)/stepSize)+1

        for i in range(rx_min,rx_max):
            for j in range(ry_min,ry_max):
                x_new[j][i] = np.nan
        for i in range(ry_min,ry_max):
            for j in range(rx_min,rx_max):
                y_new[i][j] = np.nan
    return x_new, y_new

stepSize = 0.2
##Blocks that should be disabled
allBlocks = [[(139.6, 93.6), (143.6, 93.6), (143.6, 97.6), (139.6, 97.6)],
 [(154.2, 93.4), (158.2, 93.4), (158.2, 97.4), (154.2, 97.4)],
 [(139.2, 77.8), (143.2, 77.8), (143.2, 81.8), (139.2, 81.8)],
 [(154.2, 77.8), (158.2, 77.8), (158.2, 81.8), (154.2, 81.8)],
 [(139.79999999999998, 86.4),
  (142.6, 86.4),
  (142.6, 88.0),
  (139.79999999999998, 88.0)],
 [(154.79999999999998, 87.2),
  (157.6, 87.2),
  (157.6, 88.8),
  (154.79999999999998, 88.8)]]

x = np.arange(136.0, 161.0, stepSize)
y = np.arange(75.0, 101.0, stepSize)

xv, yv = np.meshgrid(x, y)
xv, yv = cutblocks(xv,yv,allBlocks)

MazeSize = xv.shape[0]*xv.shape[1]
adj = np.matlib.zeros((MazeSize,MazeSize)) #initialize AdjacencyMatrix

#make 1 whenever there is a connection between neighboring coordinates
mazeR, mazeC = 0,0
for row in range(xv.shape[0]):

    for col in range(xv.shape[1]):
        if xv[row][col]>0 and col+1<xv.shape[1] and round(np.abs(xv[row][col] - xv[row][col+1]),2) == stepSize:
            adj[mazeR,mazeC+1] = 1
            break
        mazeC = mazeC+1
    mazeR = mazeR+1

此代码生成一个网格，其中一些点被禁用，因为它们是迷宫中的墙壁。每一步（连接的顶点之间）的成本是 1。我的问题是：1）邻接矩阵将是 NN 和 N=xy（。是乘法）。那是对的吗？

2）在邻接矩阵中找到邻居并将其分配给值 1 的有效方法是什么。（我试过但它不能正常工作）

3）我应该使用图表来解决这类问题吗？我的最终目标是找到 2 个坐标（顶点）之间的最短路径。

谢谢

标签： pythonnumpyadjacency-matrix