Map generator, generates XPM files

map.lua

--    Copyright (C) 2011 Ross Andrews
--
--    This program is free software: you can redistribute it and/or modify
--    it under the terms of the GNU General Public License as published by
--    the Free Software Foundation, either version 3 of the License, or
--    (at your option) any later version.
--
--    This program is distributed in the hope that it will be useful,
--    but WITHOUT ANY WARRANTY; without even the implied warranty of
--    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
--    GNU General Public License for more details.
--
--    You should have received a copy of the GNU General Public License
--    along with this program.  If not, see <http://www.gnu.org/licenses/>.

Map = {methods={}}

-- Create a map, either filled with a single value
-- or random values 0..15
function Map.new(width, height, fill)
   local map = Map.empty(width, height)

   for n = 0, (width * height - 1) do
	  map[n] = fill or (math.random(16) - 1)
   end

   return map
end

-- Create an empty map
function Map.empty(width, height)
   local map = {width=width, height=height}
   setmetatable(map,{__index=Map.methods})

   return map
end

-- Returns a copy of the map, independent of the first one
function Map.copy(other)
   return other:slice(0,0,other.width,other.height)
end

-- Copy a rectangular section out of a map into a new map
function Map.methods.slice(self,left,top,w,h)
   local new = Map.empty(w,h)

   for x, y, n in new:each() do
	  new[n] = self:at(x+left, y+top)
   end

   return new
end

-- Convert a 1..n value to x and y values
function Map.methods.n2p(self, n)
   return n % self.width, math.floor(n / self.width)
end

-- Convert a 0-based x,y table to a 1-based index
function Map.methods.p2n(self, x, y)
   return x + self.width * y
end

-- Takes either an n or an x, y and returns the value there.
function Map.methods.at(self, x, y)
   return self[self:p2n(x,y)]
end

-- Takes an x, y and a value and sets the value there
function Map.methods.set(self, x, y, v)
   self[self:p2n(x,y)] = v
   return self
end

-- Internal function used by each
function Map.iterator(state)
   if state.n >= state.self.width * state.self.height then
	  return nil
   else
	  local x, y = Map.methods.n2p(state.self, state.n)
	  local v = state.self[state.n]
	  state.n = state.n + 1
	  return x, y, state.n - 1, v
   end
end

-- Stateful iterator, yields x, y, n, v
function Map.methods.each(self)
   return Map.iterator, {self = self, n = 0}
end

-- Sum of the values of all neighbors (8 sides), and the count of
-- the neighbors. Takes edges into account.
function Map.methods.neighbor_sum(self, x, y)
   local s, c = 0, 0
   if x > 0 then s,c = s + self:at(x-1, y), c + 1 end
   if y > 0 then s,c = s + self:at(x, y-1), c + 1 end
   if x < self.width-1 then s,c = s + self:at(x+1, y), c + 1 end
   if y < self.height-1 then s,c = s + self:at(x, y+1), c + 1 end

   if x > 0 and y > 0 then s,c = s + self:at(x-1, y-1), c + 1 end
   if x > 0 and y < self.height-1 then s,c = s + self:at(x-1, y+1), c + 1 end

   if x < self.width-1 and y > 0 then s,c = s + self:at(x+1, y-1), c + 1 end
   if x < self.width-1 and y < self.height-1 then s,c = s + self:at(x+1, y+1), c + 1 end

   return s, c
end

-- Simple smoothing pass, average each value with its 8 neighbors
function Map.methods.smooth(self)
   local new = Map.copy(self)

   for x, y, n, v in self:each() do
	  local s, c = self:neighbor_sum(x, y)
	  local nv = (v + s) / (c + 1)
	  new[n] = math.round(nv)
   end

   return new
end

