Monday, May 26, 2008
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.
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.
Monday, May 19, 2008
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.
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.
Monday, May 12, 2008
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.
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.
Monday, May 5, 2008
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.
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.
Subscribe to:
Posts (Atom)