A*

class AStar2(val size: Int) {

    enum class Data {

        WALL,
        NONE,
        PATH,

    }

    enum class Move(private val dX: Int, private val dY: Int) {

        N(-1, 0),
        S(1, 0),
        E(0, 1),
        W(0, -1),

        NW(-1, -1),
        NE(-1, 1),
        SW(1, -1),
        SE(1, 1);


        fun move(node: Node, grid: Grid): Node? {
            return try {
                grid[node.x + dX, node.y + dY]
            } catch (ex: Exception) {
                null
            }
        }

    }

    data class Node(val x: Int, val y: Int) {

        var f = 0
        var g = 0
        var h = 0

        var d: Data = Data.NONE
        var p: Node? = null

    }

    data class Grid(val size: Int) {

        private val nodes = Array(size) { x ->
            Array(size) { y ->
                Node(x, y)
            }
        }


        operator fun get(x: Int, y: Int): Node {
            return nodes[x][y]
        }


        fun getRow(y: Int): List<Node> {
            return nodes.map { it[y] }
        }

        fun getCol(x: Int): List<Node> {
            return nodes[x].toList()
        }

    }

    val s: Node
    val e: Node

    val grid = Grid(size)

    init {
        grid.getRow(0).forEach {
            it.d = Data.WALL
        }
        grid.getCol(0).forEach {
            it.d = Data.WALL
        }

        grid.getRow(size - 1).forEach {
            it.d = Data.WALL
        }
        grid.getCol(size - 1).forEach {
            it.d = Data.WALL
        }


        val rS = (random() * size).toInt()
        val rE = (random() * size).toInt()

        s = grid[0, rS]
        e = grid[size - 1, rE]

        s.d = Data.NONE
        e.d = Data.NONE


        for (x in 1 until size - 1) {
            for (y in 1 until size - 1) {
                if (random() >= 0.30) continue
                grid[x, y].d = Data.WALL
            }
        }
    }

    fun exec() {

        val o = sortedSetOf<Node>(compareBy { it.f })
        val c = mutableSetOf<Node>()

        o += s

        while (o.isNotEmpty()) {
            val n = o.first()

            o -= n
            c += n

            if (n == e) {
                return println("Found path, next")
            }

            val next = Move.values().mapNotNull { it.move(n, grid) }.filter { it.d == Data.NONE && it !in c }

            next.forEach {

                it.g = n.g + 1
                it.h = dist(it, e)
                it.f = it.g + it.h
                it.p = n

                o += it
            }
        }
    }

    fun show() {
        println()
        for (y in 0 until size) {
            for (x in 0 until size) {
                val char = when (grid[x, y].d) {
                    Data.NONE -> '░'
                    Data.PATH -> '▒'
                    Data.WALL -> '▓'
                }
                print(char)
            }
            print("\n")
        }
        println()
    }

    fun path(): List<Node> {
        var p: Node? = e
        return generateSequence { p?.let { p = it.p; it } }.toList().reversed()
    }

    fun dist(a: Node, b: Node): Int {
        return abs(a.x - b.x) + abs(a.y - b.y)
    }

    companion object {

        @JvmStatic
        fun main(args: Array<String>) {
            val star = AStar2(20)
            star.show()
            star.exec()

            star.path().forEach { it.d = Data.PATH }

            star.show()
        }

    }

}