OneEye Changeset - 07f3fda1cbd7

Changeset - 07f3fda1cbd7

Parent rev.

Child rev.

[Not reviewed]

default

0 2 1

Laman - 7 years ago 2017-12-05 21:35:36

optimized go floodFill

3 files changed with 65 insertions and 32 deletions:

src/analyzer/__init__.py

src/go/core.py

src/go/helperboard.py

0 comments (0 inline, 0 general)

src/analyzer/__init__.py

➞

Show inline comments

 import logging as log
 from .grid import Grid
 from go.core import exportBoard, EMPTY,BLACK,WHITE
 from util import BLACK,WHITE,EMPTY
 from go.core import exportBoard
 class ImageAnalyzer:
 	def __init__(self,tresB=30,tresW=60):
-		self.board=[[EMPTY] * 19 for r in range(19)]
 		self.board=[[EMPTY]*19 for r in range(19)]
 		self.grid=None
 		self.tresB=tresB
 		self.tresW=tresW
 	# let's not concern ourselves with sizecoef and shift here anymore. we want corners to come already properly recomputed

src/go/core.py

➞

Show inline comments

 import logging as log
 from util import EMPTY,BLACK,WHITE,colorNames
 from .helperboard import HelperBoard
 from .gamerecord import GameRecord
 class Go:
 	## Initializes self.board to a list[r][c]=EMPTY.
 	def __init__(self,boardSize=19):
 		self.boardSize=boardSize
 		self.board=[[EMPTY]*boardSize for x in range(boardSize)]
 		self._temp=[[EMPTY]*boardSize for x in range(boardSize)]
 		self.toMove=BLACK
 		self._helper=HelperBoard(self.board)
 		self._record=GameRecord()
 	def listMoves(self,diff=[]):
 		return []
 	## Executes a move.
+	#
 	#  Doesn't check for kos. Suicide not allowed.
+	#
 	#  @param color BLACK or WHITE
 	#  @return True on success, False on failure (illegal move)
@@ @@ -24,54 +28,45 @@ class Go: @@
 		if self.board[row][col]!=EMPTY: return False
 		self.board[row][col]=color
 		# capture neighbors
 		for r,c in ((-1,0),(1,0),(0,-1),(0,1)):
 			self._clearTemp()
 			if not self._floodFill(-color,row+r,col+c): self._remove()
 			self._helper.clear()
 			if not self._helper.floodFill(-color,row+r,col+c,EMPTY): self._remove()
 		# check for suicide
 		self._clearTemp()
 		if not self._floodFill(color,row,col):
 		self._helper.clear()
 		if not self._helper.floodFill(color,row,col,EMPTY):
 			self.board[row][col]=EMPTY
 			return False
 		self._record.move(color,row,col)
 		self.toMove=-1*color
 		return True
 	def undoMove(self,color,r,c,captures):
 		self.board[r][c]=color
 		if len(captures)>0:
 			self._helper.clear()
 			for (r,c) in captures:
 				self._helper.floodFill(EMPTY,r,c)
 			self._fill(-color)
 	def transitionMove(self,board):
 		res=transitionMove(self.board,board)
 		if not res: return res
 		(r,c,color)=res
 		return self.move(color,r,c)
 	## Removes stones at coordinates marked with True in self.helper.
 	def _remove(self):
 		self._fill(EMPTY)
 	## Checks for liberties of a stone at given coordinates.
+	#
 	#  The stone's group is marked with True in self.temp, ready for capture if needed. Recursively called for stone's neighbors.
+	#
 	#  @return True if alive, False if captured
 	def _floodFill(self,color,row,col):
 		if col<0 or col>=self.boardSize or row<0 or row>=self.boardSize: return False # out of range
 		if self._temp[row][col]: return False # already visited
 		if self.board[row][col]==EMPTY: return True # found a liberty
 		if self.board[row][col]!=color: return False # opponent's stone
 		self._temp[row][col]=True # set visited
 		return self._floodFill(color,row,col-1) or self._floodFill(color,row,col+1) or self._floodFill(color,row-1,col) or self._floodFill(color,row+1,col) # check neighbors
 	## Removes stones at coordinates marked with True in self.temp.
 	def _remove(self):
 		for r in range(self.boardSize):
 			for c in range(self.boardSize):
 				if self._temp[r][c]: self.board[r][c]=EMPTY
 	def _clearTemp(self):
 		for i in range(self.boardSize):
 			for j in range(self.boardSize):
 				self._temp[i][j]=EMPTY
 	def _fill(self,filling):
 		for (r,c) in self._helper.continuousArea():
 			self.board[r][c]=filling
 def exportBoard(board):
 	substitutions={EMPTY:".", BLACK:"X", WHITE:"O"}
 	return "\n".join("".join(substitutions.get(x,"?") for x in row) for row in board)
@@ @@ -103,13 +98,13 @@ def transitionMove(state1,state2): @@
 		return moves[0]
 	else:
 		log.warning("too many new stones: %s",moves)
 		return False
 def transitionSequence(state1,state2,diff):
+def transitionSequence(state1,state2,diff,limit=0):
 	return []
 def dfs(stack,board,mask):
 	boardSize=len(board)
 	(r,c)=stack[0]

src/go/helperboard.py

➞

Show inline comments

@@ new file 100644 @@
 from util import EMPTY
 ## Utility class for finding continuous regions on a Go.board.
 class HelperBoard:
 	def __init__(self,board):
 		self._refBoard=board # Go.board, readonly
 		self._boardSize=len(board)
 		self._board=[[EMPTY]*self._boardSize for i in range(self._boardSize)]
 		self._usedCoords=[0]*(self._boardSize**2)*2
 		self._usedCount=0
 	def floodFill(self,filling,r,c,needle=None):
 		if c<0 or c>=self._boardSize or r<0 or r>=self._boardSize: return False # out of range
 		if self._board[r][c]: return False # already visited
 		if self._refBoard[r][c]==needle: return True # found something
 		if self._refBoard[r][c]!=filling: return False # out of area boundary
 		self._board[r][c]=True # set visited
 		self._usedCoords[self._usedCount*2]=r
 		self._usedCoords[self._usedCount*2+1]=c
 		self._usedCount+=1
 		# check neighbors
 		return self.floodFill(filling,r,c-1) or \
 			self.floodFill(filling,r,c+1) or \
 			self.floodFill(filling,r-1,c) or \
 			self.floodFill(filling,r+1,c)
 	def continuousArea(self):
 		for i in range(self._usedCount):
 			yield (self._usedCoords[i*2],self._usedCoords[i*2+1])
 	def clear(self):
 		for i in range(self._usedCount):
 			(r,c)=(self._usedCoords[i*2],self._usedCoords[i*2+1])
 			self._board[r][c]=EMPTY
 		self._usedCount=0

0 comments (0 inline, 0 general)