Messages

1

7DRLs / Re: plato rogue 7drl2014

« on: March 15, 2014, 08:20:11 AM »

2d platformer where you're just a shadow on a cave wall?

Not even close. Ever heard of PLATO computer system?

The source is in Lua so you can download Ubuntu version of the LOVE engine from https://love2d.org/ and move plato_rogue folder inside
Windows version:
http://www.sendspace.com/file/m57ipa
click on 'Pobierz'
http://chomikuj.pl/kuniqs/PLATO_ROGUE,3683740918.rar

2

7DRLs / plato rogue 7drl2014

« on: March 08, 2014, 09:52:30 AM »

wait for it

3

Programming / Lua Gravity

« on: May 14, 2013, 10:14:38 PM »

Anyone has it? Very neat concept, but this thing is unavaliable through net for some time..

4

Traditional Roguelikes (Turn Based) / De sade's dungeon - 7drl succes

« on: March 19, 2013, 12:48:22 PM »

windows version:
http://chomikuj.pl/kuniqs/De+sade*27s+dungeon+(windows),2523200275.rar

http://www.sendspace.pl/file/a0bbf49e11ee91f64166c17



linux:
http://dungeon_keeper.republika.pl/de_sade/De_Sades_dungeon.tar.gz

5

Programming / Re: Structured Enemy Design

« on: March 17, 2013, 03:09:20 PM »

Why not make a very, very simple game that would test the stat-adjusting mechanics?
Also check out the elder scrolls games and IVAN for examples of such system made wrong.

6

Programming / Quick and dirty way for typicall monster pathfinding (OR dijkstra variation)

« on: January 10, 2013, 02:42:32 PM »

I was perusing through Collaborative Diffusion Antiobjects paper which contained simple, yet ingenuous method for simple yet accurate and special-case free monster pathfinding.

Played ADOM? Mons there act simple as expected from a middle-age roguelike. Source code is not released but from experience I can extrapolate the behaviour as:

- Player leaves scent (or turn counter) where he stands
- If monster sees player, it moves closer to him (if path is blocked, sidesteps if it can)
- Else: if feels scent, moves along it
- Else: move randomly

It works pretty well, but what I don't like are all those if, ifs, else, elses scattered around handling any exception possible. Circumventing this with A* and family makes more problems than it solves. Making subtle changes becomes a pain as the game grows.



Here's a solution, modified slightly for a roguelike (examples taken from the paper):

1. Set all passable tiles scent values to 0, impassable tiles as infinite.
2. Start a flood fill from player position setting flooded cells as 1 higher than their parent cells, flooding only passable cells:

Code: [Select]

00000000000000000000000
00000000000000000000000
00000033333330000000000
00000032222230000000000
00000032111230000000000
000000321@1230000000000
00000032111230000000000
00000032222230000000000
00000033333330000000000
00000000000000000000000

empty map flood fill

Code: [Select]

00000000000000000
00555000005550000
0054#######450000
0054321@123450000
0054#######450000
00555000005550000

corridor flood fill
(to understand flood fill, imagine a height map with numbers representing elevation - 0 is sea level. Then imagine monsters as balls placed on hill slopes, rolling to the lowest possible level. There should be zillions of implementations on the Web or Roguebasin)


