Previous Up Next

Diary, December 2019



Sun Mon Tue Wed Thu Fri Sat
  1   2   3   4   5   6   7
  8   9  10  11  12  13  14
 15  16  17  18  19  20  21
 22  23  24  25  26  27  28
 29  30  31


Sunday, December 1, 2019

Random maze

In the past weeks, I have been analyzing algorithms to generate random mazes. The kind of mazes that I am studying are mazes within a rectangular grid of rooms where the maze is a spanning tree, meaning that there is exactly one route between each two rooms. In such a maze the number of doors (compared to walls) is one minus the number of rooms. Knowing how many doors and walls there are to be, you can calculate the change that at some position there door and wall. From this you can also calculate the changes for the different types of rooms (with respect to the position of the doors). There are rooms with one door, two opposite doors, two doors with a turn, three doors, and four doors. But it seems rather hard to generate random mazes that match these 'ideal' distributions. Wilson's algorithm is a simple algorithm to generate an unbiased maze. It has almost half the number of rooms with four doors as the 'ideal' maze. I also implemented an algorithm that starting with a balanced random assignment of doors and passages and fixes this by randomly changing passages into doors to connect unconnected rooms and doors into passages to prevent multiple routes between rooms. This algorithm is named 'Random' below. Alternatives of this algorithm, called 'Digging' and 'Trees' below, start with a maze with only walls and only doors, respectively. I also implemented a recursive division algorithm, called 'Spit' below. The traditional depth-first algorithm is called 'Depth-first' in the table below. This table gives for each algorithm the average percentage for the different type of rooms when the algorithm is run 500 times for a 50 by 50 room maze, and also the average distance between every two rooms (with its standard deviation).

               one    opp.    turn   three   four   dist.(dev)
'ideal'     26.69%  13.32%  26.69%  26.65%  6.65%
Wilson      29.18%  17.35%  27.82%  22.18%  3.46%  111.14(12.72)
Random      30.57%  16.15%  26.80%  22.47%  4.01%   96.49(10.20)
Digging     31.70%  15.84%  25.25%  22.79%  4.42%   94.93(11.03)
Trees       30.50%  16.45%  26.78%  22.15%  4.13%   58.50( 1.75)
Split       28.11%  13.97%  32.90%  22.01%  3.01%  123.81(16.30)
Depth-first 10.12%  31.00%  49.00%   9.72%  0.16%  403.49(32.92)

The depth-first algorithm clearly gives a different kind of maze than the other algoritms, resulting in lots of rooms with only two doors and only a very few rooms with four doors. It is obvious that this will lead to a high average distance between two rooms. However, note that the algorithm 'Random' and 'Trees', which are rather similar with respect to the types of rooms they have, yet have a different average distance. The name 'Trees' refers to the fact that the walls grow like trees from the sides, which make that the rooms in the center have short connections to the rooms further away. I have no simple explaination for the fact that the number of rooms with more doors are lower for all algorithms compared to the 'ideal' distribution. I also have not yet found an algorithm that generates mazes that on average are closer to the ideal numbers.


Wednesday, December 4, 2019

Kirsen Everink

I went to see the exhibition at B93 with paintings by Kirsten Everink. I have seen many of her paintings at the Finals 2017 exhibition, which means she has not produced many new works in the past two years.

Duin

This evening, I finished reading Duin, the Dutch translation of the novel Dune by Frank Herbert. It was my fifth reading of the novel, fourth in Dutch, once in English. The last time, I finished reading the book (in English) was on Sunday, May 8, 2011. What surprised me during this reading, was my emotional responds to it at certain important points. Is this because I am older and have more emotional experiences of because I have become more sentimental. I started to read the book because at the moment, the book is made into a film again (for the third time). I have come to the conclusion it will be very hard to adapt the book and capture the depth of the struggle of Paul, which is so much hidden for the people around him.


Friday, December 6, 2019

Book

At 09:11, I bought the book Spoedcursus verlichting written by Tijn Touber in Dutch, and published by Bruna Uitgevers in 2010, ISBN:9789044961171, from charity shop Het Goed for € 1.75. I am afraid that I am going to be disappointed by the contents


Saturday, December 7, 2019

Groninger Museum

Peter Struycken invited me to visit the Groninger Museum with him, where there is an exhibition of some of his works. After we had some coffee and tea with applepie, we went to the top floor. In the hall we were greated by three of the Boulez carpets, from left to right: Boulez 44, Boulez 27, and Boulez 45e. We sat on a bench and watched ...explosante-fixe... with music by Pierre Boulez and Skrjabins Vision with music by Alexander Scriabin, two 20 minute long animations on music displayed on five large screens. Next we saw the exhibition Presenc by Daan Roosegaarde and the exhibition Mondo Mendini about the Italian designer Alessandro Mendini. At this exhibition, I liked the following works: We also saw the museum collection. Of which I liked the following works:


Sunday, December 8, 2019

Heliophile and more

