Ambushes

[kuniqs]

Once upon a time, a roguelike developer couldn't sleep half the night, so he started wandering without legs. He visited lands of png files, image manipulation and gameplay ideas, combined them and figured out a method for implementing ambushes in roguelikes.
   In conventional games, ambushes can be made by level designer who puts appropiate zones on map. We can't do this because roguelikes generate their maps on the fly. Wiring map generator to fit ambushable areas here and there will make the code non-portable to other generators plus, such things have a tendency to look unnatural - they won't have minor artefacts and other imperfections humans are accustomed to.



Let's imagine our problem. (# - wall    . - floor    o - vicious orcs):

Code: [Select]


################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
#####################.##..######################################################
####################.......oo##############.....................................
####################.........##############.....................................
................................................................................
................................................................................
................................########....................####..######........
####################.......oo#############.....#################################
######################.....#####################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################
################################################################################


Looks like a sick colon, but let's assume it's a mountain pass
Band of orcs climbs in the mountains and figures out it'll be a good idea to wait for food rather than search for it.

Human would have no problem figuring out where to wait for enemy. Not a computer, who doesn't tolerate imperfections and can't figure out if something is 'flawed, but good enough'. Neural nets are a bit too large cannon for the task - they're extremely slow for a game and we don't need them to learn anything.
In image manipulation they use a technique called filters explained below.






An image is, as most programmers know, just an 2D array of RGB values. If we want to make the image 'sharper' or 'brighter' or whatever, we do the following:

1) for every pixel in the image:
   2) calculate the filter value for that pixel
   3) pixel's new value = filter value
4) set all pixel's values to pixel new values

filter is a (usually) 3x3 array of 'weights':

Code: [Select]

               y
               0       1       2

x      0       weight0 weight2 weight2
       1       weight3 weight4 weight5
       2       weight6 weight7 weight8

for 'sharpness' filter that's roughtly:

 1 1 1
 1 5 1
 1 1 1

the '5' weight is for the current pixel, adjacent ones are weights for pixel's neighbours. We calculate filter value as a weighted average:

Code: [Select]

int filterValue(int filter[filterY][], int imageRed[imageY][], int pixelX, int pixelY)
{
int sum = 0;
for (int x = 0 ; x < 3 ; x++)
for (int y = 0 ; y < 3 ; y++)
sum += filter[y][x]*imageRed[pixelY-1 + y][pixelX-1 + x];

return  sum / {sum of filter weights};
}


My ambush detection method uses almost the same technique to check how much a given part of the map is similar to a given filter/pattern.
It looks like this:

Code: [Select]


   filtX
 ________
|        |
           _
.XX######   |
....#####   |
.........   |
.........   | filtY
....#####   |
.XX######  _|

Left side of a mountain pass. X are passable cells that are defined as 'standing by' positions for monsters.
The filter is defined as a two-dimensional array of chars. What we do is comparing a part of the main map with every cell of the filter, then saying "yes" when at least {percentage} of cells are equal, saying "no" otherwise.

Code: [Select]

// returns 1 if passes, 0 if not
int Passes_filter? (Map_cell *Map[], int mapX, int mapY,   char *Filter[], int filtX, int filtY,   int whereX, int whereY, float percentage)
{
int sum = 0, x, y;
for (x = whereX ; x < whereX+filtX ; x++)
for (y = whereY ; y < whereY+filtY ; y++)
if (y < mapY && x < mapX)
if (Map[y][x]._character == Filter[y-whereY][x-whereX])
sum++;

return (sum > (int)(filtX*filtY * percentage));
}


This method passes the exam when we have immutable maps -> we just check every map cell freshly after generation and mark 'yes areas' for use by monster AI, being careful to not intersect already defined 'yes area'.
When we want to have the player destroy walls etc. we need to check a random coordinate every second or something, anything that won't bog down the game too much. When we find a good terrain, we mark it for monster use. When a dungeon feature has been modified and it intersects one or more of the ambush areas, we check them again and if they don't pass, remove them. That needs some game-specific tweaking, since continuous modifications to one specific zone can trigger the same number of ambush area checks, and that's terrible! One way to guarantee only one possible correctness check is to store all mods in some kind of data structure, mark ambush areas they intersect and run tests after we checked every modified cell.


There still are bugs - if we have a filter | map fragment:

Code: [Select]

..####### .########
..X###### ...######
...###### ......###
......... #........
...###### .#.######
..X###### ...######
..####### ..#######

Then we are happy. But when map fragment looks like:

Code: [Select]

..#######
...######
...######
.....#...
...######
...######
..#######


then it will pass and be marked as useful for ambush. One way to fix it is to define filter as:

Code: [Select]

