Speech bubbles 3

Another update on my turn-based, text-based rendition of stealth gameplay.

I decided it was finally time to improve the layout of speech bubbles. Here's how things looked:



The text was placed centered above the speaker with no regard to whether it went off-screen, covered other text, or covered one of the enemy guards.

The first thing I did was to constrain the speech to be on-screen. Then I generated all of the possible positions adjacent to the speaker and scored each one based on what it covered. The score penalizes speech bubbles a little bit for covering portions of the map that are either currently visible or previously seen, and it penalizes the bubbles a lot for covering the player or non-player characters. Picking the best-scoring position for each speech bubble produced good results except that the scores didn't take into account overlaps between speech bubbles. The next step was to implement some optimization. Overlaps are penalized and it looks for permutations to the current state that will reduce the overall score. The results look like this:



(I'm also experimenting with different speech bubble styles. Ultimately I will need to add stems back in to indicate where the speech is coming from.)

The optimization turned out to be really slow. It's also kind of fiddly because you have to come up with a numeric score for each kind of thing you're trying to avoid. I'm trying to think of alternatives. One idea is to treat it as a rigid-body physics problem. The speech bubbles would be constrained to be next to their sources, and would push each other away. I don't know if this would give good results or not, but since it's something I'm familiar with I will probably try it out.

Pathfinding improvements

Another weekly update for my riff on Thief in the style of Rogue.

I've been mulling over a big change. Guards need to have local knowledge of the current state of the world but use their memory of the default state of the world elsewhere. At the moment they use global knowledge of the current world state. If they are traveling somewhere and you open up a shortcut to their destination, they will veer toward it even if you opened it up out of their sight. For instance:



In this picture the guards are attempting to get to the open door next to the ghost (ignore him; he doesn't do anything yet). The window just southeast of the thief is locked from the inside so they have to take a very long route. If the thief opens the window, however, they will currently instantly change their path to this:



They shouldn't do this because they have no way of knowing that the window was opened.

I think what I will do is prepare a “field of view” for each guard on each turn. This would be an overlay created by using a version of the field of view algorithm that the thief and lamps use for projecting sight and light, respectively. When checking the world state, the guard would check the overlay first, and, if it didn't see the square, go to the world map and get the default state for that square.

This is a fairly big change, though. In the mean time I've tightened up the existing path-finding code and made a couple of improvements.

The main optimization was to reduce the number of searches the code does. The previous code was pointer-free, so there were lots of lookups based on position. Adding a closed flag to the path nodes, rather than having a separate set, was the first step. Using pointers between nodes to represent the path, and using pointers in priority-queue entries for referring to the nodes, was the next step. Finally, I stored the cost estimate for reaching the goal on each node rather than recomputing it when needed.

The enhancements I made are subtle. While messing around with secret doors I noticed that guards would sometimes take the long way to get to the secret door. This happened when I would open the door, they would see that it was open, and then I'd close it again. (Currently they don't care that it has been closed; they travel to it regardless.) The problem was because a closed secret door is currently impassable to them. (This is going to change; I need to overhaul guard movement costs to take into account the direction through doors and whether the guard has a key to that door.) When a guard tries to move to an impassable location the normal pathfinding fails. In that case he picks the closest reachable point to the goal and moves there instead. The problem came when there were multiple reachable points the same distance from the goal. The guard was just picking the first one. Now, ties are broken by considering the cost to reach each point, so the guard won't do anything crazy.

The other enhancement is something I've been meaning to add for a long time but hadn't gotten around to. Guards choose uniformly randomly from all paths that have the same cost. This breaks up their movement so they don't always take the exact same route. Each time an additional alternate path is found there is a (diminishing) chance that the algorithm will switch to that path instead. Each node keeps track of the number of paths found to it so far with the same cost. The chance of picking a new path is 1/n so that every path is equally likely even though we roll the dice every time we add a path.

Toilet seat toggling

Another update about ThiefRL, my attempt to stuff the soul of Thief into the body of Rogue.

I'm continuing to tune guard behavior and finish up their ability to sense environmental changes wrought by the player. In general, giving the player more ways to alter or control the environment is a good thing, and guard senses is unexpectedly one of those ways. You leave a door open; a guard comes along and shuts it, though not without complaining. Bam! You've got a relationship.

This week I also added a ship captain who functions as both a sort of “trainer guard” and as a way to end the level. The thief has booked passage on the captain's ship, which will set sail at dawn. The captain patrols the deck and his cabin, and when he first sees the thief he reacts as any guard would. However, when he gets close enough to recognize his passenger he returns to patrol. After not seeing the thief for a while he will revert to normal, suspicious guard behavior. My hope is that this will give the player an opportunity to study guard senses and behavior up close in a benign environment.

Once all the loot in the city has been collected, talking to the ship captain will end the game (eventually, the level). I've got a simple end-game screen now so it's actually possible to win the game! I must say, this makes it feel much more game-like.

Adding a set of things for each guard to look after in the environment has made the game much more challenging, (hopefully) in a good way. The environment now tends to reset so you can't just go around turning off all the lights and have the run of the place.

Something Amiss

Still working on my thief-like/rogue-like hybrid game (ThiefRL for short).

I've started working on having guards detect open doors and windows, doused torches, and the like and fix them. It will take work to get it all working smoothly, but it looks like it will add a lot to the game, both in difficulty and in interest.

More later; have houseguests in addition to the usual bedlam.

Refinements to guard behavior

A little more work on my thief-like/rogue-like hybrid.

The next big feature I need to put in is for guards to recognize when things in the environment are amiss: doors ajar that should be closed, lights out that should be lit, and of course missing treasure! This should beef up the difficulty of the game substantially.

I haven't had the time or energy to do that yet; hopefully this week. In the last couple of weeks I've done some small refinements to existing things.

Guards used to get completely discombobulated when a group of them would try to enter a narrow alleyway in pursuit of the thief. This was because they considered other guards to be permanent, static obstacles. The first guard would enter the alley, whereupon the rest would be forced to find paths going clear around the buildings. I fixed this by making guards into a slight penalty for movement into the occupied square. This ensures that if a guard can get around another by simply stepping around him, he will. Otherwise, he'll attempt to move into the other guard. If the other guard hasn't gotten out of the way he will stand still. My guard states already have timeouts so if this happens for two or three turns in a row the guard will give up.

Guards' attacks were a side effect of trying to move into the player, which was a problem when the player was on a square that was inaccessible to the guard. Formerly I'd prohibited guards from moving onto water or tables. I've kept the water restriction, but guards can now attack the player if he's adjacent and they can see him. In order for this to work with tables and bushes I had to add a special case to visibility: if a guard is adjacent to the player, and looking, they will see him even if he's hidden inside a bush or under a table.

Tables are now accessible to guards, but instead of a binary pass/block for each terrain type, I've now got integer-valued movement costs. This allows for some refinements to guard movement. They will avoid moving over chairs or tables, and they really try to avoid moving through bushes or windows.

Guards alerting other guards is slightly refined as well. Formerly, when a guard would sound the alarm, any guards that had not yet been updated that turn would hear the shout on that turn, while the guards that came before would not hear it until the next turn. I fixed this by running the alert status through a holding variable, so that all guards will hear alerts on the turn after they are made. This makes the speech pattern more sensible too.

I still need to add specific guard states for alerts, so their speech will be more specific. I'd like for a guard to say something about where the player is, along the lines of “He just ran behind that pillar!” This should make the player feel much more like the guards are paying attention to what he's doing. Also, I'll change the goal spot for alerted guards from the position of the alerting guard to the actual reported position of the player, which should toughen things up some.

Finally, I did some initial experiments with a ghost. The Thief games have always been supernatural tales at their core; it's part of how they sustain a feeling of dread, since you don't know what rules supernatural beings play by.

My ghost inspiration comes from Barry Hughart's book Bridge of Birds. In the book there's a bit of a trick to seeing ghosts, which the heroes learn in order to solve the central mystery of the story. I've been trying to think of interesting tricks for seeing ghosts. One is that you can only see them out of the corner of your eye. As such, I implemented a ghost which is only visible when you move away from it. It's also invisible in direct light, and invisible when it's very close to you. This ensures that, when a player first encounters a ghost, their natural inclinations to move toward it or wait to see what it does will render it invisible.

It's mildly interesting but I'll need to figure out some way to actually interact with the ghosts for them to really work. Some of the Bridge of Birds ghosts delivered a cryptic speech after they were spotted, whereupon they would vanish. Another ghost was stuck endlessly reenacting a doomed rendezvous with her lover; the protagonists had to engage her in order to break her out of it.

In Thief the various undead creatures were actually fairly straightforward modifications of the standard guards. A big part of their scare factor came from the fantastic sound design.

Look Around and Listen (The Problem With State Machines)

At the last Game Developer Conference I attended a talk about enemy design in Naughty Dog's latest game Uncharted. Having not played the game, one statement really struck me. An adversary's average lifetime after being activated was measured in seconds. Most of their animation budget was devoted to deaths.

Good game design (as with many things) is all about capitalizing on your strengths and hiding your weaknesses.

This week I did a bit more work on my thief-like/rogue-like hybrid. The thief, not being homicidally inclined, is incapable of killing the guards. The longer they live (as with anybody) the more likely they are to do something stupid.

At first, guards could only see, and all they cared about was seeing the thief. They had a simple state machine, like this:



When a guard spotted the thief he would leave his patrol state and enter a brief “look” state. This gives the player one turn in which to get back into hiding. If they don't, the guard gives chase. (This may turn out to make the game too easy; if so I may need to do something additional, like having a guard go instantly to chase if they are in a state of alert.) When the guard lost sight of the thief he would enter a “search” state which consisted simply of moving to the last place he saw the thief. After a timeout, the guard would return to his patrol.

To add the sense of hearing, the first thing I did was to simply include it in the “Can I see the thief?” calculations. The obvious problem was that a guard would hear the player and say “What's that I see?” or something similar.

One solution would be to implement some sort of memory regarding whether the guard has seen and/or heard the thief in the current “interaction”. I thought it might be interesting to make the guard behave more aggressively based on a sighting than on hearing, so I opted to just add more states to my state machine. It wound up looking like this:



Investigate is the state in which a guard moves to the point where he last heard the thief. Search is moving to the point where he last saw the thief. Distinguishing between these allows the guard to say different things when he gives up and returns to patrol (“Where'd he go?” versus “The noises have stopped,” for instance). Chase is like search except that the thief is in sight. I can't remember if I really need it, but I think I'm using it to stop updating the last-seen position one turn after the thief goes out of sight (to simulate being able to see which direction he moved to get out of sight).

This is obviously getting kind of crazy, though. The next thing I'm working on is for guards to be able to alert other nearby guards. Currently I'm putting alerted guards into the search state and setting the last-seen position to the position of the guard who called out. This causes the alerted guard to move toward the guy making noise. If he doesn't spot the thief in the process, he'll eventually give up and return to patrol. Of course, inherent in the search state is the idea that he saw the thief at some point, so he might say something to that effect when he gives up, which makes him look odd.

State machines are nice when they have a handful of states; they help you to think about all the transitions and to encapsulate all state into single nodes. I find that they don't scale very well as the complexity and number of states grows, though. I don't feel like I've got a great solution to this yet.

Code Puttering

“Blah,” as Toad might say.

I started puttering yesterday in my ThiefRL code to get back up to speed on it. I'm trying to decide how best to organize sound propagation. There's a “push” model, where the sound emitter broadcasts to nearby listeners, and a “pull” model where listeners search for nearby sound emitters. I think the broadcast model might be more efficient. Either way I'd like to hide that detail as much as possible from the AI code.

In general the programming languages I'm familiar with don't do a good job of supporting abstractions of this sort. Another sort of abstraction that isn't well-supported is deciding how to link related data: whether to embed it together in the same structure, or to use a map (dictionary) to connect them more loosely.