Diamond-square algorithm with water erosion for game maps creation

This small work is to describe my experiences with generating maps for open source game Widelands. To get an idea visit https://www.widelands.org/maps/ and filter map by author ‘Tibor’ and ‘TiborB’ - both are me. My goal was and is to generate as realistic maps as possible. Part of my workflow is to import output of this map generation script (an txt file) into widelands editor. But this is out of scope of this my blog.

Diamond-square algorithm is great here, and very easy to implement. But if you look at real world terrain - local minimas are almost non-existent. I mean a complete valley completely encircled by slopes. The reason is that every point needs an water outflow way and is eventually connected to a sea that is generally lowest point on earth. With exception of few areas on the earth.

And diamond-square algorithm create local minimums and maximums as a feature.

What are basics of this algorithm:

• We start with raw diamond square filling up the TERRAIN array

• The water rains from sky as drops

• The number of drops is defined (parameter of scrip is drops per pixel)

• the lifetime of a drop is defined (parameter of scrip) as a number of iterations (epochs) and all drops live the same time

• each drop moves independently

• each iteration every drop “wake up” and looks if it can move downward

• multiple drops can be on the same spot

• TERRAIN is defined as 2D array and WATER is separate 2D array with count of drops per each field (pixel)

• individual drop in a water column on a single point does not have own “elevation”, we presume it is always positioned on the top elevation = TERRAIN[x,y] + WATER[x,y]

• Each drop initializes on random position and (as expected) increased water value in WATER 2D array

• Each drop when evaporates (after expiration of lifetime) decreases the water level on water 2D array

• When a drop moves it takes some soil with it if elevation difference is sufficient, so drop move changes WATER array always and TERRAIN array most of time

• Amount of moved soil is derived from TERRAIN[x,y] + WATER[x,y] differences between initial and target point. As a rule, final point terrain+water height cannot be higher than final terrain+water on starting point

• a drop can move only to one of 8 nearest points.

• erosion process wraps (map wrapping is also feature of diamond-square)

• exception to “each drop moved each iteration” - in fact only 3 drops from a single spot can move in each iteration. This is just a speed-up thing. Note that you can have water column high in hundreds.

• You can have rivers visible, but for the game map I used threshold for WATER values to have actual lakes visible only. So individual drops and rivers are usually very thin and gets filtered out

Here you can see example of erosion and over-erosion. So basically we can conclude that you need to pick right time to get map with expected features.

Also the last image indeed has more water than first because if drop lifetime is 300 iterations, the water will reach target amount only after 300 iterations. In fact I dont remember if final water amount was even achieved on the last image.

Ideas that might be considered:

• variations in soil hardness
• relation between evaporation and place of rain - simulation of a wind with static direction

But it is questionable if they are worth the effort

This is still work in progress, right now I have no material for part II, but I hope I will have some soon.

Developing Widelands's (strategic game) AI with genetic / evolutionary algorithm - Part 2

Developing Widelands's (strategic game) AI with genetic / evolutionary algorithm - Part 2

This part II. will cover following topics:

* New inheritance logic
* New type of neurons
* Automated testing
* Some statistics

New inheritance logic

After some thinking current generation of new DNA of AI players look like this:

There are 4 distinct DNA sets in the code, and new AI player takes genes randomly from all of them and performs mutation with probability about 1/15 afterwards.

Moreover each of 4 input DNAs are linked to test map, I picked the maps so that they are different and covers various conditions (limited space, snow, green land). These four maps are used for testing and DNA of best AI player from particular map is copied to the source code and used for generation of new players in next iteration of test. For more info see Automated Testing section

Consideration:
Is random inheritance from 4 parents evenly the best approach?

New types of neurons:

I felt a need for more complicated neurons, that have two inputs and output is based on its combination, so I came up with "bi_neurons", that receives two bools and with probability of 1/4 returns "weight", otherwise 0. Idea is f.e. scenario:
- if my strength is growing 
- and enemy's strength is decreasing
-> return some value
(otherwise return 0)

