Agent based level generation

One of the aspects I have enjoyed immensively in pyherc is level generation. It’s no surprise then that I wanted to try a slightly different approach that I’m describing here. It’s not fully finished, but should be sufficiently ready for a blog posting

The system I’m tinkering with has a lot more random elements than the previous one (as described in here). The idea is to write bunch of different kinds of agents that modify level according to some simple algorithms or rules, let them loose and see what happens. Although, there has to be certain amount of order, otherwise the end result will be unplayable mess. One type of agent might be interested in carving tunnels from one place to another, while another digs out larger structures, thus forming cave like structures. Add a little bit of logic that directs these agents and you get a system that builds network of caves linked with tunnels.

The basic element of the system is agent. It’s a class that describes rule how the level is being modified. Interface of an agent is small, only two methods in addition of the initializer:

(defclass TunnelerAgent []
  (defn --init-- [self floor-tile section start destination stop-at-room]

  (defn run [self]

  (defn finished? [self]

When system instructs agent to modify the level, run is called. This causes one change to be made and then execution returns to the caller. Idea is that this way multiple agents can work on the level at the same time, hopefully creating emergent results from their interactions. finished? method is used to check if the agent has finished changes to the level and has nothing more to do. In case of TunnelerAgent, run directs agent from their current position towards the destination, while carving tunnel. finished? will check if agent has arrived to their destination or encountered room along the way.

There’s a little helper function for creating tunnelers:

(defn new-tunneler-agent [floor-tile section start destination &optional [stop-at-room False]]
  "create new tunneler agent"
  (TunnelerAgent floor-tile section start destination stop-at-room))

I created this as I was anticipating some extra logic being needed in the initialization phase, but turns out there weren’t need for it. In any case, it was left in the system.

Now that we have a bunch of agents ready to dig into a level, we need a way to get them started:

(defn run-step [agents]
  "run agents for one step and return active agents"
  (ap-each agents (.run it))
  (list-comp agent [agent agents] (not (.finished? agent))))

run-step calls run method of each agent and then returns list containing those agents who aren’t done modifying the level. And we can also instruct agents to run until all of them are done:

(defn run-until-done [agents]
  "run agents until all of them are finished"
  (setv active-ones (list-comp agent [agent agents]
                               (not (.finished? agent))))
  (while active-ones
    (setv active-ones (run-step active-ones))))

Running one agent for every tunnel and cave leads to boring results. Tunnels are thin, caves are small and there isn’t much interesting interactions going on. For that reason, I defined way to create a group of agents easily. For example, to create slightly larger cave, one can do following:

(defn cave-in-middle [floor-tile]
  "agents to create irregular cave in middle"
  (fn [section &optional trap-generator]
    (let [width (section-width section)
          height (section-height section)
          center (, (// width 2) (// height 2))
          size (, (// width 2) (// height 2))]
      (map (fn [x] (new-cave-agent floor-tile section center size))
           (range 20))))

This, when given a section of map, will check the bounds and create 20 cave digging agents that will start from the middle of it. As they proceed to different directions, resulting cave looks more interesting compared to cave carved out by a single agent. Here the code is starting to interact with the old system that deals with sections and rooms.

Speaking of the old system. Since I don’t have fully revamped agent based dungeon generator ready, I had to build an interface that allows agent system and old room based system to coexist. The trick was to wrap the agent based system into a function, that looks like a room generator of the old system. The following code does this:

(defn cavern [floor-tile corridor-tile]
  (new-room-generator (agent-group (cave-in-middle floor-tile)
                                   (tunnels-to-cave corridor-tile))))
(defn agent-group [&rest agents]
  "create group for agents"
  (fn [section &optional trap-generator]
    (let [primed (flatten (map (fn [x] (x section trap-generator))
      (run-until-done primed))))

This allows us to mix old and new system pretty seamlessly. There’s two types of agents in work here. Some are in charge of digging out the cave in the middle of the given section. Others are busy digging tunnels that connect cave to other sections surrounding it. One group starts from the edge of the section, working towards the cave, while another starts from the cave, working towards the edge of the section. I found after some experimentation that this gives nice looking tunnels.

Every agent based room generator is supposed to stay within bounds of their respective section, but nothing really enforces this. I have been pondering, if I want to enforce the limits, or just trust that the programmer knows what they’re doing and give them free access to whole level.

Full level

Resulting caves are fairly nice looking already. Adding more different kinds of agents should create more varied results. Also it’s worth remembering that not all agents have to run at the same time. I’m planning a system where few types of agents first tunnel out the general outline of the level and after that different agents start adding items, monsters and other details there. Ultimate goal is to revamp whole generation system and let agents first decide location of stairs and other important features and then carve the level around them in intelligent manner.

Whole agent system described in the article can be found here.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s