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
I was working on society generation, where the system would generate whole socities (villages to be specific), inhabited with people. These people could be part of various factions or secret socities and have their own agendas. Moreover, some of them might have powerful artifacts or other special items, that would have history attached to them.
I have been tinkering with building societies for my game. Basic idea behind the whole thing is that I have two tier system: one level generates blueprints and another level turns those blueprints to actual objects in game world. For scrolls (see first and second post) it already works.
I was travelling and wasn’t able to hack code as much as I would liked to (and on top of that, I wanted to play some computer games too). But I did manage to push next feature forward just a little bit and write some BDD specifications for it. It’s a bit odd to write BDD specs for a single person project, but I view doing that as a good training and a nice favour to my future self.
So, Water Guardians (among other creatures) are powerful beings that can grab and pull unsuspecting adventurers if they stray too close to water. They aren’t the only creature that can pull others, but they’re exceptionally strong at that and can pull being equal to their own size (and since they’re large creatures, there are very few things that can resist that).
In previous post I indulged myself with some wishful coding and outlined some ideas how to procedurally generate scrolls that have name and description and that can be regenerated again and again based on id number. For a change, I actually went and implemented system like that and will detail some points about that in this post.
Earlier I blogged about procedural lore generation. That in itself is very large and complex topic and I wouldn’t want to tackle that in one go. One major part of the system would be generating all kinds of artefacts, of which some could even apppear in the game. This is quite large part too and will require significant changes (I have very few item types implemented currently).
But, I can already get started on fleshing out my ideas and implement a tiny, fairly insignificant portion of the system and see how well it will work and what kind of new ideas I’ll unearth. For this I chose cosmetic (at least for now) scrolls that player can find laying around everywhere in the game. I won’t be touching that much how the scroll generating will actually be implemented as a part of item system. Instead, I’ll assume that there’s some sensible way of system to call the code (although, I do have some hazy ideas already) and trigger creation of a scroll.
Building an AI (for a game or for some other purpose) which can look ahead, subdivide its goal to smaller goals and plan actions required for completing each of them doesn’t sound too hard. Just use some mechanism to break big goal into smaller steps, maybe starting from the very last on and then working backwards towards current situation and stuff those goals into a stack. AI can then take the topmost item from the stack and start working towards solving it. If it’s not achievable, just figure out what’s needed to be done first, return original item on top of the stack and start working on the new one. If situation changes drastically, say a huge fire breathing monster appears, return the current item on top of the stack and figure out what needs to be done in the short term in order to be able to return back to that task.
I have been pondering over some ideas about traps, items and how to represent what kind of effects they have in-world. I might be over thinking this a bit and going for too general and flexible solution, when simpler solution would work just fine. Currently this isn’t that urgent yet, as there are only few monsters and two types of traps (pits and caltrops). Monsters are too stupid to avoid either one. For caltrops it sort of makes sense, but they really should be able to spot huge pits and go around.
Now that I have fully functional finite-state machine system, I can get started writing AI routines for the game, right? Apparently not yet. When inspecting the code, I realized that the finite-state machine system lacked a very important feature: ability to have values entered with –init– method. So that needed to be taken care of before starting to work with the AI.
Current implementation of rat AI is as follows:
(defclass RatAI  [[__doc__ "AI routine for rats"] [character None] [mode ["transit" None]] [--init-- (fn [self character] "default constructor" (.--init-- (super RatAI self)) (setv self.character character) None)] [act (fn [self model action-factory rng] "check the situation and act accordingly" (rat-act self model action-factory))]])
–init– is used to give AI reference to the character it’s in charge of operating. act is called every time it’s characters turn to act. I could have changed the system to pass character reference as a parameter of act, but I wanted to keep interface unchanged for now, so chose to add –init– method for finite-state machine system instead.
–init– form of defstatemachine mirrors closely what –init– does for a regular class (in fact, it’s injected to be part of –init– method of final class). It takes a list of parameters and body of code. With this it was simple to define correct parameter list and rest of the game was happily ignorant that it was interacting with finite-state machine instead of plain old class (although, that finite-state machine is still a plain old class in the end of course).
Next design challenge I encountered was related with splitting common functionality into smaller pieces. I spent couple evening prototyping this with state monad from Hymn, but couldn’t come up with a system that I liked. With Hymn passing the state back and forth would have been taken care of automatically and behind the scenes, which was one of the attractive reasons for trying to use it. In the end (or should I say, for now?), I abandoned the idea and went with regular functions. This of course meant that I had to pass the state around manually and modifying it took a bit more coding. The end goal is to have some sort of library for AI routines that can be combined easily for new creatures. Getting a simple rat AI done was lots more work than what I anticipated, but I’m hopeful that next ones will be easier.
Final wart needing solving was the need for deactivation code. When a rat notices an enemy, it switches to a different state and a little exclamation mark is shown in UI to signal player that the rat is now in alert state. When rat loses the sight of the enemy, old AI used to raise a question mark to signal that the rat wasn’t sure about location of its target (they have lousy memory). I couldn’t raise the question mark in finding home state, since then it would be shown every time the rat decides to head home. Instead of that, there was need for codeblock that gets execute when state deactivates, but before next state is activated. Adding the state was almost identical on how on-activated is handled.
Now that I had all the major parts of the code ready, I could assemble whole thing and ended up with the following code:
(defstatemachine RatAI [model action-factory rng] "AI routine for rats" (--init-- [character] (state character character)) "find a place to call a home" (finding-home initial-state (on-activate (when (not (home-location character)) (select-home character wallside?))) (active (travel-home (a-star (whole-level)) character)) (transitions [(arrived-destination? character) patrolling] [(detected-enemies character) fighting])) "patrol alongside the walls" (patrolling (on-activate (when (not (home-area character)) (map-home-area character (fill-along-walls (. character level)))) (clear-current-destination character)) (active (one-of (patrol-home-area (a-star (along-walls)) character) (wait character))) (transitions [(detected-enemies character) fighting])) "fight enemy" (fighting (on-activate (clear-current-destination character) (select-current-enemy character closest-enemy) (show-alert-icon character (current-enemy character))) (active (if (in-area area-4-around (. character location) (. (current-enemy character) location)) (melee character (current-enemy character)) (close-in (a-star (whole-level)) character (. (current-enemy character) location)))) (on-deactivate (show-confusion-icon character)) (transitions [(not (detected-enemies character)) finding-home])))
It’s pretty clear I think and should be easier to fine tune and adjust in the future. It certainly is much more reusable than the previous patrol AI code.
Here and there I used functions as parameters facilitate fine tuning algorithms. For example, when the rat is finding its way to home area, whole level is considered as valid ground for traveling. A* algorithm will try and find the shortest possible route. However, as soon as the rat arrives to home area, it switches to different mode and completely ignores anything but edges of rooms (and areas in front of doorframes, so it can pass those too). It’s still the same A* routine, but slightly differently configured.
Another example is shown below. It’s a function that maps character’s home area and assigns it to AI data:
(defn map-home-area [character neighbours] "build map of home area for character" (let [[state (ai-state character)] [to-check [(home-location character)]] [result ]] (while to-check (let [[it (.pop to-check)]] (when (not (in it result)) (.append result it) (.extend to-check (neighbours it))))) (assoc state :home-area result)))
It basically does a flood fill from home location of character. Function that provides coordinates for neighbouring cells is provided from outside and its implementation or internal behaviour isn’t any concern of this function. As a consequence, this function (couple with the neighbours function) can be used to flood fill whole level, edges of room, center of room or any other continuous area. It could even be completely random random area that gets filled.
Most of the AI functions manipulate shared state in a way or another. I’m basing this on a convention, rather than contract. Any function can read, write and otherwise manipulate the state. This allows them to be combined in a way that I didn’t anticipate at the time of writing them. Problem of course is that if I’m not careful, unexpected interactions between those functions might arise and manifest as bugs.
This was also pretty tricky code to test. While coding, I kept thinkig that I should have some sort of automated system for testing the code, but it would be pain to write and maintain. I would have to set up whole level with creatures, items and worst of all, specific internal state of the AI. These tests would break all the time if even the slightest change was made in the internal representation of AI. In the end I decided that it wouldn’t be worth the gain to go through all that pain and just resolved testing the AI by playing the game. It’s slow process that will miss errors, but it’s still better than nothing (just not by that much).