Monday, June 30, 2008

Random map generation

This week I've been working on random map generation for my Thief/Rogue hybrid. This is what new Roguelike developers generally start on, and they can easily waste years with it. It's a hard problem. I put it off on my project because I knew what a morass it could be, and because I didn't feel like I had a handle on what the gameplay would need from the landscape. Now that I have a pretty good idea of what the gameplay is, I've decided it's time to tackle landscape randomization.

By the way, here are some Roguelike development sites I keep an eye on:



What I'd like is something like the streets of Toledo (EspaƱa, not Ohio):



(Image by ctankcycles.)

I don't have any great images handy, but Google Maps does a pretty good job of showing what I'm after:



Of course this has to be rectangularized to some extent.

I tried out a Voronoi diagram on a grid. Very unsatisfactory:



There's a paper in this year's SIGGRAPH that has some ideas I might try.

Wednesday, June 25, 2008

Space Steering Revisited

I had to make a detour from my current project to finish up some Newtonian spaceflight steering stuff I worked on a year ago (detailed in parts one, two, and three).



You could think of it as the beginnings of an AI for playing the old game Space Wars, or its descendants the two-player Star Control combat modes.

The rocket is flying to a target position in the lower left; in the background I'm plotting a graph of the objective function it's trying to minimize in order to pick the correct direction to point its thruster. At the moment it's finding the minimum pretty well (its result is the yellow cross). There are situations where it doesn't do so hot, though. I'm doing an extremely simple, brute-force approach to searching for it, and I'm sure I can do much better. I just need to learn something about minimization of nonlinear functions, especially ones with hard-to-compute derivatives.

Monday, June 16, 2008

Review: Treasures of a Slaver's Kingdom

Treasures of a Slaver's Kingdom is a text adventure of sorts by S. John Ross. It's likely to offend the sensibilities of Real Interactive Fiction lovers, as it pares down input to a handful of commands. I love this because I hate “guess the verb” gameplay. Treasures also features simple stats-'n'-dice-based combat, which puts some people off. On the positive side, it's a giddy pulp pastiche of Conan, Star Wars, and more. Atomic dinosaur? Sure! Give him a light saber! The writing is frequently hilarious. The game is solidly designed: the environment is fairly small, the inventory is kept to a manageable size at all times, and you can't really get stuck.

I discovered the game through Emily Short's excellent (as always) review over at Play This Thing. I really can't add much to her review, so head over there to read it.

Treasures does a good job of making memorable non-player characters. You actually feel like you've got a relationship with them. I think the limited input vocabulary helps here as it keeps you from getting frustrated trying to interact with them.

The full game costs $13, which I think might be slightly much for the amount of gameplay. I got through the game in under eight hours, although I made fairly extensive use of the crypto-clues offered in the instruction manual, to the point of writing a Python script to decode them for me. However, I spent the entire time playing the game with a big grin plastered on my face and laughed out loud on several occasions.

There's a free demo that lets you play the first fifth or so of the game. Try it out and see if it agrees with you. You will also need a Z-machine interpreter to run the game; Gargoyle is a very nice-looking one.

Sunday, June 15, 2008

Panty Raid

Two weeks ago last Friday, over $10,000 worth of panties (about 650 pair) were stolen during business hours at my local Victoria's Secret. More info There is no surveillance footage of the incident and no suspects.

Monday, June 9, 2008

Pathfinding notes and code

No progress this week, other than writing down a list of features, both necessary and desirable, for finishing my Thief-like Rogue-like.

When I was working on the pathfinding code I did some Googling for pathfinding tutorials, example code, etc. What I found was not entirely satisfactory, so I am adding some notes of my own here. This is talking specifically about the A* Search algorithm.

The basic idea is to search for a minimum-cost path through a graph of states. In my game a state is a position in the world, and the graph edges are the legal moves from one position to its adjacent positions. There can be up to eight of these in my game: north, south, east, west, and diagonals. The cost is based primarily on distance, but I add additional penalties to discourage movement through windows, over tables, through bushes, and things like that. I originally based cost on the number of moves required, ran into an aesthetic problem. On a square grid, if diagonal moves take the same amount of time as horizontal moves (which they do, in my game), there is no difference between these two moves:



