MazeGenerator.kt

import kotlin.random.Random

/*

[ 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]:  * ##     ###     ##   #   #   ##   #   #   #      #   ##   #      # #  *
[32]:  *     #      ##    ###  # ### #   #   #  ##   #### ###    #   ####     *
[33]:  *  # ##  ##  ##  ## #       #  # ### ##  ### ## #   #  # ### ## #      *
[34]:  * ##  ## ## #### ## # ## ## # ##  ##  # ####  # # # # ##  ##  # # ## # *
[35]:  *     #       #   #   ##   #      #        #   #   #     ###      #
[36]:  ************************************************************************


Air/Wall Ratio = 1359.0/1023.0=1.3284458

 */


const val mazeWidth = 72
const val mazeHeight = 36
val randomGenerator = Random(System.currentTimeMillis())

fun main() {
    generateMaze().print()
}

//region Maze Generator

private fun generateMaze(): Array<Array<Int>> {
    val size = MazeInfo.Size(mazeWidth, mazeHeight)
    val innerMazeSize = MazeInfo.Size(mazeWidth - 2 - 2, mazeHeight - 2)
    val entryStep = MazeInfo.Step(1, 0)
    val exitStep = MazeInfo.Step(mazeHeight - 2, mazeWidth - 1)
    val outerWall = MazeInfo.OuterWall(0, 0, mazeHeight, mazeWidth)

    val airToWallRatio = 1.5//randomGenerator.nextDouble(1.2, 1.5)
    val innerWallCount = (innerMazeSize.count / (airToWallRatio + 1)).toInt()
    val innerAirCount = innerMazeSize.count - innerWallCount

    val mazeInfo = MazeInfo(
        size,
        innerMazeSize,
        entryStep,
        exitStep,
        outerWall,
        innerWallCount,
        innerAirCount
    )

    val maze = generateOuterMaze(mazeInfo)

    generateAndAddInnerMaze(mazeInfo, maze)

    return maze
}

fun generateOuterMaze(info: MazeInfo): Array<Array<Int>> {

    fun generateValue(info: MazeInfo, y: Int, x: Int): Int {
        if (info.entryStep.equals(y, x)
            || info.exitStep.equals(y, x)
            || info.isEntryRoad(y, x)
        ) return MazeInfo.INNER_AIR

        if (info.outerWall.contains(y, x)) return MazeInfo.OUTER_WALL

        return MazeInfo.INNER_AIR
    }

    val array = Array(info.size.height) { y -> Array(info.size.width) { x -> generateValue(info, y, x) } }
    // array.print()
    return array
}

private fun generateAndAddInnerMaze(mazeInfo: MazeInfo, maze: Array<Array<Int>>) {
    var airAdded = 0
    var airRemoved = 0
    val innerMazeSize = mazeInfo.innerMazeSize
    val combinedRandomMiniMazes = generateAndCombineRandomMiniMazes(innerMazeSize.width, innerMazeSize.height)
    for (y in 0 until combinedRandomMiniMazes.size) {
        for (x in 0 until combinedRandomMiniMazes[y].size) {
            maze[y + 1][x + 2] = combinedRandomMiniMazes[y][x].run {
                if (isBlank() && airAdded <= mazeInfo.innerMazeAirCount) {
                    airAdded++
                    MazeInfo.INNER_AIR
                } else {
                    if (airAdded > mazeInfo.innerMazeAirCount) {
                        airRemoved++
                    }
                    MazeInfo.INNER_WALL
                }
            }
        }
    }
    if (airRemoved > 0) System.out.println("Manuel air count balance : ${mazeInfo.innerMazeAirCount} , $airRemoved")
    //combinedRandomMiniMazes.print()
}

data class MazeInfo(
    val size: Size,
    val innerMazeSize: Size,
    val entryStep: Step,
    val exitStep: Step,
    val outerWall: OuterWall,
    val innerWallCount: Int,
    val innerAirCount: Int
) {

    private val airEntryStepsCount = ((size.height - 2) * 2) + 2

    val innerMazeAirCount = innerAirCount - airEntryStepsCount

    fun isEntryRoad(y: Int, x: Int) = (x == 1 || x == size.width - 2) && y != 0 && y != size.height - 1

    companion object Constants {
        const val OUTER_WALL = 2
        const val INNER_WALL = 1
        const val INNER_AIR = 0
    }

    data class Size(val width: Int, val height: Int) {
        val count = width * height
    }

    data class Step(val y: Int, val x: Int) {
        fun equals(y: Int, x: Int) = equals(Step(y, x))
    }

    data class OuterWall(val y: Int, val x: Int, val height: Int, val width: Int) {
        fun contains(y: Int, x: Int) = (x == 0 || x == width - 1) || (y == 0 || y == height - 1)
    }
}

