Bob*_*Jim 14 java algorithm computer-science linguistics
我正在做一个类似boggle的文字游戏.给用户一个这样的字母网格:
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的字母频率效果不佳.这在Scrabble中效果更好我认为你对使用字母的顺序的约束较少.
我尝试了一组列表,每个列表代表一个来自Boggle游戏的模具,每个字母都是从随机模具中挑选出来的(我也想知道我是否可以合法地在产品中使用这些数据).我没注意到这个工作得很好.我认为Boggle骰子的侧面是以一种合理的方式选择的,但我无法找到这是怎么做的.
我考虑过的一些想法:
列出字母对中字母对的出现频率.为了论证,可以说E在30%的时间旁边被看到.当我选择一个新的字母时,我会根据这个字母的频率随机选择一个字母,该字母出现在网格上随机选择的相邻字母旁边.例如,如果相邻的字母是E,则新字母在30%的时间内将是"A".应该意味着在地图上分散使用很多不错的对.我可以通过在两个其他字母之间出现一个字母的概率表来改善这一点.
以某种方式搜索当前网格上拼写的单词,将新单词作为通配符.然后我会用允许拼写最大单词的字母替换通配符.但是我不确定你会如何有效地做到这一点.
任何其他想法表示赞赏.我想知道是否有一种解决这个问题的常用方法以及其他文字游戏使用的方法.
编辑:感谢您迄今为止的精彩答案!我忘了提一下,如果可能的话,我的目标是低内存/ cpu要求,我可能会使用SOWPODS字典(约250,000),我的网格将能够6 x 6.
这是一个简单的方法:
使用播放器将使用的相同单词列表为游戏编写快速解算器.随机生成100个不同的可能板(使用字母频率在这里可能是一个好主意,但不是必需的).对于每个板,计算所有可生成的单词,并根据找到的单词数或由单词长度加权的计数(即找到的所有单词的单词长度总和)对单板进行评分.然后从100种可能性中挑选最好的得分板并将其交给玩家.
而且总是选择最高得分板(即最简单的板),你可以有不同的得分门槛,使专家的游戏更加困难.
我不知道这方面的预制算法，但是......
UNIX 中有一个字典文件，我想在其他平台上也有类似的东西（甚至可能在 java 库中？ - google 一下）。无论如何，使用拼写检查器使用的文件。
当他们拼写出一个单词并将其删除后，您就会看到现有的字母和空格。
1）从每个现有字母开始，向右、向左、向上、向下（您需要了解递归算法）。只要在字典文件中的单词开头或从单词末尾向后找到您到目前为止构建的字符串，就继续。当您遇到空格时，计算接下来需要的字母的频率。使用最常见的字母。
它不能保证一个单词，因为您没有检查相应的结尾或开头，但我认为这比详尽的搜索更容易实现并获得相当好的结果。