Java: 如何检查生成的关卡是否可行？

Question

我创建了一个基于文本的游戏，它会自动生成一个包含 10x10 个房间的地图，一些房间被各种碎片挡住了，我无法找出最有效的方法来检查玩家是否仍然可以到达钥匙并到达出口，而不会被地图切断。

目前需要的房间与地图的其余部分被切断的可能性很小，这使得关卡变得不可能，我想检查每个相邻的方格到起始位置，然后重复并重复直到所有方格可访问的在变量中设置为 'accessible'，然后如果这三个对象不可访问，则只需重新生成地图，直到它们可以访问为止。如果它重新生成几次，这可能会很慢。

有没有人对重复的部分有任何想法以保持快速，或者有更好的方法来实现这一点？

这是生成的地图的图片：#'s 是被封锁的房间。 http://postimg.org/image/8oo88jxgb/

Answer 1

您可以使用Dijkstra's algorithm, or some other pathfinding algorithm，检查从房间入口到每个对象是否有路，然后丢弃无效房间。不过，这可能会有点慢，特别是如果房间变大或您添加了更多对象。

更好的选择是通过构造保证可以到达房间的每个部分。这可以使用 Binary Space Partioning (BSP). It can be used to create random dungeons while assuring that all the rooms are connected. You can find more information in this tutorial.

来实现

周围有很多关于程序生成地牢的 material。你可以检查另一个有趣的 tutorial here.

Answer 2

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

Donald Knuth (1974 Turing Award Lecture, Communications of the ACM 17 (12), (December 1974), pp. 667–673)

根据 Knuth 的建议，我建议实施想到的最简单的解决方案（例如，如问题中所述），并且仅在该方法被证明是程序瓶颈时才寻找更有效的算法。如果他对具有 1974 年性能的计算机是正确的，那么他现在更正确...

Answer 3

创建一个数组 A，每个房间一行，每个房间一列。

如果两个房间相连，则在第i，j（行，列）位置各放一个1。

这个矩阵( A ) 是你的游戏图形的数字表示，图形的节点是房间，边是门。

现在取一个长度与您拥有的房间数相对应的向量，并用零填充它，但与您开始的房间相对应的位置除外。这个向量（P ) 是在 0 次转换后到达给定房间的方法数。要检查是否可以在 ( n ) 中到达给定房间，只需乘以 P A^n 并在中查找非零值表示给定房间的向量中的位置。

这是数学的概括https://en.wikipedia.org/wiki/Markov_chain

Answer 4

您可以将您的电路板表示为一个图表，其中一个坐标值作为键，一组坐标作为代表每个坐标邻居的值..示例 Map<Coordinate, HashSet<Coordinate> = new Hashmap<Coordinate, HashSet<Coordinate>();。然后用每个坐标值作为键并以它们各自的邻居作为它们的值来填充图形。每当出现被阻挡的房间时，只需从围绕它的每个坐标邻居中删除该坐标即可。

所以如果你有坐标 (5,5) 作为一个被封锁的房间，你会从 (4,5)s 邻居集中删除 (5,5)，(5,4)s 邻居集，(6, 5)s 的邻居集，和 (5,6)s 的邻居集。这基本上不会让你再通过这条路。

要填充图形，您可以使用两个循环：

    for(int r = 0; r <= 10; r++){
        for(int c = 0; c <= 10; c++){
            HashSet<Coordinate> neighbors = new HashSet<Coordinate>();
                 if(r > 0){
                    neighbors.add(new Coordinate(r - 1, c));
                 }
                if(r < 8){
                     neighbors.add(new Coordinate(r + 1, c));
                 }
                if(c > 0){
                    neighbors.add(new Coordinate(r, c - 1));
                 }
                if(c < 8){
                    neighbors.add(new Coordinate(r, c + 1));
                 }
            graph.put((new Coordinate(r,c)), neighbors);
        }
    }

希望这就是您想要的。

Java: 如何检查生成的关卡是否可行？

Java: How to check if a generated level is possible?

java

dictionary

generated