3. for every monster: check every 8 neighbour tiles, find the one with lowest scent value. If that tile's scent is lower than monster's tile scent, move on that tile. (assuming walking on player's tile is equall to attacking the player). Else: walk randomly.

That's all folks. Almost exact copy of dijkstra map technique, or hill climbing, but it doesn't matter.
The key is to run the flood fill from scratch every time, and treating monster occupied tiles as walls. This prevents jams in corridors and swarms:


Example 1:

Code: [Select]

######
#44566
#3##55
#2##4o
#1##3g
#@1234
######

Going with above algorithm, both orc and goblin will go lower corridor. But..

Code: [Select]

######
#44567
#3##67
#2##77
#1##o8
#@1g99
######
Since goblin is effectively a wall, orc will turn back and pick upper corridor, leaving '@' no chance to escape.


Second example.

Code: [Select]

              ################
                        65433#
              ##############2#
 ####                 6543211#
  oo#         ##############@#   
  oo#                 6543211#
 ####         ##############2#
                        65433#
              ################
Let's assume flood fill reaches those four White Hands by the power of ASCII limitation. First, they will probably cluster in one place..

Code: [Select]

              ################
                        65433#
              ##############2#
 ####        ooo      6543211#
    #        o##############@#   
    #                 6543211#
 ####         ##############2#
                        65433#
              ################

..then get redistributed equally by the scent blocked by other orcs.

Code: [Select]

              ################
                 o      65433#
              ##############2#
 ####               o 6543211#
  oo#         ##############@#   
  oo#                     o11#
 ####         ##############2#
              o         65433#
              ################
Trapping poor hobbit second time.


This can be extended to hunting other monsters by bookkeeping individual scent info. Tad complicated, but doable. Best thing is, it doesn't need any tweaking with existing AI, only that 'move one step towards goal' function - all the work is done by the map. It also has somewhat constant computation time if you limit the amount of flooded tiles.



Problem I noticed with this is when we have a veeeryy long corridor

Code: [Select]

#########################
.........@o.....ooo......
#########################
One orc will combat (or chase) the hobbit while rest will stand slack jawed.
To fix this, we need to modify a bit the scent propagation: instead of treating monster tiles as impassable, we add a constant to the scent value (assuming +5) and use it in flood fill. When we add tiles to flood fill queue, we sort them by scent value, so the scent will be distributed equally.

Code: [Select]

#########################
   22223456                 
   211###56   
   21@o7o66
#########################
the orc on left side of seven (Grunge) has a tile value of 6, on right of seven (Munge) also has 6. Munge will go around the wall to reach @ but..

Code: [Select]

#########################
   22223456789ABCD                 
   211##########CD   
   21@o7o9ABCDEDDD
#########################
..here Munge will keep close to his buddy, since the road is too long to be worth taking it.

7

Programming / Re: Modular monster intelligence system

« on: December 07, 2012, 10:49:21 AM »

It's unlikely I'll include neuron teaching addition since it incorporates a bit too much math for now and differential calculus neural net learning algorithms are still haunting me in nightmares .
Big time problem with monster net teaching is that we need to know what actually teaches. Survival time? Monsters learn to run all over the place. Damage done vs. damage received? Monsters turn suicidal maniacs and so on. I've never seen a good example of neural nets used in mons evolving over time (maybe Creatures, but this ain't a conventional game).

8

Programming / Modular monster intelligence system

« on: December 06, 2012, 09:47:59 PM »

Modularity is a thing not very common among the world of roguelike source code. Most of it is based upon medieval designs such as Nethack or Angband, plus the community itself only few years ago started embracing more open minded languages such as python (how python can survive in a fridge?!) abandoning ye olde senile C. Still, I have seen many outdated things written in Python I would like to forget.
It's bad since many, many roguelike projects get abandoned because the author (who's probably more of a programmer than designer) gets bored by the spagetti.




Neural Nets

What the industry calls "Neural nets" are really pattern recognizing primitives, no sentience involved. We take some inputs, perform something akin to weighted average on them, and if the output is > 0, we have recognized or liked something.

Code: [Select]

        input1       input2      input3
            |               |               |
       weight1   weight2     weight3
            \               |              /
             \              |             /
              \             |            /
               \            |           /
                \           |          /
     
                        Sum

                           |
                           |

                          f()

                           |
                          \|/
                       output
   Standard issue neuron

Schematic of neuron in work is below:

1) Sum = 0
2) for each input <> weight pair
   3) sum = sum + input*weight
4) output = F(Sum)


f() is a special function used almost exclusively during net leatning, so we don't need to concern ourselves with it now. Weights can be of any range, but for net learning purposes they range from -1.0 to 1.0. We ignore that now and use any range we find suitable.

How to understand them intuitively? How do you rank cars, for example? You probably take colour, speed, silhouette, cost and age into consideration. The higher the attribute, the more desirable it is for the 'general' perspective. So, high value for the age input is a young car, high for colour is a red car while a low (negative) value for speed is a slow car.





If you like 'best of the best' models and are a spoiled rich kid that doesn't care about money and  changes his car for newer every year, your net weights might look like this:

Code: [Select]

colour     speed       silhouette        cost       age
10           15             10                   0             20
(weight of 0 means 'we are indifferent')
This guy values most the fastest and youngest cars with good appearance, but doesn't care if the car is expensive.


Or maybe you're an eccentric who likes old, ugly cars bought in retail prices, and..

Code: [Select]



colour       speed       silhouette       cost       age
0                0                 -5               10          -10
..you don't care about car's colour or quality and the older the car, the better.






If we take a average, but expensive car like this:

Code: [Select]



colour       speed       silhouette        cost        age
3                2               5                   10            2
Our millionaire will react to it like this:

Code: [Select]

colour speed silhouette cost age
10 15 10 0 20 weights
* * * * *
3 2 5 10 2 inputs
+ + + + =  150


Since the output is more than zero, we like the car.
For an old, cheap, painted in pink amphibia we get a reaction of:

Code: [Select]



colour speed silhouette cost age
10 15 10 0 20 weights
* * * * *
-6 1 -2 1 -5 inputs
+ + + + =  -165
The vehicle is repulsing.
Important thing in all of this is that inputs can vary a bit and the spoiled kid will still react negatively to .



