Главная » Разработка для Windows Phone 7 » Лабиринт Windows Phone 7

0

Одним из самых естественных применений функциональности катящегося шара является игра лабиринт. Несомненно, в связи с этим необходимо решить несколько проблем, включая создание случайного лабиринта и реализацию логики, которая обеспечит удержание шара в границах «коридоров» лабиринта.

Немного изучив алгоритмы поколений лабиринтов, я остановил свой выбор на, возможно, самом простом. Он называется «рекурсивное деление» и обеспечивает создание лабиринта, который выглядит примерно, как показано на рисунке:

Как видим, это не очень интересный лабиринт, но его основным преимуществом является то, что из любой его области можно попасть в любую другую область.

Концептуально вся область лабиринта – это сетка ячеек. В данном примере мы видим пять ячеек по горизонтали и восемь ячеек по вертикали, всего 40. Каждая из этих ячеек может быть окружена «стеной» максимум с трех из сторон. Рассмотрим простую открытую структуру из библиотеки Petzold.Phone.Xna, которая описывает такую ячейку:

Проект: Petzold.Phone.Xna Файл: MazeCell.cs

namespace Petzold.Phone.Xna {

public struct MazeCell {

public bool HasLeft { internal set; get; } public bool HasTop { internal set; get; } public bool HasRight { internal set; get; } public bool HasBottom { internal set; get; }

public MazeCell(bool left, bool top, bool right, bool bottom) : this() {

HasLeft = left; HasTop = top; HasRight = right; HasBottom = bottom;

}

}

}

Свойство HasTop (Закрыта сверху) всех верхних ячеек имеет значение true; свойство HasLeft (Закрыта слева) имеет значение true для всех ячеек вдоль левого края; и аналогично для правого края и низа.

Массив объектов MazeCell (Ячейка лабиринта), составляющих лабиринт, создается и сохраняется в объекте MazeGrid (Сетка лабиринта). Единственный конструктор MazeGrid принимает ширину и высоту, выраженные числом ячеек (например, 5 и 8 для приведенного выше примера). Рассмотрим конструктор MazeGrid, три открытых свойства, а также объект Random:

Проект: Petzold.Phone.Xna Файл: MazeGrid.cs (фрагмент)

public class MazeGrid {

Random rand = new Random();

public MazeGrid(int width, int height) {

Width = width; Height = height;

Cells = new MazeCell[Width, Height];

for (int y = 0; y < Height; y++)

for (int x = 0; x < Width; x++) {

Cells[x, y].HasLeft = x == 0; Cells[x, y].HasTop = y == 0; Cells[x, y].HasRight = x == Width – 1; Cells[x, y].HasBottom = y == Height – 1;

}

MazeChamber rootChamber = new MazeChamber(0, 0, Width, Height); DivideChamber(rootChamber);

}

public int Width { protected set; get; } public int Height { protected set; get; } public MazeCell[,] Cells { protected set; get; }

}

Конструктор MazeGrid завершается созданием объекта типа MazeChamber (Секция лабиринта), размер которого соответствует размеру MazeGrid, и вызовом рекурсивного метода DivideChamber (Разделить секцию), который мы вскоре рассмотрим. В алгоритме формирования лабиринта секция – это прямоугольная сетка ячеек, внутренняя область которой освобождена от перегородок. Каждая секция сначала делится надвое посредством установления произвольным образом (но, как правило, вдоль меньшего размера) перегородки с одним просветом, который также размещается произвольным образом. В результате этого процесса создаются две секции, соединенные этим просветом. Такое последовательное деление на секции продолжается до тех пор, пока секции не достигают размера ячейки.

MazeChamber – это класс библиотеки Petzold.Phone.Xna. Рассмотрим полный код класса, который имеет собственное поле Random:

Проект: Petzold.Phone.Xna Файл: MazeChamber.cs

using System;

