Bug reports and technical issues

Are you using the VD package? If so, have you also installed the patch I have uploaded?
 
I downloaded version 1.9 and 'Varietas Delectat and Ethnic City Styles for DoC', that's all. Do I have to download something more?
 
Sorry, Leoreth, but should the patch solve all previous errors, like "Memory errors: bad allocation" ?
Click to expand...
This error looks like your computer just can't handle the (rather badly optimized) Firaxis Civ4 code, plus RFC: DoC code on top of that, plus the graphical strain of VD.
 
Played another time. Rome captured Greece and gave Sparta to me. Next turn they declared war on me. An army spwaned next to my cities (I think this is normal in DoC, can someone give some more information please) and I could never defeat them. Tried to reload but again I got a FATAL_ERROR message.
 
Victory.py, rev384

There is a defect in the function you use to check Trans-Siberian Railroad.
This is your code.
Spoiler :

Code: 
	def isConnectedByRailroad(self, iPlayer, iStartX, iStartY, iTargetX, iTargetY):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer): return False
		
		lNodes = [(-utils.calculateDistance(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
		lVisitedNodes = []
		
		while len(lNodes) > 0:
			h, x, y = lNodes[0]
			lNodes.remove((h, x, y))
			lVisitedNodes.append((h, x, y))
			
			for i in range(x-1, x+2):
				for j in range(y-1, y+2):
					plot = gc.getMap().plot(i, j)
					if plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == gc.getInfoTypeForString("ROUTE_RAILROAD")):
						if (i, j) == (iTargetX, iTargetY): return True
						tTuple = (-utils.calculateDistance(i, j, iTargetX, iTargetY), i, j)
						[COLOR="Red"]if not tTuple in lVisitedNodes:
							lNodes.append(tTuple)[/COLOR]
						
			lNodes.sort()
			
		return False


In my opinion, it should be
Spoiler :

Code: 
	def isConnectedByRailroad(self, iPlayer, iStartX, iStartY, iTargetX, iTargetY):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer): return False
		
		lNodes = [(-utils.calculateDistance(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
		lVisitedNodes = []
		
		while len(lNodes) > 0:
			h, x, y = lNodes[0]
			lNodes.remove((h, x, y))
			lVisitedNodes.append((h, x, y))
			
			for i in range(x-1, x+2):
				for j in range(y-1, y+2):
					plot = gc.getMap().plot(i, j)
					if plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == gc.getInfoTypeForString("ROUTE_RAILROAD")):
						if (i, j) == (iTargetX, iTargetY): return True
						tTuple = (-utils.calculateDistance(i, j, iTargetX, iTargetY), i, j)
						[COLOR="Red"]if not tTuple in lVisitedNodes:[/COLOR]
							[COLOR="Blue"]if tTuple not in lNodes:[/COLOR]
								[COLOR="Red"]lNodes.append(tTuple)[/COLOR]
						
			lNodes.sort()
			
		return False


If you don't add "if tTuple not in lNodes:", lNodes will contain duplicated items, namely some nodes will be processed multiple times.
Under some circumstances, the check will be extremely slow. It would take several minutes or even more time to finish the calculation.

Moreover, the first elemet of 3-tuple, -utils.calculateDistance(i, j, iTargetX, iTargetY) is completely useless. The coordinate pair is enough.
 
Actually, the algorithm you used is simple, just one-pass, but quite slow. Fortunately, we don't use it frequently. Thus the slowness is tolerable.
But I prefer another variation of this algorithm, which is much faster. Though by some famous algorithm's standard, it is still very slow.
Spoiler :

Code: 
	def isConnectedByRailroad(self, iPlayer, iStartX, iStartY, iTargetX, iTargetY):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer):
			return False
		
		iRailroad = gc.getInfoTypeForString("ROUTE_RAILROAD")
		lNodes = [(iStartX, iStartY)]
		lVisitedNodes = []
		
		while True > 0:
			lTempNodes = []
			
			for (x, y) in lNodes:
				if (x, y) not in lVisitedNodes:
					lVisitedNodes.append((x, y))
					for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
									(x, y-1), (x, y+1),
									(x+1, y-1), (x+1, y), (x+1, y+1)]:
						plot = gc.getMap().plot(i, j)
						if not plot.isNone() and plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == iRailroad):
							if (i, j) == (iTargetX, iTargetY): 
								return True
							if (i, j) not in lNodes:
								if (i, j) not in lTempNodes:
									lTempNodes.append((i, j))

			if lTempNodes:
				lNodes = lTempNodes
			else:
				return False


