关于这个游戏的创意和较为深入的研究来自于新浪博客大力水手。
拉登游戏的游戏思路是:
一个N*N的方格,每个格子的有两种颜色状态(黑色,黄色);初始时所有格子为同一种颜色(比如:黑色),通过点击其中的一个格子,该格子以及其上下左右的格子的颜色将变为相反的颜色(之前黑色,之后黄色;反之亦然)。
如下面六张图可以看到整个游戏的玩法:
游戏开发过程考虑的几个问题:
1.生成的N*N格子的应该自适应Window
2.点击格子四周的格子的边界问题处理
3.格子的颜色变化设置
4.判断所有格子颜色是否发生改变
5.如何实现自动完成功能
游戏开发的关键就在于这个自动完成的算法实现。
算法:
格子共有N*N个,共N行N列,自动完成基于第一行的实现,每一个格子的状态只有两种,设为0或1.
1.第0行有N个格子,每个格子共有2中状态,全排列共有Pow(2, N)中情况。
2.给每一种情况进行编号[0,Pow(2,N))
如下图3*3的格子,第0行的格子的状态:
分析:第0行的状态共有Pow(2,N)中,接下来对第1行至第N-1一行进行遍历,每一行有N个格子进行点击处理,这样时间复杂度上升为:Pow(2, N)*Pow(N, 2)。如果N为32的时候,就仅仅让计算机走完这个数,Java中Integer.MAX_VALUE尝试了一下没有等到这个数就给Stop了。
具大力水手的说法,目前通过分布式计算,已经完成到了N=35。每一种贴下来的图都是一幅美丽的图片(这个得仔细想象加观察)
下面贴一张图:
下面是C#版的部分代码程序较为简单,主要立足解决分布式问题。
- using System;
-
using System.Collections.Generic;
-
using System.ComponentModel;
-
using System.Data;
-
using System.Drawing;
-
using System.Text;
-
using System.Windows.Forms;
-
using System.Threading;
-
-
namespace OkLight
- {
-
public partial class FormMain : Form
- {
-
Button[] btns = new Button[25];
-
-
static int[] states;
-
static int[] operaters;
-
-
static int count = 0;
-
-
-
public FormMain()
- {
- InitializeComponent();
- }
-
-
-
private void FormMainLoad(object sender, EventArgs e)
- {
-
-
int min = panelMain.Height;
-
if (min > panelMain.Width)
- {
- min = panelMain.Width;
- }
-
int maxNumber = min / 40;
-
for (int i = 1; i < maxNumber + 1; i++)
- {
- comboBoxIndex.Items.Add(i);
- }
- comboBoxIndex.SelectedIndex = 4;
-
InitalButton((int)comboBoxIndex.SelectedItem);
- }
-
-
-
private void InitalButton(int number)
- {
- panelMain.Controls.Clear();
-
-
int x = (panelMain.Width - number*40) / 2;
-
int y = (panelMain.Height - number * 40) / 2;
-
btns = new Button[number * number];
-
-
-
for (int i = 0; i < number*number; i++)
- {
-
btns[i] = new Button();
- btns[i].Width = 40;
- btns[i].Height = 40;
-
- btns[i].Left = x + (i % number) * 40;
- btns[i].Top = y + (i / number) * 40;
-
- btns[i].BackColor = Color.Black;
-
-
btns[i].Click += new EventHandler(FormMainClick);
- panelMain.Controls.Add(btns[i]);
- }
-
- }
-
-
-
void FormMainClick(object sender, EventArgs e)
- {
-
int number = (int)comboBoxIndex.SelectedItem;
-
Button btn = sender as Button;
-
-
int x = (panelMain.Width - 40*number) / 2;
-
int y = (panelMain.Height - 40*number) / 2;
-
-
int i = (btn.Left - x) / 40;
-
int j = (btn.Top - y) / 40;
-
-
int top = j - 1;
-
int buttoom = j + 1;
-
int left = i - 1;
-
int right = i + 1;
- count++;
- ChangeButtonColor(btn);
-
if (top >= 0)
- {
-
int index = i + number * top;
- ChangeButtonColor(btns[index]);
- }
-
if (buttoom < number)
- {
-
int index = i + number * buttoom;
- ChangeButtonColor(btns[index]);
- }
-
if(left>=0)
- {
-
int index = left + number * j;
- ChangeButtonColor(btns[index]);
- }
-
if (right < number)
- {
-
int index = right + number * j;
- ChangeButtonColor(btns[index]);
- }
-
showLabel.Text = "您当前已经点击次数为: " + count;
-
if (IsSucceed(number))
- {
-
DialogResult dr=MessageBox.Show("恭喜你,成功完成", "消息");
- }
- }
-
-
-
private void ChangeButtonColor(Button btn)
- {
-
if (btn.BackColor == Color.Black)
- {
- btn.BackColor = Color.Yellow;
- }
-
else
- {
- btn.BackColor = Color.Black;
- }
- btn.Refresh();
-
- }
-
-
-
private void GetShow(int number)
- {
-
-
-
int count = (int)Math.Pow(number, 2);
-
-
-
-
-
-
for (int i = 0; i < (int)Math.Pow(2, number); i++)
- {
-
states = new int[count];
-
operaters = new int[count];
-
int x = i;
-
int j = 0;
-
-
while (true)
- {
-
if (x == 0)
- {
-
break;
-
- }
-
- operaters[j] = x % 2;
- x = x / 2;
- j++;
- }
-
-
-
for (int k = 0; k < number; k++)
- {
-
-
if (operaters[k] == 1)
- {
- ToClick(k, number);
- }
- }
-
-
-
for (int k = 1; k < number; k++)
- {
-
-
for (int m = 0; m < number; m++)
- {
-
-
-
-
if (states[(k - 1) * number + m] == 0)
- {
-
- operaters[k * number + m] = 1;
- ToClick(k * number + m, number);
- }
-
- }
- }
-
-
int statesCount = 0;
-
for (int k = 0; k < states.Length; k++)
- {
-
if (states[k] == 1)
- {
- statesCount++;
- }
- }
-
-
if (statesCount == count)
- {
-
break;
- }
-
- }
-
- }
-
-
-
private bool IsSucceed(int number)
- {
-
bool result = false;
-
for (int i = 0, j = number * number; i < j; i++)
- {
-
if (btns[i].BackColor == Color.Black)
- {
-
result = false;
-
break;
- }
-
else
- {
-
result = true;
- }
- }
-
return result;
- }
-
-
-
private void SelectedIndexChanged(object sender, EventArgs e)
- {
-
int number = (int)comboBoxIndex.SelectedItem;
- count = 0;
-
showLabel.Text = "您当前已经点击次数为:";
- InitalButton(number);
- }
-
-
-
private static void ToClick(int tag, int number)
- {
-
-
-
int j = tag / number;
-
-
int i = tag % number;
-
int left = i - 1;
-
int right = i + 1;
-
int top = j - 1;
-
int buttom = j + 1;
- ChangeButtonStates(tag);
-
if (left >= 0)
- {
- ChangeButtonStates(left + number * j);
- }
-
if (right < number)
- {
- ChangeButtonStates(right + number * j);
- }
-
if (top >= 0)
- {
- ChangeButtonStates(i + number * top);
- }
-
if (buttom < number)
- {
- ChangeButtonStates(i + number * buttom);
- }
- }
-
-
-
private static void ChangeButtonStates(int index)
- {
-
if (states[index] == 0)
- {
- states[index] = 1;
- }
-
else
- {
- states[index] = 0;
- }
- }
-
-
-
private void BtnShowClick(object sender, EventArgs e)
- {
-
int number = (int)comboBoxIndex.SelectedItem;
- GetShow(number);
-
for(int i = 0; i < operaters.Length;i++)
- {
-
if(operaters[i]==1)
- {
- btns[i].PerformClick();
- Thread.Sleep(1000);
- }
- }
- }
- }
-
- }
游戏算是成功的开发完了,而且这个游戏是没有终结点的。因为任何人在每一步都走对的情况下都没法通过鼠标点击走到N=32的情况去,甚至更小。这算是一个探讨分布式计算的一个非常好的实例。
本文转自 secondriver 51CTO博客,原文链接:http://blog.51cto.com/aiilive/1073349,如需转载请自行联系原作者