First of all, the algorithm displayed on your image from the pdf file is not a solution to the problem of the Hamilton path, but a solution for generating a maze, since the final path has several branches.
To find the labyrinth generation algorithms, see https://en.wikipedia.org/wiki/Maze_generation_algorithm
Now we have a simple algorithm for generating a Hamiltonian trajectory on an N * M 2D grid:
1) Let the grid N * M be (for example, 4 * 5):
OOOOO | | | | | OOOOO | | | | | OOOOO | | | | | OOOOO
2) Start from the east / north corner and create a simple zigzag to the West and East:
OOOOO | OOOOO | OOOOO | OOOOO
Now we have the Hamiltonian path.
3) Let the search for two glued edges that are one front of the other. This is the beginning and end of the cycle:
OOOOO | O-OXO-OO | O-OXO-OO | OOOOO
4) Make sure that there is at least one edge inside the loop that is glued to the edge outside the loop, otherwise go to step 3:
OOOOO | O-OXO-OO | O-OXOxO-O | OO-OxO-O
5) Label loop:
OOOOO | OO OOO | | | OO OxO-O | OO-OxO-O
6) Reconnect the loop to the other two glued edges:
OOOOO | OO OOO | | | OO O OO | | | OOO OO
7) If the Hamiltonian path is not sufficiently randomized, go to step 3.
Only the beginning and end will not move. To randomize the end or the beginning, you can replace the initial zigzag with another algorithm:
- Choose from four corners.
- Search for all non-visited neighbors
- If there is no neighbor, the card is filled, otherwise go to step 4
- Support only neighbors who have a void or cell visited on one side, left or right (in other words, neighbors who walk along the border of the area without visiting)
- Select one of these neighbors, go into it and go to step 2
The result may look like this:
OOOOO | OOOO O | | | O OO OO | | | | OOO OO
With this algorithm, the beginning remains at the corner, but the end can be anywhere. To randomize the beginning and the end, you can apply an algorithm that you can repeat as many times as you want, either at the beginning or at the end. Take the beginning:
1) Find the beginning:
|
v
OOOOO
|
OOOO O
| | |
O OO OO
| | | |
OOO OO
2) Find a neighbor who is not directly connected to the start (you will always find him in the 2D grid):
OOOOO
|
-> OOOO O
| | |
O OO OO
| | | |
OOO OO
3) Find where you came to him from the very beginning (respectively, from the end):
OOOOO
|
OXO-OO O
| | |
O OO OO
| | | |
OOO OO
4) Cut this link and create a link between this point and the beginning:
OOOOO
| |
O OOO O
| | |
O OO OO
| | | |
OOO OO
The beginning moved two cells. The beginning and end are like on a chessboard, and they can only move on the case of 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 ), which is written twice (with arrows and with nodes and rows). The first two glued ribs are called permutation, and the second - 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()