Pathfinding and flood traversals
justinkwaugh opened this issue · 1 comments
justinkwaugh commented
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.
- A traverser which will perform breadth-first traversal
- 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 commented
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?