等距拓扑排序问题

Question

我刚刚使用本指南在我的等距游戏中实现了拓扑排序算法：https://mazebert.com/2013/04/18/isometric-depth-sorting/

问题

这是一个小例子（这只是一张绘图来说明我的问题，因为正如我们所说，一张图片值一千个字), 我期望的在左边而拓扑排序算法的结果在右边

所以在右图中，问题是框是在角色之前绘制的，我希望它是AFTER 绘制，如左图。

拓扑排序算法代码(Typescript)

private TopologicalSort2() {
    // https://mazebert.com/2013/04/18/isometric-depth-sorting/

    for(var i = 0; i < this.Stage.children.length; i++) {
        var a = this.Stage.children[i];
        var behindIndex = 0;

        for(var j = 0; j < this.Stage.children.length; j++) {
            if(i == j) {
                continue;
            }

            var b = this.Stage.children[j];

            if(!a.isoSpritesBehind) {
                a.isoSpritesBehind = [];
            }

            if(!b.isoSpritesBehind) {
                b.isoSpritesBehind = [];
            }

            if(b.posX < a.posX + a.sizeX && b.posY < a.posY + a.sizeY && b.posZ < a.posZ + a.sizeZ) {
                a.isoSpritesBehind[behindIndex++] = b;
            }
        }

        a.isoVisitedFlag = 0;
    }

    var _sortDepth = 0;

    for(var i = 0; i < this.Stage.children.length; ++i) {
        visitNode(this.Stage.children[i]);
    }

    function visitNode(n: PIXI.DisplayObject) {
        if(n.isoVisitedFlag == 0) {
            n.isoVisitedFlag = 1;

            if(!n.isoSpritesBehind) {
                return;
            }

            for(var i = 0; i < n.isoSpritesBehind.length; i++) {
                if(n.isoSpritesBehind[i] == null) {
                    break;
                } else {
                    visitNode(n.isoSpritesBehind[i]);
                    n.isoSpritesBehind[i] = null;
                }
            }

            n.isoDepth = _sortDepth++;
        }
    }

    this.Stage.children.sort((a, b) => {
        if(a.isoDepth - b.isoDepth != 0) {
            return a.isoDepth - b.isoDepth;
        }

        return 0;
    });
}

信息

玩家：

posX: [the x coordinate of the player]
posY: [the y coordinate of the player]
posZ: 0

sizeX: 1
sizeY: 1
sizeZ: 1

盒子:

posX: [the x coordinate of the box]
posY: [the y coordinate of the box]
posZ: 0

sizeX: 3
sizeY: 1
sizeZ: 1

X 轴和 Y 轴

您知道这个问题的根源吗？以及如何解决？

Answer 1

确定一个对象是否在另一个对象之前的方法需要更多的线性代数知识。

首先，我建议将坐标从 "world" 坐标转换为 "view" 二维坐标，即转换为显示的行和列。

另请注意，原始 Z 坐标不影响排序顺序（假设一个对象将沿 Z 轴提升：我们可以找到此移动不会产生任何影响的排序顺序）。所以上述翻译可以假设所有点都在 Z=0.

让我们采用此设置，但从 "above" 开始描绘，因此当沿 Z 轴向下查看游戏地板时：

图中有7个物体，编号从0到6。游戏中的视线从这张图的左下角开始。我建议在其中平移一些点的坐标系用红色 row/col 轴表示。

每个对象中的白色对角线 link 将在算法中转换和使用的两个点。假设是当一个物体在另一个物体前面时，它们的对角线不会相交。如果是这样，那就意味着物体在游戏世界中相互重叠，这意味着它们就像气体，而不是固体 :) 我假设情况并非如此。

当在新的坐标系中，一个对象A可能在另一个对象B之前，B的最左边的列坐标落在A的两列坐标之间（反之亦然）。当它们的 Z 坐标差异足够大时，可能不会真正重叠，但我们可以忽略这一点，因为当没有重叠时，我们无论如何都可以指定特定的顺序。

现在，当坐标指示重叠时，（A 和 B 的）对角线坐标必须与一些线性代数公式进行比较，这将确定哪个在另一个前面。

这是执行此操作的改编函数：