namespace Petzold.Phone.Xna {

internal class MazeChamber {

static Random rand = new Random();

public MazeChamber(int x, int y, int width, int height) : base ()

X = x; Y = y;

Width = width;

Height                         = height;

}

public int            X { protected set; get; }

public int            Y { protected set; get; }

public int          Width { protected set; get; }

public int          Height { protected set; get; }

public MazeChamber Chamber1 { protected set; get; } public MazeChamber Chamber2 { protected set; get; }

public int Divide(bool divideWidth) {

if (divideWidth) {

int col = rand.Next(X + 1, X + Width – 1); Chamber1 = new MazeChamber(X, Y, col – X, Height); Chamber2 = new MazeChamber(col, Y, X + Width – col, Height); return col;

}

else {

int row = rand.Next(Y + 1, Y + Height – 1); Chamber1 = new MazeChamber(X, Y, Width, row – Y); Chamber2 = new MazeChamber(X, row, Width, Y + Height – row); return row;

}

}

}

}

Метод Divide (Разделить) фактически разделяет одну секцию на две на основании выбранных случайным образом строки и столбца и создает два новых объекта MazeChamber. Рекурсивный метод DivideChamber объекта MazeGrid отвечает за вызов этого метода Divide и окружение получившихся ячеек перегородками с трех сторон:

Проект: Petzold.Phone.Xna Файл: MazeGrid.cs (фрагмент)

void DivideChamber(MazeChamber chamber) {

if (chamber.Width == 1 && chamber.Height == 1) {

return;

}

bool divideWidth = chamber.Width > chamber.Height;

if (chamber.Width == 1 || chamber.Height >= 2 * chamber.Width) {

divideWidth = false;

}

else if (chamber.Height == 1 || chamber.Width >= 2 * chamber.Height) {

divideWidth = true;

}

else {

divideWidth = Convert.ToBoolean(rand.Next(2));

}

int rowCol = chamber.Divide(divideWidth);

if (divideWidth) {

int col = rowCol;

int gap = rand.Next(chamber.Y, chamber.Y + chamber.Height);

for (int y = chamber.Y; y < chamber.Y + chamber.Height; y++) {

Cells[col – 1, y].HasRight = y != gap; Cells[col, y].HasLeft = y != gap;

}

}

else {

int row = rowCol;

int gap = rand.Next(chamber.X, chamber.X + chamber.Width);

for (int x = chamber.X; x < chamber.X + chamber.Width; x++) {

Cells[x, row – 1].HasBottom = x != gap; Cells[x, row].HasTop = x != gap;

}

}

DivideChamber(chamber.Chamber1); DivideChamber(chamber.Chamber2);

}

Также я понял, что должен обобщить логику отскока, и для этого мне необходимо найти хороший способ представления геометрического сегмента линия, который бы позволял вычислять точки пересечения и осуществлять другие полезные операции. Эту структуру я назвал Line2D. Сегмент линия определяется двумя точками, которые также описывают свойство Vector и свойство Normal (Нормаль) (перпендикуляр к вектору), таким образом, концептуально линия имеет направление и также «внутреннюю» и «внешнюю» стороны.

Проект: Petzold.Phone.Xna Файл: Line2D.cs

using System;

using Microsoft.Xna.Framework;