That technique can be used for making npc's a tad smarter by making them evaluate their targets. Lets say we want a goblin to avoid strong enemies. How do we define 'strong'? Are tigers strong? How strong exactly? If we make all goblins avoid tigers, all goblins will run from all tigers, so this will get old quickly. If the goblins are cunning, they may run away from adult tigers, but pick on baby tigers or even malnourished adult ones if they have good weapons and significant numbers advantage.
Humans (and goblins by extension) can only approximate if somebody is strong enough. Using neurons, we can emulate this behaviour.
Let me see..  Goblins are cowards who dislike attacking anyone taller and with more friends than them. They also know how to backstab - attacking creatures not hostile to them. They're not stupid or sociable enough to sacrifice themselves for the greater good and will value their own health very much. If the output is positive, there's more motivation to attack than not to. Input values are obtained solely by functions, to be more general than direct variable checking.

Code: [Select]



input weight
IsHostile(Enemy) -2
WeaponValue(Goblin) 5
NumberOfFightingAlliesOf(Goblin) 10
HeightDifference(Goblin,Enemy) 4
HPDifference(Goblin,Enemy) 5
Difference(HP,MaxHP) 10
This way, we designed an 'Attack' neuron, that will call a mystic InitiateAttack() function if there are no better actions to take (no other neuron has higher output). What sets this apart from other AI methods is that the goblin can act a little erratic - sometimes it runs away when heavily wounded and surrounded by friends, sometimes it's wounded heavily, but so is the surrounded enemy so the goblin keeps fighting. We can have either species weights (all goblins use the same weight vector) or custom weights (every goblin gets his slightly altered set of weights). Adjusting the weights to change a coward into a berserker is very easy from both the programmer and the monster designer's perspective. Some gobbos are afraid of everything, others are overconfident and there are some dirty cowards mugging on the weak and alone. The player will never be sure.

Those are the most basic things in neural net theory, but enough for us to understand what's going on below.



   Modular decision maker.

Code: [Select]


struct Neuron{
VectorOfInputGettingFunctions I; // those are something like int Func(Creature Self, Object Target)
VectorOfWeights W;
FunctionToCallAfterGettingOutput F; // void Func(Creature Self, Object Target)
int output;
};


struct Brain{
VectorOfNeurons N;
};



void RunNeuron(Neuron N, Creature Owner, Object Target)
{
 call all those Input Getters, building the I vector, multipy I vector by W vector, obtaining output
}

void ContestOfNeurons(Brain B, Creature Owner, Object Target)
{
  call RunNeuron for all Neurons in vector N
choose the neuron with maximum output
return it
}

void UseTheBrain(Brain B, Creature Owner, ListOfTargets L)
{
for every target in L:
call ContestOfNeurons(B, Owner, Target)
store the returned neuron somewhere

choose a neuron from the stored ones with the highest output
call that neuron's F function
Fin
}

There's more pseudocode than C here, but almost everybody will have their own ideas of what a Creature and Object is. In my book, Creatures are Npc's, Objects are Creatures, items and possibly (if we go for very general design) doors, trees, anything we can interact with. Since we use value obtaining inputs instead of directly wiring the input vector to some raw values, the neurons can obtain a sensible value if we try to obtain a weapon value of a door.


   
   Why should I use it?

Remember our goblin? What if we want to teach him something like casting spells? While playing the game? Using states, this requires some magic with flags and ifs which is nice, but a bitch to modify once you've written all the state code.

With the modular design of neuron method, Goblins have Move, Attack, Flee, PickUp, Wear and other neurons. We just add water, or the CastMinorSpell neuron and that's all. Great thing is that we can add and remove those neurons at run time, so we can have a spell named Evolve which grants spellcasting abilities to any humanoid we cast it upon. Or Touch Of Idiocy, which retards everyone into zombie who only StandBy, CloseWith and Attack.

We can also add some unorthodox behaviours like rust monsters hunting for swords in the dungeon, orc pyromaniacs blowing up every powder barrel they spot (if they have too much mana on their hands), kobold skirmishers who keep 1 tile distance to the player when wounded and moving for a strike at full health, or Confusion spell which gives a temporary neuron with a very high output and a function which makes the monster move randomly. Maybe incorporate a phobia system in your game, so every mundane monster has a chance of being blessed with arachnophobia (reacts very negatively to spiders), hydrophobia (hates water elementals) or paranoia (has an insanity counter incremented every time hears a weird noise, starts panic after a certain number of them). Some minor changes in neuron themselves could be done by Fear spell, which alters some kind of EstimetePower function to give much higher value for the caster.

As I said, altering the brain is a trivial task - we can design dozens of neurons and construct many different brains from those blocks. Also storing the weights themselves in a file is nice and clean, so is making minor changes to them.


   Why shouldn't I use it?

