Saturday, 31 March 2018

ASCII Art Mazes and Playing with Kotlin

I decided to play around with Kotlin for fun on a home project that interested me.  At many points during the development I was thankful that I was using Kotlin and not Java, here's a few notes that explain why.  All the code for this page can be found here: https://github.com/phillbarber/kotlin-maze-demo

The Problem

Given a simple 2D maze inputted in an "ASCII art" format, write some kotlin code that will plot a route from the Start to Finish.

In other words, given this...

############################################
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #         F             #
#                  #                       #
#                  #                       #
#                  #                       #
#    S             #                       #
#                  #                       #
#                  #                       #
#                                          #
#                  #                       #
#                  #                       #
#                  #                       #
############################################

Output this...

############################################
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #         F             #
#                  #         .             #
#                  #         .             #
#                  #         .             #
#    S             #         .             #
#    .             #         .             #
#    .             #         .             #
#    .........................             #
#                  #                       #
#                  #                       #
#                  #                       #
############################################

Approach

Tried to be disciplined and use a TDD approach from the start.

Implementation

As soon as I started, I had an idea of how I wanted to achieve this.  I wanted to use recursion.  I remember learning recursion as a student and finding it strangely fascinating.  It seemed so powerful with such a small amount of code.  Also, it's one of these techniques I never seem to use at work.

First acceptance test - The `is` issue

I like using hamcrest matchers in my test as I think it makes tests closer to plain English (more readable).  A very common method used with hamcrest is CoreMatchers.is().  Unfortunately, the word "is" is a keyword in kotlin but can be escaped for compatibility with methods that happen to clash by name.  This is great, but in my opinion makes the code look a little ugly as shown below...

assertThat(mazeAsStringWithRoute, `is`(expectedMazeWithRoute)) 

A quick google for some alternatives brought me here where it was pointed out that static methods can be aliased on import in the following way:

import org.hamcrest.CoreMatchers.is as Is

This is purely a styling issue but I chose to import as _is.  It looks better in my eyes (possibly from enjoying using the wonderful underscore.js library).

Multi-line (raw) Strings - Hooray!

At first I stored my mazes in .txt files in my test resources directory.  Then I had to write some code to load the file into a String.  Converting a file into a String always seems much harder than it should in Java.  To do it succinctly you have to import a library (e.g. Apache Commons IO), even then I'm forced to think of directories and classpaths etc etc as my first attempt never works!  Once I had imported Apache Commons and got it working, I was left with the following code.

FileUtils.readFileToString( File(javaClass.getClassLoader().getResource("expected-super-simple-solvable-maze-with-route.txt").file), CHARSET)

A bit of a pain, but at least my maze files are easily viewable.  One alternative would be to store the mazes in a String in Java as follows

String maze = "#########\n" +
              "# S  F  #\n" +
              "#########\n" +;

...over simple example

This is obviously very ugly and fiddly.  However, with Kotlin this becomes very easy thanks to multi-line Strings:

val maze = """
########## 
# S  F   #
##########"""


I think it's great that Kotlin supports multi-line (or rather raw) Strings. However, perhaps the more relevant point here is "Why does Java not support it?".  It looks like it might be coming to Java if JEP 326 gets its way - let's hope it does.

Extension methods

Although the multi-line Strings improved things, I did have a slight issue.  To format the maze nicely, I had to introduce a newline character so that everything would line up.  To remove this from each String I used an extension function.

In Java it would have just been a static method, but an extension method did make the code seem cleaner...

val maze = """
##########
# S  F   #
##########""".removeFirstCharacter()

fun String.removeFirstCharacter(): String{
    return this.substring(1, this.length);
}

Data classes

