Как улучшить производительность лабиринта на основе DFS? - PullRequest
Новая
       37

Как улучшить производительность лабиринта на основе DFS?

0 голосов
/ 05 февраля 2020

Я написал игру, основанную на JS и алгоритме DFS. Это похоже на pacman, только компьютер и игрок пытаются получить как можно больше золотых монет.

Я использую DFS, чтобы вычислить путь компьютера к монете, затем с помощью setTimeout инициализирую путь. Если игрок раньше брал монеты, он пересчитывает путь к следующей монете.

Дело в том, что каждый раз, когда пользователь берет монету, компьютеру требуется слишком много времени sh для вычисления новый путь, особенно если он берет несколько подряд. в результате компьютер застревает в одном и том же положении.

Kinda 80-е выглядят одинаково по производительности игры ...

Код гораздо больше, но ниже приведены основные функции. Как мне улучшить производительность этой игры?

// Вот код, генерирующий путь DFS 


checkPath = (rowS, colS, rowM, colM, matrix)=>{

        if (rowS < 0 || colS < 0 || rowS > this.row || colS > this.col) return false
        if(matrix[rowS][colS] == 'b' || matrix[rowS][colS] == '$' || matrix[rowS][colS]== '2') return false

        matrix[rowS][colS] = '$'

        this.printAnyMatrix(matrix)

        if (rowS == rowM && colS== colM){
            this.compPath.unshift({'row': rowS, 'col': colS})
            return true  
        } 

        if (this.checkPath(rowS-1, colS, rowM, colM, matrix)){
            this.compPath.unshift({'row': rowS, 'col': colS})
            return true  
        } 
        if (this.checkPath(rowS, colS+1, rowM, colM, matrix)){
            this.compPath.unshift({'row': rowS, 'col': colS})
            return true  
        }       
        if (this.checkPath(rowS+1, colS, rowM, colM, matrix)){
            this.compPath.unshift({'row': rowS, 'col': colS})
            return true  
        }      
        if (this.checkPath(rowS, colS-1, rowM, colM, matrix)) {
            this.compPath.unshift({'row': rowS, 'col': colS})
            return true  
        }

        this.printAnyMatrix(matrix)
        console.log('false')

        return false

    }

// А вот функция компьютера, она вызывается каждый раз, когда компьютер получает к монете или к тому, что игрок взял монету. 


const getClosestCoin = function (location, goldMap) {
    let closestCoin = goldMap[0]
    closestCoin.distance = Math.abs(goldMap[0].row - location.row) + Math.abs(goldMap[0].col - location.col)

    for (let i = 0; i < goldMap.length; i++) {
        goldMap[i].distance = Math.abs(goldMap[i].row - location.row) + Math.abs(goldMap[i].col - location.col)     

        if (goldMap[i].distance < closestCoin.distance){
            closestCoin = goldMap[i]
            closestCoin.goldIndex = i
        }
    }
    return closestCoin
}

const computer = function(GoldRushBoard, clearTimeoutArry){
    let rowM = GoldRushBoard.row +1
    let colM = GoldRushBoard.col +1
    let location = {row:GoldRushBoard.player1.row, col:GoldRushBoard.player1.col}
    let closestCoin = {}
    let path = GoldRushBoard.compPath = []

    GoldRushBoard.goldMap = []
    let matrixCopy = copyMatrix(GoldRushBoard.matrix, GoldRushBoard.goldMap)
    if(GoldRushBoard.goldMap.length==0) return

    closestCoin = getClosestCoin(location, GoldRushBoard.goldMap)
    GoldRushBoard.checkPath(location.row, location.col, closestCoin.row, closestCoin.col, matrixCopy)

    for (let i = 0; i < path.length-1; i++) {

        let k = i

        let setTimeoutMove = setTimeout(function(){
            console.log('count ', k);

            if(GoldRushBoard.matrix[path[k+1].row][path[k+1].col]=='c'){
                GoldRushBoard.player1.score ++
                Render.updateScore(GoldRushBoard.player1)
            }

            GoldRushBoard.alter(path[k].row, path[k].col,'.')
            GoldRushBoard.alter(path[k+1].row, path[k+1].col, 1)

            GoldRushBoard.player1.row = path[k+1].row
            GoldRushBoard.player1.col = path[k+1].col

            Render.generateMatrix(rowM, colM, GoldRushBoard.matrix)

            if(k == path.length-2){
                computer(GoldRushBoard, clearTimeoutArry)
            }

        }, 500*(k+1))

        clearTimeoutArry.push(setTimeoutMove)

        location.row = path[i+1].row
        location.col = path[i+1].col
    }
}
...