Since we have to use indirect function calls and calculate every neuron, it's extremely slow in comparison with most other roguelike AI's. Multipy that by the number of targets we want to check with the brain. Turn time roguelikes (most of them) probably won't even notice since you have the user slowing down the game, but this system is rather overkill for real time. I think the reuse and ease factor far oughtweights time and memory consumption and I intend to use this in a general roguelike engine.

Some neurons can frequently alternate between negative and positive outputs - some monsters may exhibit unbalanced behaviour, quickly changing from escaping to attacking or simillar flavour. Could be a problem when we want monsters who can be relied to run at least N turns when scared.

Plus, having unbalanced weight ranges for various neurons can result in the lower ranged ones being seldomly called, if at all. If we assign CastSpell neuron with min/max weight ranges of -10/10 to brain with neurons of average range of -100/100 will probably exclude that neuron from being useful. Additional tests need to be made, if there's really a problem it is solved by restricting the weights to a global range, -10000/10000 for example with normalizing functions when loading the weights from a file.

There are other methods like this one that are more lightweight, like Need driven AI by Bjorn Bergstrom http://www.roguebasin.com/index.php?title=Need_driven_AI.

9

Programming / Re: Programming habits, standards, and learning.

« on: October 25, 2012, 07:19:43 PM »

C++ is more cathedral-style language; great when you are 99% certain what you want to write. Add new ideas, code refactoring, bugs in multi-parametrized templates, multiple polymorphic inheritance with overloadings and the code gets undecidable.
Main problem of this language is the lack of standarization at compiler and library level. Amazing that mixing C and C++ is often easier than mixing C++ and C++. Standard library doesn't standarize sockets, windows, sound etc. only containers, which there are hordes around the net. There's also the problem of C++ claiming to be high level language, and C legacy you have to tend around the code.
The standard comitee is utterly insane - they couldn't bother to make lists, vectors standard types, support multithreading or include optional garbage collection to the language. Instead they approve existing libraries like boost as standard - check the lambda library if you think about learning C++. This was my first language, and I'm not sure if learning python/lisp first wouldn't be better.


Language wars aside, I advise learning:
- Scheme (very gentle introduction to functional language, much cleaner language than Common Lisp). Try DrRacket.
- Lua (fun little language, it's table-based OO rocks).
- C (the mother of all languages..  If you 'really' want to learn C++, learn C beforehand. Might cool you down a bit. Lua/Python were written with it, so it might come handy if you decide to learn them from the inside)
- C# (will be a cakewalk if you know VB.net)
- Python (since virtually everyone goes wild when hearing that word, why not go with the hype ?  I prefer Lua, but learning Python will certainly pay off for anybody).

Of course every one of them has major repulsivenesses - thousand and one Scheme distros, Lua is 'only' a C glue language, ancient imperative artifacts in C, windows dependancy of C# and rather not very serious Python community (Guido said we don't need it, so why question his decisions?).
Also try learning some dry Object Orientation theory (interfaces and stuff). Just don't practice OO with C++, with it's Encapsulation, Inheritance, Polymorphysm trinity.

10

Programming / Re: [Idea] RogueLike in facebook

« on: October 07, 2012, 07:38:31 PM »

Anyone played Combat Mission? I think about giving each player 1 minute, 30 action points and simultaneous action. Move 1 tile - 2 points. Use a wand - 15 points. Hit somebody - 20 points etc.  A unused points pass to the next phase (with restriction of not having more than twice the normal). Your action queue is visible to everyone.
When everybody's ready, both players and monsters move in real time for few seconds maybe?

Sonuds like a pretty great concept. What if the players actions interfere with each other. Example: first player wants to move 10 steps north and second player want to make a "magic wall" infront of him. What would happens then?

Then others gang up on the mason and kill the idiot. Couldn't simillar scenarios occur in typicall MMO? Besides, you know action queue of everyone, so..

Also if you queue up a certain amount of actions there could be monsters coming and attacking you without you knowing about it. If you decide to move 10 steps north, there could be a monster just outside the FOV at the north of you that will start attacking you under these 10 steps.

Maybe I understood it wrong?

Since it's a multiplayer roguelike, I think somebody should be covering you there.

11

Programming / Re: [Idea] RogueLike in facebook

« on: October 07, 2012, 07:07:19 PM »

Anyone played Combat Mission? I think about giving each player 1 minute, 30 action points and simultaneous action. Move 1 tile - 2 points. Use a wand - 15 points. Hit somebody - 20 points etc.  A unused points pass to the next phase (with restriction of not having more than twice the normal). Your action queue is visible to everyone.
When everybody's ready, both players and monsters move in real time for few seconds maybe?

12

Programming / Re: Ambushes

« on: October 07, 2012, 07:01:32 PM »

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.

13

Programming / Ambushes

« on: October 05, 2012, 09:10:51 AM »

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