I went to see the performance of Heliophile in Haaksbergen. I just missed the start of the performance, because I had left a little late and had to bike against the wind. This was the first performance where the background tracks were replaced with a life performance with a large modular synthesizer. It was also the last performance with Bernard, which means Heliophile will continue as a duo. In the room they were performing, there was also an exhibition of Fotobond Twente. I liked the photographs by Hans Wissink, Marinus Rouweler, and Anja Jalving. When I biked to Enschede, I saw several rainbows (which all originate from the same cloud, I guess). At 14:59. while I was biking on the Helweg, I saw a fragment (left) of a rainbow at the horizon. From 15:10 till about 15:13, I saw a rather bright, double partial (left) rainbow. Then at 15:16, I saw a partial (right) rainbow. It slowly started to rain, while the sun was still shining, and finally, around 15:20, I saw a full, but rather faint, rainbow. I went to Het Bolwerk, where the opening of the exhibition with drawings by Johan Leerkotte. There also were some music performances.


Thursday, December 12, 2019

Books

At 17:03, I bought the following two books from charity shop Het Goed:


Wednesday, December 18, 2019

The Rise of Skywalker

This afternoon, Annabel and I went to watch the movie Star Wars: The Rise of Skywalker. It has been a kind of traditiong that we go to see the new Star Wars movies on the day that they are released. Although there are tons of so called Star Wars fans who are going to say that this is the worst Star Wars movie ever, for me this one is going to be in the top three. I think this is a very balanced and well directed movie with a believable plot, which places the two previous movies in context and resolve some of the appearant plot holes.


Thursday, December 19, 2019

15°Celsius

This week, it has been warm for the time of the year. Today, the temperature at the airport Twente weather station, reached 15°Celsius, which is a record for this day (but not for this time of the year).

Book

At 17:53, I bought the book De gouden eeuw van Twente: zij die de kunst schonken written by Doreen Flierman and Josien Beltman, in Dutch and published by Rijksmuseum Twenthe in 2015, ISBN:9789072250414, from charity shop Het Goed for € 1.50.


Saturday, December 21, 2019

Exhibitions

At 14:58, I bought the book AKI-jaarboek 2005/06 written in Dutch and English, published by AKI akademie voor beeldende kunst in June 2006, ISBN:9073025087, from Kringloop Enschede for € 1.00. I went to TETEM art space to see the exhibition Should I Stay or Should I Go. I did the Nederlands Gastronomisch Inburgeringsexamen test, but I did not see if I passed of failed the test. Although I am Dutch and should pass the test, I guess, I might have failed, because I do no longer follow the typical Dutch eating habits. The installation Tune of the Hamlets did not work. This installation allows you to mix a choir of people who sing the same song in different dialects of Low Saxon. I also went to photo galery Objektief to the exhibition with pictures by Hessel Bosch, who has been a photographer for more than fifty years. He was present at the exhibition.


Monday, December 30, 2019

'Raw' parser

I remember working on a 'raw' parser during Overkill Festival, 2018. I had several reasons to work on this. I wanted to have a C version of IParse because I came to the realization that C is the most universal supported programming language, the language that is used to implement almost all other programming language (interpretters and compilers) or at least use it to bootstrap it. (IParse was originally written in C.) I also wanted to implement scannerless parsing instead of using a hand-code scanner as in IParse, based on experiments I did with introducing characters sets. During these experiments, I also encountered the need to be more flexable in constructing results of the parsing. IParse has a build-in implementation of abstract syntax tree (or abstract parse tree, as it is called within IParse). This also because I discovered that sometimes you want to deviate the abstract syntax tree from the parse grammar, such as the example of representing array declarations in IDL, which is kind similar to that of C. (As a side note: C# avoided this problem, by having an alternative syntax for declaring arrays.) Furthermore, I had developed a method for defining a grammar in IParse using code, instead of constructing it from a hard coded syntax tree. The idea was to make the parser algorithm agnostic to the data (by using a void pointer) and how it is constructed (by the use of function pointers). This gave me the idea to call it a 'raw' parser. In the past year, I did sometimes have a look at it, but most often I did not enough time to really get into it and make some progress. In the past week, I did set some time aside and also got the idea to make the implementation more self explanatory as a kind of educational tool to explain parsing by adding a narrative in comments. Doing this, already has led some improvements in the code. Interesting. The code can be found in the github repository RawParser.


Tuesday, December 31, 2019

New Years Eve

Because Tuesday is the day that the space of TkkrLab is open for visitors, and usually also the time that most members are visiting, I decided to spend New Years Eve at the space. Someone suggested to order some Chinese/Indonesian food, and I joined in. Several people had brought some oliebollen and drinks. Someone had brought a SodaStream and we produced some carbonated Rooibos thea. As usally, most people did their own thing. Some people played some card games. When one other member exclaimed that he had no idea where to start with Escape room: The Game, I decided to give him some help. After about two thirds of the game, I got bored and another member completed the game with him. I continued working on RawParser. We were not going to see much of the traditional fireworks from the space, from which we have a good view of a large part of the city from about nine meter above ground level, because of the heavy fog outside. Visibility dropped below 100 meters.


This months interesting links


Home | November 2019 | January 2020 | Random memories