Furthermore, when you check Trans-Siberian Railroad, there are more than one target. You check them one by one
Spoiler :

Code: 
					for tCoast in lSiberianCoast:
						if self.isConnectedByRailroad(iRussia, con.tCapitals[0][iRussia][0], con.tCapitals[0][iRussia][1], tCoast[0], tCoast[1]):
							bRailroad = True
							break


I prefer to use the following function to check them simultaneously.
Spoiler :

Code: 
	def isConnectedByRailroadTuple(self, iPlayer, iStartX, iStartY, tTargets):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer):
			return False
		
		iRailroad = gc.getInfoTypeForString("ROUTE_RAILROAD")
		lNodes = [(iStartX, iStartY)]
		lVisitedNodes = []
		
		while True > 0:
			lTempNodes = []
			
			for (x, y) in lNodes:
				if (x, y) not in lVisitedNodes:
					lVisitedNodes.append((x, y))
					for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
									(x, y-1), (x, y+1),
									(x+1, y-1), (x+1, y), (x+1, y+1)]:
						plot = gc.getMap().plot(i, j)
						if not plot.isNone() and plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == iRailroad):
							[COLOR="Red"]if (i, j) in tTargets:[/COLOR]
								return True
							if (i, j) not in lNodes:
								if (i, j) not in lTempNodes:
									lTempNodes.append((i, j))

			if lTempNodes:
				lNodes = lTempNodes
			else:
				return False
 
zahlen said:
Actually, the algorithm you used is simple, just one-pass, but quite slow. Fortunately, we don't use it frequently. Thus the slowness is tolerable.
But I prefer another variation of this algorithm, which is much faster. Though by some famous algorithm's standard, it is still very slow.
Spoiler :

Code: 
	def isConnectedByRailroad(self, iPlayer, iStartX, iStartY, iTargetX, iTargetY):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer):
			return False
		
		iRailroad = gc.getInfoTypeForString("ROUTE_RAILROAD")
		lNodes = [(iStartX, iStartY)]
		lVisitedNodes = []
		
		while True > 0:
			lTempNodes = []
			
			for (x, y) in lNodes:
				if (x, y) not in lVisitedNodes:
					lVisitedNodes.append((x, y))
					for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
									(x, y-1), (x, y+1),
									(x+1, y-1), (x+1, y), (x+1, y+1)]:
						plot = gc.getMap().plot(i, j)
						if not plot.isNone() and plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == iRailroad):
							if (i, j) == (iTargetX, iTargetY): 
								return True
							if (i, j) not in lNodes:
								if (i, j) not in lTempNodes:
									lTempNodes.append((i, j))

			if lTempNodes:
				lNodes = lTempNodes
			else:
				return False


Furthermore, when you check Trans-Siberian Railroad, there are more than one target. You check them one by one
Spoiler :

Code: 
					for tCoast in lSiberianCoast:
						if self.isConnectedByRailroad(iRussia, con.tCapitals[0][iRussia][0], con.tCapitals[0][iRussia][1], tCoast[0], tCoast[1]):
							bRailroad = True
							break


I prefer to use the following function to check them simultaneously.
Spoiler :

Code: 
	def isConnectedByRailroadTuple(self, iPlayer, iStartX, iStartY, tTargets):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer):
			return False
		
		iRailroad = gc.getInfoTypeForString("ROUTE_RAILROAD")
		lNodes = [(iStartX, iStartY)]
		lVisitedNodes = []
		
		while True > 0:
			lTempNodes = []
			
			for (x, y) in lNodes:
				if (x, y) not in lVisitedNodes:
					lVisitedNodes.append((x, y))
					for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
									(x, y-1), (x, y+1),
									(x+1, y-1), (x+1, y), (x+1, y+1)]:
						plot = gc.getMap().plot(i, j)
						if not plot.isNone() and plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == iRailroad):
							[COLOR="Red"]if (i, j) in tTargets:[/COLOR]
								return True
							if (i, j) not in lNodes:
								if (i, j) not in lTempNodes:
									lTempNodes.append((i, j))

			if lTempNodes:
				lNodes = lTempNodes
			else:
				return False
Click to expand...


