宾果游戏套件 - 第 1 部分
4.88/5 (7投票s)
在第一部分中，我们将探讨玩家宾果卡上数字的随机排列。
目录
1. 引言 
本文是描述我在过去几个月里开发的宾果游戏套件的三篇文章中的第一篇。发表这些文章的目的是希望该软件对读者有所帮助。这三篇文章将介绍拥有75个编号球的美式宾果游戏。
1.1. 宾果游戏
在美国，宾果是一种机会游戏，每个玩家匹配印在不同排列卡片上的数字。游戏主持人（叫号员）随机抽号，并用标记片盖住选中的数字。当玩家发现自己卡片上的数字连成一行时，他们会喊出“Bingo!”以提醒所有参与者有获胜的卡片，这会促使游戏主持人（或协助主持人的助手）检查卡片以验证获胜。玩家们相互竞争，争当第一个获得奖品或头奖的获胜者。宣布获胜者后，玩家清理卡片上的标记片，游戏主持人开始新一轮游戏。
一种乐透形式，其中随机抽取带有数字和字母B、I、N、G或O之一的球或纸条，玩家覆盖他们卡片上印的相应数字，第一个在任何行或对角线上覆盖五个数字，或者有时是卡片上所有数字的玩家为获胜者。
宾果是一种机会游戏，因为叫号员是随机抽号的，而且玩家宾果卡上的数字也是随机排列的。本文要讨论的正是后者。
为了玩宾果游戏，必须生成并打印玩家将使用的宾果卡。
本文讨论上图中加粗的项目。
1.2. 宾果卡
宾果卡由六行五列组成。第一行是卡片标题，包含字母 'B'、'I'、'N'、'G' 和 'O'，每个字母占一列。接下来的五行包含根据一套规则生成的随机数字，这些规则指定了特定列中允许出现的值。一张未经装饰的宾果卡如下所示
5 x 5 卡片的中心方格被称为“自由格”，被视为已叫号。当插入24个随机数字后，卡片可能如下所示。
 |  |
