2

一段时间以来，我一直在思考游戏Ruzzle中使用的算法。游戏的目的是在给定的网格中找到任何单词的存在，单词可以在上下、上下、左右、左右、上下对角线等任何方向上匹配。

让我们简单点。在具有相同匹配约束（方向）的二维网格中查找给定单词。具有最佳时间复杂度的算法是什么？

例如，可以在此网格中找到 FOREVER。

ER的H

L RE TO

信噪比_ _ _

PQT E N

4

2 回答 2

1

您可以使用Trie数据结构进一步优化它。一旦你用所有的英语单词（或不同的语言）填写了结构，你就可以在 O(1) 中检查是否需要探索特定的邻居角色。

请注意，此时您正在用存储换取时间：您可能需要更多的 RAM 来存储整个 Trie，但您查询它的速度比检查有序的单词列表要快。

就游戏背后的架构而言，我认为他们使用专用服务器，该服务器全职工作以将新游戏（矩阵）及其允许单词列表存储在数据库中。在游戏过程中，您的设备会收到一个 ID，它会下载矩阵和允许单词列表，这足以让您玩游戏。在每场比赛结束时，所有内容都会被删除，最终分数（只是一个整数）会提交给服务器，服务器会更新您的个人资料。在实际游戏中还有更多的东西，因为他们也有徽章和统计数据（但收集这些东西是微不足道的）。请记住，这正是我设计和开发它的方式。

你怎么看？我们还能做得更好吗？

于 2014-06-19T07:28:16.327 回答
-2

我创建了一个关于在 Unity 中制作 ruzzle 游戏机制的课程。请检查一下，您会找到确切的答案：

https://www.udemy.com/word-game-unity/?couponCode=wordgamecourse

于 2015-05-22T11:49:23.457 回答