This is a bit for fun and a bit for serious.
Jetblade, the open-source game I've been working on off and on, has a spacefilling automaton that I use to carve tunnels into the game world. Here's an example animation showing how the algorithm works:
Basically a selection of "seeds" are laid down along the various lines that describe where the game wants to place tunnels. These seeds have two attributes: an owner and a lifespan. Each tick, they attempt to replace all neighboring cells with a copy of themselves with shorter life, and make an open space. If there's already a seed adjacent to them with a different owner, however, then they create a wall instead.
There's a problem, though: this is slow. For a (fairly small) map of 250x250 cells, seed expansion takes 7 seconds, and this scales approximately linearly with the number of cells (35 seconds at 500x500). So here's the function; do you see any notable improvements that could be made?
Language: python
## Run a spacefilling automaton to divide a grid up into different sectors.
# \param seeds A mapping of locations to Seed instances
# \param blocks A grid of cells to be converted to walls and open space
# Each seed ordinarily replaces all neighbor spaces with copies of itself
# that have 1 less turn to live. When a seed dies (has 0 life), its location
# is marked as open in the blocks grid. Dead seeds are retained so we can
# map spaces to the sectors that own those spaces.
# When two expanding seeds collide, they merge if they are for the same
# sector (as determined by their 'owner' property), or form a wall between
# them if they are not.
def expandSeeds(self, seeds, blocks):
deadSeeds = dict()
numCols = len(blocks)
numRows = len(blocks[0])
logger.debug("Expanding seeds for a",numCols,"by",numRows,"grid")
while len(seeds):
newSeeds = dict()
for loc, curSeed in seeds.iteritems():
# If the counter expires while the seed is not in open space,
# replace it with a wall.
if (not self.getIsInBounds(loc, numCols, numRows) or
(curSeed.life <= 0 and blocks[loc.ix][loc.iy] != BLOCK_EMPTY)):
deadSeeds[loc] = curSeed
blocks[loc.ix][loc.iy] = BLOCK_WALL
continue
if (blocks[loc.ix][loc.iy] == BLOCK_WALL):
# A wall sprung up under us. Check if there's a dead
# seed there; if so, try to merge with it.
if loc in deadSeeds:
newSeed = self.tryMergeDeadSeed(curSeed, loc, seeds, deadSeeds, numCols, numRows)
if newSeed is not None:
newSeeds[loc] = newSeed
del deadSeeds[loc]
blocks[loc.ix][loc.iy] = BLOCK_UNALLOCATED
else:
# No seeds on walls.
continue
if blocks[loc.ix][loc.iy] == BLOCK_EMPTY:
# No seeds on empty space
deadSeeds[loc] = curSeed
continue
for adjLoc in loc.perimeter():
# Check adjacent blocks for seeds. If none, expand into the
# space. If there is a seed, make a wall, unless it's our
# own seed in which case we merge with it.
if not self.getIsInBounds(adjLoc, numCols, numRows):
continue
if adjLoc in seeds or adjLoc in newSeeds:
# Two adjacent seeds; either merge or make wall.
altSeed = None
if adjLoc in seeds:
altSeed = seeds[adjLoc]
else:
altSeed = newSeeds[adjLoc]
if altSeed.owner == curSeed.owner:
# Merge the seeds
newSeeds[adjLoc] = seed.Seed(curSeed.owner,
max(curSeed.life, altSeed.life) - 1,
max(curSeed.age, altSeed.age) + 1)
else:
# Conflict; make a wall.
altSeed.life = 0
altSeed.age = constants.BIGNUM
curSeed.life = 0
curSeed.age = constants.BIGNUM
blocks[loc.ix][loc.iy] = BLOCK_WALL
blocks[adjLoc.ix][adjLoc.iy] = BLOCK_WALL
elif blocks[loc.ix][loc.iy] == BLOCK_UNALLOCATED:
# No seed there; plant one.
newSeeds[adjLoc] = seed.Seed(curSeed.owner, curSeed.life - 1, curSeed.age + 1)
elif (blocks[adjLoc.ix][adjLoc.iy] != BLOCK_EMPTY and
deadSeeds.has_key(adjLoc)):
# Hit a wall containing a dead seed; try to merge
# with it.
newSeed = self.tryMergeDeadSeed(curSeed, adjLoc, seeds, deadSeeds, numCols, numRows)
if newSeed is not None:
newSeeds[adjLoc] = newSeed
del deadSeeds[adjLoc]
blocks[adjLoc.ix][adjLoc.iy] = BLOCK_UNALLOCATED
# Done expanding; zero our location if we didn't wall it
# earlier.
if blocks[loc.ix][loc.iy] != BLOCK_WALL:
blocks[loc.ix][loc.iy] = BLOCK_EMPTY
deadSeeds[loc] = curSeed
seeds = newSeeds
return (blocks, deadSeeds)
Voting yes, of course. Great work, Ryuto! The playarounds during the bosses, and the humiliation of the AI bombermen in the arena, were much appreciated.