Skip to content

Instantly share code, notes, and snippets.

Created March 13, 2013 14:56
Show Gist options
  • Save anonymous/5152903 to your computer and use it in GitHub Desktop.
Save anonymous/5152903 to your computer and use it in GitHub Desktop.
GridPather class
// This file created by Emma 'Eniko' Maassen
// Licensed under Creative Commons Attribution 3.0 Unported (CC BY 3.0)
// http://creativecommons.org/licenses/by/3.0/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
namespace Indigo.Framework.Random {
public class GridPath {
public GridCell[,] Grid;
public GridCell From;
public GridCell To;
public GridPath(GridCell[,] grid, GridCell from, GridCell to) {
Grid = grid;
From = from;
To = to;
}
public GridCell GetConnectedCell(GridCell cell, CellConnection con) {
GridCell conCell = null;
switch (con) {
case CellConnection.East:
conCell = Grid[cell.X + 1, cell.Y];
break;
case CellConnection.West:
conCell = Grid[cell.X - 1, cell.Y];
break;
case CellConnection.South:
conCell = Grid[cell.X, cell.Y + 1];
break;
case CellConnection.North:
conCell = Grid[cell.X, cell.Y - 1];
break;
}
return conCell;
}
/// <summary>
/// Create a number of random connections between cells in the grid.
/// </summary>
/// <param name="count">Number of connections to make.</param>
/// <param name="includeFinal">Allows making connections to/from the final cell in the path if true.</param>
public void AddRandomConnections(int count, System.Random random, bool includeFinal = true) {
// make list of cells that can be connected
List<GridCell> connectableCells = new List<GridCell>();
foreach (GridCell cell in Grid) {
if (cell.HasUnconnectedNeighbors && (cell != To || includeFinal))
connectableCells.Add(cell);
}
for (int i = 0; i < count; i++) {
if (connectableCells.Count == 0)
break;
GridCell cell = null;
while (connectableCells.Count > 0 &&
(cell == null || !cell.HasUnconnectedNeighbors || (!includeFinal && cell == To))) {
cell = connectableCells[random.Next(connectableCells.Count)];
if (!includeFinal) {
List<GridCell> uncNeigh = cell.GetUnconnectedNeighbors(this);
if (uncNeigh.Count == 1 && uncNeigh[0] == To) {
connectableCells.Remove(cell);
cell = null;
}
}
}
if (cell == null)
break;
CellConnection con = cell.ConnectRandom(random);
GridCell conCell = GetConnectedCell(cell, con);
conCell.ConnectedFrom(con);
if (!cell.HasUnconnectedNeighbors)
connectableCells.Remove(cell);
if (!conCell.HasUnconnectedNeighbors)
connectableCells.Remove(conCell);
}
}
}
public enum CellConnection {
North,
South,
East,
West
}
public class GridCell {
public int X { get; set; }
public int Y { get; set; }
private List<CellConnection> connections;
private List<CellConnection> neighbors;
private List<CellConnection> unconnectedNeighbors;
public GridCell(int x, int y, List<CellConnection> neighbors) {
X = x;
Y = y;
connections = new List<CellConnection>();
this.neighbors = neighbors;
if (this.neighbors == null)
this.neighbors = new List<CellConnection>();
unconnectedNeighbors = new List<CellConnection>(this.neighbors);
}
public void Connect(CellConnection connection) {
if (!Connections.Contains(connection)) {
Connections.Add(connection);
UnconnectedNeighbors.Remove(connection);
}
}
public void ConnectedFrom(CellConnection side) {
CellConnection con;
switch (side) {
case CellConnection.East:
con = CellConnection.West;
break;
case CellConnection.West:
con = CellConnection.East;
break;
case CellConnection.South:
con = CellConnection.North;
break;
case CellConnection.North:
default:
con = CellConnection.South;
break;
}
Connect(con);
}
public CellConnection ConnectRandom(System.Random random) {
if (UnconnectedNeighbors.Count == 0)
throw new NoUnconnectedNeighborsException("Error connecting GridCell to random neighbor");
CellConnection con = UnconnectedNeighbors[random.Next(UnconnectedNeighbors.Count)];
Connect(con);
return con;
}
public CellConnection? ConnectToRandomConnectedNeighbor(System.Random random, GridPath path) {
if (UnconnectedNeighbors.Count == 0)
return null;
List<CellConnection> possibleNeighbors = new List<CellConnection>(unconnectedNeighbors);
while (possibleNeighbors.Count > 0) {
CellConnection con = possibleNeighbors[random.Next(possibleNeighbors.Count)];
GridCell cell = path.GetConnectedCell(this, con);
if (cell.IsConnected) {
Connect(con);
return con;
}
else
possibleNeighbors.Remove(con);
}
return null;
}
public List<GridCell> GetUnconnectedNeighbors(GridPath path) {
if (!HasUnconnectedNeighbors)
return null;
List<GridCell> unconnectedNeighbors = new List<GridCell>();
List<CellConnection> cons = new List<CellConnection>();
if (X > 0)
cons.Add(CellConnection.West);
if (X < path.Grid.GetUpperBound(0))
cons.Add(CellConnection.East);
if (Y > 0)
cons.Add(CellConnection.North);
if (Y < path.Grid.GetUpperBound(1))
cons.Add(CellConnection.South);
foreach (CellConnection con in Connections) {
cons.Remove(con);
}
foreach (CellConnection con in cons) {
unconnectedNeighbors.Add(path.GetConnectedCell(this, con));
}
return unconnectedNeighbors;
}
#region Properties
public bool IsConnected {
get {
return connections.Count > 0;
}
}
public bool HasUnconnectedNeighbors {
get {
return unconnectedNeighbors.Count > 0;
}
}
public List<CellConnection> Connections { get { return connections; } }
public List<CellConnection> Neighbors { get { return neighbors; } }
public List<CellConnection> UnconnectedNeighbors { get { return unconnectedNeighbors; } }
#endregion
}
public static class GridPather {
private static GridPath GetPath(int xSize, int ySize, int? seed = null, Point? fromPoint = null) {
GridCell[,] grid = new GridCell[xSize, ySize];
GridPath path = new GridPath(grid, null, null);
System.Random random;
if (seed.HasValue)
random = new System.Random(seed.Value);
else
random = new System.Random();
List<GridCell> unconnectedRooms = new List<GridCell>(xSize * ySize);
// create cells and add possible neighbors
for (int y = 0; y < ySize; y++) {
for (int x = 0; x < xSize; x++) {
List<CellConnection> neighbors = new List<CellConnection>();
if (x > 0)
neighbors.Add(CellConnection.West);
if (x < xSize - 1)
neighbors.Add(CellConnection.East);
if (y > 0)
neighbors.Add(CellConnection.North);
if (y < xSize - 1)
neighbors.Add(CellConnection.South);
grid[x, y] = new GridCell(x, y, neighbors);
unconnectedRooms.Add(grid[x, y]);
}
}
if (fromPoint.HasValue)
path.From = grid[fromPoint.Value.X, fromPoint.Value.Y];
else
path.From = grid[random.Next(xSize), random.Next(ySize)];
GridCell curCell = path.From;
// connect rooms randomly until the path ends
while (curCell.HasUnconnectedNeighbors) {
CellConnection con = curCell.ConnectRandom(random);
unconnectedRooms.Remove(curCell);
curCell = path.GetConnectedCell(curCell, con);
curCell.ConnectedFrom(con);
unconnectedRooms.Remove(curCell);
}
// connect unconnected rooms
while (unconnectedRooms.Count > 0) {
unconnectedRooms.Shuffle(random);
for (int i = 0; i < unconnectedRooms.Count; i++ ) {
curCell = unconnectedRooms[i];
CellConnection? con = curCell.ConnectToRandomConnectedNeighbor(random, path);
if (curCell.IsConnected)
unconnectedRooms.RemoveAt(i);
if (con.HasValue) {
GridCell conCell = path.GetConnectedCell(curCell, con.Value);
unconnectedRooms.Remove(conCell);
}
}
}
path.To = curCell;
return path;
}
}
public class NoUnconnectedNeighborsException : Exception {
public NoUnconnectedNeighborsException(string desc) : base(desc + "; already connected to all neighbors.") { }
}
public static class ShuffleExtension {
/// <summary>
/// Shuffles list.
/// </summary>
/// <param name="list">List to shuffle.</param>
/// <param name="rng">System.Random instance to use for randomizing.</param>
public static void Shuffle<T>(this IList<T> list, System.Random rng) {
int n = list.Count;
while (n > 1) {
n--;
int k = rng.Next(n + 1);
T value = list[k];
list[k] = list[n];
list[n] = value;
}
}
/// <summary>
/// Shuffles list.
/// </summary>
/// <param name="seed">Seed to use for randomizing.</param>
public static void Shuffle<T>(this IList<T> list, int seed) {
Shuffle(list, new System.Random(seed));
}
/// <summary>
/// Shuffles list, creates a new randomizer to shuffle with.
/// </summary>
public static void Shuffle<T>(this IList<T> list) {
Shuffle(list, new System.Random());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment