Генерация карты - C#
Формулировка задачи:
Доброе время суток. Подскажите пожалуйста алгоритмы с помощью которых можно сделать подобного рода карты:
Может быть есть готовые C# реализации, буду благодарен даже за названия алгоритмов, так как находил алгоритмы генерации лабиринтов. Но там лабиринты слишком сложные, да и по факту там лабиринт, а мне бы карту...
Решение задачи: «Генерация карты»
textual
Листинг программы
private static readonly Random Randomizer = new Random();
private static void Main()
{
const int N = 12 * 2 + 1, M = 12 * 2 + 1;
const int MAX_VISITS = 2;
const int CHANCE_TO_BREAK_WALL = 30;
Cell[,] grid = Init(N, M);
var stack = new Stack<Cell>();
Cell current = grid[1, 1];
current.IsWall = false;
current.Visits++;
while (true)
{
List<Cell> neighbours = GetNeighbours(grid, current.X, current.Y, MAX_VISITS);
if (neighbours.Count > 0)
{
Cell neighbour = neighbours[Randomizer.Next(neighbours.Count)];
bool breakWall = neighbour.Visits == 0 || Randomizer.Next(100 / CHANCE_TO_BREAK_WALL + 1) == 0;
if (breakWall)
neighbour.IsWall = false;
neighbour.Visits++;
if (breakWall)
{
Cell wall = GetWall(grid, current, neighbour);
wall.IsWall = false;
}
stack.Push(current);
current = neighbour;
}
else if (stack.Count > 0)
current = stack.Pop();
else
break;
}
Show(grid);
}
private static void Show(Cell[,] grid)
{
for (var i = 0; i < grid.GetLength(0); i++)
{
for (var j = 0; j < grid.GetLength(1); j++)
Console.Write(grid[i, j].IsWall ? "O" : " ");
Console.WriteLine();
}
}
private static Cell GetWall(Cell[,] grid, Cell a, Cell b)
{
int x = Math.Min(a.X, b.X) + Math.Abs(a.X - b.X) / 2;
int y = Math.Min(a.Y, b.Y) + Math.Abs(a.Y - b.Y) / 2;
return grid[y, x];
}
private static List<Cell> GetNeighbours(Cell[,] grid, int x, int y, int maxVisits)
{
var neighbours = new List<Cell>();
if (x - 2 >= 0 && grid[y, x - 2].Visits < maxVisits)
neighbours.Add(grid[y, x - 2]);
if (y - 2 >= 0 && grid[y - 2, x].Visits < maxVisits)
neighbours.Add(grid[y - 2, x]);
if (x + 2 < grid.GetLength(1) && grid[y, x + 2].Visits < maxVisits)
neighbours.Add(grid[y, x + 2]);
if (y + 2 < grid.GetLength(0) && grid[y + 2, x].Visits < maxVisits)
neighbours.Add(grid[y + 2, x]);
return neighbours;
}
private static Cell[,] Init(int n, int m)
{
var grid = new Cell[n, m];
for (var i = 0; i < n; i++)
for (var j = 0; j < m; j++)
grid[i, j] = new Cell { X = j, Y = i, IsWall = true };
return grid;
}
private class Cell
{
public int X { get; set; }
public int Y { get; set; }
public bool IsWall { get; set; }
public int Visits { get; set; }
}