If an AI needs to walk in a straight horizontal or vertical line it looks very strange if they veer out of their way, so I made the movement cost approximate true distance. It doesn't need to be exact; just enough so that a northeast-then-southeast move is more expensive than an east-east move, and a southeast move is cheaper than an east-then-south or south-then-east move. I assigned a cost of 2 to horizontal and vertical movements and a cost of 3 to diagonal movements, which took care of the problem.

The gist of A* is that we examine states in the order of the estimated total cost of a path through them from the start to the goal. In my code the states are called nodes, since they are nodes in a graph being searched. During a search I maintain a set (using an STL set) of nodes that have been seen so far. Here's the data structure:

struct PATH_NODE
{
PATH_NODE() {}
PATH_NODE(POINT2 pos_):
pos(pos_),
prev(NULL),
cost_from_start(0),
est_cost_to_goal(0),
num_paths(1),
closed(false)
{}

bool operator < (const PATH_NODE & other) const
{
return pos < other.pos;
}

POINT2 pos;

// Previous state on path through this node:

PATH_NODE * prev;

// Minimum cost found so far to reach this node from the start:

int cost_from_start;

// Estimated cost to reach goal from this node:

int est_cost_to_goal;

// How many paths with the same cost_from_start have been found so far?

int num_paths;

// Has the best path to this node been found already?

bool closed;
};


The node has a less-than operator for ordering nodes; this allows me to store them easily in an STL set. It's just ordering them by position, which will be unique.

The prev pointers allow the path to be reconstructed: once the search reaches the goal we just follow these pointers back to the start. std::set's implementation keeps entries at the same place in memory for their entire lifetimes so it's safe to keep pointers to them, as I'm doing here. cost_from_start may be reduced over time; it's possible to find one path to a node and later find a better path to that node. est_cost_to_goal never changes, though; it's based solely on the node's position. It's stored here just to save time recomputing it. num_paths is used to be able to choose uniformly randomly from paths with equal cost. Finally, closed indicates when we've found the best path to the node, after which we do not need to do anything further with it.

The other data structure used during the search is a priority queue, which keeps track of nodes to be examined in order of the total estimated cost to reach the goal through each one. I use the STL priority_queue for this, with the following queue entry data structure:

struct PRIORITY_NODE
{
PRIORITY_NODE() {}
PRIORITY_NODE(PATH_NODE * node_, int est_total_cost_):
node(node_),
est_total_cost(est_total_cost_)
{}

bool operator < (const PRIORITY_NODE & p) const
{
// Lower cost values have higher priority in the queue.
return p.est_total_cost < est_total_cost;
}

int est_total_cost;
PATH_NODE * node;
};


Again, I'm storing a pointer to a PATH_NODE inside a std::set.

