Блог

Прочитав об алгоритмах поля зрения, я решил создать его сам для игры, над которой я работаю. Через пару часов я придумал следующий скрипт:

 function CalculateFOV() {
    ClearFOV();

    map[player.x][player.y].light = 100;

    var open = new Array();
    var closed = new Array();

    sourceNeighbors = map[player.x][player.y].neighbors;

    for(var i = 0;i<sourceNeighbors.length;i  ) {
        open.push(sourceNeighbors[i]);
    }

    while(open.length > 0) {
        var curTile = open[0];

        var highestLightValue = 0;

        for(j in curTile.neighbors) {
            if(curTile.neighbors[j].light > highestLightValue) {
                highestLightValue = neighbors[j];               
            }
        }

        curTile.light = highestLightValue-10;

        if(curTile.light > 10) {
            for(var j = 0;j<curTile.neighbors.length;j  ) {
                var addCell = true;

                if(FindValue(closed, open[0].neighbors[j])) addCell = false;

                if(addCell) {
                    open.push(neighbors[j]);
                }
            }
        }

        closed.push(curTile);
        open.shift();
    }
}

function ClearFOV() {
    for(var x = 0;x<mapSizeX;x  ) {
        for(var y = 0;y<mapSizeY;y  ) {
            map[x][y].lightValue = 0;
        }
    }
}

function FindValue(list, value) {
    for(var i = 0;i<list.length;i  ) {
        if(list[i] == value) {
            return true;
        }
    }

    return false;
}
  

Предполагается, что значение light-value распространяется от источника наружу, уменьшаясь по мере продвижения. Он использует закрытый список фрагментов, которым уже присвоено значение light, чтобы избежать попадания в одну ячейку несколько раз. Это должно теоретически значительно повысить эффективность.

К сожалению, похоже, что с этим связана ошибка, возможно, не одна. Мой усталый мозг не может найти это (или их), поэтому я был бы очень признателен за некоторую помощь в этом. Имеет ли это вообще смысл?

Кроме того, на случай, если вам это может понадобиться, вот класс Tile:

 function Tile(x,y,character, thisMap, blocked, blockSight) {
    this.x = x;
    this.y = y;
    this.character = character;
    this.blocked = blocked;
    this.blockSight = blockSight;
    this.lightValue = 25;

    this.neighbors = new Array();
}

Tile.prototype = {
    create: function(blocked, blockSight, character) {
        this.blocked = blocked;
        this.blockSight = blockSight;
        this.character = character;

        var rockTile = RandomRange(1,4);
        var rockTileStr = "rock" rockTile;
    },

    draw: function() {
        var id = '#t'   this.x   '_'   this.y;

        var lightColor = this.lightValue/100;

        $(id).css("opacity", lightColor); 
    },

    assign: function() {
        var north = this.x-1;
        var south = this.x 1;
        var east = this.y 1;
        var west = this.y-1;

        if(north >= 0 amp;amp; south <= mapSizeX amp;amp; west >= 0 amp;amp; east <= mapSizeY) {

            //1st: we add the northwest neighbor.
            // *|/
            // -#-
            // /|
            this.neighbors[0] = map[north][west];

            //2nd: we add the north neighbor.
            // */
            // -#-
            // /|
            this.neighbors[1] = map[north][this.y];

            //3rd: we add the northeast neighbor.
            // |*
            // -#-
            // /|
            this.neighbors[2] = map[north][east];

            //4th: we add the east neighbor.
            // |/
            // -#*
            // /|
            this.neighbors[3] = map[this.x][east];

            //5th: we add the southeast neighbor.
            // |/
            // -#-
            // /|*
            this.neighbors[4] = map[south][east];

            //6th: we add the south neighbor.
            // |/
            // -#-
            // /*
            this.neighbors[5] = map[south][this.y];

            //7th: we add the southwest neighbor.
            // |/
            // -#-
            // *|
            this.neighbors[6] = map[south][west];

            //8th: we add the west neighbor.
            // |/
            // *#-
            // /|
            this.neighbors[7] = map[this.x][west];
        }
    },
}
  

Спасибо и приношу извинения за публикацию такого длинного вопроса; я просто не знаю, к кому еще обратиться в данный момент.

Я вижу следующую опечатку:

Наивысшее значение параметра Light = neighbors[j];

должно быть

Наивысшее значение параметра Light = neighbors[j].light;

Кроме того, если вас беспокоит эффективность, возможно, вам захочется изменить способ хранения набора закрытых элементов. Для массива закрытых листов требуется O (n) времени для выполнения findValue (фактически, при текущих реализациях массивов javascript, O(n*log(n))). Если вы используете массив true / false, индексированный идентификатором плитки, вы получаете O (1) (или O(log(n)) в реальном мире javascript). Поскольку это происходит во внутреннем цикле вычисления, ускорение может быть заметным.