65.9K
CodeProject 正在变化。 阅读更多。
Home

Code Project 凯文·贝肯游戏（第三部分）

Derek Bartram
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.69/5 (8投票s)

2008年5月1日

CPOL

8分钟阅读

viewsIcon

51318

downloadIcon

763

一个利用 CodeProject.dll 的 Code Project 导向的 Kevin Bacon 游戏

http://www.derek-bartram.co.uk/index.cfm?PageID=kevinbacon - Code Project Kevin Bacon 游戏的在线版本。请注意，该游戏仍在填充中，因此目前找到链接非常困难（尝试从 10 到 1 的链接）。

codeprojectkevinbacon2.png

codeprojectkevinbacon1.jpg

引言

本文档演示了如何使用 CodeProject.dll 为 Code Project Kevin Bacon 游戏提取信息！

重要提示 - 如果要检索的数据集设置为 5,000,000，这会消耗 Code Project 大量的带宽；如果您想试用演示版，请使用限制数据集，例如 1000 个用户。我已包含前 1000 个用户的批量加载数据，您最好使用这些数据。请尊重 Code Project。在线版本目前正在填充中！

背景

“关于凯文·贝肯的六度分隔游戏，它基于“小世界现象”概念的一个变体，并声称任何演员都可以通过其电影角色与演员凯文·贝肯联系起来。游戏要求一群玩家尽可能快地、尽可能少地通过联系将历史上任何电影演员与凯文·贝肯联系起来。该游戏在 20 世纪 90 年代初在各个大学校园中流行。[需要引用]它的名字是对“六度分隔”概念的文字游戏。2007 年，贝肯成立了一个名为 SixDegrees.org 的慈善组织。”

凯文·贝肯在 1994 年为电影《河流狂奔》接受《Premiere》杂志采访时，在谈论他的名气和职业生涯时评论道，他与好莱坞的每个人或与他们合作过的人都合作过。

《关于凯文·贝肯的六度分隔》游戏大约在同一时间首次出现。1994 年 4 月 7 日，一个长篇新闻组帖子标题为“凯文·贝肯是宇宙的中心”出现。

该游戏于 1994 年初由艾尔布赖特学院的三名学生 Craig Fass、Brian Turtle 和 Mike Ginelli 创作。根据他们 1999 年春季在学校杂志《The Albright Reporter》上的采访，他们当时正在一场大雪中观看《足迹》。当这部电影之后是《水银》时，他们开始推测贝肯拍过多少部电影以及他与多少人合作过。

在采访中，Brian Turtle 说：“我想这成了我们愚蠢的派对技巧之一。人们会向我们扔名字，我们会将他们与凯文·贝肯联系起来。”

三人写信给脱口秀主持人乔恩·斯图尔特，告诉他“凯文·贝肯是娱乐界的中心”，并解释了游戏。[需要引用]

他们与贝肯一起出现在《乔恩·斯图尔特秀》和《霍华德·斯特恩秀》上解释游戏。贝肯承认他最初不喜欢这个游戏，因为他认为这在嘲笑他，但他最终还是喜欢上了它。游戏的三位发明者发布了《关于凯文·贝肯的六度分隔》（ISBN 9780452278448）一书，贝肯为该书写了序言，并且 Endless Games 公司发布了一款基于该概念的棋盘游戏。

到了 21 世纪，这个游戏已经足够为人所知，可以在美国的流行文化中被提及。例如，在 NBC 的《威尔与格蕾丝》剧集“贝肯与鸡蛋”中，贝肯客串出演，扮演自己。在此剧集中，他在与威尔（由 Eric McCormack 扮演）交谈时明显提到了这个游戏。

威尔：你——你和方·基尔默演过一部电影？
凯文：不，但瓦尔和汤姆·克鲁斯一起出演了《壮志凌云》，而汤姆和我一起出演了《好人》。嗯，那部电影很短。贝肯还在一个 Visa 支票卡的商业广告中扮演过一个模仿这个游戏的角色。在广告中，贝肯想写一张支票买一本书，但店员要他的身份证，他没有。他离开，然后带着一群人回来，然后对店员说：“好吧，我演过一个电影，里面有一个群众演员，尤妮斯，她的发型师韦恩，和参加主日学的奥尼尔神父一起，奥尼尔神父和桑杰医生一起打壁球，桑杰医生最近摘除了金的阑尾，金在你大二时和你分手了。所以你看，我们几乎是兄弟。”

