Pathfinding and flood traversals

[justinkwaugh]

The current set of traversers are not sufficient for pathfinding or flooding to a range w/ obstacles. There are sort of two things needed that would make such things more easily doable.

1. A traverser which will perform breadth-first traversal
2. Which accepts a predicate closure to determine traversability

I created something that works for me, but it doesn't handle the cursor param appropriately as I did not need it

export function flood<T extends Hex>(options: FloodOptions): Traverser<T> {
    return function floodTraverser(createHex, _cursor) {
        const visitedHexes = new Map<number, T>()

        const startHex = createHex(options.start)
        const directions = startHex.isPointy ? POINTY_NEIGHBORS : FLAT_NEIGHBORS

        let depth = 0
        const queue: T[] = [startHex]
        visitedHexes.set(axialCoordinatesToNumber(startHex), startHex)

        while (queue.length > 0 && depth < options.range) {
            const numAtCurrentDepth = queue.length
            for (let i = 0; i < numAtCurrentDepth; i++) {
                const currentHex = queue.shift()!
                for (const direction of directions) {
                    const neighbor = createHex(neighborOf(currentHex, direction))
                    if (options.canTraverse && !options.canTraverse(neighbor)) {
                        continue
                    }
                    const neighborKey = axialCoordinatesToNumber(neighbor)
                    if (!visitedHexes.has(neighborKey)) {
                        visitedHexes.set(neighborKey, neighbor)
                        queue.push(neighbor)
                    }
                }
            }
            depth++
        }
        return [...visitedHexes.values()]
    }
}

/**
 * @category Traverser
 */
export interface FloodOptions {
    start: HexCoordinates
    range: number
    canTraverse?: (hex: Hex) => boolean
}

const POINTY_NEIGHBORS = [
    Direction.E,
    Direction.SE,
    Direction.SW,
    Direction.W,
    Direction.NW,
    Direction.NE
]
const FLAT_NEIGHBORS = [
    Direction.N,
    Direction.NE,
    Direction.SE,
    Direction.S,
    Direction.SW,
    Direction.NW
]

[flauwekeul]

Thanks for opening a ticket. I'll try to look into it in the coming weeks, but to be honest, Honeycomb has low priority for me...

It looks like you delimited the code with a single back tick, did you try delimiting with 3 back ticks?