You have been concerned about Tieba ,haven't you?:goodjob:
 
borhap88 said:
Sorry, Leoreth, but should the patch solve all previous errors, like "Memory errors: bad allocation" ?
Click to expand...
As Lone Wolf said, it's possible that these errors are caused because your RAM is full. How many GB do you use?

Zaanzie said:
I downloaded version 1.9 and 'Varietas Delectat and Ethnic City Styles for DoC', that's all. Do I have to download something more?
Click to expand...
Yes, I mentioned this in the VD thread OP in hopes everyone would notice it. Repackaging and reuploading the whole package is quite annoying so I released this small patch instead. See here:
Leoreth said:
Even more important note: There were some errors in the VD files. I'm going to repackage it with the fixes soon, but until the please also download this patch (unpack it into your Mods folder after you have installed VD), even when you've just downloaded VD. People who are using it already should do the same of course.
Click to expand...

zahlen said:
Victory.py, rev384

There is a defect in the function you use to check Trans-Siberian Railroad.
This is your code.
Spoiler :

Code: 
	def isConnectedByRailroad(self, iPlayer, iStartX, iStartY, iTargetX, iTargetY):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer): return False
		
		lNodes = [(-utils.calculateDistance(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
		lVisitedNodes = []
		
		while len(lNodes) > 0:
			h, x, y = lNodes[0]
			lNodes.remove((h, x, y))
			lVisitedNodes.append((h, x, y))
			
			for i in range(x-1, x+2):
				for j in range(y-1, y+2):
					plot = gc.getMap().plot(i, j)
					if plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == gc.getInfoTypeForString("ROUTE_RAILROAD")):
						if (i, j) == (iTargetX, iTargetY): return True
						tTuple = (-utils.calculateDistance(i, j, iTargetX, iTargetY), i, j)
						[COLOR="Red"]if not tTuple in lVisitedNodes:
							lNodes.append(tTuple)[/COLOR]
						
			lNodes.sort()
			
		return False


In my opinion, it should be
Spoiler :

Code: 
	def isConnectedByRailroad(self, iPlayer, iStartX, iStartY, iTargetX, iTargetY):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer): return False
		
		lNodes = [(-utils.calculateDistance(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
		lVisitedNodes = []
		
		while len(lNodes) > 0:
			h, x, y = lNodes[0]
			lNodes.remove((h, x, y))
			lVisitedNodes.append((h, x, y))
			
			for i in range(x-1, x+2):
				for j in range(y-1, y+2):
					plot = gc.getMap().plot(i, j)
					if plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == gc.getInfoTypeForString("ROUTE_RAILROAD")):
						if (i, j) == (iTargetX, iTargetY): return True
						tTuple = (-utils.calculateDistance(i, j, iTargetX, iTargetY), i, j)
						[COLOR="Red"]if not tTuple in lVisitedNodes:[/COLOR]
							[COLOR="Blue"]if tTuple not in lNodes:[/COLOR]
								[COLOR="Red"]lNodes.append(tTuple)[/COLOR]
						
			lNodes.sort()
			
		return False


If you don't add "if tTuple not in lNodes:", lNodes will contain duplicated items, namely some nodes will be processed multiple times.
Under some circumstances, the check will be extremely slow. It would take several minutes or even more time to finish the calculation.
Click to expand...
You're right, for some reason I thought I'd be fine if I removed the originally expanded node but that's obviously not the case.

Moreover, the first elemet of 3-tuple, -utils.calculateDistance(i, j, iTargetX, iTargetY) is completely useless. The coordinate pair is enough.
Click to expand...
It's not necessary, but should optimize the algorithm. I repurposed A* for this algorithm even though it's not strictly path-finding (since it only needs to find one path, not the best). Using the distance as first element means that the nodes list will be sorted by distance, so nodes close to the target will be checked before all others (otherwise the front would expand uniformly from the center instead of towards the target).

If I wanted to optimize the algorithm I'd need to replace the lNodes.sort() part, because that's costing me n log n time every iteration, so the whole algorithm is in O(n² log n), which is of course terrible. Multiple node checks is nothing compared to that. But because the graph that represents the game world isn't terribly large and the calculateDistance heuristic does a pretty good job in this scenario (since it is mainly just moving eastwards if the player built a halfway sensible railroad), it's not that noticeable. I'd have to find the Python equivalent to a heap because then I could rely on it's log n insertion complexity to arrive at O(n log n), but afaik base Python doesn't support heaps and I didn't bother to look it up further.

zahlen said:
Actually, the algorithm you used is simple, just one-pass, but quite slow. Fortunately, we don't use it frequently. Thus the slowness is tolerable.
But I prefer another variation of this algorithm, which is much faster. Though by some famous algorithm's standard, it is still very slow.
Spoiler :

Code: 
	def isConnectedByRailroad(self, iPlayer, iStartX, iStartY, iTargetX, iTargetY):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer):
			return False
		
		iRailroad = gc.getInfoTypeForString("ROUTE_RAILROAD")
		lNodes = [(iStartX, iStartY)]
		lVisitedNodes = []
		
		while True > 0:
			lTempNodes = []
			
			for (x, y) in lNodes:
				if (x, y) not in lVisitedNodes:
					lVisitedNodes.append((x, y))
					for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
									(x, y-1), (x, y+1),
									(x+1, y-1), (x+1, y), (x+1, y+1)]:
						plot = gc.getMap().plot(i, j)
						if not plot.isNone() and plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == iRailroad):
							if (i, j) == (iTargetX, iTargetY): 
								return True
							if (i, j) not in lNodes:
								if (i, j) not in lTempNodes:
									lTempNodes.append((i, j))

			if lTempNodes:
				lNodes = lTempNodes
			else:
				return False


