### 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
}
```

## Comments

## Post a Comment