daniberg.com

posts github chip8 rtc guitar

Maze Search

This post was inspired by the book Classic Computer Science Problems in Java. In chapter two, the algorithms DFS, BFS, and A* are introduced. I thought it would be fun to implement the examples with a small twist: I instrumented the code to emit logs that describe how each algorithm performs its search. A short Rust program then reads these logs and renders an animation of the search process.

DFS	BFS	A*

The source code is available here.

The implementation of each algorithm differs in the data structure it requires. DFS uses a stack, BFS uses a queue, while A* uses a priority queue and an heuristic function.

DFS

fun  dfs(initial: T, goalTest: (T) -> Boolean, successors: (T) -> List): Node? {
    val frontier: Stack> = Stack()
    frontier.push(Node(initial, null))
    val explored: MutableSet = mutableSetOf()
    explored.add(initial)

    while (!frontier.isEmpty()) {
        val currentNode: Node = frontier.pop()
        val currentState = currentNode.state

        if (goalTest(currentState)) {
            return currentNode
        }

        for (child in successors(currentState)) {
            if (!explored.contains(child)) {
                explored.add(child)
                frontier.push(Node(child, currentNode))
            }
        }
    }

    return null
}

BFS

fun  bfs(initial: T, goalTest: (T) -> Boolean, successors: (T) -> List): Node? {
    val frontier: Queue> = LinkedList()
    frontier.offer(Node(initial, null))
    val explored: MutableSet = mutableSetOf()
    explored.add(initial)

    while (!frontier.isEmpty()) {
        val currentNode = frontier.poll()
        val currentState = currentNode.state

        if (goalTest(currentState)) {
            return currentNode
        }

        for (child in successors(currentState)) {
            if (!explored.contains(child)) {
                explored.add(child)
                frontier.offer(Node(child, currentNode))
            }
        }

    }
    return null
}

A*

fun  astar(initial: T, goalTest: (T) -> Boolean, successors: (T) -> List, heuristic: (T) -> Double): Node? {
    val frontier: PriorityQueue> = PriorityQueue()
    frontier.offer(Node(initial, null, 0.0, heuristic(initial)))
    val explored: MutableMap = mutableMapOf()
    while (!frontier.isEmpty()) {
        val currentNode: Node = frontier.poll()
        val currentState: T = currentNode.state
        if (goalTest(currentState)) {
            return currentNode
        }
        for (child in successors(currentState)) {
            // hardcoded cost function as 1
            val newCost: Double = currentNode.cost + 1
            val exploredCost = explored[child]
            if (exploredCost == null || exploredCost > newCost) {
                explored[child] = newCost
                frontier.offer(Node(child, currentNode, newCost, heuristic(child)))
            }
        }
    }
    return null
}

The terminal animation is written in Rust using the ncurses library. I used asciinema and agg to generate the animated GIFs.

Instructions for generating the mazes, logs and animations can be found in the project's README.