这个概念也在 1996 年 11 月 19 日播出的电视剧《为你疯狂》的一集中被提出，其中一个角色认为每个演员都只和凯文·贝肯有三个程度的联系。

贝肯为纽约帝国大厦的 NY Skyride 景点提供画外音解说。在解说中的几个地方，贝肯通过他曾合作过的其他演员暗示了他与好莱坞明星的联系。

引用：维基百科 - 关于凯文·贝肯的六度分隔

游戏目标

游戏的目标很简单，找到一对会员 ID，它们通过文章中的评论相关联，但需要最长的最小连接链。例如，用户 Mike Klimentiev（3045）到 Michael Dunn（152）就相当不错，他的贝肯数是 3（因为链中有三个链接）。

  1. 3045 在 230 撰写的“编写文档的技巧”文章中留下了评论
  2. 230 在 117 撰写的“生存发布版本”文章中留下了评论
  3. 117 在 152 撰写的“使用自定义绘制在列表控件中做有趣的事情”文章中留下了评论

用户 230 是 Tibor Blazko。
用户 117 是 Joseph M. Newcomer。

游戏理论

本文档无意作为凯文·贝肯游戏背后理论的介绍，但在此处提供摘要以求完整。

将用户与文章评论之间的链接视为一个（非完全）有向图，如下所示；

codeprojectkevinbacon3.jpg

贝肯数（或更确切地说，路径）是源点和目标点之间最短的跳数路径。这可以通过 Dijkstra 算法确定（参见 http://en.wikipedia.org/wiki/Dijkstra's_algorithm）。在此版本的游戏中，我使用了 Michael Demeersseman（ https://codeproject.org.cn/KB/recipes/ShortestPathCalculation.aspx）提供的现有 .Net 实现，但进行了一些小的修改，将文章信息存储在 Connection 中，并移除了 Connection 权重（因为在这个游戏中，所有连接的权重都是 1）。

检索所需数据

需要两类信息：用户文章和在文章中留下的评论。节点（即端点）代表来自单个用户的所有文章，可以通过 CodeProject.dll 的 ArticlesSummary 类进行数据挖掘。ArticlesSummary 需要会员编号，但通过从 1 到 5,000,000（Code Project 会员数量）的简单循环即可完成此任务；

counter = 1;
StreamWriter articleDataWriter = new StreamWriter(System.Environment.CurrentDirectory 
   + "\\articles.blf", false);
articleDataWriter.AutoFlush = true;

while (counter < maxUsers && false)
{
    ArticlesSummary summary = new ArticlesSummary(counter.ToString());
    summary.update();

    List<Article> articles =  summary.Articles;
    foreach (Article a in articles){
        articleDataWriter.Write(counter + "," + a.Title + "," + a.Link + "\r");
    }

    if (counter % 100 == 0)
    {
        articleDataWriter.Flush();
        Console.Write(".");
    }

    counter++;
}
articleDataWriter.Flush();
articleDataWriter.Close();
Console.WriteLine(".");

结果将被写入一个简单的文本文件，准备进行批量加载。

第二项所需信息是每个用户在文章中留下的评论，即节点之间的连接。对用户编号进行类似的循环即可完成此任务；

counter = 1;
StreamWriter commentDataWriter = new StreamWriter(System.Environment.CurrentDirectory 
   + "\\comments.blf", false);
commentDataWriter.AutoFlush = true;

while (counter < maxUsers)
{
    User u = new User(counter.ToString());

    foreach (String article in u.ArticleComments)
    {
        commentDataWriter.Write(counter + "," + article + "\r");
    }

    if (counter % 100 == 0)
    {
        commentDataWriter.Flush();
        Console.Write(".");
    }

    counter++;
}
commentDataWriter.Flush();
commentDataWriter.Close();
Console.WriteLine(".");

以类似的方式，将结果数据写入文本文件以进行批量加载。