Furthermore, when you check Trans-Siberian Railroad, there are more than one target. You check them one by one
Spoiler :

Code: 
					for tCoast in lSiberianCoast:
						if self.isConnectedByRailroad(iRussia, con.tCapitals[0][iRussia][0], con.tCapitals[0][iRussia][1], tCoast[0], tCoast[1]):
							bRailroad = True
							break


I prefer to use the following function to check them simultaneously.
Spoiler :

Code: 
	def isConnectedByRailroadTuple(self, iPlayer, iStartX, iStartY, tTargets):
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer):
			return False
		
		iRailroad = gc.getInfoTypeForString("ROUTE_RAILROAD")
		lNodes = [(iStartX, iStartY)]
		lVisitedNodes = []
		
		while True > 0:
			lTempNodes = []
			
			for (x, y) in lNodes:
				if (x, y) not in lVisitedNodes:
					lVisitedNodes.append((x, y))
					for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
									(x, y-1), (x, y+1),
									(x+1, y-1), (x+1, y), (x+1, y+1)]:
						plot = gc.getMap().plot(i, j)
						if not plot.isNone() and plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == iRailroad):
							[COLOR="Red"]if (i, j) in tTargets:[/COLOR]
								return True
							if (i, j) not in lNodes:
								if (i, j) not in lTempNodes:
									lTempNodes.append((i, j))

			if lTempNodes:
				lNodes = lTempNodes
			else:
				return False
Click to expand...
Did you actually profile them against my implementation? I'd be curious about the results.

I think the reason that slows my implementation down is the horrible implementation of the heuristic which is completely lacking in yours. I'm sure with a suitable data type using the heuristic would still be better than expanding the front concentrically.

But checking for all targets simultaneously really does make sense.
 
Okay, the whole thing piqued my interest so I actually looked up Python's heap implementation which is the heapq module. I modified my implementation as follows, also integrating your change to check for multiple targets:
Code: 
	def isConnectedByRailroad(self, iPlayer, tStart, lTargetList):
		if len(lTargetList) == 0:
			return False
		
		iStartX, iStartY = tStart
		iTargetX, iTargetY = lTargetList[0]
		startPlot = gc.getMap().plot(iStartX, iStartY)
		if not (startPlot.isCity() and startPlot.getOwner() == iPlayer): return False
		
		lNodes = [(utils.calculateDistance(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
		heapq.heapify(lNodes)
		lVisitedNodes = []
		
		while len(lNodes) > 0:
			h, x, y = heapq.heappop(lNodes)
			lVisitedNodes.append((h, x, y))
			
			for i in range(x-1, x+2):
				for j in range(y-1, y+2):
					plot = gc.getMap().plot(i, j)
					if plot.getOwner() == iPlayer and (plot.isCity() or plot.getRouteType() == gc.getInfoTypeForString("ROUTE_RAILROAD")):
						if (i, j) in lTargetList: return True
						tTuple = (utils.calculateDistance(i, j, iTargetX, iTargetY), i, j)
						if not tTuple in lVisitedNodes:
							if not tTuple in lNodes:
								heapq.heappush(lNodes, tTuple)
			
		return False
Then I've set up four situations to test them:

1) Only Moscow, no other cities
2) Only one direct railroad connection
3) Several Russian cities that are connected by railroad, including cities west and north of Moscow
4) Same as (3), but with a railroad on every tile covered by Russian culture

Then I tested the following implementations on them:
- my original implementation
- your suggestion to remove the calculateDistance heuristic
- keep the calculateDistance heuristic, but maintaining a priority queue using heapq instead of a constantly sorted list

These are the average results in milliseconds:
Code: 
			(1)	(2)	(3)	(4)
Old Implementation	0.0916	2.7036	7.5538	---
Without Heuristic	0.1121	2.3804	7.1167	35.3760
Heuristic and heapq	0.1121	2.4170	2.8812	4.1016
So it should be clear that using the heuristic is advisable, especially in a situation where the player covers his whole territory with railroads, which isn't that rare (and the AI does it all the time).
 
You are right. I forgot calculateDistance played a role in lNodes.sort().

Since I have no access to Civ4 now, I just tested a very simple case.
I assume:
1. The test region is a 50*50 square and all tiles built railroad.
2. Starting tile is (1,1). Target tile is (50,50).

f1: with heuristic function
f2: without heuristic function
f3: my variation

The result is
Spoiler :

*** Python 2.7.2 (default, Jun 12 2011, 15:08:59) [MSC v.1500 32 bit (Intel)] on win32. ***
*** Remote Python engine is active ***
>>>
*** Remote Interpreter Reinitialized ***
>>>
>>> f1(1,1,50,50)
Time 1.50900006294
Visited 2497
>>> f2(1,1,50,50)
Time 1.40199995041
Visited 2449
>>> f3(1,1,50,50)
Time 0.463000059128
Visited 2401


A larger region, 70*70. The result is
Spoiler :

>>> isValid = lambda i,j: 1<=i<=70 and 1<=j<=70
>>> f1(1,1,70,70)
Time 5.67499995232
Visited 4897
>>> f2(1,1,70,70)
Time 5.47300004959
Visited 4829
>>> f3(1,1,70,70)
Time 1.62000012398
Visited 4761


The heuristic function version is slowest. I guess is due to function call overhead in Python is relatively high.

The following is my testing code
Spoiler :

Code: 
import time

def timer(f):
    def g(*args):
        start = time.time()
        f(*args)
        end = time.time()
        print 'Time ', end - start
        show()
    return g

def show():
    print 'Visited ', len(lVisitedNodes)

def dist(x1, y1, x2, y2):
        dx = abs(x2-x1)
        dy = abs(y2-y1)
        return max(dx, dy)

def isValid(i, j):
    return 1 <= i <= 50 and 1 <= j <= 50

