Finding non-shortest paths between two points

I am currently working on a new project that is somewhat inspired by Tower Defence games. My aim is to randomly generate a “map” where everything will take place. Just to visualise things, I am using a Canvas element.

There are four main components at this stage:

• A start (red on the map)
• An end (yellow on the map)
• Walls that paths cannot go through (black)
• Paths

I very specifically do not want the shortest possible path, otherwise I would be using one of the many algorithms designed with that in mind. I wrote some JavaScript to try and brute-force every possible path and then pick one of median length of the outcomes. This worked on small maps but caused my browser tab to hang on larger ones.

I added some optimisations:

• Ending the recursion chain once a determined max length had been surpassed
• Ending the search if a single path of a perfect length had been found (may make this ±1 or so)

However, I’m still brute-forcing, and it’s honestly not great.

Here is an example of a generated map. A lot of things aren’t final and there’s currently nothing stopping a map from generating will walls blocking any path from the start to end.

Here are some relevant snippets from my code:

const canvasWidth = 1920
const canvasHeight = 720
const cellSize = 30

const wallCount = 350

const horizontalCells = canvasWidth / cellSize
const verticalCells = canvasHeight / cellSize

const idealPathLength = horizontalCells * 1.5
const pathLengthCancelPoint = horizontalCells * 3

class Position {
    constructor(x, y) {
        this.x = x
        this.y = y
        this.adjacent = []
    }
    
    add(position) {
        if (position instanceof Position) {
            this.adjacent.push(position)
        }
    }
}

function generateGraph() {
    const N = []
    for (let x = 0; x < horizontalCells; x++) {
        for (let y = 0; y < verticalCells; y++) {
            N.push(new Position(x, y))
        }
    }
    
    const inBounds = (x, y) => x >= 0 && x < horizontalCells && y >= 0 && y < verticalCells
    const isStart = (x, y) => x === startPosition.x && y === startPosition.y
    const isWall = (x, y) => wallPositions.filter(wp => wp.x === x && wp.y === y).length > 0
    const f = (x, y) => N.find(p => p.x === x && p.y === y)
    
    for (let i = 0; i < N.length; i++) {
        const pos = N[i]
        const {x, y} = pos
        for (let xM = -1; xM <= 1; xM++) {
            for (let yM = -1; yM <= 1; yM++) {
                if (xM === yM || Math.abs(xM - yM) === 2) continue
                const newCoords = [x + xM, y + yM]
                if (inBounds(...newCoords) && !isWall(...newCoords) && !isStart (...newCoords)) {
                    pos.add(f(...newCoords))
                }
            }
        }
    }
    
    return N
}

function clone(arr) {
    return [...arr]
}

const N = generateGraph()
const startPosition = N.find(p => p.x === startPosition.x && p.y === startPosition.y)
const validPaths = []

let idealPathFound = false

function traverse(position, path) {
    if (position === undefined) {
        position = startPosition
    }
    if (path === undefined) {
        path = []
    }
    path.push(position)
    if (position.x === gatePosition.x && position.y === gatePosition.y) {
        validPaths.push(clone(path))
        console.log('Found valid path', path)
        if (validPaths.length === idealPathLength) {
            idealPathFound = true
        }
        return
    }
    if (idealPathFound || path.length >= pathLengthCancelPoint) {
        return
    }
    position.adjacent.forEach(p1 => {
        if (path.filter(p2 => p2.x === p1.x && p2.y === p1.y).length === 0) {
            traverse(p1, clone(path))
        }
    })
}

function findPath() {
    traverse()

    let deviation = 0
    let filteredPaths = []
    do {
        filteredPaths = validPaths.filter(path => path.length >= idealPathLength - deviation && path.length <= idealPathLength + deviation)
        deviation++
    } while (filteredPaths.length === 0)
    const sortedPaths = filteredPaths.sort((a, b) => a.length - b.length)
    const chosenPath = sortedPaths[Math.floor(sortedPaths.length / 2)]
    
    console.log(chosenPath)
    
    ctx.lineWidth = cellSize / 2
    ctx.strokeStyle = '#c99e87'
    
    const offset = cellSize / 2
    for (let i = 0; i < chosenPath.length - 1; i++) {
        let {x: x1, y: y1} = chosenPath[i]
        let {x: x2, y: y2} = chosenPath[i + 1]
        ctx.beginPath()
        ctx.moveTo(x1 * cellSize + offset, y1 * cellSize + offset)
        ctx.lineTo(x2 * cellSize + offset, y2 * cellSize + offset)
        ctx.stroke()
    }
}

Path finding isn’t something I’ve done before and I’m attempting to learn this as I go but this is obviously not the way to go about it.

Without getting the absolute shortest path (unless it’s the only path), what should I be doing here? Thanks in advance.