Breath First Search is to be simply put a searching algorithm for traversing a Graph. Well, what I did my search on wasn’t exactly a Graph but regardless… 🙂 The simple idea, that this hard coded part is used for the traversing:
static class Map
{
public static char[,] map = new char[,]
{
{'r', '*', '*', '#', '*', '*'},
{'*', '#', '#', '#', '#', '*'},
{'*', '#', '*', '*', '*', '*'},
{'*', '#', '*', '#', '#', '*'},
{'*', '#', '*', '#', '*', '*'},
{'*', '#', '*', '#', '*', '*'},
{'*', '*', '*', '#', 'g', '*'}
};
}
Little explanation for the above code
The r means ready and the g is the goal, moreover the hashtags # represent the walls, on top of that the asterisks * show us the free places.
Explaining the classes below
The Position class is responsible for storing the x and y coordinates, and two Position objects can be compared by the help of the Equals method.
The Element class is the basic building block of this program. It is responsible for:
- holding the Position, the character (#, *, s, g),
- the Visited state (necessary for Breadth First Algorithm),
- the adjacent/neighboring Elements and the Parent (necessary for BFS as well)
- the element type which is the character
- The SelectNeighbours method does what the name implies. The tricky part for this, was that the array behaves in a way that the first parameter for accessing the array is y, than x. Contradicting the common sense. For the Left side I needed to use the y coordinate.
The Game class is creating the Elements from the simple Map.
The TryToSolve method will initialize a Queue -we use a queue in order to avoid the usage of backtracking- then calls the BFS.
//Left
if (this.Position.y - 1 > -1 &&
map[this.Position.x, this.Position.y - 1].elementType != '#')
{
Left = map[this.Position.x, this.Position.y - 1];
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace BreadthFirstSearch
{
struct Position : IEquatable<Position>
{
public int x;
public int y;
public bool Equals(Position other)
{
return this.x == other.x && this.y == other.y;
}
public override string ToString()
{
return string.Format("{0}, {1}", x, y);
}
}
class Element
{
Position position;
char elementType;
bool visited;
public char ElementType { get => elementType; set => elementType = value; }
public bool Visited { get => visited; set => visited = value; }
public Position Position { get => position; }
public Element Left, Right, Top, Bottom;
public Element parent;
public Element(Position position, char elementType)
{
this.position = position;
this.ElementType = elementType;
}
public void SelectNeighbours(ref Element[,] map)
{
if (this.ElementType != '#')
{
//Left
//Ha nem lóg ki bal oldalt és nem fal azaz #
if (this.Position.y - 1 > -1 &&
map[this.Position.x, this.Position.y - 1].elementType != '#')
{
Left = map[this.Position.x, this.Position.y - 1];
}
//Right
//Ha nem lóg ki jobb oldalt és nem fal azaz #
if (this.Position.y + 1 < map.GetLength(1) &&
map[this.Position.x, this.Position.y + 1].elementType != '#')
{
Right = map[this.Position.x, this.Position.y + 1];
}
//Top
//Ha nem lóg ki felül és nem fal azaz #
if (this.Position.x - 1 > -1 &&
map[this.Position.x - 1, this.Position.y].elementType != '#')
{
Top = map[this.Position.x - 1, this.Position.y];
}
//Bottom
//Ha nem lóg ki alul és nem fal azaz #
if (this.Position.x + 1 < map.GetLength(0) &&
map[this.Position.x + 1, this.Position.y].elementType != '#')
{
Bottom = map[this.Position.x + 1, this.Position.y];
}
}
}
}
static class Map
{
public static char[,] map = new char[,]
{
{'r', '*', '*', '#', '*', '*'},
{'*', '#', '#', '#', '#', '*'},
{'*', '#', '*', '*', '*', '*'},
{'*', '#', '*', '#', '#', '*'},
{'*', '#', '*', '#', '*', '*'},
{'*', '#', '*', '#', '*', '*'},
{'*', '*', '*', '#', 'g', '*'}
};
}
class Game
{
Element[,] mapElements;
char[,] map = Map.map;
public Game()
{
mapElements = new Element[map.GetLength(0), map.GetLength(1)];
for (int x = 0; x < map.GetLength(0); x++)
{
for (int y = 0; y < map.GetLength(1); y++)
{
mapElements[x,y] = new Element(new Position() { x = x, y = y }, map[x,y]);
}
}
for (int x = 0; x < map.GetLength(0); x++)
{
for (int y = 0; y < map.GetLength(1); y++)
{
mapElements[x,y].SelectNeighbours(ref mapElements);
}
}
var kiirando = mapElements[2,2];
/*
Console.WriteLine("Top: " + kiirando.Top?.Position +
" Bottom: " + kiirando.Bottom?.Position +
" Left: " + kiirando.Left?.Position +
" Right: " + kiirando.Right?.Position);
Console.WriteLine("Position x: {0}, y: {1} and value: {2}", kiirando.Position.x, kiirando.Position.y, kiirando.ElementType);
*/
}
private Element starting;
private Element ending;
public void PrintElements()
{
for (int x = 0; x < mapElements.GetLength(0); x++)
{
for (int y = 0; y < mapElements.GetLength(1); y++)
{
//Finding the starting point
if (mapElements[x,y].ElementType.Equals('r'))
{
starting = mapElements[x,y];
}
//Finding the ending point
else if (mapElements[x,y].ElementType.Equals('g'))
{
ending = mapElements[x,y];
}
Console.Write(mapElements[x,y].ElementType);
//Thread.Sleep(1000);
}
Console.WriteLine();
}
}
Queue<Element> elements;
public void TryToSolve()
{
elements = new Queue<Element>();
elements.Enqueue(starting);
BFS(ref elements);
PrintOutTheResult(ref elements);
}
public void PrintOutTheResult(ref Queue<Element> elements)
{
char[,] map = Map.map;
bool found;
for (int x = 0; x < map.GetLength(0); x++)
{
for (int y = 0; y < map.GetLength(1); y++)
{
found = false;
foreach (var element in elements)
{
if (element.Position.Equals(new Position {x = x, y = y}))
{
found = true;
Console.Write("O");
}
}
if (found == false)
{
Console.Write(map[x,y]);
}
}
Console.WriteLine();
}
}
public Queue<Element> BFS(ref Queue<Element> elements)
{
while (elements.Count != 0)
{
Element actual = elements.Dequeue();
actual.Visited = true;
//Console.WriteLine($"{++hanyszor} " + actual.Position);
if (actual.Left != null && actual.Left.Visited == false)
{
actual.Left.Visited = true;
actual.Left.parent = actual;
elements.Enqueue(actual.Left);
}
if (actual.Top != null && actual.Top.Visited == false)
{
actual.Top.Visited = true;
actual.Top.parent = actual;
elements.Enqueue(actual.Top);
}
if (actual.Right != null && actual.Right.Visited == false)
{
actual.Right.Visited = true;
actual.Right.parent = actual;
elements.Enqueue(actual.Right);
}
if (actual.Bottom != null && actual.Bottom.Visited == false)
{
actual.Bottom.Visited = true;
actual.Bottom.parent = actual;
elements.Enqueue(actual.Bottom);
}
if (actual.ElementType == 'g')
{
Console.WriteLine("The endpoint reached!");
elements = new Queue<Element>();
var drawingBack = actual;
while (drawingBack != null)
{
Console.WriteLine(drawingBack.Position);
elements.Enqueue(drawingBack);
drawingBack = drawingBack.parent;
}
return elements;
}
}
return elements;
}
}
class TestTheArray
{
char[,] map = new char[,]
{
{'r', '*', '#', '*', 'g'},
{'*', '*', '#', '#', '*'},
{'*', '*', '*', '*', '*'},
{'*', '*', '#', '*', '*'},
{'*', '*', '#', '*', '*'}
};
public TestTheArray()
{
Console.WriteLine(map[0,0]);
}
}
class Program
{
static void Main(string[] args)
{
Game game = new Game();
game.PrintElements();
//TestTheArray testTheArray = new TestTheArray();
game.TryToSolve();
Console.ReadKey();
}
}
}