topologicalSort() {
    // Exit if sorting is a non-operation
    if (this.Stage.children.length < 2) return; 
    // Add two translated coordinates, where each of the resulting 
    //   coordinates has a row (top to bottom) and column 
    //   (left to right) part. They represent a position in the final 
    //   rendered view (the screen).  
    // The two pairs of coordinates are translations of the 
    //   points (posX + sizeX, Y, 0) and (posX, posY + sizeY, 0).
    // Z is ignored (0), since it does not influence the order.
    for (let obj of this.Stage.children) {
        obj.leftCol  = obj.posY - obj.posX - obj.sizeX; 
        obj.rightCol = obj.posY - obj.posX + obj.sizeY;
        obj.leftRow  = obj.posY + obj.posX + obj.sizeX;
        obj.rightRow = obj.posY + obj.posX + obj.sizeY;
        obj.isoSpritesBehind = [];
    }

    for(let i = 0; i < this.Stage.children.length; i++) {
        let a = this.Stage.children[i];
        // Only loop over the next objects
        for(let j = i + 1; j < this.Stage.children.length; j++) {
            let b = this.Stage.children[j];
            // Get the two objects in order of left column:
            let c = b.leftCol < a.leftCol ? b : a;
            let d = b.leftCol < a.leftCol ? a : b;
            // See if they overlap in the view (ignoring Z):
            if (d.leftCol < c.rightCol) {
                // Determine which is behind: some linear algebra
                if (d.leftRow < 
                        (d.leftCol - c.leftCol)/(c.rightCol - c.leftCol) 
                        * (c.rightRow - c.leftRow)  + c.leftRow) {
                    // c is in front of d
                    c.isoSpritesBehind.push(d);
                } else { // d is in front of c
                    d.isoSpritesBehind.push(c);
                }
            } // in the else-case it does not matter which one comes first
        }
    }

    // This replaces your visitNode function and call:
    this.Stage.children.forEach(function getDepth(obj) {
        // If depth was already assigned, this node was already visited
        if (!obj.isoDepth) {
            // Get depths recursively, and retain the maximum of those.
            // Add one more to get the depth for the current object
            obj.isoDepth = obj.isoSpritesBehind.length
                ? 1+Math.max(...obj.isoSpritesBehind.map(getDepth))
                : 1; // Depth when there is nothing behind it
        }
        return obj.isoDepth; // Return it for easier recursion
    });

    // Sort like you did, but in shorter syntax
    this.Stage.children.sort((a, b) => a.isoDepth - b.isoDepth);
}

我添加了一个片段，其中我用最少的代码完成了 class，足以使其成为运行并根据对象索引号输出最终顺序（因为它们最初被插入):

class Game {
    constructor() {
        this.Stage = { children: [] };
    }
    addObject(posX, posY, posZ, sizeX, sizeY, sizeZ) {
        this.Stage.children.push({posX, posY, posZ, sizeX, sizeY, sizeZ, 
                id: this.Stage.children.length}); // add a unique id
    }
    topologicalSort() {
        // Exit if sorting is a non-operation
        if (this.Stage.children.length < 2) return; 
        // Add two translated coordinates, where each of the resulting 
        //   coordinates has a row (top to bottom) and column 
        //   (left to right) part. They represent a position in the final 
        //   rendered view (the screen).  
        // The two pairs of coordinates are translations of the 
        //   points (posX + sizeX, Y, 0) and (posX, posY + sizeY, 0).
        // Z is ignored (0), since it does not influence the order.
        for (let obj of this.Stage.children) {
            obj.leftCol  = obj.posY - obj.posX - obj.sizeX; 
            obj.rightCol = obj.posY - obj.posX + obj.sizeY;
            obj.leftRow  = obj.posY + obj.posX + obj.sizeX;
            obj.rightRow = obj.posY + obj.posX + obj.sizeY;
            obj.isoSpritesBehind = [];
        }
        
        for(let i = 0; i < this.Stage.children.length; i++) {
            let a = this.Stage.children[i];
            // Only loop over the next objects
            for(let j = i + 1; j < this.Stage.children.length; j++) {
                let b = this.Stage.children[j];
                // Get the two objects in order of left column:
                let c = b.leftCol < a.leftCol ? b : a;
                let d = b.leftCol < a.leftCol ? a : b;
                // See if they overlap in the view (ignoring Z):
                if (d.leftCol < c.rightCol) {
                    // Determine which is behind: some linear algebra
                    if (d.leftRow < 
                            (d.leftCol - c.leftCol)/(c.rightCol - c.leftCol) 
                            * (c.rightRow - c.leftRow)  + c.leftRow) {
                        // c is in front of d
                        c.isoSpritesBehind.push(d);
                    } else { // d is in front of c
                        d.isoSpritesBehind.push(c);
                    }
                } // in the else-case it does not matter which one comes first
            }
        }
        
        // This replaces your visitNode function and call:
        this.Stage.children.forEach(function getDepth(obj) {
            // If depth was already assigned, this node was already visited
            if (!obj.isoDepth) {
                // Get depths recursively, and retain the maximum of those.
                // Add one more to get the depth for the current object
                obj.isoDepth = obj.isoSpritesBehind.length
                    ? 1+Math.max(...obj.isoSpritesBehind.map(getDepth))
                    : 1; // Depth when there is nothing behind it
            }
            return obj.isoDepth; // Return it for easier recursion
        });

        // Sort like you did, but in shorter syntax
        this.Stage.children.sort((a, b) => a.isoDepth - b.isoDepth);
    }
    toString() { // Just print the ids of the children
        return JSON.stringify(this.Stage.children.map( x => x.id ));
    }
}

const game = new Game();
game.addObject( 2, 2, 0, 1, 1, 1 );
game.addObject( 1, 3, 0, 3, 1, 1 );
game.addObject( 6, 1, 0, 1, 3, 1 );
game.addObject( 9, 3, 0, 1, 1, 1 );
game.addObject( 5, 3, 0, 1, 3, 1 );
game.addObject( 7, 2, 0, 1, 1, 1 );
game.addObject( 8, 2, 0, 3, 1, 1 );
game.topologicalSort();
console.log(game + '');

片段中的对象与图片中的对象相同，编号相同。输出顺序为 [0,1,4,2,5,6,3]，这是绘制对象的有效顺序。

等距拓扑排序问题

Isometric topological sort issue

javascript

html

canvas

isometric

问题

拓扑排序算法代码(Typescript)

信息

X 轴和 Y 轴