为什么在文本冒险游戏中使用树型数据结构来表示数据？

Question

为什么在文本冒险游戏中使用树型数据结构来表示数据？

c++data-structuresgraphtree

7

作为我C++模块的任务，我需要构建一个文本冒险游戏。我面临的问题是概念性的，所有人都说我应该使用树数据结构来表示我的游戏，但我不明白为什么。

比如说我有一个有4个房间的房子。我们可以将其想象成一个2x2的数组。每个房间里有两个物品。我想以这样一种方式显示这些数据，使得我能够轻松地移动我的角色从0x0到0x1（直接 - 1步，或间接 - 3步），并带着一个物品。

为什么使用树来保存所有的数据会更好？我的角色如何从一个节点移动到另一个节点？还是说角色本身就是一个节点？我的角色不应该是一个带有库存列表的对象吗？

我对此有点困惑。我不是在寻找任何代码，只是想更好地理解数据表示和操作。

建议使用地图。但是我不明白我的角色如何“导航”地图。

- Adrian

6

也许你的同龄人认为你在建一个“树屋”。 - Kerrek SB

抱歉，我不太确定你想表达什么。 - Adrian

5

学习新概念时，尝试将其应用于各方面是正常的。树形数据结构仅是您工具箱中的一种工具。有时它是完成任务的好工具，而有时则不是。 - Emile Cormier

有很多事情可以使用图形（我知道，因为我的一个朋友也在尝试文本冒险游戏）。另一方面，树似乎不太有用。但无论如何，你必须说出你所代表的数据结构是什么。人们是否真的建议你使用树来表示地图？如果是这样，请要求详细信息。 - user395760

2

明显的出口是NORTH，SOUTH和DENNIS。 - Emile Cormier

1

为什么大家都想关闭这个问题？这是一个关于数据结构选择的好问题。 - Eric J.

3个回答

9

你所需要的不是一棵树，而是一个图。

之所以更喜欢使用图，是因为“位置”的数组并不一定代表你想要的。相邻房间之间并不一定有门，所以你可能不能直接从一个房间到另一个房间。此外，在典型的文字冒险游戏中，你可能会有一些走廊（或其他道路），它们可以将你带到不那么相邻的房间。此外，你可能会遇到单向通道，这些通道可以将你从一个地方带到另一个地方，但你无法转身回去。所有这些都可以用有向图来表示，但用数组则很难表示。

- Jerry Coffin

我同意你的观点，认为图表更适合文本冒险游戏。然而，如果我成功地创建了一个代表地图的图表（C++没有这个），我不明白我的角色如何在图表上移动。它难道不是这个结构的一部分吗？ - Adrian

2

@Adrian：不是的——你的角色可能有一个指向图中节点的“当前位置”成员指针。如果这是一个多人游戏，您还可以让每个节点具有指向当前占据该节点的玩家指针列表（在这种情况下，遍历节点通常涉及玩家在进入时向新节点注册，并在退出时取消注册）。 - Jerry Coffin

现在更有意义了。谢谢。 - Adrian

只是为了确保，每当角色从一个地方移动到另一个地方时，在现实中程序只是切换指针（在角色对象内部）。当谈到对象时，这个观点是否成立？也就是说，很可能每个房间也会有一个对象列表。当角色“拿走”一个对象并“走出”房间时，我是不是应该将对象从原始列表复制到我的库存列表中？ - Adrian

@Adrian：是的，很可能。除非你有一些非常大/昂贵的对象需要创建/复制，或者你经常移动它们——但至少在这种情况下，似乎都不太可能。在后一种情况下，你可以考虑使用 unique_ptr<T> 这样的东西。 - Jerry Coffin

0

我认为树是更好的选择，因为你想要表示房间之间可能的状态转换，除了房间本身。

把它看作一个图：状态是房间，但特定事件会触发从一个状态到另一个状态的转换。它表达了用户不能随意从一个状态到另一个状态的事实。

考虑有限自动机和状态机。

- duffymo

2

请注意，树不等于图（事实上，树是一种非常特定和有限的图形）。对于大多数地图来说，树是不足够的，你需要一个更通用的图形。 - user395760

1

同意。我认为树比2x2数组更好，而图形比树更好。 - duffymo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric J. · Accepted Answer

如果你的“房子”是一个网格，你可以从任何网格单元移动到任何其他网格单元，则数组是可以的。我猜测你的同行们所暗示的是，你可能不想能够从任何房间移动到任何相邻的房间（也不能从例如0,0移动到42,13）。

然而，使用树结构仍然无法表示房间之间的任意转换集合。

一种更灵活的方法是Adjacency List，它是一种专门的graph类型。将每个房间视为一个节点，并给每个节点一个可过渡到其他房间的列表。有了这个结构，甚至可以允许单向转换（想象一下许多冒险游戏中的单向门）。 伪代码

class Room
{
    string Name;
    string Description
    List<Room> ConnectedRooms;
}

那么在表示字符时，

class Character
{
    string Name;
    Room CurrentRoom;
}

查看一个给定字符可以移动到的位置：

List<Room> availableRooms = myCharacter.CurrentRoom.ConnectedRooms;