MazeGenerator2.kt

import kotlin.random.Random

/*

[ 1]:  ***************
[ 2]:    ### ##### ##*
[ 3]:  * #     #     *
[ 4]:  * # # # # ### *
[ 5]:  *   ###   ##  *
[ 6]:  * # # # # ### *
[ 7]:  * #     #     *
[ 8]:  * ### ##### ##*
[ 9]:  * #     #     *
[10]:  * # # # # #   *
[11]:  *   ###   ### *
[12]:  * # # # # #   *
[13]:  * #     #     *
[14]:  * ### ###      
[15]:  ***************
 

Air/Wall Ratio = 102.0/69.0=1.4782609

 */


const val mazeWidth = 15
const val mazeHeight = 15
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 - 1, 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 = randomGenerator.nextDouble(MazeInfo.MIN_AIR_COUNT, MazeInfo.MAX_AIR_COUNT + 1)
    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>>) {
    val innerMazeSize = mazeInfo.innerMazeSize

    //if (airRemoved > 0) System.out.println("Manuel air count balance : ${mazeInfo.innerMazeAirCount} , $airRemoved")


    var airCount = Int.MAX_VALUE
    var combinedRandomMiniMazes: MutableList<MutableList<String>> = mutableListOf(mutableListOf())
    while (airCount > mazeInfo.innerAirCount) {
        combinedRandomMiniMazes = generateAndCombineRandomMiniMazes(innerMazeSize.width, innerMazeSize.height)
        airCount = combinedRandomMiniMazes.sumBy { row -> row.let { it.sumBy { col -> if (col.isBlank()) 1 else 0 } } }
        System.out.println("airCount : ${mazeInfo.innerAirCount} : $airCount")
    }

    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()) MazeInfo.INNER_AIR else MazeInfo.INNER_WALL }
        }
    }
    //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 = innerMazeSize.height

    val innerMazeAirCount = innerAirCount - airEntryStepsCount

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

    companion object Constants {
        const val OUTER_WALL = 2
        const val INNER_WALL = 1
        const val INNER_AIR = 0
        const val MIN_AIR_COUNT = 1.2
        const val MAX_AIR_COUNT = 1.5
    }

    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

val miniMaze1 = arrayOf(
    arrayOf("#", "#", "#", " ", "#", "#", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", " ", "#", " ", " ", " ", "#"),
    arrayOf(" ", " ", "#", "#", "#", " ", " "),
    arrayOf("#", " ", "#", " ", " ", " ", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", "#", "#", " ", "#", "#", "#")
)

val miniMaze2 = arrayOf(
    arrayOf("#", "#", "#", " ", "#", "#", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", " ", "#", "#", "#", " ", "#"),
    arrayOf(" ", " ", "#", "#", " ", " ", " "),
    arrayOf("#", " ", "#", "#", "#", " ", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", "#", "#", " ", "#", "#", "#")
)

val miniMaze3 = arrayOf(
    arrayOf("#", "#", "#", " ", "#", "#", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", " ", "#", " ", " ", " ", "#"),
    arrayOf(" ", " ", "#", "#", "#", " ", " "),
    arrayOf("#", " ", " ", " ", "#", " ", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", "#", "#", " ", "#", "#", "#")
)

//7x7
val miniMaze4 = arrayOf(
    arrayOf("#", "#", "#", " ", "#", "#", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", " ", "#", " ", "#", " ", "#"),
    arrayOf(" ", " ", "#", "#", "#", " ", " "),
    arrayOf("#", " ", "#", " ", "#", " ", "#"),
    arrayOf("#", " ", " ", " ", " ", " ", "#"),
    arrayOf("#", "#", "#", " ", "#", "#", "#")
)

//5x5
val allMiniMazes = arrayOf(
    miniMaze1,
    miniMaze2,
    miniMaze3,
    miniMaze4
)

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) {
                    if (outerY == height - 1) {
                        elements = emptyList()
                    } else {
                        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