namespace Petzold.Phone.Xna {

// представляем линию как pt1 + t(pt2 – pt1)

public struct Line2D {

public Line2D(Vector2 pt1, Vector2 pt2) : this() {

Point1 = pt1; Point2 = pt2;

Vector = Point2 – Point1;

Normal = Vector2.Normalize(new Vector2(-Vector.Y, Vector.X));

}

public Vector2 Point1 { private set;            get; }

public Vector2 Point2 { private set;            get; }

public Vector2 Vector { private set;            get; }

public Vector2 Normal { private set;            get; }

public float Angle {

get {

return (float)Math.Atan2(this.Point2.Y – this.Point1.Y,

this.Point2.X – this.Point1.X);

public Line2D Shift(Vector2 shift) {

return new Line2D(this.Point1 + shift, this.Point2 + shift);

}

public Line2D ShiftOut(Vector2 shift) {

Line2D shifted = Shift(shift);

Vector2 normalizedVector = Vector2.Normalize(Vector); float length = shift.Length();

return new Line2D(shifted.Point1 – length * normalizedVector, shifted.Point2 + length * normalizedVector);

}

public Vector2 Intersection(Line2D line) {

float tThis, tThat;

IntersectTees(line, out tThis, out tThat); return Point1 + tThis * (Point2 – Point1);

}

public Vector2 SegmentIntersection(Line2D line) {

float tThis, tThat;

IntersectTees(line, out tThis, out tThat);

if (tThis < 0 || tThis > 1 || tThat < 0 || tThat > 1) return new Vector2(float.NaN, float.NaN);

return Point1 + tThis * (Point2 – Point1);

}

void IntersectTees(Line2D line, out float tThis, out float tThat) {

float den = line.Vector.Y * this.Vector.X – line.Vector.X * this.Vector.Y;

tThis = (line.Vector.X * (this.Point1.Y – line.Point1.Y) -

line.Vector.Y * (this.Point1.X – line.Point1.X)) / den;

tThat = (this.Vector.X * (this.Point1.Y – line.Point1.Y) -

this.Vector.Y * (this.Point1.X – line.Point1.X)) / den;

}

public override string ToString() {

return String.Format("{0} –> {1}", this.Point1, this.Point2);

}

public static bool IsValid(Vector2 vector) {

return ISingle.IsNaN(vector.X) && ISingle.IsInfinity(vector.X) && ISingle.IsNaN(vector.Y) && ISingle.IsInfinity(vector.Y);

}

}

}

Поскольку линия описывается параметрическими уравнениями, не составляет особого труда найти точки пересечения, подставляя предполагаемые значения t, связанные с точкой на линии.

Все эти предварительные мероприятия являются подготовкой к проекту TiltMaze (Лабиринт с наклонением). Поля проекта включают tinyTexture, используемый для отображения перегородок сетки. Чрезвычайно важную роль в этом приложении играет коллекция List объектов Line2D под именем borders (рамки). Объекты Line2D в коллекции borders определяют контуры перегородок, разделяющих ячейки. Каждая перегородка имеет ширину, которая определяется константой WALL_WIDTH.

Проект XNA: TiltMaze Файл: Game1.cs (фрагмент, демонстрирующий поля)

public class Game1 : Microsoft.Xna.Framework.Game {

const      float GRAVITY = 1000;       // пикселы в секунду в квадрате

const      float BOUNCE = 2f / 3; // доля скорости

const      int BALL_RADIUS = 16;

const      int BALL_SCALE = 16;

const      int WALL WIDTH = 32;

GraphicsDeviceManager graphics; SpriteBatch spriteBatch;

Viewport viewport; Texture2D tinyTexture;

MazeGrid mazeGrid = new MazeGrid(5, 8); List<Line2D> borders = new List<Line2D>();

Texture2D ball;

Vector2 ballCenter;

Vector2 ballPosition;

Vector2 ballVelocity = Vector2.Zero;

Vector3 oldAcceleration, acceleration;

object accelerationLock = new object();

public Game1() {

graphics = new GraphicsDeviceManager(this); Content.RootDirectory = "Content";

// Частота кадров по умолчанию для устройств Windows Phone – 30 кадров/с TargetElapsedTime = TimeSpan.FromTicks(333333);

// Задаем портретную ориентацию как единственно возможную graphics.SupportedOrientations = DisplayOrientation.Portrait; graphics.PreferredBackBufferWidth = 480; graphics.PreferredBackBufferHeight = 768;

}

}

Как обычно, перегруженный Initialize определяет объект Accelerometer, и обработчик ReadingChanged сохраняет сглаженное значение.

Проект XNA: TiltMaze Файл: Game1.cs (фрагмент)

protected override void Initialize() {

Accelerometer accelerometer = new Accelerometer(); accelerometer.ReadingChanged += OnAccelerometerReadingChanged;

try { accelerometer.Start(); } catch { }

base.Initialize();

void OnAccelerometerReadingChanged(object sender, AccelerometerReadingEventArgs

args) {

lock (accelerationLock) {

acceleration = 0.5f * oldAcceleration +

0.5f * new Vector3((float)args.X, (float)args.Y,

(float)args.Z);

oldAcceleration = acceleration;

}

}

Большая часть метода LoadContent посвящена построению коллекции borders, и я совершенно недоволен этим кодом. (Он в моем первоочередном списке на переработку, как только у меня найдется свободное время.) Данный код рассматривает отдельно каждую ячейку и затем отдельно каждую сторону этой ячейки. Если с определенной стороны ячейки имеется перегородка, рамка этой ячейки определяется тремя объектами Line2D:

Проект XNA: TiltMaze Файл: Game1.cs (фрагмент)

protected override void LoadContent() {

// Создаем новый SpriteBatch, который может использоваться для отрисовки текстур spriteBatch = new SpriteBatch(GraphicsDevice);

viewport = this.GraphicsDevice.Viewport;

// Создаем текстуру для перегородок лабиринта tinyTexture = new Texture2D(this.GraphicsDevice, 1, 1); tinyTexture.SetData<Color>(new Color[] { Color.White });

// Создаем шар

ball = Texture2DExtensions.CreateBall(this.GraphicsDevice,

BALL RADIUS * BALL SCALE);

ballCenter = new Vector2(ball.Width / 2, ball.Height / 2); ballPosition = new Vector2((viewport.Width / mazeGrid.Width) / 2,

(viewport.Height / mazeGrid.Height) / 2);

// Инициализируем коллекцию borders borders.Clear();

// Создаем объекты Line2D для перегородок лабиринта int cellWidth = viewport.Width / mazeGrid.Width; int cellHeight = viewport.Height / mazeGrid.Height; int halfWallWidth = WALL WIDTH / 2;

for (int x = 0; x < mazeGrid.Width; x++)

for (int y = 0; y < mazeGrid.Height; y++) {

MazeCell mazeCell = mazeGrid.Cells[x, y];

Vector2 ll = new Vector2(x * cellWidth, (y + 1) * cellHeight); Vector2 ul = new Vector2(x * cellWidth, y * cellHeight); Vector2 ur = new Vector2((x + 1) * cellWidth, y * cellHeight); Vector2 lr = new Vector2((x + 1) * cellWidth, (y + 1) * cellHeight); Vector2 right = halfWallWidth * Vector2.UnitX; Vector2 left = -right;

Vector2 down = halfWallWidth * Vector2.UnitY; Vector2 up = -down;

if (mazeCell.HasLeft) {

borders.Add(new Line2D(ll + down, ll + down + right));

borders.Add(new Line2D(ll + down + right, ul + up + right)); borders.Add(new Line2D(ul + up + right, ul + up));

if (mazeCell.HasTop)

borders.Add(new Line2D(ul + left, ul + left + down)); borders.Add(new Line2D(ul + left + down, ur + right + down)); borders.Add(new Line2D(ur + right + down, ur + right));

if (mazeCell.HasRight)

borders.Add(new Line2D(ur + up, ur + up + left)); borders.Add(new Line2D(ur + up + left, lr + down + left)); borders.Add(new Line2D(lr + down + left, lr + down));

if (mazeCell.HasBottom)

borders.Add(new Line2D(lr + right, lr + right + up)); borders.Add(new Line2D(lr + right + up, ll + left + up)); borders.Add(new Line2D(ll + left + up, ll + left));

}

}

}

Проблема в том, что в коллекции borders слишком много объектов Line2D. Они часто дублируются для одной и той же или примыкающих ячеек. Такое дублирование абсолютно избыточно, поскольку все эти объекты Line2D, по сути, накладываются на одну общую перегородку.

Сама по себе проблема не так велика, но избыточные объекты Line2D оказывают негативное влияние на производительность приложения. Это становится абсолютно очевидным, когда шар скатывается вдоль длинной перегородки. Он, кажется, немного спотыкается, как будто натыкается на одну из этих невидимых границ и отскакивает от нее.

Решение данной проблемы перенесем в логику метода Update. Как я говорил ранее, мне требовалось найти более обобщённый метод реализации отражения шара от перегородок. В результате я пришел к следующему подходу, который мне тоже не очень нравится. Он использует коллекцию borders и привносит собственные небольшие ошибки:

Проект XNA: TiltMaze Файл: Game1.cs (фрагмент)

protected override void Update(GameTime gameTime) {

// Обеспечиваем возможность выхода из игры

if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed) this .Exit();

// Вычисляем новую скорость и координаты Vector2 acceleration2D = Vector2.Zero;

lock (accelerationLock) {

acceleration2D = new Vector2(acceleration.X, -acceleration.Y);

}

float elapsedSeconds = (float)gameTime.ElapsedGameTime.TotalSeconds; ballVelocity += GRAVITY * acceleration2D * elapsedSeconds; Vector2 oldPosition = ballPosition; ballPosition += ballVelocity * elapsedSeconds;

bool needAnotherLoop = false;

do {

needAnotherLoop = false;

foreach (Line2D line in borders) {

Line2D shiftedLine = line.ShiftOut(BALL RADIUS * line.Normal); Line2D ballTrajectory = new Line2D(oldPosition, ballPosition); Vector2 intersection = shiftedLine.SegmentIntersection(ballTrajectory); float angleDiff = MathHelper.WrapAngle(line.Angle – ballTrajectory.Angle);

if (Line2D.IsValid(intersection) && angleDiff > 0 && Line2D.IsValid(Vector2.Normalize(ballVelocity)))

{

float beyond = (ballPosition – intersection).Length(); ballVelocity = BOUNCE * Vector2.Reflect(ballVelocity, line.Normal); ballPosition = intersection + beyond * Vector2.Normalize(ballVelocity);

needAnotherLoop = true; break;

}

}

}

while (needAnotherLoop); base.Update(gameTime);

}

Для каждого объекта Line2D в коллекции borders этот код вызывает метод ShiftOut (Выдвинуть) структуры, которая создает еще одну линию на внешней стороне перегородки, отстоящую от линии края на величину BALL_RADIUS и удлиненную на BALL_RADIUS со всех сторон. Я использую этот новый объект Line2D как пограничную линию. Она непроницаема для центра шара и обеспечивает поверхность, от которой этот центр шара может отскакивать.

В этом подходе две проблемы. Во-первых, он не годится для углов. Если я на самом деле хочу предотвратить прохождение шара сквозь границу, эта граница в углах должна быть образована дугой, являющейся четвертью окружности. Во-вторых, в отличие от составляющих перегородки объектов Line2D этот новый Line2D «торчит» из стены, что и обусловливает этот эффект «спотыкания», о котором я говорил ранее.

Перегруженный Draw вообще не использует коллекцию borders, но реализует подобную логику для отрисовки иногда перекрывающихся прямоугольных текстур:

Проект XNA: TiltMaze Файл: Game1.cs (фрагмент)

protected override void Draw(GameTime gameTime) {

GraphicsDevice.Clear(Color.Navy); spriteBatch.Begin();

// Отрисовываем перегородки лабиринта int cellWidth = viewport.Width / mazeGrid.Width; int cellHeight = viewport.Height / mazeGrid.Height; int halfWallWidth = WALL_WIDTH / 2;

for (int x = 0; x < mazeGrid.Width; x++)

for (int y = 0; y < mazeGrid.Height; y++) {

MazeCell mazeCell = mazeGrid.Cells[x, y];

if (mazeCell.HasLeft) {

Rectangle rect = new Rectangle(x * cellWidth,

y * cellHeight – halfWallWidth, halfWallWidth, cellHeight +

WALL_WIDTH);

spriteBatch.Draw(tinyTexture, rect, Color.Green);

}

if (mazeCell.HasRight) {

Rectangle rect = new Rectangle((x + 1) * cellWidth – halfWallWidth,

y * cellHeight – halfWallWidth, halfWallWidth, cellHeight +

WALL_WIDTH);

spriteBatch.Draw(tinyTexture, rect, Color.Green);

}

if (mazeCell.HasTop) {

Rectangle rect = new Rectangle(x * cellWidth – halfWallWidth,

y * cellHeight, cellWidth + WALL_WIDTH,

halfWallWidth);

spriteBatch.Draw(tinyTexture, rect, Color.Green);

}

if (mazeCell.HasBottom) {

Rectangle rect = new Rectangle(x * cellWidth – halfWallWidth,

(y + 1) * cellHeight – halfWallWidth, cellWidth + WALL_WIDTH,

halfWallWidth);

spriteBatch.Draw(tinyTexture, rect, Color.Green);

}

}

// Отрисовываем шар

spriteBatch.Draw(ball, ballPosition, null, Color.Pink, 0,

ballCenter, 1f / BALL SCALE, SpriteEffects.None, 0);

spriteBatch.End();

base.Draw(gameTime);

}

Конечно, я знаю, что должен делать: я должен использовать более обобщенный подход при создании этих перегородок. Необходимо знать, сколько перегородок встречается в каждом пересечении, и определять только истинные контуры этих перегородок.

Как и многие программные проекты, которые никогда по-настоящему не заканчиваются, подозреваю, эта книга тоже не окончена.

 

Источник: Чарльз Петзольд, Программируем Windows Phone 7, Microsoft Press, © 2011.

По теме:

  • Комментарии