Javascript решает лабиринт с движущейся конечной позицией и осями X и Y (начальные и конечные координаты являются известными значениями)

Question

Математика не моя огромная сила.У меня есть сетка с НЕИЗВЕСТНЫМИ препятствиями (показана черным цветом), и конечное положение лабиринта (красного цвета) может быть либо неподвижным, либо движущимся.

Мне нужен начальный квадрат (желтый), чтобы иметь возможностьперемещайтесь вокруг объектов и находите красный квадрат.

Координаты для начального квадрата и конечного квадрата всегда известны (то есть желтый не должен «находить» красный, он знает свою позицию и просто должен перейти кэто, красный движется произвольно, независимо от желтого.)

Я работал над этим в течение нескольких дней, но потерпел неудачу.

Мне удалось получить желтый квадрат, чтобы найтикрасный без каких-либо препятствий на пути (это было тривиально).

Мне удалось сделать действительно базовое обнаружение столкновений, но оно было очень примитивным и работало только в очень специфических условиях.

Я посмотрел в Интернете много алгоритмов.Тем не менее, все они, кажется, знают гирду заранее (например, матрицу массива).

Этот код буквально просто перемещает игрока вдоль оси X, а затем по Y. Если обнаружено «столкновение», онопросто провалиться до следующего условия и попытаться пойти другим путем.(Как я уже сказал, он работает в очень специфических условиях.)

Он не работает, когда объекты выбрасываются в смесь.

Я не уверен, как это поможет.Делать это таким образом совершенно бесполезно.Он нуждается в реальном алгоритме общего назначения.

Я недавно искал алгоритм поиска A *, так как он лучше всего подходит для того, что мне нужно, но опять-таки кажется, что вам нужно передать карту.

Краткий обзор: сокет будет отправлять обновления положения монстра и игрока (X, Y).Обе позиции обновляются.

Когда игрок перемещается, через веб-сокет отправляется команда.

Веб-сокет получает новое сообщение с указанием, где находятся новые координаты для объекта.(Опять же, это не очень помогает в решении проблемы.)

ws = new WebSocket('wss://localhost/ws')

var monsters = {}
var currentPlayer = {
    position: {}
};

monstersToLog = [
    'Windsor Rat',
    'Bonecrusher',
    'Windsor Spider',
    'Windsor Bat',
    'Cursed Lich',
    'Forest Oni',
    'Inferno Skeleton',
    'Brown Bear',
    'Kreme',
    'Amon'
]

ws.onmessage = function(event) {
    let data = JSON.parse(event.data)
    entity = data.entityId
    x = data.x
    y = data.y
    orientation = data.o
    dataType = data.$type


    if(dataType.includes('EntitySpawn')){
        if(data.name === 'SteamyRayVaun') {
            currentPlayer.entityId = data.entityId
            console.log("Current Player: ", data);
        }

        if(monstersToLog.includes(data.name)) {
            console.log("Added Bear:", data)
            monsters[data.entityId] = data;
        }
    }

    if(dataType.includes('EntityDestroy')){
        if( monsters[data.entityId]){
            console.log("Removed Monster:", data)
            delete monsters[data.entityId]
        }

    }

    if(dataType.includes('EntityPositionUpdate')){
        if(data.entityId == currentPlayer.entityId) {
            currentPlayer.position.x = data.x;
            currentPlayer.position.y = data.y;
        } else {    
            if(monsters[data.entityId]){
                monsters[data.entityId] = data
            }

        }
    }
};

(function autoHunt (i) {     
    setTimeout(function () { 
        const monsterIDs = Object.keys(monsters)

        if(monsterIDs.length > 0) {
            let currentMonster = monsters[monsterIDs[0]]
            if((currentPlayer.position.x > currentMonster.x) && (diff(currentPlayer.position.x, currentMonster.x) !== 1) && !collisionDetection(currentPlayer.position.x, lastPositionx, currentPlayer.position.y, lastPositiony,'Left')){
                lastPositionx = currentPlayer.position.x
                lastPositiony = currentPlayer.position.y
                console.log('POSITION UPDATe', {lastPositionx, lastPositiony}, 'LEFT')
                move('Left',1)
            } else if ((currentPlayer.position.x < currentMonster.x) && (diff(currentPlayer.position.x, currentMonster.x) !== 1) && !collisionDetection(currentPlayer.position.x, lastPositionx, currentPlayer.position.y, lastPositiony, 'Right')){
                lastPositionx = currentPlayer.position.x
                lastPositiony = currentPlayer.position.y
                console.log('POSITION UPDATe', {lastPositionx, lastPositiony}, 'RIGHT')
                move('Right',1)
            } else if((currentPlayer.position.y > currentMonster.y) && (diff(currentPlayer.position.y, currentMonster.y) !== 1) && !collisionDetection(currentPlayer.position.y, lastPositiony, currentPlayer.position.x, lastPositionx, 'Down')){                 
                lastPositionx = currentPlayer.position.x
                lastPositiony = currentPlayer.position.y
                console.log('POSITION UPDATe', {lastPositionx, lastPositiony}, 'DOWN')
                move('Down',1)
            } else if((currentPlayer.position.y < currentMonster.y) && (diff(currentPlayer.position.y, currentMonster.y) !== 1)&& !collisionDetection(currentPlayer.position.y, lastPositiony, currentPlayer.position.x, lastPositionx, 'Up')){
                lastPositionx = currentPlayer.position.x
                lastPositiony = currentPlayer.position.y
                console.log('POSITION UPDATe', {lastPositionx, lastPositiony}, 'UP')
                move('Up',1)
            }
        }

        autoHunt(true);  
    }, 300)
})(true); 

function move(direction, steps) {
    ws.send(JSON.stringify({"$type":"de.fky.model.PlayerChangeOrientation","orientation":3}));             
    ws.send(JSON.stringify({"$type":`de.fky.model.PlayerMove${direction}`}));
}

function collisionDetection(x, lastx, y, lasty){
    let collision = false
    if((x === lastx) && (y == lasty)){
        collision = true
    }

    if(collision){
        lastPositionx = 0
        lastPositiony = 0
    } 

    return collision
}