右图的创建要求是在宾果卡中分布星星。当施加此要求时，每张宾果卡上都会随机放置一颗星。每张卡片上星星的位置会记录在宾果卡文件中。
自由格中的数值，本例中为 2066057，被命名为 group_face，并唯一标识该卡片。它由编码后的卡片颜色（2代表LightCoral）和卡片面号（从1开始，直到生成的卡片数量）组成。
卡片的布局由 Print_Cards 程序负责（这是本系列第二部分的主题）。
2. 保存宾果卡
虽然本文专门讨论宾果卡的生成，但一旦生成，新的宾果卡就会被保存起来。
2.1. 宾果卡文件格式
宾果卡文件的格式是一个128字节的头文件，后跟若干张宾果卡。每张卡由25个字节组成。该集合中心的字节（索引为13）用于记录卡片上“星”的位置。
使用字节作为保存宾果卡的形式是基于可能生成大量宾果卡的考虑。例如，一个包含800,000张25字节宾果卡的文件需要20,000,128字节；而如果使用无符号32位整数（代替8位字节），文件大小将为80,000,128字节。
宾果卡文件是一个直接访问文件。用于访问编号为 card_number 的特定记录的公式是
// in Utilities.Constants with a using statement
// using CONST = Utilities.Constants;
public const int CARD_DATA_VALUES = 25;
public const int CARD_VALUES_AT = 128;
public const int CARD_VALUES_SIZE =
CARD_DATA_VALUES *
sizeof ( byte );
public const int CARD_SIZE = CARD_VALUES_SIZE;
// in local compilation unit
card_offset = ( ( card_number - 1 ) * CONST.CARD_SIZE ) +
CONST.CARD_VALUES_AT;
当玩家喊出“Bingo!”时，叫号员会询问玩家卡片上打印的 group_face 号码。从 group_face 中剥离出组别信息，得到用于访问宾果卡的 card_number。请注意，卡号并未存储在宾果卡文件中，而是隐含的。
每当一张唯一的宾果卡被生成时，其25字节的记录就会被附加到宾果卡文件的末尾。
2.2. Card_File_IO 类
为了保存宾果卡，使用了 FileStream 类 [^]。保存卡片文件所需的各种方法被封装在 Utilities 项目的 Card_File_IO 类中。请注意，以下内容并非该类的全部，仅包含在生成过程中使用的方法。缺失的部分将在本系列的其他部分中讨论。
using System;
using System.IO;
using System.Linq;
using CONST = Utilities.Constants;
namespace Utilities
{
// ******************************************** class Card_File_IO
public class Card_File_IO
{
// the FileStream fs is known
// only within the
// Card_File_IO class
private FileStream fs = null;
// *********************************************** create_file
/// <summary>
/// create a new FileStream for reading and writing
/// </summary>
/// <param name="path">
/// fully qualified path of the file to create
/// </param>
/// <param name="error_message">
/// reference to a string that will receive the error message
/// from the IO system if the creation process fails
/// </param>
/// <returns>
/// true, if the file is created successfully; false otherwise
/// </returns>
public bool create_file ( string path,
ref string error_message )
{
bool success = false;
error_message = String.Empty;
try
{
fs = new FileStream ( path,
FileMode.CreateNew,
FileAccess.ReadWrite,
FileShare.Read );
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
return ( success );
} // create_file
⋮
// **************************************** zero_bytes_in_file
/// <summary>
/// zeros the specified bytes in the FileStream
/// </summary>
/// <param name="start_at">
/// long value specifying the location where the zeroing will
/// begin
/// </param>
/// <param name="count">
/// integer value specifying how many bytes are to be zeroed
/// </param>
/// <note>
/// the file must have been successfully opened or created by
/// an earlier invocation of open_file or create_file
/// </note>
public void zero_bytes_in_file ( long start_at,
int count )
{
if ( fs != null )
{
fs.Seek ( start_at, SeekOrigin.Begin );
for ( int i = 0; ( i < count ); i++ )
{
fs.WriteByte ( ( byte ) 0 );
}
}
} // zero_bytes_in_file
⋮
// *************************************** write_bytes_to_file
/// <summary>
/// writes bytes the card file
/// </summary>
/// <param name="bytes">
/// reference to a byte array from which bytes are to be
/// written
/// </param>
/// <param name="file_offset">
/// long value specifying the location within the file where
/// writing will begin
/// </param>
/// <param name="error_message">
/// reference to a string that will receive the error message
/// from the IO system if the write process fails
/// </param>
/// <returns>
/// true, if the file is written successfully; false otherwise
/// </returns>
/// <note>
/// the file must have been successfully opened or created by
/// an earlier invocation of open_file or create_file
/// </note>
public bool write_bytes_to_file (
byte [ ] bytes,
long offset,
ref string error_message )
{
bool success = false;
error_message = String.Empty;
if ( fs != null )
{
try
{
fs.Seek ( offset, SeekOrigin.Begin );
for ( int i = 0; ( i < bytes.Length ); i++ )
{
fs.WriteByte ( bytes [ i ] );
}
fs.Flush ( );
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
}
return ( success );
} // write_bytes_to_file
// ************************************** append_bytes_to_file
/// <summary>
/// appends (writes) bytes to the end of the card file
/// </summary>
/// <param name="bytes">
/// reference to a byte array from which bytes are to be
/// written
/// </param>
/// <param name="byte_count">
/// integer value containing the number of bytes to write
/// </param>
/// <param name="error_message">
/// reference to a string that will receive the error message
/// from the IO system if the write process fails
/// </param>
/// <returns>
/// true, if the file is written successfully; false otherwise
/// </returns>
/// <note>
/// the file must have been successfully opened or created by
/// an earlier invocation of open_file or create_file
/// </note>
public bool append_bytes_to_file (
byte [ ] bytes,
int byte_count,
ref string error_message )
{
bool success = false;
error_message = String.Empty;
if ( fs != null )
{
try
{
fs.Seek ( 0, SeekOrigin.End );
fs.Write ( bytes, 0, byte_count );
fs.Flush ( );
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
}
return ( success );
} // append_bytes_to_file
// ************************************************ close_file
/// <summary>
/// closes the open card file
/// </summary>
/// <param name="error_message">
/// reference to a string that will receive the error message
/// from the IO system if the close process fails
/// </param>
/// <returns>
/// true, if the file is closed successfully; false otherwise
/// </returns>
/// <note>
/// the file must have been successfully opened or created by
/// an earlier invocation of open_file or create_file
/// </note>
public bool close_file ( ref string error_message)
{
bool success = false;
error_message = String.Empty;
try
{
if ( fs != null )
{
fs.Close ( );
}
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
return ( success );
} // close_file
// *************************************************** Dispose
/// <summary>
/// disposes the card file
/// </summary>
/// <param name="error_message">
/// reference to a string that will receive the error message
/// from the IO system if the disposal process fails
/// </param>
/// <returns>
/// true, if the file is disposed successfully; false,
/// otherwise
/// </returns>
public bool Dispose ( ref string error_message )
{
bool success = false;
error_message = String.Empty;
try
{
if ( fs != null )
{
fs.Dispose ( );
fs = null;
}
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
return ( success );
} // Dispose
} // class Card_File_IO
} // namespace Utilities
FileStream (fs) 是 Card_File_IO 类的私有成员。在 Generate_Cards 应用程序中，它只被创建一次，并由应用程序退出时触发的 application_cleanup 事件处理程序关闭。
// *************************************** application_cleanup
void application_cleanup ( object sender,
EventArgs e )
{
cfio.close_file ( ref error_message );
cfio.Dispose ( ref error_message );
} // application_cleanup
Card_File_IO 类中并没有什么出人意料的地方。其中包含的所有方法都简单明了。
3. 生成卡片
生成唯一宾果卡的方法是：
- 生成一张卡片
- 为卡片中的值生成一个哈希值
- 在哈希值二叉树中搜索新生成的哈希值
- 如果在哈希值二叉树中找到该哈希值，则返回第1步
- 如果在哈希值二叉树中未找到该哈希值
- 将哈希值插入到哈希值二叉树中
- 将新的宾果卡追加到宾果卡文件的末尾
- 如果需要生成另一张卡片，则返回第1步
宾果卡由 BackgroundWorker [^] 的 generate_cards_DoWork 生成。
// ************************************* generate_cards_DoWork
void generate_cards_DoWork ( object sender,
DoWorkEventArgs e )
{
BackgroundWorker worker = ( BackgroundWorker ) sender;
watch.Start ( );
zero_header ( );
for ( int i = 0; ( i < cards_to_generate ); i++ )
{
byte [ ] bytes;
uint hash = 0;
thread_pause_state.Wait ( );
if ( worker.CancellationPending )
{
e.Cancel = true;
return;
}
// loop generates non-
// duplicative Bingo cards
do
{
// generate a Bingo card
bytes = populate_card_array ( );
// generate the hash for the
// Bingo card excluding the
// star index value
hash = generated_hash ( bytes,
CONST.CENTER_CELL_INDEX );
// determine if hash is a
// duplicate
} while ( duplicate_hash ( hash ) );
// no hash duplicate; the hash
// has been added to hashes;
// append the card to the end
// of the card file
append_bingo_card ( bytes );
// update progress bar
worker.ReportProgress ( 0, ( i + 1 ) );
}
// all cards generated
watch.Stop ( );
elapsed_time = watch.Elapsed.TotalSeconds;
e.Result = elapsed_time;
} // generate_cards_DoWork
generate_cards_DoWork 是一个 BackgroundWorker [^]。该算法基于以下观察：
如果一张宾果卡的哈希值与之前的哈希值重复，那么后一张宾果卡与前一张宾果卡重复的概率不为零。
请注意，哈希值重复并不意味着两张宾果卡是重复的。相反，这意味着发生了哈希碰撞。然而，两个不重复的哈希值意味着相关的宾果卡不是重复的。
如果遇到重复的哈希值，新创建的宾果卡不会被添加到不断增长的宾果卡文件中，而是会生成一张新的宾果卡。
3.1. 生成规则
给定列中的值必须遵守以下规则：
- 'B' 列只能包含 1 - 15 之间的值
- 'I' 列只能包含 16 - 30 之间的值
- 'N' 列只能包含 31 - 45 之间的值
- 'G' 列只能包含 46 - 60 之间的值
- 'O' 列只能包含 61 - 75 之间的值
任何列中都不能出现重复的值。
负责生成卡片中值的方法是 populate_card_array。
// in Utilities.Constants with a using statement
// using CONST = Utilities.Constants;
public const int CARD_DATA_VALUES = 25;
public const int CARD_VALUES_AT = 128;
public const int CARD_VALUES_SIZE =
CARD_DATA_VALUES *
sizeof ( byte );
public const int CARD_SIZE = CARD_VALUES_SIZE;
public const int CENTER_CELL_INDEX = 12;
public const int COLUMNS = 5;
public const int ROWS = 5;
// in local compilation unit
const int ALLOWED_IN_COLUMN = 15;
// *************************************** populate_card_array
byte [ ] populate_card_array ( )
{
// allowed is int because
// Enumerable.Range is int
List < int > allowed = new List < int > ( );
byte [ ] bytes = new byte [ card_size ];
int cell = 0;
int index = 0;
for ( int column = 0;
( column < CONST.COLUMNS );
column++ )
{
// generate the 15 allowed
// values for this column
allowed = Enumerable.Range (
( 1 + ( column * ALLOWED_IN_COLUMN ) ),
ALLOWED_IN_COLUMN ).ToList ( );
// for the center column there
// are only 4 rows however we
// generate the free space
// value for simplicity then
// replace it with the star
// position for this card
// for each row, choose a
// value from the allowed
// values and add it to the
// array of bytes
for ( int row = 0; ( row < CONST.ROWS ); row++)
{
// obtain a value from zero
// to ( allowed.Count - 1 )
index = random.Next ( allowed.Count );
bytes [ cell++ ] = ( byte ) allowed [ index ];
// then remove the allowed
// value at index (this
// eliminates duplicates in
// the column)
allowed.RemoveAt ( index );
}
}
// generate the star index
// have 25 indices (0-24) less
// the center cell index (a
// star is never placed in the
// center square); randomly
// choose the index of the
// square that is to have the
// star from star_indices
index = random.Next ( star_indices.Count );
// replace the center square
// with the index of the star
// position for this card
bytes [ CONST.CENTER_CELL_INDEX ] =
( byte ) star_indices [ index ];
return ( bytes );
} // populate_card_array
对于每一列，populate_card_array 首先生成一个列表（allowed），其中包含当前列生成规则所允许的值。请注意， Enumerable.Range [^] 定义在 System.Link 命名空间中，需要使用 "using System.Linq;" 语句。然后对于每一行，生成一个介于 0 和 allowed 列表中当前值数量之间的随机数 [^]。（请注意，random.Next 返回的值总是小于 allowed.Count。）这个值成为 allowed 列表的索引，指向要插入到卡片数组（bytes）中的值。当该值插入到 bytes 数组后，它会从 allowed 列表中移除。这确保了不会在任何列中插入重复的值。
请注意，populate_card_array 会生成25个值，尽管只有24个值是有效的。宾果卡的中心方格将包含一个随机数，该数字是宾果卡上星星位置的索引。为了高效地获取此值，在执行 generate_cards_DoWork 之前，会调用 initialize_star_indices 来生成 star_indices 中允许的索引值。
// *********************************** initialize_star_indices
// generates the allowed indices for the positioning of the
// star
void initialize_star_indices ( )
{
star_indices = Enumerable.Range (
0,
CONST.CARD_DATA_VALUES ).ToList ( );
star_indices.RemoveAt ( CONST.CENTER_CELL_INDEX );
} // initialize_star_indices
如果没有 initialize_star_indices，每次生成宾果卡时都必须生成索引。populate_card_array 从 star_indices 中随机选择一个索引，并将该值放在中心方格中。
3.2. 消除重复的宾果卡
populate_card_array 方法确保在一张宾果卡内部不会出现重复的值。但是，还有另一条规则必须满足——此程序生成的任意两张宾果卡都不能是重复的。为此，需要对宾果卡数组中的值进行哈希计算。
宾果卡被传递给 generated_hash，它为宾果卡数组生成并返回一个无符号的32位整数哈希值。中心方格的索引 (CONST.CENTER_CELL_INDEX) 作为排除索引被传递。
// ******************************************** generated_hash
/// <summary>
/// computes the FNV hash of its parameter
/// </summary>
/// <param name="bytes">
/// byte array containing items for which a hash is required
/// </param>
/// <param name="exclude">
/// integer index into bytes of an element that will be
/// excluded from the generation of the hash; to include all
/// values that are in bytes, set exclude to a value less than
/// zero or greater than the length of bytes
/// </param>
/// <returns>
/// unsigned integer that is the hash of bytes
/// </returns>
/// <reference>
/// FNV hash in https://archive.vn/SFYTe#selection-477.0-477.8
/// </reference>
uint generated_hash ( byte [ ] bytes,
int exclude ) // zero based
{
uint hash = 2166136261;
unchecked
{
for ( int i = 0; ( i < bytes.Length ); i++ )
{
if ( i == exclude )
{
continue;
}
hash = ( hash * 16777619 ) ^ bytes [ i ];
}
}
return ( hash );
} // generated_hash
将要印上星星的方格不应参与哈希生成，因此被排除在外。由 generated_hash 返回的哈希值被传递给 duplicate_hash。
3.3. 搜索重复的宾果卡
在生成宾果卡的过程中，必须避免重复。回想一下，如果两个对象的哈希码不同，那么这两个对象就不相等。问题在于，所有先前生成的宾果卡的哈希值都必须与新生成的宾果卡的哈希值进行比较。本程序用于存储这些哈希值的结构是一个名为 hashes 的无符号整数二叉树。它在 Utilities 项目的 Find_Or_Add 类中声明。
using System.Collections.Generic;
namespace Utilities
{
// ********************************************* class Find_Or_Add
public class Find_Or_Add : List < uint >
{
private static List < uint > hashes = new List < uint > ( );
// *********************************************** find_or_add
public bool find_or_add ( uint hash,
ref int hash_collisions )
{
bool found = true;
int position = this.BinarySearch ( hash );
found = ( position >= 0 );
if ( found )
{
hash_collisions++;
}
else
{
position = ~position;
this.Insert ( position, hash );
}
return ( found );
} // find_or_add
} // class Find_Or_Add
} // namespace Utilities
因此，如果要生成 400,000 张宾果卡，hashes 二叉树将有 400,000 个节点。每当生成一张新的宾果卡时，都必须计算其哈希值，并与 hashes 中不断增加的项目进行比较。
using FOA = Utilities.Find_Or_Add;
⋮
FOA foa = new FOA ( );
⋮
// ******************************************** duplicate_hash
// there may be a hash collision, if there is, duplicate_hash
// returns true
bool duplicate_hash ( uint hash )
{
return ( foa.find_or_add ( hash,
ref hash_collisions ) );
} // duplicate_hash
在 duplicate_hash 返回 true 的情况下，do-while 循环
do
{
bytes = populate_card_array ( );
hash = generated_hash ( bytes,
CONST.CENTER_CELL_INDEX );
} while ( duplicate_hash ( hash ) );
会再次执行。如果 duplicate_hash 返回 false，新的宾果卡将被写入宾果卡文件，然后生成下一张（如果有的话）宾果卡。
当所有宾果卡都生成完毕后，将写入宾果文件头。
// *********************************************** emit_header
void emit_header ( )
{
byte [ ] bytes;
long header_offset = ( long ) ( int ) CONST.HEADER_AT;
bytes = header_values_to_byte_array ( version,
number_cards,
cards_start_at,
card_size,
date_created );
cfio.write_bytes_to_file ( bytes,
header_offset,
ref error_message );
} // emit_header
emit_header 调用辅助方法 header_values_to_byte_array，将构成头部的各个值转换为将作为头部写入的字节数组。
// ******************************* header_values_to_byte_array
// converts individual header items into a single header array
byte [ ] header_values_to_byte_array ( int version,
int number_cards,
int cards_start_at,
int card_size,
int date_created )
{
using ( MemoryStream ms = new MemoryStream ( ) )
{
using ( BinaryWriter bw = new BinaryWriter ( ms ) )
{
bw.Write ( version );
bw.Write ( number_cards );
bw.Write ( cards_start_at );
bw.Write ( card_size );
bw.Write ( date_created );
return ( ms.ToArray ( ) );
}
}
} // header_values_to_byte_array
4. 执行 Generate_Cards
为了执行，Generate_Cards 需要以下信息：
- 保存宾果卡文件的位置
- 要生成的卡片数量
为避免权限问题，Generate_Cards 的默认目录是 C:\Users\Public\Bingo。当点击 Browse 按钮时，将显示默认目录中的现有文件。选择一个现有文件将导致类似以下的警告：
一旦指定了输出文件，并输入了要生成的卡片数量，点击 Go 按钮，Generate_Cards 就会执行到结束。
在这种情况下，指定了 800,000 张卡片。
为了验证卡片的生成，我使用了 ViewFile [^] 工具。
值 0x03（十进制3）是版本号；值 0xC3500（十进制800,000）是此文件中包含的卡片数量；值 0x80（十进制128）是宾果卡的起始字节；值 0x19（十进制25）是每张宾果卡的字节数；而 0x134B03D（十进制20230205）是此宾果卡文件的创建日期。第一张卡在字节128处可见。如果 ViewFile 以十进制显示左侧（通过清除十六进制复选框），显示将如下所示。
从字节 128 开始，前五个字节是第一列 ('B') 的值；接下来五个字节是第二列 ('I') 的值；再接下来两个字节是第三列 ('N') 的前两个值；下一个字节是星星的索引 (4)；再接下来两个字节是第三列 ('N') 的后两个值；接下来五个字节是第四列 ('G') 的值；最后五个字节是第五列 ('O') 的值。
如果将这些值放在宾果卡上，它们将如下图所示。这就是 Print_Cards 所做的工作，也是本系列下一篇文章的主题。
请注意，这些列中的值遵守之前的生成规则。
最后，我认为最好验证一下星星的位置。数据从宾果卡文件中收集，并转换为一个DataTable，然后转换为一个CSV文件。CSV文件由Excel打开，并绘制了数据图表。
结果与预期相符：星星的分布相对均匀，并且没有星星被放置在中心方格。所有分布的总和为 800,000，即生成的卡片数量。
5. 结论
Generate_Cards 会生成一个包含唯一宾果卡的文件。下一步是根据用户规格打印这些卡片。这是本系列第二篇文章的主题。
6. 参考文献
- BackgroundWorker [^]
- Bingo [^]
- Bingo (American version) [^]
- Enumerable.Range [^]
- FileStream 类 [^]
- Random [^]
- ViewFile [^]
7. 开发环境
本文介绍的软件是在以下环境中开发的
| Microsoft Windows 7 Professional Service Pack 1 |
| Microsoft Visual Studio 2008 Professional |
| Microsoft .Net Framework Version 3.5 SP1 |
| Microsoft Visual C# 2008 |
8. 历史记录
| 宾果游戏 - 3部分之1 - 生成卡片 | 02/10/2023 | 原始文章 |