1

我创建了一个基于文本的游戏，它会自动生成一个包含 10x10 房间的地图，其中一些房间被各种碎片挡住了，我无法找到最有效的方法来检查玩家是否仍然可以拿到钥匙并获得在没有他们被从地图上截断的情况下到出口。

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

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

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

4

4 回答 4

2

您可以使用Dijkstra 算法或其他一些寻路算法来检查从房间入口到每个对象是否有路，然后丢弃无效房间。不过，这可能会有点慢，特别是如果房间变大或添加更多对象时。

更好的选择是通过施工保证房间的每个部分都可以到达。这可以使用二进制空间分区 (BSP)来实现。它可用于创建随机地牢，同时确保所有房间都已连接。您可以在本教程中找到更多信息。

周围有很多关于程序生成的地牢的材料。你可以在这里查看另一个有趣的教程。

于 2015-04-01T04:27:47.947 回答
1

真正的问题是程序员在错误的地方和错误的时间花费了太多时间来担心效率。过早优化是编程中万恶之源（或至少是大部分）。

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

接受 Knuth 的建议，我建议实施想到的最简单的解决方案（例如，如问题中所述），并且仅在该方法成为程序瓶颈时才寻找更有效的算法。如果他适合具有 1974 年性能的计算机，那么他现在更适合...

于 2015-04-01T04:32:54.347 回答
1

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

因此，如果您将坐标 (5,5) 作为阻塞房间，您将从 (4,5)s 邻居集、(5,4)s 邻居集、(6,5)s 邻居集中删除 (5,5) , 和 (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);
        }
    }

我希望这是你所要求的。

于 2015-04-01T05:17:40.207 回答
0

制作一个数组 A，每个房间对应一行，每个房间对应一列。

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

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

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

这是这里很好地描述的数学的概括https://en.wikipedia.org/wiki/Markov_chain

于 2015-04-01T04:57:41.163 回答