..#######
..X######
...######
555555555
...######
..X######
..#######
where numbered passable cells indicate 'weights' (other cells have weight 1). In layman's words, a map fragment with some of the '5' cells obstructed will be much less probable to pass the test. This filter can still pass incorrect fragments, and imposes the need to calculate custom 'max correctness' value rather than simple filtX*filtY, so it's not much improvement. Consider this:

Code: [Select]

..#######
..X######
...######
@@@@@@@@@
...######
..X######
..#######
where @ are cells that 'must' be passable in the map fragment to pass. This way we guarantee the pass will be..  a pass (duh). Still, I think we're wasting too much time and space for calculations, and that the ambush site would still look dull.

Code: [Select]

**##*****
**X#*****
**.###***
.........
**.###***
**X#*****
**##*****

X - passable cell fo monster placement
. - passable cell
# - cell not passable
* - we don't care

Now, our area is not constrained by a matrix (but we still treat is as such to simplify some 'checking' calculations), much more random and correct at the same time. It can also be stored more efficently as a array (or list) of tagged coordinates (displacements from upper left corner actually) rather than as a matrix. Of course we can fiddle with the probability of '.' cells being '.' in the map if it still looks boring.

Code: [Select]

// returns 1 if passes, 0 if not.  We assume the filter rectangle won't intersect map bounds.
// Filter[i] = x
// Filter[i+1] = y
// Filter[i+2] = character

int Passes_filter? (Map_cell *Map[], int mapX, int mapY,   int Filter[], int filtLen, int filtX, int filtY,   int whereX, int whereY, float percentage)
{
int sum, i;

if (whereX + filtX >= mapX || whereY + filtY >= mapY)
return 0;

for (sum = i = 0 ; i < filtLen ; i += 3)
if (Map[whereY + Filter[i+1]][whereX + Filter[i]]._character == Filter[i+2])
sum++;

return (sum > (int)(filtLen * percentage));
}



Example C data implementation:

Code: [Select]

struct Map_cell{
char _character; // can a monster/player walk through it?
};

Map_cell  Map[25][80]; // standard roguelike map size



struct Ambush_zone{
int *_Filter; // array of map cell coordinates which have to be exact (it's a pointer to filter stored elswhere, doesn't allocate it's own - used for checking the area again when the area gets mutated)
int *_MonPositions; // MonPosition[i] = x  MonPosition[i+1] = y
int _FilterLen;
int _PositionsLen;
int _filtX;
int _filtY;
};


List *Ambush_list; // linked list of Ambush_zone for the Map
List *Ambush_coords_checked_list; // linked list of upper left corners (x,y) we checked already



pseudocode algorithm for mutable maps (called once per game loop):
   
if passed enough time:                     // call it once in a while to not bog down the game
   if Ambush_coords_checked_list size < MapX*MapY/2:      // if no more than half map cells have been checked
      do:
         1) x = random(MapX)
         2) y = random(MapY)
      while coord(x,y) is in Ambush_coords_checked_list
      if Chosen_filter's rectangle doesn't intersect any other defined areas:
         if Passes_filter?(Map, mapX, mapY, Filter, filtLen, filtX, filtY, x,y, percentage) == 1:
            3) push that area on Ambush_list
            4) push every cell in that area on checked_list
         else
            5) push coord(x,y) on Ambush_coords_checked_list
   

[Quendus]

Let's imagine our problem. (# - wall    . - floor    o - vicious orcs):

// damn, this font is really screwing with the image

If you put the diagrams in [ code]..##..[ /code] tags (remove the spaces after the "["s), then they might be easier to read. Example:

Code: [Select]

...#
###.
#..#

[requerent]

Hmm... I'm trying to wrap my head around this idea. Are you more or less evaluating the map for highly constrained areas that the player is likely to pass through?

[Omnomnom]

Interesting post. I think the filtering method you suggest is nice and would also be useful for many other purposes where certain map fragment patterns would be useful to find (eg for placing traps, detecting corners of rooms, etc).

One question I have is how do you know which direction the player will come from? I suppose you can guess and tolerate the ambushers screwing up occasionally and being caught out by the player, but did you have something more clever in mind?

[kuniqs]

If you put the diagrams in [ code]..##..[ /code] tags (remove the spaces after the "["s), then they might be easier to read.

>> Thank You very much


Hmm... I'm trying to wrap my head around this idea. Are you more or less evaluating the map for highly constrained areas that the player is likely to pass through?

>> Yes, though this thingy can recognize pieces of map suitable for traps, gates, drawbridges..


One question I have is how do you know which direction the player will come from? I suppose you can guess and tolerate the ambushers screwing up occasionally and being caught out by the player, but did you have something more clever in mind?

>> Actually I developed this for an open-world roguelike with indefinite map generated on the fly, so there wasn't really a direction there   I think if you have an up stairs (or other feature player can use to enter the dungeon) you can fire an expensive, but doable flood fill to check direction.  Or at least dx,dy for approximation. I think sneaking upon ambushers once in a time can be nice.