Here's the pathfinding function:
POINT2 move_toward(POINT2 pos_start, POINT2 pos_goal)
{
if (pos_start == pos_goal)
return POINT2(0, 0);

std::set<PATH_NODE> path_nodes;
std::priority_queue<PRIORITY_NODE> open;

typedef std::pair<std::set<PATH_NODE>::iterator, bool> INSERT_RESULT;

INSERT_RESULT insert_result = path_nodes.insert(PATH_NODE(pos_start));
PATH_NODE * start_node = &*insert_result.first;
start_node->est_cost_to_goal = cost_estimate(pos_start, pos_goal);

open.push(PRIORITY_NODE(start_node, start_node->est_cost_to_goal));

while (!open.empty())
{
PATH_NODE * node = open.top().node;
open.pop();

if (node->closed)
continue;
node->closed = true;

// Have we found a path?

if (node->pos == pos_goal)
{
while (node->prev != start_node)
node = node->prev;

POINT2 pos_new = node->pos;

if (GUARD::at(pos_new) || SHIP_CAPTAIN::at(pos_new))
return POINT2(0, 0);

return pos_new - pos_start;
}

// Generate successor states.

for (int i = 0; i < 8; ++i)
{
POINT2 pos_new = node->pos + dir[i];

int move_cost = guard_move_cost(node->pos, pos_new);
if (move_cost == infinite_cost)
continue;

move_cost += dir_cost[i];

int cost_from_start = node->cost_from_start + move_cost;

INSERT_RESULT insert_result = path_nodes.insert(PATH_NODE(pos_new));
PATH_NODE * node_next = &*insert_result.first;
if (insert_result.second)
{
// Node was just inserted

node_next->prev = node;
node_next->cost_from_start = cost_from_start;
node_next->est_cost_to_goal = cost_estimate(node_next->pos, pos_goal);

open.push(PRIORITY_NODE(node_next,
node_next->cost_from_start + node_next->est_cost_to_goal));
}
else if (!node_next->closed)
{
// Node already exists; do we need to adjust its path?

if (cost_from_start < node->cost_from_start)
{
// Better path to node_next found.

node_next->prev = node;
node_next->cost_from_start = cost_from_start;
node_next->num_paths = 1;

open.push(PRIORITY_NODE(node_next,
node_next->cost_from_start + node_next->est_cost_to_goal));
}
else if (cost_from_start == node->cost_from_start)
{
// Same-length path; randomly replace existing path with new one

++node_next->num_paths;
if (random(node_next->num_paths) == 0)
{
node_next->prev = node;
}
}
}
}
}

// No path to destination found.

return POINT2(0, 0);
}


If I find a better path to a node, I don't bother trying to adjust the priority on the existing priority queue entry for that node; I just push another entry into the queue with the improved priority. When the function eventually pops the older queue entry off it'll see that the node is already closed and just ignore it.

One thing that wasn't clear to me at first when I was learning the algorithm: the first time you pop off a node from the priority queue, you have found the best path to it. This is why we're able to immediately mark the node as closed in the code.

Eventually I may refactor this code to separate enumeration of successor states from the search. At the moment you can see a loop over the eight possible neighbor states.

My actual pathfinding function has a coda at the end. Instead of giving up when no path can be found, it searches through the node set for the closest node to the goal. In the case where multiple nodes are found with the same estimated cost to the goal, the one that is cheapest to reach from the start is chosen. Then I return the first step along that path.

As you can see, I'm currently regenerating paths from scratch every turn. So far it hasn't been a problem but if it does become a noticeable CPU drain it would be possible to cache paths in some fashion.

When a path is found there is some ugly code in there checking to see if a guard or ship captain is at the spot where we want to move. I'm treating them as passable during the search, and just not moving if one happens to be in the way.

Monday, June 2, 2008

Relative Priority Queue

Games that choose lines of speech “randomly” from a set usually don't want true randomness. They want to be sure that the same line isn't chosen twice in a row, or perhaps for an even longer period.

For my game I opted for the simplest solution first. I just keep an iterator into each line set and run through the lines in order, wrapping back to the start after I've used all of them. I doubt anyone will notice that the lines are used in the same order, since I have lots of different line sets that come into play during gameplay.

I couldn't help thinking about more complicated solutions to the problem, though. What if you have some lines that are so memorable you don't want them to reappear for a long time after they've been used? Other, simpler lines could be reused more frequently without sounding dumb.

One way to do this would be to assign to each line a “timeout”; a duration before it can be used again. The line with the lowest timeout is the next to be used. After using it you'd reset its timeout value and decrement all the rest.

This is sort of like a regular priority queue, except that you really don't want to have to decrement priorities on all the entries every time you extract something.

I was thinking that you could implement a relative priority queue as a binary heap where each element stores its priority relative to its parent rather than a global priority value. For instance, here's a standard priority queue containing absolute priority values:



The relative representation of the same priorities would be:



The usual binary-heap-based queue algorithms should work with only small modifications to take into account the relative nature of the priority values. Here's extraction of the lowest-value element. The end element is swapped into the first position:



Then additional swaps are made to ensure that parent nodes have lower values than any of their children:



Relative priority queues could also be useful if you've got timer events in a game that are set to go off at times in the future. Some (shipped!) games I've worked on used absolute times for everything; they run into problems if you let them run continuously for too long. Dealing in relative times lets your game run in a kiosk at Best Buy for days on end.