-- Scale the spaces in between the tiles. Each original pixel
-- becomes the top-left corner of a scale*scale tile, with its
-- other corners populated by that pixels right/btm/SE neighbors.
-- The last row / col in the scaled map doesn't have all its
-- corners set, so to get a 128x128 map to fractalize, you need
-- a 17x17 seed map (if you're scaling by 8).
function Map.methods.scale(self, scale)
   scale = scale or 8

   local new = Map.new(self.width * scale, self.height * scale, 0)
   local d = scale - 1

   -- Each element in the old map (except the right col / btm row)
   -- becomes a scale * scale square in the new map, with the corner
   -- values copied from the old map.
   for x, y in self:each() do
	  if x < self.width - 1 and y < self.height - 1 then
		 new:set(x*scale, y*scale, self:at(x,y))
		 new:set(x*scale + d, y*scale, self:at(x+1, y))
		 new:set(x*scale, y*scale + d, self:at(x, y+1))
		 new:set(x*scale + d, y*scale + d, self:at(x+1, y+1))
	  end
   end

   return new
end

-- Fractalize a square region of a size, with the
-- upper-left point at x, y
function Map.methods.fractal(self, x, y, size)
   if size < 4 then return self end

   function pick(a, b)
	  if math.random(2) == 1 then return a else return b end
   end

   -- top
   local top = pick(self:at(x,y), self:at(x+size-1,y))
   self:set(x+size/2, y, top)
   self:set(x+size/2 - 1, y, top)

   -- bottom
   local btm = pick(self:at(x,y+size-1), self:at(x+size-1,y+size-1))
   self:set(x+size/2, y+size-1, btm)
   self:set(x+size/2 - 1, y+size-1, btm)

   -- left
   local left = pick(self:at(x,y), self:at(x,y+size-1))
   self:set(x, y+size/2, left)
   self:set(x, y+size/2 - 1, left)

   -- right
   local right = pick(self:at(x+size-1,y), self:at(x+size-1,y+size-1))
   self:set(x+size-1, y+size/2, right)
   self:set(x+size-1, y+size/2 - 1, right)

   -- middle
   local middle = pick(pick(top,btm), pick(left,right))
   self:set(x+size/2, y+size/2, right)
   self:set(x+size/2, y+size/2 - 1, right)
   self:set(x+size/2 - 1, y+size/2, right)
   self:set(x+size/2 - 1, y+size/2 - 1, right)

   self:fractal(x,y,size/2)
   self:fractal(x+size/2,y,size/2)
   self:fractal(x,y+size/2,size/2)
   self:fractal(x+size/2,y+size/2,size/2)

   return self
end

-- Once a map has been scaled to a grid of tiles, call this to
-- fractalize each one.
function Map.methods.fractal_tile(self, tile_size)
   for y = 0, self.height / tile_size - 1 do
	  for x = 0, self.width / tile_size - 1 do
		 self:fractal(x*tile_size, y*tile_size, tile_size)
	  end
   end

   return self
end

-- Returns the XPM data for a map.
function Map.methods.xpm(self, name)
   name = name or 'map'
   local header = '\"' .. self.width .. ' ' .. self.height .. ' 16 1\",'

   local color_names = '0123456789abcdef'
   local colors = {}

   for n=1,8 do -- blues
	  local cn = color_names:sub(n, n)
	  local ch = color_names:sub(n+3, n+3)
	  local c = '\"' .. cn .. ' c #0000' .. ch:rep(2) .. '\",'
	  table.insert(colors, c)
   end

   for n=9,10 do -- greens
	  local ch = color_names:sub(n, n)
	  local c = '\"' .. ch .. ' c #00' .. ch:rep(2) .. '00\",'
	  table.insert(colors, c)
   end

   for n=11,16 do -- grays
	  local ch = color_names:sub(n, n)
	  local c = '\"' .. ch .. ' c #' .. ch:rep(6) .. '\",'
	  table.insert(colors, c)
   end

   --------------------

   local rows = {}

   for y = 0, self.height - 1 do
	  local r = ''

	  for x = 0, self.width - 1 do
		 local v = self:at(x, y)
		 r = r .. color_names:sub(v+1, v+1)
	  end

	  r = '\"' .. r .. '\"'
	  if y < self.height - 1 then r = r .. ',' end
	  table.insert(rows, r)
   end

   --------------------

   local s = '/* XPM */\nstatic char * ' .. name .. '_xpm[] = {\n'
   s = s .. header .. '\n'

   for n, c in ipairs(colors) do s = s .. c .. '\n' end
   for n, r in ipairs(rows) do s = s .. r .. '\n' end
   return s .. '}'
end

----------------------------------------
----------------------------------------

function math.round(n)
   if n - math.floor(n) < math.ceil(n) - n then
	  return math.floor(n)
   else
	  return math.ceil(n)
   end
end

----------------------------------------
----------------------------------------

-- Generate a map with all the trimmings.
-- seed is a random seed
-- size is the size of the resultant map (square maps only, powers of 2 only)
-- chunk_size is how big each fractalized tile is.
-- Larger chunks make larger continents, but look more square.
-- smoothing_passes is how many times to smooth after fractalization.
-- (we always smooth the seed map once pre-fractalization)
function Map.generate(seed, size, chunk_size, smoothing_passes)
   math.randomseed(seed)
   local seed_dim = size/chunk_size + 1
   local seed_map = Map.new(seed_dim, seed_dim):smooth()

   local fractalized = seed_map:scale(chunk_size):fractal_tile(chunk_size)

   smoothing_passes = smoothing_passes or 1
   local smoothed = fractalized:slice(0,0,size,size)

   for n = 1, smoothing_passes do
	  smoothed = smoothed:smooth()
   end

   return smoothed
end

m = Map.generate(31337, 512, 16, 5)
file = io.open("map.xpm", "w")
file:write(m:xpm())