Algorithm to create realistic forest

I am doing some funny spare coding these days (while getting used to emacs) - and in the picture above you can see one of my projects. I call this "Rangband" - a simple clone of Zangband, actually. But it seems that Zangband (the best crawl rpg I saw) and ToME (the crawl rpg with the best story setting) are out of active development, and also they are buggy as hell.

So I set off to write a small clone, just for my fun.

As for now, there is only auto-generated forest, moving character (@), and line-of-sight and fog-of-war calculations.

First thought for generating forest is just to spray objects all over the map randomly, but that generates true chaos. And I wanted some clearings and thickenings in my forest, so I decided to trim that chaos a bit.

It turns out that if we run this chaotic forest through just one iteration of modified game of life algorithm, we will get exactly what we want (or I want :) You just need to remove all trees that have less than three neighbors (non-iteratively!)

  def getRandomWalls = {
    val raw = Seq.fill((300*80*0.5).toInt)((rand.nextInt(300),rand.nextInt(80))).toList.distinct
    val rawS = raw.toSet
    raw.filter { case (x,y) => 
      (for {xi <- x - 1 to x + 1; yi <- y - 1 to y + 1} yield {
        rawS.contains((xi,yi)) // I know, not very efficient, but it still works trough 300x150 field in a snap
      }).filter(a => a).size > 3
    }.map{case (x,y) => (Object(('%', TC.fg.V(Seq("22","28","34")(rand.nextInt(2))), // getting random color
                                   TC.bg.Black),"Tree",blocking = true, fixed = true),x,y)}
  }

Also, I implemented a ray-tracing algorithm, to do realistic line-of-sight computation. The basic idea is to emit ~ 5000 rays from the center point and extend them till you get too far or run into an obstacle.

Here's the code, implemented in almost functional way (there are only two vars - the obstacles and visibility maps, for efficiency):

  class CircularMap[T : ClassManifest](range:Int,default:T) {
    val data = Array.fill(range * 2 + 1, range * 2 + 1)(default)
    def apply(x:Int,y:Int):T = {
      if (x >= -range && x <= range&& y >= -range && y <= range) {
        data(x + range)(y + range)
      } else default
    }
    def apply(p:(Int,Int)):T = apply(p._1,p._2)
    def update(x:Int,y:Int,v:T) {
      if (x >= -range && x <= range && y >= -range && y <= range) {
 data(x + range)(y + range) = v
      }
    }
    def update(p:(Int,Int),v:T):Unit = update(p._1,p._2,v)
  }

  def calc(pos:(Int,Int), sightRange:Int, obstacles:Traversable[(Int,Int)]):Set[(Int,Int)] = {
    // filter the obstacles and populate the obstacle map with them
    val obstacleMap = new CircularMap(sightRange, default = false)
    obstacles.filter(_.distance(pos) <= sightRange).map { case (ox,oy) => (ox - pos._1, oy - pos._2)}
    .foreach { o => obstacleMap(o._1,o._2) = true}
    // create the visibility map (default state is non-visible)
    val visMap = new CircularMap(sightRange, default = false)
    // create ~ 5500 rays (so that a wall tile at distance 20 would still be visible)
    (0d to math.Pi * 2 by (math.Pi * 2 / 5500))
    .foreach { 
      ray =>
      // for each ray, create a stream of intersections (horizontal and vertical, separately) with grid
      val yh = if (ray <= math.Pi) 0.5 else -0.5
      val xh = yh / math.tan(ray)
      val hi = Stream.from(0).map(2 *).map(1 +).flatMap { i =>
        val xi = xh * i
        val yi = yh * i
        List( (math.floor(xi + 0.5) toInt, math.round(yi - 0.5).toInt),
              (math.floor(xi + 0.5) toInt, math.round(yi + 0.5).toInt))
      }
      val xv = if (ray <= math.Pi / 2 || ray >= math.Pi * 3 / 2) 0.5 else -0.5
      val yv = xv * math.tan(ray)
      val vi = Stream.from(0).map(2 *).map(1 +).flatMap { i =>
 val xi = xv * i
        val yi = yv * i
        List( (math.round(xi - 0.5).toInt, math.floor(yi + 0.5) toInt), 
              (math.round(xi + 0.5).toInt, math.floor(yi + 0.5) toInt) )
      }
      // get tiles
      def hv(h:Stream[(Int,Int)],v:Stream[(Int,Int)]):Stream[(Int,Int)] = 
        (h,v) match { case (h @ h1 #:: ht, v @ v1 #:: vt) => 
                        if (h1.distance > v1.distance) v1 #:: hv(h,vt) else h1 #:: hv(ht,v)}
      // get tiles with that intersections and test until obstacle is found
      hv(hi,vi).span(p => p.distance < sightRange && !(obstacleMap(p)))
        .morph(t => t._1 :+ t._2.head) // morph is just my version of scalaz |>
        .foreach(visMap(_) = true) 
    }
    // need diagonal sighting also
    Seq(1,-1).morph(s => for (a1 <- s; b1 <- s) yield (a1,b1))
    .foreach{s => Stream.from(1).map(i => (s._1 * i, s._2 * i))
    .span(p => p.distance < sightRange && !(obstacleMap(p)))
    .morph(t => t._1 :+ t._2.head).foreach(visMap(_) = true)}
    // transform and return resulting map
    visMap.data.map(_.toList.zipWithIndex).toList.zipWithIndex
    .flatMap { case (list,xi) => list.filter(_._1).map(y =>(xi,y._2))}
    .map{case (x,y) => (x + pos._1 - sightRange, y + pos._2 - sightRange)}.toSet
  }