private fun Array<Array<Int>>.print() {
    var airCount = 0f
    var wallCount = 0f
    forEachIndexed { y, ar ->
        var line = "[${"%2d".format(y + 1)}]:  "
        ar.forEach { value ->
            line += when (value) {
                2 -> "*"
                1 -> {
                    wallCount++
                    "#"
                }
                0 -> {
                    airCount++
                    " "
                }
                else -> "?"
            }
        }
        println(line)
    }
    println(" \n")
    println("Air/Wall Ratio = $airCount/$wallCount=${airCount / wallCount}")
}

//endregion

//region MiniMazes

//5x5
val miniMaze1 = arrayOf(
    arrayOf("#", " ", "#", " ", " "),
    arrayOf(" ", " ", " ", " ", "#"),
    arrayOf("#", "#", "#", " ", "#"),
    arrayOf("#", " ", "#", " ", " "),
    arrayOf("#", " ", "#", " ", "#")
)
//5x5
val miniMaze2 = arrayOf(
    arrayOf("#", "#", " ", " ", "#"),
    arrayOf("#", " ", " ", " ", " "),
    arrayOf(" ", " ", "#", "#", "#"),
    arrayOf(" ", " ", "#", "#", "#"),
    arrayOf("#", " ", "#", " ", "#")
)
//5x5
val miniMaze3 = arrayOf(
    arrayOf("#", " ", "#", " ", " "),
    arrayOf(" ", " ", " ", " ", "#"),
    arrayOf(" ", "#", "#", "#", " "),
    arrayOf(" ", " ", "#", " ", " "),
    arrayOf("#", " ", "#", " ", "#")
)
//5x5
val miniMaze4 = arrayOf(
    arrayOf("#", "#", " ", "#", "#"),
    arrayOf(" ", " ", " ", " ", "#"),
    arrayOf("#", " ", "#", " ", "#"),
    arrayOf("#", " ", " ", " ", " "),
    arrayOf("#", "#", " ", "#", "#")
)
//5x5
val miniMaze5 = arrayOf(
    arrayOf("#", " ", "#", "#", "#"),
    arrayOf(" ", " ", " ", "#", "#"),
    arrayOf("#", " ", " ", " ", " "),
    arrayOf("#", " ", " ", "#", "#"),
    arrayOf("#", "#", " ", "#", "#")
)
//5x5
val miniMaze6 = arrayOf(
    arrayOf("#", "#", " ", " ", "#"),
    arrayOf(" ", "#", " ", " ", " "),
    arrayOf(" ", " ", " ", "#", "#"),
    arrayOf("#", " ", " ", "#", "#"),
    arrayOf("#", " ", "#", "#", "#")
)
//5x5
val miniMaze7 = arrayOf(
    arrayOf("#", "#", " ", "#", "#"),
    arrayOf("#", "#", " ", " ", " "),
    arrayOf(" ", " ", " ", " ", "#"),
    arrayOf(" ", "#", " ", "#", "#"),
    arrayOf("#", "#", " ", " ", "#")
)
//5x5
val allMiniMazes = arrayOf(
    miniMaze1,
    miniMaze2,
    miniMaze3,
    miniMaze4,
    miniMaze5,
    miniMaze6,
    miniMaze7
)

private val getARandomMiniMaze get() = allMiniMazes[randomGenerator.nextInt(allMiniMazes.size)]

//TODO can be optimized 
private fun generateAndCombineRandomMiniMazes(width: Int, height: Int): MutableList<MutableList<String>> {
    val result = mutableListOf<MutableList<String>>()
    while (result.isEmpty() || result[0].size < width) {
        var outerY = 0
        var innerY = 0
        var miniMaze = getARandomMiniMaze
        while (outerY < height) {
            if (innerY == miniMaze.size) {
                miniMaze = getARandomMiniMaze
                innerY = 1
            }
            if (result.size <= outerY || result[outerY].isEmpty()) {
                result.add(miniMaze[innerY].toMutableList())
            } else {
                var elements = miniMaze[innerY].toMutableList().drop(1)
                if (result[outerY].size + elements.size > width) {
                    elements = elements.take(elements.size - (result[outerY].size + elements.size - width))
                }
                result[outerY].addAll(elements)
            }
            innerY++
            outerY++
        }
    }
    return result
}

private fun MutableList<MutableList<String>>.print() {
    System.out.println("${get(0).size}:${size}")

    forEach {
        it.forEach {
            System.out.print(it)
        }
        System.out.println()
    }
}

//endregion