The pain of creating Java Beans isn't too high in Java when using a good IDE such as IntelliJ IDEA.  I tend to create my Java Beans with their attributes and just hit Alt+Enter to insert my constructor and my getters.  Builders can definitely be a pain however as I don't think I've ever found a nice shortcut or plugin to create/maintain them.  Regardless of how easy it is to create this code, you're still left with a lot of it about!  Data classes in Kotlin make this so much nicer.  They provide equals(), toString() and no real need for builders due to the nice syntax of the language (See this... How to create a builder in kotlin? - Don't!).

How Immutable to be?

Whilst trying to make all of my objects nice and immutable, I hit a problem.  I wanted to created a Maze from my ASCII art input as shown above.  Each Maze consisted of a List of a List of Cells.  The original idea was to have a Cell consist of immutable attributes (i.e. vals and not vars) as follows:-

data class Cell(val type: Type,
                val xAxis: Int,
                val yAxis: Int,
                val down: Cell,
                val up: Cell,
                val left: Cell,
                val right: Cell)

Given that a Cell consisted of four other Cells (i.e. a recursive data structure), you couldn't create a cell until you have created every other cell required for the entire maze.  This didn't seem possible.  One option would be to create a "half baked" Cell which had it's sibling cells missing (null) at first.  From that, a copy could be made each time a new sibling needed to be set.  I considered this, but thought that it was more complex than just having a mutable Cell class as follows:

data class Cell(val type: Type,
                val xAxis: Int,
                val yAxis: Int,
                var down: Cell? = null,
                var up: Cell? = null,
                var left: Cell? = null,
                var right: Cell? = null)

This design made it actually possible for me to write the code (which was a good sign!).

Parsing the ASCII and generating a Maze


The ASCII art was parsed a line at a time creating the List of List of Cells.  The first parse would create Cells with just the type, xAxis and yAxis set.

Cell(   type = fromChar(character.toChar()), 
        xAxis = xIndex, 
        yAxis = yIndex)

Once complete, the Cells would have their sibling Cells set by the addDownUpLeftRightToCells method.

private fun addDownUpLeftRightToCells(gridOfRows: List<List<Cell>>) {
    gridOfRows.forEach{ rowOnYAxis ->        rowOnYAxis.forEach { cell ->            
            cell.down = getCellByCoordinates(gridOfRows, cell.yAxis + 1, cell.xAxis)
            cell.up = getCellByCoordinates(gridOfRows, cell.yAxis - 1, cell.xAxis)
            cell.left = getCellByCoordinates(gridOfRows, cell.yAxis, cell.xAxis - 1)
            cell.right = getCellByCoordinates(gridOfRows, cell.yAxis, cell.xAxis + 1)
        }    }
}

Solve the problem

With the data structure in place, now the code to solve the maze could actually be written.

This ended up being pretty simple!

private fun getFinish(cell: Cell?, route: MutableList<Cell>): List<Cell> {
    if (route.filter { cell -> cell.type == Type.Finish }.any()){
        return route;
    }
    if (cell != null){
        route.add(cell)
        if (cell.type == Type.Finish){
            return route;
        }
        if (shouldVisitCell(cell.down, route)){
            getFinish(cell.down, route);
        }

        if (shouldVisitCell(cell.right, route)){
            getFinish(cell.right, route);
        }
        if (shouldVisitCell(cell.left, route)){
            getFinish(cell.left, route);
        }
        if (shouldVisitCell(cell.up, route)){
            getFinish(cell.up, route);
        }
    }
    return route;
}

This produced a solution....

############################################
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #.........F             #
#                  #.......................#
#                  #.......................#
#                  #.......................#
#    S             #.......................#
#    .             #.......................#
#    .             #.......................#
#    .            .........................#
#    ..............#.......................#
#    ..............#.......................#
#    ..............#.......................#
############################################

...but a very bad one!

Final Thoughts

This was always going to be a very simplistic route finder as shown by the "solved" maze above.  I think it would be great fun to extend this and use some AI concepts I was taught back at Uni.    This was a fun task and made more fun with Kotlin.  



No comments:

Post a Comment