First of all, the algorithm displayed on your image from the pdf file is not a solution to the Hamilton path problem but a solution to a maze generation as the final path has several branches.
To find algorithms for a maze generation, see:
https://en.wikipedia.org/wiki/Maze_generation_algorithm
Now here is a simple algorithm to generate a Hamiltonian path on a N*M 2D grid:
1) Let a N*M grid be (for instance, 4*5):
O-O-O-O-O
| | | | |
O-O-O-O-O
| | | | |
O-O-O-O-O
| | | | |
O-O-O-O-O
2) Let's start from the East/North corner and let's create a simple zigzag to the West and to the East:
O-O-O-O-O
|
O-O-O-O-O
|
O-O-O-O-O
|
O-O-O-O-O
Now we have a Hamiltonian path.
3) Let's search two glued edges which one front of the other. They are the beginning and the end of a loop:
O-O-O-O-O
|
O-OXO-O-O
|
O-OXO-O-O
|
O-O-O-O-O
4) Ensure that there is at least one edge inside the loop that is glued to an edge outside the loop, otherwise, go to step 3:
O-O-O-O-O
|
O-OXO-O-O
|
O-OXOxO-O
|
O-O-OxO-O
5) Shortcut the loop:
O-O-O-O-O
|
O-O O-O-O
| | |
O-O OxO-O
|
O-O-OxO-O
6) Reattach the loop by the two other glued edges:
O-O-O-O-O
|
O-O O-O-O
| | |
O-O O O-O
| | |
O-O-O O-O
7) If the Hamiltonian path is not randomized enough, go to step 3.
Only the start and the end will not move. To randomize the end or the start, you can replace the initial zigzag by another algorithm:
- Choose one of the four corners
- Search all the non-visited neighbors
- If there is no neighbor, the map is filled, otherwise go to step 4
- Only keep the neighbors that have a void or a visited cell on one side, left or right (in other words, the neighbors that walk along the border of the non-visited area)
- Choose one of those neighbors, visit it and go to step 2
The result may look like that:
O-O-O-O-O
|
O-O-O-O O
| | |
O O-O O O
| | | |
O-O-O O-O
With this algorithm, the start remains on a corner but the end can be anywhere. To randomize the start AND the end, you can apply an algorithm that you can iterate as many times as you want either on the start or on the end. Let's take the start:
1) Locate the start:
|
v
O-O-O-O-O
|
O-O-O-O O
| | |
O O-O O O
| | | |
O-O-O O-O
2) Locate a neighbor that is not directly connected to the start (you will always find one in a 2D grid):
O-O-O-O-O
|
->O-O-O-O O
| | |
O O-O O O
| | | |
O-O-O O-O
3) Find from where you arrive to it from the start (respectively from the end):
O-O-O-O-O
|
OXO-O-O O
| | |
O O-O O O
| | | |
O-O-O O-O
4) Cut this link and create a link between this point and the start:
O-O-O-O-O
| |
O O-O-O O
| | |
O O-O O O
| | | |
O-O-O O-O
The start has moved two cells. The start and the end are as on a checkerboard and they only can move on a case with the same color.
Now your path is completely randomized.
Here is the whole algorithm in Python. You can run it here:
http://www.compileonline.com/execute_python3_online.php
The result is stored in an array (self.gameGrid) that is logged twice (with arrows and with nodes and lines). The first two glued edges are called a permutation and the second ones are called an intersection.
#!/usr/local/bin/python3
import random
class CellRoom:
def generateGame(self):
## Constants
self.UNDEFINED = 0
self.FROM_NOWHERE = 1
self.FROM_NORTH = 2
self.FROM_EAST = 3
self.FROM_SOUTH = 4
self.FROM_WEST = 5
self.LEFT = 0
self.RIGHT = 1
self.GAME_WIDTH = random.randint(3, 20)
self.GAME_HEIGHT = random.randint(3, 20)
self.initGame()
for i in range(100):
self.permutate()
##self.logGameWithPath()
##self.logGameWithArrow()
for i in range(50):
self.start = self.moveExtremity(self.start)
self.logGameWithPath()
self.logGameWithArrow()
self.verifyGame()
## Print the map of the game on the standard output.
## Do not show the orientation.
def logGameWithPath(self):
print ('game width: ' + str(self.GAME_WIDTH))
print ('game height: ' + str(self.GAME_HEIGHT))
print ('Start [x=' + str(self.start[1]) + ', y=' + str(self.start[0]) + ']')
gameText = ''
for i in range(len(self.gameGrid)):
for j in range(len(self.gameGrid[i])):
if (self.gameGrid[i][j] == self.FROM_NORTH) or ((i > 0) and (self.gameGrid[i - 1][j] == self.FROM_SOUTH)):
gameText = gameText + ' |'
else:
gameText = gameText + ' '
gameText = gameText + ' \n'
for j in range(len(self.gameGrid[i])):
if (self.gameGrid[i][j] == self.FROM_WEST) or ((j > 0) and (self.gameGrid[i][j - 1] == self.FROM_EAST)):
gameText = gameText + '-O'
else:
gameText = gameText + ' O'
gameText = gameText + ' \n'
for j in range(len(self.gameGrid[i])):
gameText = gameText + ' '
gameText = gameText + ' \n'
print (gameText)
## Print the map of the game on the standard output.
## It shows the orientation.
def logGameWithArrow(self):
gameText = ''
for gameLine in self.gameGrid:
for j in gameLine:
if j == self.FROM_NOWHERE:
gameText = gameText + 'X'
elif j == self.FROM_NORTH:
gameText = gameText + 'V'
elif j == self.FROM_EAST:
gameText = gameText + '('
elif j == self.FROM_SOUTH:
gameText = gameText + '^'
elif j == self.FROM_WEST:
gameText = gameText + ')'
gameText = gameText + '\n'
print (gameText)
## Generate a new map with an extremity (ex. start point) at another place.
## It receives and returns a valid map.
def moveExtremity(self, extremity):
## Search the points.
possibleNewOrigins = []
if ((extremity[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[extremity[0] + 1][extremity[1]] != self.FROM_NORTH)):
possibleNewOrigins.append(self.FROM_NORTH)
besidePoint = [extremity[0] + 1, extremity[1]]
elif ((extremity[1] > 0) and (self.gameGrid[extremity[0]][extremity[1] - 1] != self.FROM_EAST)):
possibleNewOrigins.append(self.FROM_EAST)
besidePoint = [extremity[0], extremity[1] - 1]
elif ((extremity[0] > 0) and (self.gameGrid[extremity[0] - 1][extremity[1]] != self.FROM_SOUTH)):
possibleNewOrigins.append(self.FROM_SOUTH)
besidePoint = [extremity[0] - 1, extremity[1]]
elif ((extremity[1] < self.GAME_WIDTH - 1) and (self.gameGrid[extremity[0]][extremity[1] + 1] != self.FROM_WEST)):
possibleNewOrigins.append(self.FROM_WEST)
besidePoint = [extremity[0], extremity[1] + 1]
besidePointNewOrigin = possibleNewOrigins[random.randint(0, len(possibleNewOrigins) - 1)]
if besidePointNewOrigin == self.FROM_NORTH:
besidePoint = [extremity[0] + 1, extremity[1]]
elif besidePointNewOrigin == self.FROM_EAST:
besidePoint = [extremity[0], extremity[1] - 1]
elif besidePointNewOrigin == self.FROM_SOUTH:
besidePoint = [extremity[0] - 1, extremity[1]]
elif besidePointNewOrigin == self.FROM_WEST:
besidePoint = [extremity[0], extremity[1] + 1]
##print ('New start: [' + str(extremity[0]) + ', ' + str(extremity[1]) + ']')
##print ('besidePoint: [' + str(besidePoint[0]) + ', ' + str(besidePoint[1]) + ']')
## Search the new extremity
if self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_NORTH:
newExtremity = [besidePoint[0] - 1, besidePoint[1]]
elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_EAST:
newExtremity = [besidePoint[0], besidePoint[1] + 1]
elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_SOUTH:
newExtremity = [besidePoint[0] + 1, besidePoint[1]]
elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_WEST:
newExtremity = [besidePoint[0], besidePoint[1] - 1]
## Do the move.
self.reversePath(extremity, newExtremity)
self.gameGrid[besidePoint[0]][besidePoint[1]] = besidePointNewOrigin
self.gameGrid[newExtremity[0]][newExtremity[1]] = self.FROM_NOWHERE
##print ('extremity: [' + str(newExtremity[0]) + ', ' + str(newExtremity[1]) + ']')
return newExtremity
## Rewrite the path on the map as the end was the start and vice versa.
## The end becomes undefined.
def reversePath(self, start, end):
currentPoint = start
##print ('start: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
##print ('end: [' + str(end[0]) + ', ' + str(end[1]) + ']')
while (currentPoint[0] != end[0]) or (currentPoint[1] != end[1]):
##print ('currentPoint: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
## We search the next point, not the point we just have reversed
if (currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.FROM_NORTH) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_SOUTH):
self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_SOUTH
currentPoint[0] = currentPoint[0] + 1
elif (currentPoint[1] > 0) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.FROM_EAST) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_WEST):
self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_WEST
currentPoint[1] = currentPoint[1] - 1
elif (currentPoint[0] > 0) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.FROM_SOUTH) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_NORTH):
self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_NORTH
currentPoint[0] = currentPoint[0] - 1
elif (currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.FROM_WEST) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_EAST):
self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_EAST
currentPoint[1] = currentPoint[1] + 1
##print ('reversePath: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
self.gameGrid[currentPoint[0]][currentPoint[1]] = self.UNDEFINED
## Check that we go on every cell.
def verifyGame(self):
moveCount = 0
currentPoint = [self.start[0], self.start[1]]
isEnd = 0
while (isEnd == 0):
if (currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.FROM_NORTH):
currentPoint[0] = currentPoint[0] + 1
elif (currentPoint[1] > 0) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.FROM_EAST):
currentPoint[1] = currentPoint[1] - 1
elif (currentPoint[0] > 0) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.FROM_SOUTH):
currentPoint[0] = currentPoint[0] - 1
elif (currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.FROM_WEST):
currentPoint[1] = currentPoint[1] + 1
else:
isEnd = 1
if isEnd == 0:
moveCount = moveCount + 1
## The number of moves should equal to the size of the map minus one cell because we don't arrive on the start
if moveCount == ((self.GAME_HEIGHT * self.GAME_WIDTH) - 1):
print ('OK')
else:
print ('ko!!!')
## Fill the map with void data.
def initGame(self):
self.gameGrid = []
for i in range(self.GAME_HEIGHT):
gameLine = []
for j in range(self.GAME_WIDTH):
gameLine.append(self.UNDEFINED)
self.gameGrid.append(gameLine)
self.initComplexMap()
## Create a valid simple map.
## It uses a complex algorithm.
def initComplexMap(self):
startPoint = random.randint(0, 3)
if startPoint == 0:
self.start = [0, 0]
elif startPoint == 1:
self.start = [0, self.GAME_WIDTH - 1]
elif startPoint == 2:
self.start = [self.GAME_HEIGHT - 1, 0]
elif startPoint == 3:
self.start = [self.GAME_HEIGHT - 1, self.GAME_WIDTH - 1]
self.gameGrid[self.start[0]][self.start[1]] = self.FROM_NOWHERE
currentPoint = [self.start[0], self.start[1]]
while ((0 < currentPoint[0]) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.UNDEFINED)) or ((currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.UNDEFINED)) or ((0 < currentPoint[1]) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.UNDEFINED)) or ((currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.UNDEFINED)):
possibilities = []
if ((0 < currentPoint[0]) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.UNDEFINED)) and (((0 == currentPoint[1]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[1] == self.GAME_WIDTH - 1) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] + 1] != self.UNDEFINED))):
possibilities.append([currentPoint[0] - 1, currentPoint[1], self.FROM_SOUTH])
if ((currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.UNDEFINED)) and (((0 == currentPoint[1]) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[1] == self.GAME_WIDTH - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] + 1] != self.UNDEFINED))):
possibilities.append([currentPoint[0] + 1, currentPoint[1], self.FROM_NORTH])
if ((0 < currentPoint[1]) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.UNDEFINED)) and (((0 == currentPoint[0]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[0] == self.GAME_HEIGHT - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] - 1] != self.UNDEFINED))):
possibilities.append([currentPoint[0], currentPoint[1] - 1, self.FROM_EAST])
if ((currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.UNDEFINED)) and (((0 == currentPoint[0]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] + 1] != self.UNDEFINED)) or ((currentPoint[0] == self.GAME_HEIGHT - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] + 1] != self.UNDEFINED))):
possibilities.append([currentPoint[0], currentPoint[1] + 1, self.FROM_WEST])
possibility = possibilities.pop(random.randint(0, len(possibilities) - 1))
currentPoint = [possibility[0], possibility[1]]
self.gameGrid[possibility[0]][possibility[1]] = possibility[2]
## Create a valid simple map.
## It uses a basic algorithm.
def initSimpleMap(self):
direction = self.RIGHT
if random.randint(0, 1) == 0:
for i in range(self.GAME_HEIGHT):
if direction == self.RIGHT:
self.gameGrid[i][0] = self.FROM_NORTH
for j in range(1, self.GAME_WIDTH):
self.gameGrid[i][j] = self.FROM_WEST
direction = self.LEFT
else:
for j in range(self.GAME_WIDTH - 1):
self.gameGrid[i][j] = self.FROM_EAST
self.gameGrid[i][self.GAME_WIDTH - 1] = self.FROM_NORTH
direction = self.RIGHT
self.gameGrid.append(gameLine)
self.gameGrid[0][0] = self.FROM_NOWHERE
else:
for j in range(self.GAME_WIDTH):
if direction == self.RIGHT:
self.gameGrid[0][j] = self.FROM_WEST
for i in range(1, self.GAME_HEIGHT):
self.gameGrid[i][j] = self.FROM_NORTH
direction = self.LEFT
else:
for i in range(self.GAME_HEIGHT - 1):
self.gameGrid[i][j] = self.FROM_SOUTH
self.gameGrid[self.GAME_HEIGHT - 1][j] = self.FROM_WEST
direction = self.RIGHT
self.gameGrid[0][0] = self.FROM_NOWHERE
## Search all the possible permutations.
## It doesn't affect the map.
def listPermutation(self):
self.permutableZones = []
for i in range(self.GAME_HEIGHT - 1):
for j in range(self.GAME_WIDTH - 1):
if (self.gameGrid[i + 1][j] == self.FROM_NORTH) and (self.gameGrid[i][j + 1] == self.FROM_SOUTH):
self.permutableZones.append([[i + 1, j], [i, j + 1]])
elif (self.gameGrid[i][j] == self.FROM_SOUTH) and (self.gameGrid[i + 1][j + 1] == self.FROM_NORTH):
self.permutableZones.append([[i, j], [i + 1, j + 1]])
elif (self.gameGrid[i][j] == self.FROM_EAST) and (self.gameGrid[i + 1][j + 1] == self.FROM_WEST):
self.permutableZones.append([[i, j], [i + 1, j + 1]])
elif (self.gameGrid[i][j + 1] == self.FROM_WEST) and (self.gameGrid[i + 1][j] == self.FROM_EAST):
self.permutableZones.append([[i, j + 1], [i + 1, j]])
## Permutate the connection of path.
## It receives and returns a valid map.
def permutate(self):
self.listPermutation()
if len(self.permutableZones) > 0:
permutation = self.permutableZones.pop(random.randint(0, len(self.permutableZones) - 1))
start = permutation[0]
end = permutation[1]
##print ('Entry of the loop: (' + str(start[0]) + ', ' + str(start[1]) + ')')
##print ('Exit of the loop: (' + str(end[0]) + ', ' + str(end[1]) + ')')
if self.isLoop(end, start):
self.findPermutation(start, end)
else:
end = permutation[0]
start = permutation[1]
## Assertion
if not self.isLoop(end, start):
print ('Wrong!')
self.findPermutation(start, end)
## It doesn't affect the map.
def isInLoop(self, searchedPoint):
found = False
for point in self.currentLoop:
if (searchedPoint[0] == point[0]) and (searchedPoint[1] == point[1]):
found = True
return found
## It doesn't affect the map.
def isLoop(self, originalPoint, destination):
self.currentLoop = []
point = []
point.append(originalPoint[0])
point.append(originalPoint[1])
self.currentLoop.append([originalPoint[0], originalPoint[1]])
while ((point[0] != destination[0]) or (point[1] != destination[1])) and (self.gameGrid[point[0]][point[1]] != self.FROM_NOWHERE):
##print ('Loop point: (' + str(point[0]) + ', ' + str(point[1]) + ')')
newY = point[0]
newX = point[1]
if self.gameGrid[point[0]][point[1]] == self.FROM_SOUTH:
newY = point[0] + 1
elif self.gameGrid[point[0]][point[1]] == self.FROM_NORTH:
newY = point[0] - 1
elif self.gameGrid[point[0]][point[1]] == self.FROM_WEST:
newX = point[1] - 1
elif self.gameGrid[point[0]][point[1]] == self.FROM_EAST:
newX = point[1] + 1
point[0] = newY
point[1] = newX
self.currentLoop.append([newY, newX])
return ((point[0] == destination[0]) and (point[1] == destination[1]))
## Permutate the connections of path.
## It receives and returns a valid map.
def findPermutation(self, start, end):
self.findIntersections()
if len(self.intersections) > 0:
self.modifyIntersection(start, end)
## Permutate the connections of path.
## It doesn't affect the map.
def findIntersections(self):
self.intersections = []
for i in range(1, len(self.currentLoop) - 1):
point = self.currentLoop[i]
if self.gameGrid[point[0]][point[1]] == self.FROM_NORTH:
if (0 < point[1]) and (self.gameGrid[point[0] - 1][point[1] - 1] == self.FROM_SOUTH) and not self.isInLoop([point[0] - 1, point[1] - 1]):
self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] - 1]])
elif (point[1] < self.GAME_WIDTH - 1) and (self.gameGrid[point[0] - 1][point[1] + 1] == self.FROM_SOUTH) and not self.isInLoop([point[0] - 1, point[1] + 1]):
self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] + 1]])
elif self.gameGrid[point[0]][point[1]] == self.FROM_SOUTH:
if (0 < point[1]) and (self.gameGrid[point[0] + 1][point[1] - 1] == self.FROM_NORTH) and not self.isInLoop([point[0] + 1, point[1] - 1]):
self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] - 1]])
elif (point[1] < self.GAME_WIDTH - 1) and (self.gameGrid[point[0] + 1][point[1] + 1] == self.FROM_NORTH) and not self.isInLoop([point[0] + 1, point[1] + 1]):
self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] + 1]])
elif self.gameGrid[point[0]][point[1]] == self.FROM_WEST:
if (0 < point[0]) and (self.gameGrid[point[0] - 1][point[1] - 1] == self.FROM_EAST) and not self.isInLoop([point[0] - 1, point[1] - 1]):
self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] - 1]])
elif (point[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[point[0] + 1][point[1] - 1] == self.FROM_EAST) and not self.isInLoop([point[0] + 1, point[1] - 1]):
self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] - 1]])
elif self.gameGrid[point[0]][point[1]] == self.FROM_EAST:
if (0 < point[0]) and (self.gameGrid[point[0] - 1][point[1] + 1] == self.FROM_WEST) and not self.isInLoop([point[0] - 1, point[1] + 1]):
self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] + 1]])
elif (point[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[point[0] + 1][point[1] + 1] == self.FROM_WEST) and not self.isInLoop([point[0] + 1, point[1] + 1]):
self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] + 1]])
## Permutate the connections of path.
## It receives and returns a valid map.
def modifyIntersection(self, start, end):
##self.logGameWithPath()
##self.printGameOld()
intersection = self.intersections[random.randint(0, len(self.intersections) - 1)]
## Disconnect the loop
self.modifyPath([start, end])
## Reconnect the loop
self.modifyPath(intersection)
## Change the connections on the map.
def modifyPath(self, intersection):
##print ('modifyPath: (' + str(intersection[0][0]) + ', ' + str(intersection[0][1]) + ') with (' + str(intersection[1][0]) + ', ' + str(intersection[1][1]) + ')')
firstPoint = self.gameGrid[intersection[0][0]][intersection[0][1]]
secondPoint = self.gameGrid[intersection[1][0]][intersection[1][1]]
if (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_NORTH) or (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_SOUTH):
if (intersection[0][1] < intersection[1][1]):
firstPoint = self.FROM_EAST
secondPoint = self.FROM_WEST
else:
firstPoint = self.FROM_WEST
secondPoint = self.FROM_EAST
if (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_EAST) or (self.gameGrid[intersection[0][0]][intersection[0][1]] == self.FROM_WEST):
if (intersection[0][0] < intersection[1][0]):
firstPoint = self.FROM_SOUTH
secondPoint = self.FROM_NORTH
else:
firstPoint = self.FROM_NORTH
secondPoint = self.FROM_SOUTH
self.gameGrid[intersection[0][0]][intersection[0][1]] = firstPoint
self.gameGrid[intersection[1][0]][intersection[1][1]] = secondPoint
cellRoom = CellRoom()
cellRoom.generateGame()
This paper describes a method:
Oberdorf, R.; Ferguson, A.; Jacobsen, J.L.; Kondev, J. - Secondary Structures in Long Compact Polymers (arXiv.org)
The method roughly consists of the following: start with a zig-zag pattern (a non-random Hamiltonian path on the grid) and repeatedly apply a transformation (called "backbite") to the path. A backbite consists of adding an edge from one of the endpoints A to an adjacent vertex B other than the one A is connected to (thus creating a loop), and then remove the edge that starts in B that is not the one just added and that causes a loop (there will always be only one causing a loop other than the one just added).
The authors add some conditions to obtain rough uniformity (including an estimation on how many times to apply the backbite move). Details in the paper.
The authors also prove empirically that the probability of their method generating adjacent endpoints approximately matches the theoretical probability in uniform random Hamiltonian paths.
There is an implementation of the algorithm in JavaScript here: Hamiltonian Path Generator
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://img.manongdao.com/sparkler-677774__340.jpg', '推荐 再贱就再见 的文章《Algorithm to find a random Hamiltonian path in a g》','https://www.manongdao.com/article-590537.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}