326 lines
11 KiB
Python
326 lines
11 KiB
Python
# coding=utf-8
|
|
import copy
|
|
|
|
from ..OtherTools import GetDistance
|
|
|
|
routeControls = {} # 所有路径节点
|
|
|
|
|
|
class ConnectChangedState(object):
|
|
"""
|
|
当发生连接变化时的状态
|
|
"""
|
|
DisConnect = 0b00
|
|
Connect = 0b01
|
|
ConvertConnect = 0b00
|
|
ReallyConnect = 0b10
|
|
|
|
|
|
def GetRouteByPosDim(posDim):
|
|
# type:(Union[List,Tuple]) -> RouteControl
|
|
"""
|
|
通过维度坐标获取加载的路径节点
|
|
"""
|
|
return routeControls.get(posDim)
|
|
|
|
|
|
class RouteControl(object):
|
|
"""
|
|
路径节点
|
|
"""
|
|
|
|
def __init__(self, posDim):
|
|
# type:(Tuple[int,int,int,int]) -> None
|
|
self.posDim = posDim
|
|
self.connections = [] # 真连接
|
|
self.convertConnections = [] # 隐性连接,用于记录哪个路径节点连接与此
|
|
routeControls[posDim] = self
|
|
|
|
def HasConnection(self):
|
|
"""
|
|
判断是否有方向:自身 -> routeControl的连接
|
|
"""
|
|
return self.connections.__len__() > 0
|
|
|
|
def ConnectionChanged(self, routeControl, state):
|
|
"""
|
|
当连接情况发生改变完成后触发,包括真连接和隐性连接
|
|
:param routeControl: 将要变化的路径节点
|
|
:param state: ConnectChangedState不同位的不同state
|
|
"""
|
|
pass
|
|
|
|
def Destroy(self):
|
|
"""
|
|
销毁本路径节点
|
|
:return:
|
|
"""
|
|
for routeControl in copy.copy(self.convertConnections):
|
|
# 销毁, 不可触发自身连接改变
|
|
routeControl.DisConnectBefore(self)
|
|
routeControl.connections.remove(self)
|
|
self.convertConnections.remove(routeControl)
|
|
routeControl.ConnectionChanged(self, ConnectChangedState.ReallyConnect | ConnectChangedState.DisConnect)
|
|
for routeControl in copy.copy(self.connections):
|
|
# 销毁, 不可触发自身连接改变
|
|
self.DisConnectBefore(routeControl)
|
|
self.connections.remove(routeControl)
|
|
routeControl.convertConnections.remove(self)
|
|
routeControl.ConnectionChanged(self, ConnectChangedState.ConvertConnect | ConnectChangedState.DisConnect)
|
|
del routeControls[self.posDim]
|
|
|
|
def DisconnectTo(self, routeControl):
|
|
"""
|
|
单向取消与路径节点的单向连接, 方向:自身 -> routeControl
|
|
|
|
:param routeControl:将要取消的路径节点
|
|
:return:
|
|
"""
|
|
if self.IsConnection(routeControl):
|
|
self.DisConnectBefore(routeControl)
|
|
self.connections.remove(routeControl)
|
|
routeControl.convertConnections.remove(self)
|
|
self.ConnectionChanged(routeControl, ConnectChangedState.ReallyConnect | ConnectChangedState.DisConnect)
|
|
routeControl.ConnectionChanged(self, ConnectChangedState.ConvertConnect | ConnectChangedState.DisConnect)
|
|
|
|
@staticmethod
|
|
def DisconnectBy(routeControl):
|
|
"""
|
|
单向取消与路径节点的单向连接, 方向: routeControl -> 自身
|
|
|
|
:param routeControl:将要取消的路径节点
|
|
:return:
|
|
"""
|
|
routeControl.DisconnectTo(routeControl)
|
|
|
|
def InterDisconnect(self, routeControl):
|
|
"""
|
|
双向取消与路径节点的连接
|
|
|
|
:param routeControl:将要取消的路径节点
|
|
:return:
|
|
"""
|
|
self.DisconnectTo(routeControl)
|
|
self.DisconnectBy(routeControl)
|
|
|
|
def IsConnection(self, routeControl):
|
|
"""
|
|
判断路径节点是否与本路径节点连接
|
|
|
|
:param routeControl:路径节点
|
|
:return:
|
|
"""
|
|
return routeControl in self.connections
|
|
|
|
def Connectable(self, routeControl):
|
|
"""
|
|
在尝试与对方进行连接时触发,方向:自身 -> routeControl
|
|
|
|
:param routeControl:将要连接的路径节点
|
|
:return:是否与对方连接
|
|
"""
|
|
if abs(GetDistance(self.posDim[:3], routeControl.posDim[:3]) - 1) < 10e-6:
|
|
return True
|
|
|
|
def DisConnectBefore(self, routeControl):
|
|
"""
|
|
当断开方向为:routeControl -> 自身 连接之前触发
|
|
"""
|
|
pass
|
|
|
|
def ConnectBefore(self, routeControl):
|
|
"""
|
|
当发生方向为:routeControl -> 自身 连接之前触发
|
|
"""
|
|
pass
|
|
|
|
def ConnectTo(self, routeControl):
|
|
"""
|
|
与另外一个路径节点进行单向连接,方向:自身 -> routeControl
|
|
如果routeControl不可连接与此, 将无法建立连接
|
|
"""
|
|
routeControl.ConnectBefore(self)
|
|
if self.Connectable(routeControl) and routeControl not in self.connections:
|
|
self.connections.append(routeControl)
|
|
routeControl.convertConnections.append(self)
|
|
self.ConnectionChanged(routeControl, ConnectChangedState.ReallyConnect | ConnectChangedState.Connect)
|
|
routeControl.ConnectionChanged(self, ConnectChangedState.ConvertConnect | ConnectChangedState.Connect)
|
|
|
|
def ConnectBy(self, routeControl):
|
|
"""
|
|
与另外一个路径节点进行单向连接,方向:routeControl -> 自身
|
|
"""
|
|
routeControl.ConnectTo(self)
|
|
|
|
def InterConnect(self, routeControl):
|
|
"""
|
|
与另外一个路径节点进行双向连接
|
|
"""
|
|
self.ConnectTo(routeControl)
|
|
self.ConnectBy(routeControl)
|
|
|
|
def ConnectBeside(self):
|
|
"""
|
|
与周围的可连接的路径节点进行连接
|
|
"""
|
|
myPosDim = list(self.posDim)
|
|
dr = [-1, 1]
|
|
posDimBeside = [(myPosDim[0] + x, myPosDim[1], myPosDim[2], myPosDim[3]) for x in dr] + \
|
|
[(myPosDim[0], myPosDim[1] + y, myPosDim[2], myPosDim[3]) for y in dr] + \
|
|
[(myPosDim[0], myPosDim[1], myPosDim[2] + z, myPosDim[3]) for z in dr]
|
|
for posDim in posDimBeside:
|
|
routeControl = routeControls.get(posDim)
|
|
self.InterConnect(routeControl) if routeControl else 0
|
|
|
|
def IsFinal(self, *args, **kwargs):
|
|
"""
|
|
是否为终点
|
|
:param args:判断时可能传入的参数
|
|
:param kwargs:判断时可能传入的参数
|
|
:return:
|
|
"""
|
|
return self.connections.__len__() == 1
|
|
|
|
|
|
def Finder(routeControl, maxRuntime=10e5):
|
|
# type:(RouteControl,int)->List
|
|
"""
|
|
寻找器,不可跨维度寻找
|
|
|
|
:param routeControl:起点路径节点
|
|
:param maxRuntime:最大运行次数
|
|
:return:终点集
|
|
"""
|
|
destination = [] # 目标集
|
|
x = {} # 储存已经寻找过的节点
|
|
runTime = 0 # 寻找次数
|
|
hand = routeControl.posDim # 运行指针
|
|
subRoute = [] # 下一节点
|
|
while runTime < maxRuntime:
|
|
routeControl = routeControls.get(hand) # type:RouteControl
|
|
y = x.get(hand[0], {})
|
|
z = y.get(hand[1], {})
|
|
# 如果获取错误,或者此节点已被寻找,则尝试下一个分流节点
|
|
if routeControl is None or z.get(hand[2], False):
|
|
if subRoute.__len__() == 0:
|
|
break
|
|
hand = subRoute.pop()
|
|
continue
|
|
# 储存节点
|
|
z[hand[2]] = routeControl
|
|
y[hand[1]] = z
|
|
x[hand[0]] = y
|
|
|
|
if routeControl.IsFinal():
|
|
destination.append(routeControl)
|
|
|
|
for connection in routeControl.connections:
|
|
posDim = connection.posDim
|
|
# 判断下一节点是否被储存过
|
|
if not x.get(posDim[0], {}).get(posDim[1], {}).get(posDim[2], False):
|
|
subRoute.append(connection.posDim)
|
|
if subRoute.__len__() == 0:
|
|
break
|
|
hand = subRoute.pop()
|
|
runTime += 1
|
|
return destination
|
|
|
|
|
|
def FinderStopWhenFindDestination(routeControl, maxRuntime=10e5):
|
|
# type:(RouteControl,int)->List
|
|
"""
|
|
寻找器,不可跨维度寻找,每个分路遇到终点会停止寻路
|
|
|
|
:param routeControl:起点路径节点
|
|
:param maxRuntime:最大运行次数
|
|
:return:终点集
|
|
"""
|
|
destination = []
|
|
x = {}
|
|
runTime = 0
|
|
hand = routeControl.posDim
|
|
subRoute = []
|
|
while runTime < maxRuntime:
|
|
routeControl = routeControls.get(hand) # type:RouteControl
|
|
y = x.get(hand[0], {})
|
|
z = y.get(hand[1], {})
|
|
if routeControl is None or z.get(hand[2], False):
|
|
if subRoute.__len__() == 0:
|
|
break
|
|
hand = subRoute.pop()
|
|
continue
|
|
z[hand[2]] = True
|
|
y[hand[1]] = z
|
|
x[hand[0]] = y
|
|
if routeControl.IsFinal():
|
|
destination.append(routeControl)
|
|
else:
|
|
for connection in routeControl.connections:
|
|
posDim = connection.posDim
|
|
if not x.get(posDim[0], {}).get(posDim[1], {}).get(posDim[2], False):
|
|
subRoute.append(connection.posDim)
|
|
if subRoute.__len__() == 0:
|
|
break
|
|
hand = subRoute.pop()
|
|
runTime += 1
|
|
return destination
|
|
|
|
|
|
def FinderStopSampleNum(routeControl, sampleNum, maxRuntime=10e5):
|
|
# type:(RouteControl,int,int)->Dict
|
|
"""
|
|
寻找器,不可跨维度寻找,每个分路到达sampleNumber时停止寻路
|
|
|
|
:param routeControl:起点路径节点
|
|
:param maxRuntime:最大运行次数
|
|
:param sampleNum:距离起点相隔的节点个数
|
|
:return:结果集无论是否为终点
|
|
"""
|
|
destination = {} # 目标集
|
|
x = {} # 储存已经寻找过的节点
|
|
runTime = 0 # 寻找次数
|
|
hand = routeControl.posDim # 运行指针
|
|
subRoute = [] # 下一节点
|
|
subRouteNum = {} # 下一节点计数
|
|
presentNum = 0 # 当前计数
|
|
while runTime < maxRuntime:
|
|
routeControl = routeControls.get(hand) # type:RouteControl
|
|
y = x.get(hand[0], {})
|
|
z = y.get(hand[1], {})
|
|
# 如果获取错误,或者此节点已被寻找,再或者此时计数大于sampleNum则尝试下一个分流节点
|
|
if presentNum >= sampleNum or presentNum == -1 or z.get(hand[2], False) or routeControl is None:
|
|
if subRoute.__len__() == 0:
|
|
break
|
|
hand = subRoute.pop()
|
|
continue
|
|
|
|
# 储存节点
|
|
z[hand[2]] = routeControl
|
|
y[hand[1]] = z
|
|
x[hand[0]] = y
|
|
|
|
if presentNum > 0:
|
|
destination[presentNum] = destination.get(presentNum, [])
|
|
destination[presentNum].append(routeControl)
|
|
|
|
presentNum += 1
|
|
|
|
for connection in routeControl.connections:
|
|
posDim = connection.posDim
|
|
# 判断下一节点是否被储存过
|
|
if not x.get(posDim[0], {}).get(posDim[1], {}).get(posDim[2], False):
|
|
subRoute.append(connection.posDim)
|
|
a = subRouteNum.get(posDim[0], {})
|
|
subRouteNum[posDim[0]] = a
|
|
|
|
b = a.get(posDim[1], {})
|
|
a[posDim[1]] = b
|
|
|
|
b[posDim[2]] = presentNum
|
|
if subRoute.__len__() == 0:
|
|
break
|
|
hand = subRoute.pop()
|
|
presentNum = subRouteNum.get(hand[0], {}).get(hand[1], {}).get(hand[2], False)
|
|
runTime += 1
|
|
return destination
|