如何连接*算法的节点 [英] How to connect nodes for a* algorithm
问题描述
我正在尝试构建一个程序，用户可以在地图上选择起点和终点，并显示这两点之间的最短路径。我的代码适用于所有输入的地图，而不仅仅是一个。
我已将所有节点放在地图上。我想连接这些节点以构建节点树，因此我可以执行A *算法。我想知道如何编写连接这些节点的东西？
（例如：计算机如何知道哪些节点应该是其他节点的子节点？如果存在障碍，计算机如何确保2个节点未连接？他们之间？）谢谢。
地图上所有节点的图像（注意没有显示起点和终点，因为它们将由用户每次选择）：
https：/ /i.imgur.com/RMhSGoq.jpg [ ^ ]
地图上识别出的所有障碍的图像：
https://i.imgur.com/RpiY2tf.jpg [ ^ ]
我的尝试：
我在这里试图解决问题一直陷入死胡同。我无法在解决方案方面提出太多建议。
我目前将所有节点存储在一个数组中，以及存储在另一个中的所有障碍物。仅供参考，我在下面包含了我的代码，但是，大多数都涉及生成节点，因此与问题无关。
＃ ！/ usr / bin / env python3
＃ - * - 编码：utf-8 - * -
创建于3月15日星期三21:23:40 2018
@author：2020shatgiskesselldd
import cv2
import numpy as np
import scipy.signal
import math
class 节点：$ b $ b xcoordinate = 0 ;
ycoordinate = 0 ;
roomimg = cv2.imread（ / Users / 2020shatgiskessell / Desktop / Maps / medium2.jpg）
＃ 边缘检测
＃ ret，thresh = cv2.threshold（roomimg，127,255，cv2.ADAPTIVE_THRESH_GAUSSIAN_C ）
thresh = cv2.cvtColor（roomimg，cv2.COLOR_BGR2GRAY）
edge = cv2.Canny（thresh， 100 ，< span class =code-digit> 200 ）
height，width，channels = roomimg.shape
＃ 定义网格的维度
def estimate_noise（I）：
H，W = I.shape
M = [[ 1 ， - 2 ， 1 ]，
[ - 2 ， 4 ， - 2 ]，
[ 1 ， - 2 ， 1 ]]
sigma = np。 sum（np.sum（np.absolute（scipy.signal.convolve2d（np.array（I），M））））
sigma = sigma * np.sqrt（ 0 。 5 * np.pi）/（ 6 *（W - 2 ）*（H- 2 ））
return sigma
boxsize =（math.pow（estimate_noise（edge）， - 0 。< span class =code-digit> 708 ）* 112 。 32 ）
matrix_icrement_width = int（width / int（boxsize））
matrix_icrement_height = int（height / int（boxsize））
Matrix = [[ 0 x range（matrix_icrement_width）] y 在范围内（matrix_icrement_height）]
Nodes = [ ]
＃ 定义什么是障碍，什么不是
cut_off_point = 15
print （boxsize）
＃ 你必须根据每个图像改变切断点
box_num = 0
boxesdrawn = 0
for i < span class =code-keyword>在范围内（ 0 ，height，int（boxsize））：
for j in 范围（ 0 ，width，int（boxsize）） ：
＃ 1。绘制块
roi_gray = edge [i：i + int（boxsize），j：j + int（boxsize）]
＃ 2。寻找投资回报率的强度
roi_avg_intensity = np.mean（roi_gray）
＃ 3 。基于此，看看投资回报率是否是障碍
＃ print（box_num， （，i，，，j，））
如果 roi_avg_intensity> cut_off_point：
＃ 如果box_num< 200：
＃ print（roi_avg_intensity：，roi_avg_intensity）
＃ 在OBSATLLE附近绘制RECTANGLE
＃ cv2.rectangle（roomimg，（j，i），（j + int（boxsize），i + int（boxsize）），（0,0,255 ））
Matrix [int（i / int（boxsize））] [int（j / int（boxsize））] = < span class =code-string> o
boxesdrawn + = 1
else ：
Matrix [int（i / int（boxsize））] [int（j / int（boxsize））] = c
box_num + = 1
nodescreated = 0
def createNewNode（i，j）：
newNode = Node（）
newNode.xcoordinate = i
newNode.ycoordinate = j
Nodes.append（newNode）
converted_j = j * int（boxsize）
converted_i = i * int（boxsize）
cv2.rectangle（roomimg， （converted_j，converted_i），（converted_j + int（boxsize），converted_i + int（boxsize）），（ 0 ， 255 ， 255 ））
＃ 我知道createNewNode（i，j）函数是否正常工作
＃ 我知道矩阵数据结构也是所有G
＃ PERHAPS ，使用图像，只需使用.TXT文件并仅与矩阵交易
def traverse_matrix（）：
i 范围内（ 0 ，matrix_icrement_width - 1 ）：
j in range（ 0 ，matrix_icrement_height- 1 ）：
if Matrix [i] [j] == o：
＃ 如果您遇到障碍，请勿做任何事情
继续
如果 Matrix [i] [j- 2 ] == N：
＃ 如果有节点2 s你背后的步伐，不做反对
继续
如果 Matrix [i] [j- 1 ] == N：
＃ 如果你后面有一个节点2个空格，不要做反对
继续
如果 Matrix [ i- 2 ] [j] == N ：
＃ 如果你后面有一个节点2个空格，不要做antything
继续
如果 Matrix [i- 1 ] [j] == N ：
＃ 如果你后面有一个节点2个空格，不要做反对
继续
如果 Matrix [i] [j- 1 ] == o：
＃ 如果你遇到了障碍，但不再是
createNewNode（i，j）
Matrix [i] [j] = N
if Matrix [i + 1 ] [j] == c：
＃ 如果u下方的空格是路径
createNewNode（i，j）
Matrix [i] [j] = N
如果 Matrix [i] [j + 1 ] == o：
＃ 如果空间面前你是一个障碍
createNewNode（i，j）
Matrix [i] [j] = N
def printMatrix（）：
f = open（' obstaclemap.txt'，' w'）
f.write（' \ n' .join（['' ' .join（[' {：4}' .format（item） for item in row]）
行 Matrix]））
f.close（）
def astar（）：
＃ A STAR TIME
＃ 1。从节点N开始
节点在节点中：
< span class =code-keyword> print （node.xcoordinate）
＃ 2。计算NESW方向上节点N与其最近邻点之间的距离（可能添加东北，西北，东南，西南）
＃ 3。计算每个节点到终点的距离（weristic）
＃ 4 。添加它们
＃ 5。将最低成本节点添加到列表中
＃ 6。 N =成本最低的节点
＃ 图出最后要做什么
traverse_matrix（）
＃ printMatrix（）
astar（）
cv2.imwrite（' roomimg.jpg'，roomimg）
cv2.imshow（ image，roomimg）
if cv2.waitKey（ 0 ）& 0xff == 27 ：
cv2.destroyAllWindows（）
< blockquote> Dijkstra算法的Python实现·GitHub [ ^ ]
用Python实现Djikstra的最短路径算法 - Ben Alex Keen [ ^ ]
I am attempting to build a program where a user is able to select a starting and ending point on a map, and the shortest path between those two points is displayed. My code should work for all maps inputted, not just one.
I already have placed all the nodes on the map. I would like to connect these nodes in order to build a node tree, so I can perform the A* algorithm. I was wondering how might I code something that connects these nodes?
(eg: how does the computer know which nodes should be children of other nodes? How does the computer make sure that 2 nodes are not connected if there is an obstacle between them?) Thanks.
Image of all of the nodes on the map (note that no starting and ending point is displayed because they will be chosen each time by the user):
https://i.imgur.com/RMhSGoq.jpg[^]
Image of all the obstacles recognized on the map:
https://i.imgur.com/RpiY2tf.jpg[^]
What I have tried:
I have been stuck at a dead end here trying to solve the problem. I have not been able to come up with much in terms of solutions.
I currently have all of the nodes stored in an array, and all of the obstacles stored in another. Just for reference, I have included my code below, however, most of it concerns generating the nodes, and thus is irrelevant to the problem.
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Mar 15 21:23:40 2018
@author: 2020shatgiskesselldd
"""
import cv2
import numpy as np
import scipy.signal
import math
class Node:
xcoordinate = 0;
ycoordinate = 0;
roomimg = cv2.imread("/Users/2020shatgiskessell/Desktop/Maps/medium2.jpg")
# edge detection
# ret, thresh = cv2.threshold(roomimg, 127, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C)
thresh = cv2.cvtColor(roomimg, cv2.COLOR_BGR2GRAY)
edge = cv2.Canny(thresh, 100, 200)
height,width,channels = roomimg.shape
#define the dimensions of the grid
def estimate_noise(I):
H, W = I.shape
M = [[1, -2, 1],
[-2, 4, -2],
[1, -2, 1]]
sigma = np.sum(np.sum(np.absolute(scipy.signal.convolve2d(np.array(I), M))))
sigma = sigma * np.sqrt(0.5 * np.pi) / (6 * (W-2) * (H-2))
return sigma
boxsize = (math.pow(estimate_noise(edge),-0.708)* 112.32)
matrix_icrement_width = int(width/int(boxsize))
matrix_icrement_height = int(height/int(boxsize))
Matrix = [[0 for x in range(matrix_icrement_width)] for y in range(matrix_icrement_height)]
Nodes = []
#defines what are obstacles and what are not
cut_off_point = 15
print (boxsize)
#U HAVE TO CHANGE CUT OFF POINT BASED ON EVERY IMAGE
box_num = 0
boxesdrawn = 0
for i in range (0,height, int(boxsize)):
for j in range (0,width, int(boxsize)):
#1. DRAW THE BLOCKS
roi_gray = edge[i:i+int(boxsize),j:j+int(boxsize)]
#2. FIND INTENSITY OF ROI
roi_avg_intensity = np.mean(roi_gray)
#3. BASED ON THAT, SEE IF ROI IS AN OBSTACLE OR NOT
#print(box_num,"(",i,",",j,")")
if roi_avg_intensity > cut_off_point:
# if box_num < 200:
# print("roi_avg_intensity:", roi_avg_intensity)
#DRAW RECTANGLE AROUND OBSATCLE
#cv2.rectangle(roomimg, (j,i), (j+int(boxsize), i+int(boxsize)),(0,0,255))
Matrix[int(i/int(boxsize))][int(j/int(boxsize))] = "o"
boxesdrawn += 1
else:
Matrix[int(i/int(boxsize))][int(j/int(boxsize))] = "c"
box_num += 1
nodescreated = 0
def createNewNode(i,j):
newNode = Node()
newNode.xcoordinate = i
newNode.ycoordinate = j
Nodes.append(newNode)
converted_j = j * int(boxsize)
converted_i = i * int(boxsize)
cv2.rectangle(roomimg, (converted_j,converted_i), (converted_j+int(boxsize), converted_i+int(boxsize)),(0,255,255))
#SO I KNOW THAT THE createNewNode(i,j) function is working as should
#AND I KNOW THAT THE Matrix DATA STRUCUTRE IS ALSO ALL G
#PERHAPS, INSTEAD OF USING A IMAGE, JUST USE A .TXT FILE AND ONLY DEAL WITH Matrix
def traverse_matrix():
for i in range (0,matrix_icrement_width-1):
for j in range (0,matrix_icrement_height-1):
if Matrix[i][j]== "o" :
#if u r on an obstacle, dont do anything
continue
if Matrix[i][j-2] == "N":
#if there is a node 2 spaces behind u, dont do antything
continue
if Matrix[i][j-1] == "N":
#if there is a node 2 spaces behind u, dont do antything
continue
if Matrix[i-2][j] == "N":
#if there is a node 2 spaces behind u, dont do antything
continue
if Matrix[i-1][j] == "N":
#if there is a node 2 spaces behind u, dont do antything
continue
if Matrix[i][j-1] == "o":
#if u were on an obstacle, but not anymore
createNewNode(i,j)
Matrix[i][j] = "N"
if Matrix[i+1][j] == "c":
#if the space below u is a path
createNewNode(i,j)
Matrix[i][j] = "N"
if Matrix[i][j+1] == "o":
#if the space infront of u is an obstacle
createNewNode(i,j)
Matrix[i][j] = "N"
def printMatrix():
f = open('obstaclemap.txt', 'w')
f.write('\n'.join([''.join(['{:4}'.format(item) for item in row])
for row in Matrix]))
f.close()
def astar ():
#A STAR TIME
#1. Start with node N
for node in Nodes:
print (node.xcoordinate)
#2. Calculate distance between node N and its nearest neighbores in the NESW directions (possible add northeast, northwest, southeast, soutthwest)
#3. Calculate the distance of each of those nodes to the end point (the hueristic)
#4. Add them up
#5. Add the lowest cost node to the list
#6. N = lowest cost node
#FIGURE OUT WHAT TO DO AT END
traverse_matrix()
#printMatrix()
astar()
cv2.imwrite('roomimg.jpg', roomimg)
cv2.imshow("image", roomimg)
if cv2.waitKey(0) & 0xff == 27:
cv2.destroyAllWindows()Python implementation of Dijkstra's Algorithm · GitHub[^]
Implementing Djikstra’s Shortest Path Algorithm with Python – Ben Alex Keen[^]
这篇关于如何连接*算法的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
![https：/ /i.imgur.com/RMhSGoq.jpg](\"https://i.imgur.com/RMhSGoq.jpg\"){kind=link}
