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
|
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.
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.
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.
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
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:
- Schermo for Porro by Alessandro Mendini, 2014.
- Sinnoso for Maison Matisse by Alessandro Mendini, 2019.
- (Without title) by Alessandro Mendini, nitro lacquer on wood, 1986.
- (Without title) by Alessandro Mendini, nitro lacquer on wood, 1990.
- Photograph of Goetheanum, Dornach designed by Rudolf Steiner.
- Portret van Alessandro Mendini by Han Meilin, 2010.
- With suprematistisch huis by Kazimir Malevich, 1920.
- Stilemi enigmatici by Alessandro Mendini, 2015.
We also saw the museum collection. Of which I liked the following works:
- Kerkje te Oostrum by Johan Dijkstra, 1922.
- Meisje aan de pomp by Matthijs Maris, 1872.
- Mijn atelier by Lawrence Alma-Tadema, 1867.
- Figuren op het strand by Isaac Israës, about 1925.
- Jahresteller 1981 for Rosenthal (one of 2500) by Morandini, 1980.
- Job Hansen by Jan Altink, 1922-23.
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.
Books
At 17:03, I bought the following two books from charity shop Het Goed:
- Alchemie van de liefde written by Lisette Thooft in Dutch and
published by Scriptum in 2008, ISBN:9789055945832, for € 1.80.
- Het ware geluk written by Lucius Annaeus Seneca, translated by
Vincent Hunink from De vita beata (written in Latin) to Dutch,
published by Singel Uitgeverijen in 2013
ISBN:9789025301538, for € 2.90.
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.
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).
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.
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.
'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 (interpreters 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.
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