Keep it mind, the AI is to be blackbox and I am not to say which of possible combinations:

• me up, enemy down
• me up, enemy up
• me down, enemy up
• me down, enemy down

should return a value and what value it should be. This is the purpose of "evolution" to figure it out. The value is than used as a part of score when deciding about attacking the enemy.

Automated testing

After some struggling with widelands ability to launch "unattended" games, I come up with this setup:

• I have 4 scripts, and each one runs games in loop - using the same map (4 maps are used for testing), writes logs to files (file names are unique, of  course)
• I was not able to redirect it to Xvfb, so the games pops up on screen, so I decided to run test while I am not on PC (at night f.e.)
• Lua scripts are terminating a every game after some gametime (2 - 4 hours, depending on map size), that in real time means 10 - 30 minutes of game
• duration of "test session" is about 4 hours, so I am getting 10 - 30 games per map during "session"
• All 4 scripts are running concurently (that means 4 games concurently)
• I have python script that goes over acquired logs and pick player with higher score and prints its DNA, so I can easily copy it to cc file and recompile

Some statistics

As I probably mentioned, I am using score to evaluate "fitness" of AI player and it is also used to find out if best AI player is better that best AI player from previous session. Usually it is so and with each iteration best score goes up by 10% (evaluated per map).
I have to say that spread of scores per map in a session is very big, f.e. on map Elven Forests I right now have these results (from 27 games from last test session):

Winner score:   1814
Average score:  910
Lowest score:   223

For this stage of development the variance is no issue, but for final version AI will have to provide more consistent performance.


Part I.

Developing Widelands's AI with genetic / evolutionary algorithm

Developing Widelands's (strategic game) AI with genetic / evolutionary algorithm

Disclaimer: This is experimental work and might never make it into release.

Content of this blogspot:

* Introduction of widelands
* Current status of AI in (pre-)B19
* Idea
* Neuron
* AI training

Introduction of Widelands

Widelands is Settlers II clone, open source strategy game, available for all platforms. Please visit widelands homepage for more info.


Current status of AI in (pre-)B19

I significantly reworked AI in 2015 & 2016, this is between releases 18 and 19. Size of code (as located in src/ai/) grew significantly, 2-fold or more. In addition to new functionality and logic, the code contains a lot of numbers, see at this chunk of code (no need to study it deeply):

// score here is a compound of various input values
// usually resources in vicinity, but when enemy is nearby
// additional bonus is added
if (bf->enemy_nearby) {
prio += bf->military_loneliness / 3;
prio += (20 - bf->area_military_capacity) * 10;
prio -= bo.build_material_shortage * 50;
prio -= (bf->military_in_constr_nearby + bf->military_unstationed) * 50;
} else {
if (bf->near_border) {
prio += 50;
prio -= bo.build_material_shortage * 150;
} else {
prio -= bo.build_material_shortage * 500;  // prohibitive
}
prio -= (bf->military_in_constr_nearby + bf->military_unstationed) * 150;
prio += (5 - bf->own_military_sites_nearby_()) * 15;
}
prio += bf->unconnected_nearby * 50;
prio += bf->unowned_land_nearby * resource_necessity_territory_ / 100;
prio += bf->unowned_mines_spots_nearby * resource_necessity_mines_ / 100;
prio +=
  ((bf->unowned_mines_spots_nearby > 0) ? 35 : 0) * resource_necessity_mines_ / 100;
prio += bf->rocks_nearby / 2;
prio += bf->water_nearby;
prio += bf->distant_water * resource_necessity_water_needed_ / 100;
prio += bf->military_loneliness / 10;
prio += bf->trees_nearby / 3;
if (bf->portspace_nearby == ExtendedBool::kTrue) {
if (num_ports == 0) {
prio += 100;
} else {
prio += 25;
}
}


First a broad view: this is part of construct_building() function, which in addition to many other things, goes over empty spaces ("buildable fields") and buildable buildings and scores all combinations. The "prio" is a score for building x field. This chunk of code is for military sites.