处理数据

在成功使用数据之前，需要使用以下命令将其导入 SQL Server 数据库。

创建表

USE [KevinBacon]
GO
/****** Object:  Table [dbo].[Articles]    Script Date: 04/27/2008 21:03:15 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Articles](
    [memberID] [nchar](10) NOT NULL,
    [articleName] [nchar](512) NOT NULL,
    [webLink] [nchar](128) NOT NULL
) ON [PRIMARY];

USE [KevinBacon]
GO
/****** Object:  Table [dbo].[Comments]    Script Date: 04/27/2008 21:03:19 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Comments](
    [memberID] [nchar](10) NOT NULL,
    [articleName] [nchar](512) NOT NULL
) ON [PRIMARY];

导入数据

对于不熟悉 BULK INSERT 命令（或 BCP 工具）的用户，它允许以更快的速度将数据导入 SQL Server 数据库表，因为不会检查约束，并且只需一个命令即可插入多行。考虑导入评论数据的情况；有 5,000,000 条评论，平均每条有 20 条评论，总共需要 100,000,000 次 INSERT 或 1 次 BULK INSERT。

BULK INSERT Articles
   FROM 'C:\Users\Administrator\Documents\Visual Studio 2008\Projects\CodeProject\
KevinBaconDataRetrieval\bin\Debug\articles.blf'
   WITH 
      (
         FIELDTERMINATOR =',',
         ROWTERMINATOR ='\r'
      );

BULK INSERT Comments
   FROM 'C:\Users\Administrator\Documents\Visual Studio 2008\Projects\CodeProject\
KevinBaconDataRetrieval\bin\Debug\comments.blf'
   WITH 
      (
         FIELDTERMINATOR =',',
         ROWTERMINATOR ='\r'
      );

请注意，数据检索的最终输出需要对文本文件进行微小修改；需要删除文件中的最后一个字符（即最后的 \n）。记事本或类似工具即可完成；应按以下方式执行此过程；

  1. 在记事本中打开文件
  2. 转到文件末尾（按 Ctrl+End）
  3. 删除最后一个字符（按退格键）*
  4. 保存并退出记事本
  5. 对两个文件重复此操作

* 请注意，光标位置似乎没有变化，这是正常且正确的。

计算最短路径

游戏程序按以下阶段进行；

  1. 获取位置数据，即用户/文章信息
  2. 获取连接数据，即哪个用户评论了哪篇文章
  3. 创建路由引擎（基于 Michael Demeersseman 的作品）
  4. 循环直到程序关闭
    1. 获取第一个会员 ID（及其对应的位置）
    2. 获取第二个会员 ID（及其对应的位置）
    3. 使用 engine.CalculateMinCost(fromLocation) 函数获取指向所有其他位置的路由字典
    4. 选择对应于 Location 的路由从引擎结果中

获取位置数据

SELECT memberID FROM Comments GROUP BY memberID

获取一个不同的会员 ID 列表

获取连接数据

SELECT 
    Comments.memberID AS fromMemberID, 
    Articles.memberID AS toMemberID, 
    Articles.articleName AS articleName 
FROM Articles, Comments 
WHERE Articles.articleName = Comments.articleName

将 Article 和 Comments 表连接起来。fromMemberID 和 toMemberID 用作之前生成的会员位置字典的键，并相应地创建新的 Connection（以及 articleName）

创建路由引擎

RouteEngine engine = new RouteEngine();
engine.Connections = connectionsList;
engine.Locations = locationsList;

实例化路由引擎。

历史

版本 1.0.0.0 - 首次构建

有用链接

codeprojectarticle.aspx（第一部分，文章）

codeprojectuser.aspx（第二部分，用户）

codeprojectkevinbacon.aspx（第三部分，凯文·贝肯）

其他许可说明

请随时在您的工作中对此进行使用，但请注意，这里使用的是修改后的 Code Project 开放许可证 (CPOL)；基本上与标准许可证相同，只是此代码未经事先授权不得用于商业或非营利性商业用途。请参阅随附的源代码和演示文件中的 license.txt 或 license.pdf。

© . All rights reserved.