@timer
def f1(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(-dist(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
    lVisitedNodes = []

    while len(lNodes) > 0:
        h, x, y = lNodes[0]
        lNodes.remove((h, x, y))
        lVisitedNodes.append((h, x, y))

        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if isValid(i, j):
                    if (i, j) == (iTargetX, iTargetY): return True
                    tTuple = (-dist(i, j, iTargetX, iTargetY), i, j)
                    if not tTuple in lVisitedNodes:
                        if tTuple not in lNodes:
                            lNodes.append(tTuple)

        lNodes.sort()

    return False

@timer
def f2(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(iStartX, iStartY)]
    lVisitedNodes = []

    while len(lNodes) > 0:
        x, y = lNodes[0]
        lNodes.remove((x, y))
        lVisitedNodes.append((x, y))

        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if isValid(i, j):
                    if (i, j) == (iTargetX, iTargetY): return True
                    tTuple = (i, j)
                    if not tTuple in lVisitedNodes:
                        if tTuple not in lNodes:
                            lNodes.append(tTuple)

        lNodes.sort()

    return False

@timer
def f3(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(iStartX, iStartY)]
    lVisitedNodes = []

    while True > 0:
        lTempNodes = []

        for (x, y) in lNodes:
            if (x, y) not in lVisitedNodes:
                lVisitedNodes.append((x, y))
                for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
                                (x, y-1), (x, y+1),
                                (x+1, y-1), (x+1, y), (x+1, y+1)]:

                    if isValid(i, j):
                        if (i, j) == (iTargetX, iTargetY):
                            return True
                        if (i, j) not in lNodes:
                            if (i, j) not in lTempNodes:
                                lTempNodes.append((i, j))

        if lTempNodes:
            lNodes = lTempNodes
        else:
            return False
 
Yeah, without relying on a data structure with O(log n) sorted insertion complexity the heuristic has no positive effect, no need to demonstrate that. But my testing shows that it can provide a ~900% speed increase under reasonable circumstances when using such a data structure.
 
Using a more complicated data structure and algorithm usually made code harder to understand and debug.
IMHO, in this case maybe the only necessary optimization is caching ROUTE_RAILROAD type.
 
Well, no. Look at the implementation I've posted above. The whole implementation of heapq is in the other module so the only change is interacting with the heapq interface instead of the list interface. So from an implementation perspective, nothing changes.

Look at the speed increase it shows when traversing complete graphs - it's almost ten times faster! It's definitely worth it.
 
At least, for the worst case, namely railroad everywhere, I didn't notice any significant improvement after replacing list by heapq.

Code: 
@timer
def h(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(-dist(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
    lVisitedNodes = []

    while len(lNodes) > 0:
        h, x, y = lNodes[0]
        heapq.heappop(lNodes)
        lVisitedNodes.append((h, x, y))

        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if isValid(i, j):
                    if (i, j) == (iTargetX, iTargetY): return True
                    tTuple = (-dist(i, j, iTargetX, iTargetY), i, j)
                    if not tTuple in lVisitedNodes:
                        if tTuple not in lNodes:
                            heapq.heappush(lNodes, tTuple)

    return False

70 * 70
Code: 
>>> isValid = lambda i,j:1<=i<=70 and 1<=j<=70
>>> h(1,1,70,70)
Time  5.69000005722
Visited  4897
>>> f1(1,1,70,70)
Time  5.72499990463
Visited  4897
>>> f2(1,1,70,70)
Time  5.58899998665
Visited  4829
>>> f3(1,1,70,70)
Time  1.63800001144
Visited  4761

80 * 80
Code: 
>>> isValid = lambda i,j:1<=i<=80 and 1<=j<=80
>>> h(1,1,80,80)
Time  9.71899986267
Visited  6397
>>> f1(1,1,80,80)
Time  9.77900004387
Visited  6397
>>> f2(1,1,80,80)
Time  9.51099991798
Visited  6319
>>> f3(1,1,80,80)
Time  2.72699999809
Visited  6241

Full code
Spoiler :

Code: 
import time
import heapq

def timer(f):
    def g(*args):
        start = time.time()
        f(*args)
        end = time.time()
        print 'Time ', end - start
        show()
    return g

def show():
    print 'Visited ', len(lVisitedNodes)

def dist(x1, y1, x2, y2):
        dx = abs(x2-x1)
        dy = abs(y2-y1)
        return max(dx, dy)

def isValid(i, j):
    return 1 <= i <= 50 and 1 <= j <= 50

@timer
def h(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(-dist(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
    lVisitedNodes = []

    while len(lNodes) > 0:
        h, x, y = lNodes[0]
        heapq.heappop(lNodes)
        lVisitedNodes.append((h, x, y))

        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if isValid(i, j):
                    if (i, j) == (iTargetX, iTargetY): return True
                    tTuple = (-dist(i, j, iTargetX, iTargetY), i, j)
                    if not tTuple in lVisitedNodes:
                        if tTuple not in lNodes:
                            heapq.heappush(lNodes, tTuple)

    return False

@timer
def f1(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(-dist(iStartX, iStartY, iTargetX, iTargetY), iStartX, iStartY)]
    lVisitedNodes = []

    while len(lNodes) > 0:
        h, x, y = lNodes[0]
        lNodes.remove((h, x, y))
        lVisitedNodes.append((h, x, y))

        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if isValid(i, j):
                    if (i, j) == (iTargetX, iTargetY): return True
                    tTuple = (-dist(i, j, iTargetX, iTargetY), i, j)
                    if not tTuple in lVisitedNodes:
                        if tTuple not in lNodes:
                            lNodes.append(tTuple)

        lNodes.sort()

    return False


@timer
def f2(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(iStartX, iStartY)]
    lVisitedNodes = []

    while len(lNodes) > 0:
        x, y = lNodes[0]
        lNodes.remove((x, y))
        lVisitedNodes.append((x, y))

        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if isValid(i, j):
                    if (i, j) == (iTargetX, iTargetY): return True
                    tTuple = (i, j)
                    if not tTuple in lVisitedNodes:
                        if tTuple not in lNodes:
                            lNodes.append(tTuple)

        lNodes.sort()

    return False

@timer
def f3(iStartX, iStartY, iTargetX, iTargetY):
    global lVisitedNodes
    lNodes = [(iStartX, iStartY)]
    lVisitedNodes = []

    while True:
        lTempNodes = []

        for (x, y) in lNodes:
            if (x, y) not in lVisitedNodes:
                lVisitedNodes.append((x, y))
                for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
                                (x, y-1), (x, y+1),
                                (x+1, y-1), (x+1, y), (x+1, y+1)]:

                    if isValid(i, j):
                        if (i, j) == (iTargetX, iTargetY):
                            return True
                        if (i, j) not in lNodes:
                            if (i, j) not in lTempNodes:
                                lTempNodes.append((i, j))

        if lTempNodes:
            lNodes = lTempNodes
        else:
            return False

@timer
def f4(iStartX, iStartY, tTargets):
    global lVisitedNodes
    lNodes = [(iStartX, iStartY)]
    lVisitedNodes = []

    while True > 0:
        lTempNodes = []

        for (x, y) in lNodes:
            if (x, y) not in lVisitedNodes:
                lVisitedNodes.append((x, y))
                for (i, j) in [(x-1, y-1), (x-1, y), (x-1, y+1),
                                (x, y-1), (x, y+1),
                                (x+1, y-1), (x+1, y), (x+1, y+1)]:
                    if isValid(i, j):
                        if (i, j) in tTargets:
                            return True
                        if (i, j) not in lNodes:
                            if (i, j) not in lTempNodes:
                                lTempNodes.append((i, j))

        if lTempNodes:
            lNodes = lTempNodes
        else:
            return False

@timer
def ff(iStartX, iStartY, iTargetX, iTargetY):
    g[0] = 0
    global lNodes
    global lVisitedNodes
    lNodes = [(iStartX, iStartY)]
    lVisitedNodes = []

    while True > 0:

        lTemp = []
        for (x, y) in lNodes:
            if (x, y) not in lVisitedNodes:
                lVisitedNodes.append((x, y))

                for i in range(x-1, x+2):
                    for j in range(y-1, y+2):
                        if isValid(i, j):
                            if (i, j) == (iTargetX, iTargetY):
                                return True
                            if (i, j) not in lNodes:
                                if (i, j) not in lTemp:
                                    lTemp.append((i, j))
        if lTemp:
            lNodes = lTemp
        else:
            return False

        if debug:
            print lNodes

@timer
def ff2(iStartX, iStartY, tTarget):
    g[0] = 0
    global lNodes
    global lVisitedNodes
    lNodes = [(iStartX, iStartY)]
    lVisitedNodes = []

    while True > 0:

        lTemp = []
        for (x, y) in lNodes:
            if (x, y) not in lVisitedNodes:
                lVisitedNodes.append((x, y))

                for i in range(x-1, x+2):
                    for j in range(y-1, y+2):
                        if isValid(i, j):
                            if (i, j) in tTarget:
                                return True
                            if (i, j) not in lNodes:
                                if (i, j) not in lTemp:
                                    lTemp.append((i, j))
        if lTemp:
            lNodes = lTemp
        else:
            return False

        if debug:
            print lNodes
 
Oh, you need to replace the heuristic (remove the negative sign). Heapq sorts so that it pops the minimum, while list.sort() results in the highest number at index 0.
 
You are right. It does work, Much faster.
But this wrong negative sign is not trivial to debug.

Premature optimization is the root of all evil.
Caching is a good habit.
 
I rewrite my filter function isValid.
Spoiler :

Code: 
def d(x, y, z):
    d = {}
    for i in range(1, x+1):
        for j in range(1, y+1):
            r = random.random()
            d[(i, j)] = True if r > z else False

    d[(1, 1)] = True
    d[(x+1, y+1)] = True
    return d

region = d(70, 70, 0.3)

def isValid(i, j):
    return region.get((i, j), False)


Then I found A* with heuristic function is much faster if target is connected.
But it has no advantage or is even slower when target is not connected.

70 * 70, 70% possibility with railroad, from (1,1) to (70,70)
Result:
Spoiler :

>>> for i in range(1,6):
... print 'Test %d' % i
... test(70, 70, 0.3)
... print
...
Test 1
heapq with heuristic
False
Time 1.98300004005
Visited 3363
list with heuristic
False
Time 2.08400011063
Visited 3363
list without heuristic
False
Time 2.0609998703
Visited 3363
zahlen
False
Time 0.766999959946
Visited 3363

Test 2
heapq with heuristic
True
Time 0.00600004196167
Visited 84
list with heuristic
True
Time 2.26699995995
Visited 3464
list without heuristic
True
Time 2.14099979401
Visited 3420
zahlen
True
Time 0.815999984741
Visited 3462

Test 3
heapq with heuristic
True
Time 0.00600004196167
Visited 95
list with heuristic
True
Time 2.30400013924
Visited 3423
list without heuristic
True
Time 2.12199997902
Visited 3380
zahlen
True
Time 0.775000095367
Visited 3418

Test 4
heapq with heuristic
False
Time 2.03399991989
Visited 3391
list with heuristic
False
Time 2.07300019264
Visited 3391
list without heuristic
False
Time 2.03600001335
Visited 3391
zahlen
False
Time 0.756999969482
Visited 3391

Test 5
heapq with heuristic
False
Time 2.09599995613
Visited 3441
list with heuristic
False
Time 2.1930000782
Visited 3441
list without heuristic
False
Time 2.14400005341
Visited 3441
zahlen
False
Time 0.785000085831
Visited 3441


You need to consider that there is only one success but many failures.
 
zahlen said:
You are right. It does work, Much faster.
But this wrong negative sign is not trivial to debug.
Click to expand...
It is trivial if you properly read the documentation :D I initially made the same mistake though :)

zahlen said:
Then I found A* with heuristic function is much faster if target is connected.
But it has no advantage or is even slower when target is not connected.
Click to expand...
I don't see how it could be slower. It's obvious that if there is no connection you're in the worst case because you have to traverse the whole graph. The presence of a heuristic doesn't really change that; you might traverse the graph in a different way but in the end you visit every node once.
 
Perhaps due to function call overhead in Python is relatively high.

Still 70 * 70, 70% possibility with railroad, from (1,1) to (70,70)
Spoiler :

Test 1
heapq with heuristic
True
Time 0.00499987602234
Visited 89

zahlen
True
Time 0.768999814987
Visited 3394

Test 2
heapq with heuristic
True
Time 0.00399994850159
Visited 81

zahlen
True
Time 0.805999994278
Visited 3457

Test 3
heapq with heuristic
True
Time 0.00699996948242
Visited 103

zahlen
True
Time 0.774999856949
Visited 3411

Test 4
heapq with heuristic
False
Time 2.16599988937
Visited 3464

zahlen
False
Time 0.825000047684
Visited 3464

Test 5
heapq with heuristic
True
Time 0.00499987602234
Visited 94

zahlen
True
Time 0.767999887466
Visited 3398

Test 6
heapq with heuristic
False
Time 2.13499999046
Visited 3455

zahlen
False
Time 0.797999858856
Visited 3455

Test 7
heapq with heuristic
True
Time 0.00699996948242
Visited 109

zahlen
True
Time 0.8140001297
Visited 3488

Test 8
heapq with heuristic
True
Time 0.0199999809265
Visited 102

zahlen
True
Time 0.786000013351
Visited 3424

Test 9
heapq with heuristic
False
Time 2.0490000248
Visited 3404

zahlen
False
Time 0.770999908447
Visited 3404

Test 10
heapq with heuristic
False
Time 2.1779999733
Visited 3477

zahlen
False
Time 0.813999891281
Visited 3477


Connected 6
 
You must log in or register to reply here.

Similar threads

Leoreth
City Names Feedback Thread
Replies
18
Views
1K
manio curio
M
voigt
(RFC3E) Bug Reports and Technical Issues
2
Replies
31
Views
3K
voigt
voigt
bmaupin
Reload mod changes without exiting the game
Replies
2
Views
344
Ryan F. Mercer
Ryan F. Mercer
C
[BNW] AddGameplayScript not working
Replies
3
Views
122
clamlol
C
Nikas Kunitz
My suggestions for the new RFCDoC
3 4 5
Replies
94
Views
8K
IrishDragon
I
Back
Top Bottom