As you can notice a lot of variables and a lot of numbers (perhaps we can use word WEIGHT) are employed here.

Idea

Such development and tweaking is very time consuming. You need to compile - run - watch (game and logs) - re-think - edit - compile and again and again. As now there is a lot of discussion about AI (mainly neural networks) everywhere, so I decided that it would be very convenient if I could use some AI algorithm to simplify the development.

Neural networks - no go for now

First where I looked at was neural networks. I have no personal experience with this, but based on what I read on internet, it would be very complicated. At least memory requirements would be huge. Consider map of 512x512, each field having multiple attributes, about 50 types of buildings, roads between them, dependencies (material flows) between them, warfare aspects. Looks like a huge task. Moreover it seems to me that no implementation of neural network for a game like this exists yet.

Lightweight approach

In fact I don't think it is necessary to dump and scrap current AI, but we can use lightweight approach to use some AI technique to help with only small portion of AI. This is what I decided for.

If you look at above code snippet, you there is a lot of numbers there. And idea is to use randomness and natural selection to come up with best AI. So in other words, the evolutionary algorithm is not to be used to play the game, but to help pick best parameters for the game's AI.

Neurons

This is inspiration from neural networks.

Two things can be mentioned in relation to NN:

Activation curves

Well, if you look at example above, most variables have linear impact on the score. But when I was reading about neural networks I noticed strong emphasis on non-linearity of activation curve. And this is something that looks very interesting and useful here. But I also realized, that computation of such curves is CPU demanding and CPU use is already a problem here. The solution is mentioned below.

Neurons

Well, my AI uses word NEURON but it misuses it a bit. Neuron in my implementation is just an object the receives inputs in range (0 - 20) and returns outputs in range (-100 - 100). As number of possible outputs is limited to 21, the neuron contains array with all outputs and no calculation is done in realtime.

Following predefined curves are available for neurons:

{   0,  5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100}
{   0,  0, 1,  2,  4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100}
{   0, 17, 25, 32, 38, 44, 49, 53, 58, 62, 66, 70, 74, 78, 81, 84, 88, 91, 94,7, 100}
{ 100, 97,  94, 91, 88, 84, 81, 78, 74, 70, 66, 62, 58, 53, 49, 44, 38, 32, 15, 17,   0}
{ 100, 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10,  5, 0}
{-100,-99, -98,-96,-94,-92,-88,-83,-73,-55,  0, 55, 73, 83, 88, 92,94, 96, 98, 99, 100}

The curve is modified by weight parameter (-100 - 100), that is multiplicator of above curve (and divided by 100), so if we will use weight -20, values from first curve will range from 0 to -20.

What is a bit of work for developer is to trim a variable to get (mostly) in range 0 - 20, if the value is out of range, outputs corresponding to 0 or 20 is returned by neuron. So I have to modify inputs so that range is used as much as possible, but got rarely out of it.

So entire AI can be "dumped" (and used for initialization) as:

const std::vector<int8_t> input_weights =
      { 86,  70, -52,  30, -25,  30,  30,  -5,  15,  80,
        30, -98,  30, -60,  93, -68, -34, -29,  30,  73,
        30, -12,  30, -93,  30,  30,  30,  80,   6,  30,
       -30,   9, -18,   3,  30, -58,  30,  30,  30}

const std::vector<int8_t> input_func =
      {  4,   1,   5,   1,   0,   1,   1,   0,   1,   3,
         1,   1,   1,   4,   1,   2,   3,   5,   1,   2,
         1,   2,   1,   3,   1,   1,   1,   3,   1,   1,
         4,   2,   2,   0,   1,   1,   1,   1,   1}


So it is a bunch of numbers. Every neuron is initialized with a pair taken from both vectors. And the code where these values are used can look like:

field.military_score_ += management_data.neuron_pool[0].get_result_safe(field.military_loneliness / 50);
field.military_score_ += management_data.neuron_pool[4].get_result_safe((field.area_military_capacity + 4) / 5);
field.military_score_ +=
management_data.neuron_pool[8].get_result_safe((field.military_in_constr_nearby + field.military_unstationed));
field.military_score_ +=
management_data.neuron_pool[12].get_result_safe(field.own_military_sites_nearby_());
field.military_score_ +=
management_data.neuron_pool[13].get_result_safe(field.military_stationed);
field.military_score_ +=
management_data.neuron_pool[1].get_result_safe(static_cast<uint8_t>(soldier_status_) * 3);

For sake of simplicity, I will use word DNA when talking about function type and weights used to initialize neurons.

AI training

Well very basic setup for this kind of stuff is to start a game (AI players only), with very high number of AI players with slightly changed "DNA". Afterwards to pick one or two best performers and use their DNA to breed new bunch of AI players for next game.

But here it is not so simple. Number of players is limited to 8, game even in high speed can take about 1 hour. Than copy/pasting of DNA of winner (being dumped into terminal) into source, then compilation is needed and new game must be started and run.

So when AI is initialized, it takes given arrays with DNA information and randomly changes about 10% of neurons. This is done for every computer player separately, of course.

Measuring of performance of AI

Well, the game provides few types of graphs (territory curves, military strength curves), so I can have some rough indication which AI is working best, or at least a better as in previous iteration. But for purposes described lower, I generates simple formula how to measure performance of AI:

score = 3 * military_sites + buildable_fields + 10 * production_sites + 10 * mines + 3 * military_strength;

score = military_sites + buildable_fields + 6 * production_sites + 10 * mines + 2 * military_strength + 4 * lost_soldiers + 8 * warehouses + 5 * my_strength_minus_average_enemies_strength;

In-game DNA mutation

Well, due to low number of players I was looking for ways how to enable modification of DNA of AI players during game. Above I presented a score, this is what I use to watch how AI is coping. Currently the logic is:

if score / score_40_minutes_ago < 1.1:
modify_DNA()

This allow the game itself (without my intervention) to change DNA of weak performers. But until one critical point - when AI starts fight together. Here it is much more difficult to come up with score that would indicate "good enough performance".

Final words

Well this is open-end endeavor - I have no idea if this ever be good enough for release, but it is fun to work on :)

Part II

River networks generation for game terrains

Small disclaimer: This post will be a bit off topic - when looking on a title of my blogs here, yet this something that I am interested in.

Generating of realistic looking rivers with branching for computer games is not an easy task. First, I talk here about large-scale maps, in games like Settlers, where a player is looking on the map from upside perspective. Of course drawing maps manually is quite possible and sometimes easier and less time consuming, but on the other hand purely random rivers have specific look, similar to terrain generated via fractals algorigthms, f.e. diamond-square algorithm.

In fact initially my idea was to use terrain generated by diamond square algorithm and put rivers there. It is not easy, at all. My second attempt was rivers generated randomly and fractal mountains created around them. This works. Though my rivers just do not branch. They are just lines growing thicker near to the lake where they flow to. Here is screenshot from finalized map used in Widelands game:

.

Both game and map (can be downloaded from homepage, map separately from section 'maps', look for Sprider Lake map) are free, so you can look at the map in details.

Such (no branching rivers) are not bad but still...

So here I present..

...my attempt to create branching rivers.

Ideas and/or assumptions I used are:

• Rivers are created of rain water.
• The amount of felt rain water is the same everywhere (this is something that can be modified of course)
• Rainwater do not soak into ground and do not evaporate (this would be easy to implement though)
• No erosion and deposition is taking place (in fact the map has no height defined in this stage at all)
• The land (map) is made of squares and each of them has a slope and water from it is flowing to one and only one of 8 neighbors.
• The "end points" are to be defined beforehand. All water that flow will end in one of end points. No random lakes are generated on the map.
• When map is generated the way that you can track every single drop (water originating on a field) to one of endpoints.
• You can count number of drops flowing over every single square and use threshold to say "this is small or big river here, or no river at all"
• Map wraps (expected from such maps)

Algorithm:

We have grid and every field (square) can has 2 states:

• directed (we can say 'processed' as well): the square has an arrow on it or circle meaning endpoint of rivers
• the other (not directed yet) quares

Rivers are generated in iterations, on the image below every picture presents one iteration. Steps within iteration are:

1. Get list of fields that have at least on adjacent field in "directed" state
2. Choose some of fields from the list (not all)
3. For every selected field identify all directed neighbors pick one of its neighbors and put an arrow on the field pointing to that neighbor. (It becomes directed from now on)
4. Repeat iteration (iterate until all pixels are directed)

And almost all :). The step by step progress is shown here:

Well rivers on the last image are bit funny or ugly, but on larger-scale they looks better, see below.

But return one step back - to get a rivers we have to track every single drop from source square to one of endpoints and every square on map has count of drops that passed over it. So here in this map 12x12 drops will end in the end point.

Rivers itself are generated based on thresholds, every single pixel that exceeds a threshold is made into river. 

On my sample images the shade reflects amount of water on the fields, but in real game the thickness of rivers might be modified. 

Here is the example of final river networks, and with two "end points". Also note wrapping in action...

Also, modifications to algorithm are possible, f.e. you can manipulate amount of rained water, or create spring wells. But here I used other feature - I created "obstacles" - see image below. Pixels in red are impassable for water, and as you see my algorithm put random crosses on map to simulate mountains. Also you can notice there were isolated square sections created where no water is flowing from...

Of a lot of work remains until the scheme is made into playable map, but this is not a part of this blog post.

I hope the algorithm is obvious enough:)

If any questions feel free to ask, I am interested in any feedback 

Retention/Versioning jungle of Tivoli Storage Manager

-->

This blog will try to explain VEREXIST, VERDELETED, RETEXTRA and RETONLY options. This will not attempt to explain how to find out those values for a random file backed up on your TSM though.
First question: do you use queries to look up your backups? Yes, command line I mean. For advanced things it is a must. Here is a simple example:

select * from backups where node_name='MAILSERVER'

      NODE_NAME: MAILSERVER

 FILESPACE_NAME: MAILSERVER.DOMDBS

   FILESPACE_ID: 1

          STATE: INACTIVE_VERSION

           TYPE: FILE

        HL_NAME: \MAIL\

        LL_NAME: JOHNSMITH.NSF.DATA

      OBJECT_ID: 597594810

    BACKUP_DATE: 2013-06-12 20:49:57.000000

DEACTIVATE_DATE: 2013-06-13 20:51:48.000000

          OWNER:

     CLASS_NAME: DEFAULT

[many more items follows]


You can investigate what is there, but what is interesting now is the “STATE” information. As you know, the TSM can keep multiple versions of one file. A backed up file has one or no active version and might have multiple inactive versions. Unique identification here is not HL_NAME+LL_NAME (all versions of the file has the same LL and HL_NAME ), but OBJECT_ID. From above you can say that this version was backed up on June 12th, and new version of file was backed up a day later and so status of this version changed to inactive
So this was short but needed introduction and now the main part:

Two processes are important:

A) Backup process - it applies versioning policy every time you are backuping/archiving:

	If source file exists	If source file no more exists
Previous active version	Changed to inactive	Changed to inactive*
Inactive versions (including newly de-activated one)	Their number are reduced*** to $VEREXIST-1** (if needed)	Their number are reduced*** to $VERDELETED (if needed)

* Under some circumstances the file will remain active (while the source file no more exists on client server) and may remain so “forever”. It seems that it might relate to the type of backup incremental vs. selective. (But this issue/behaviour out of scope of this blog.)
** because active version is also counted
*** the 'reduction' is done via setting 'DEACTIVATE_DATE: 1900-01-01 00:00:00.000000', the version of file itself is deleted by next expiration process


B) Expiration process - As you probably know, expiration is a separate process running once per day or so....
Important: This deals with inactive files only!

	If source file exists	If source file no more exists
The latest inactive version of non-existent file	Not applicable	expires after $RETONLY days after time when status was changed to INACTIVE
Interactive versions in general (save the one reffered to in a row above)	expires after $RETEXTRA days after time when status was changed to to INACTIVE	expires after $RETEXTRA days after time when status was changed to INACTIVE

Well I wrote "expires" but it should be read "is deleted".

And this is all, I hope it helped you and there are no factual errors (save some simplifications).

Creating bootable system backup tape on other server (for AIX)

Creating bootable system backup tape on other server (for AIX)

Lately I needed to make system backup from remote AIX servers, but have it saved to a tape on local machine. And I found out that things are not that simply. I found just handfull of resources on internet, but none that would be comprehensive and fully reliable, and none official from ibm. So I started my quest for the proper procedure.

I spent quite some time with it, but I will present my results in very concise form.

First, a bit of theory:

A bootable tape as a result of mksysb contains 4 records (set of data).

1. boot image - should contain all drivers from and for backed up server, so I reccomend to create own image for every backed up server (Doesnt take a lot of time anyway)

2. mkinsttape image - contains some install data and structure and mountpoints of rootvg

3. dummy "Table of Content" record - not used, it is here only for some compatibility reasons

4. mksysb image - archive of rootvg files - the "core" part of tape

"Terminology"

To distinguish servers I will reffer to them:

1. remote - the one that will be backed up

2. local - the one where we will write to the tape

Preparation of files on remote server

I will use below variable in my explanation:

$WORKDIR=/bla/bla - this is directory where prepared images will be stored.

The procedure will look like:

#1. Bootable image

bosboot -ad /dev/rmt0 -b $WORKDIR/1_bosboot.img

#2. Mkinsttape image

mkinsttape $WORKDIR/2_mkinsttape.img

#3. mksysb image

mksysb -e -i -p $WORKDIR/4_mksysb.img #swith -e is for exluding files, it is optional only

So the result is three files in $WORKDIR:

1_bosboot.img

2_mkinsttape.img

4_mksysb.img

(Yes, the number in names indicates final order on the tape)

This is all we need to do on remote server and now we go to local server to create the tape. Of course, copy the above files to local server first.

Work on locale server

In this part we will use 2 variables:

$RMTDEVICE=rmt0 - as example

$WORKDIR=/bla/bla - directory with above images

Preparation of tape

chdev -l ${RMTDEVICE} -a extfm=yes

tctl -f /dev/${RMTDEVICE} rewind

chdev -l ${RMTDEVICE} -a block_size=512

tctl -f /dev/${RMTDEVICE} rewind

#1 Saving bosboot image to tape

dd if=$WORKDIR/1_bosboot.img of=/dev/${RMTDEVICE} bs=512 conv=sync

tctl -f /dev/${RMTDEVICE} rewind

tctl -f /dev/${RMTDEVICE}.1 fsf 1

#2 Saving mkinsttape image to tape

dd if=$WORKDIR/2_mkinsttape.img of=/dev/${RMTDEVICE}.1 bs=512

tctl -f /dev/${RMTDEVICE} rewind

tctl -f /dev/${RMTDEVICE}.1 fsf 2

#3 Create & save dummy TOC to tape

echo "Dummy tape TOC" | dd of=/dev/${RMTDEVICE}.1 bs=512 conv=sync

tctl -f /dev/${RMTDEVICE} rewind

tctl -f /dev/${RMTDEVICE}.1 fsf 3

#4 Write mksysb file to tape (4/4)

dd if=$WORKDIR/4_mksysb.img of=/dev/${RMTDEVICE}.1 bs=512

tctl -f /dev/${RMTDEVICE} rewind # optional

And that is all, of course you can partially check the tape with command

lsmksysb -V -f /dev/${RMTDEVICE}

this will check readability and consistency of mksysbfile and whether is located as fourth record on tape. But it seems that only reliable test if the tape is functional is to boot from the tape.

Issues:

I dont have procedure for situation when backup can not fit to single tape. In such case use "exclude files swith: -e" , in fact it is listed above, but to be effective you need /etc/exclude.rootvg file with appropriate content)

This should be all, feel free to ask&comment