14

我正在制作一个类似字谜的文字游戏。给用户一个像这样的字母网格：

O V Z W X
S T A C K
Y R F L Q

用户使用任何相邻的字母链来挑选一个单词，例如中间行的单词“STACK”。然后使用的字母被机器替换，例如（小写的新字母）：

O V Z W X
z e x o p
Y R F L Q

请注意，您现在可以使用新字母拼写“OVeRFLoW”。我的问题是：我可以使用什么算法来挑选新字母，以最大限度地增加用户可以拼写的长单词的数量？我希望游戏有趣并且有时会涉及拼写例如 6 个字母的单词，但是，如果您选择了糟糕的字母，游戏只会让用户拼写 3 个字母的单词，而没有机会找到更大的单词。

例如：

  • 您可以从字母表中随机选择新字母。这效果不好。

  • 同样，我发现随机选择但使用 Scrabble 中的字母频率效果不佳。我认为这在拼字游戏中效果更好，因为您对使用字母的顺序的限制较少。

  • 我尝试了一组列表，每个列表代表 Boggle 游戏中的一个骰子，每个字母都会从随机骰子一侧挑选出来（我也想知道我是否可以在产品中合法地使用这些数据）。我没有注意到这运作良好。我想 Boggle 骰子的面是以某种明智的方式选择的，但我不知道这是怎么做的。

我考虑过的一些想法：

  • 制作一个表格，说明字典中字母对一起出现的频率。为了争论起见，假设 E 在 30% 的时间出现在 A 旁边。When picking a new letter, I would randomly pick a letter based on the frequency of this letter occurring next to a randomly chosen adjacent letter on the grid. 例如，如果相邻字母是 E，则新字母将有 30% 的时间是“A”。这应该意味着有很多不错的对散布在地图上。我可以通过制作一个字母出现在其他两个字母之间的概率表来改进这一点。

  • 以某种方式搜索当前网格上可以拼写的单词，将新字母作为通配符。然后我会用允许拼写最大单词的字母替换通配符。但是，我不确定您将如何有效地做到这一点。

任何其他想法表示赞赏。我想知道是否有解决这个问题的通用方法以及其他文字游戏使用什么。

编辑：感谢到目前为止的精彩回答！我忘了提一下，如果可能的话，我的目标是低内存/cpu 要求，我可能会使用 SOWPODS 字典（大约 250,000），我的网格将能够达到 6 x 6。

4

7 回答 7

7

这是一个简单的方法：

使用玩家将使用的相同单词列表为游戏编写一个快速求解器。随机生成 100 个不同的可能板（在这里使用字母频率可能是个好主意，但不是必需的）。对于每个棋盘，计算所有可以生成的词，并根据找到的词数或按词长加权的计数（即所有找到的词的词长总和）对棋盘进行评分。然后从 100 种可能性中选出最好的计分板，然后将其提供给玩家。

此外，您可以设置不同的分数阈值，而不是总是选择得分最高的棋盘（即最简单的棋盘），以使游戏对专家来说更加困难。

于 2010-02-15T18:48:06.037 回答
2

You should look up n-gramming, and Markovian Models.

Your first idea is very losely related to Markovian algorithms. Basically, if you have a large text corpus, say of 1000 words. What you can do is analyse each letter and create a table to know the probability of a certain letter following the current letter.

For example, I know that the letter Q from my 1000 words ( 4000 letters in total ) is used only 40 times. Then I calculate what probable letters follow using my markov hash table.

For example, QU happens 100% of the time so I know that should Q be randomly chosen by your application that I need to make sure that the letter U is also included. Then, the letter "I" is used 50% of the time, and "A" 25% of the times and "O" 25% of the time.

Its actually really complicated to explain and I bet there are other explainations out there which are much better then this.

But the idea is that given a legitmately large text corpus you can create a chain of X letters which are probably consistent with English language and thus should be easy for users to make words out of. You can choose to look forward on a value of n-gram, the highest the number the easier you could make your game. For example, an n-gram of two would probably make it very hard to create words over 6, but an n-gram of 4 would be very easy.

The Wikipedia explains it really badly, so I wouldn't follow that.

Take a look at this Markov generator:

http://www.haykranen.nl/projects/markov/demo/

于 2010-02-15T18:55:56.913 回答
2

字母对方法的一个小变化：在长词中使用字母对的频率——比如 6 个字母或更长——因为这是你的目标。您还可以开发一个包括所有相邻字母的权重，而不仅仅是一个随机字母。

于 2010-02-15T18:49:06.097 回答
2

我不久前推出的这个文字游戏，其行为与您描述的非常相似，使用英语频率表来选择字母，但首先决定是生成元音还是辅音，让我确保板上元音的给定比率。这似乎工作得相当好。

于 2010-02-15T18:50:11.627 回答
1

我不知道一个预先确定的算法，但是......

在 UNIX 中有一个字典文件，我想在其他平台上也有类似的东西（甚至可能在 java 库中？ - 谷歌它）。无论如何，使用拼写检查器使用的文件。

在他们拼出一个单词后，它会丢失，你有现有的字母和空格。

1）从每个现有的字母，向右、向左、向上、向下（你需要了解递归算法）。只要在字典文件中的单词开头或从单词结尾向后找到您到目前为止构建的字符串，就继续。当你遇到一个空格时，计算你接下来需要的字母的频率。使用最常用的字母。

它不能保证一个单词，因为您没有检查相应的结尾或开头，但我认为它比穷举搜索更容易实现并获得相当不错的结果。

于 2010-02-15T18:48:01.480 回答
1

我认为这将使您离目的地更近一步：http ://en.wikipedia.org/wiki/Levenshtein_distance

于 2010-02-15T18:48:03.243 回答
0

您可能会查看Jumble 算法的Java 实现，以查找置换为多个字典单词的字母集：

$ java -jar dist/jumble.jar | 排序-nr | 头
11 Orang Ronga angor argon goran grano groan nagor orang organ rogan
10 Elaps Lepas Pales 失效 salep saple sepal slape spale speal
9 酯 estre reest 重置 steer stere stree terse tsere
9 caret carte 满足 crate crate creat creta react recta trace
9 Easter Eastre asteer Easter reseat saeter seater staree teaser
9 Canari Carian Crania acinar 山金车 canari carina crania narica
8 jumpt palet patel pelta 花瓣盘 褶皱 tepal
8 laster lastre rastle relast resalt salter slater stelar
8 Trias arist astir Sitar 楼梯 stria tarsi tisar
8 Trema armet mater metra ramet tamer terma trame
...
于 2010-02-16T00:52:59.443 回答