Finding the shortest path through a 2d space with a display

I decided to implement most of the reddit Daily Programmer space probe challenge. My program creates a 2D space that have asteroids and gravity wells distributed (the percentage of gravity wells and asteroids is given to the SpaceProbeModel class which randomly distributes them) and finds the shortest path from a start to a finish.

Asteroids render the space they occupy impassable and gravity wells render the space they occupy and the 8 adjacent cells impassable. Movement may occur in the cardinal directions as well as diagonally.

The WPF UI displays the start and finish as well as the path between start and finish (if there is one.) and colors each square based on whether it is a gravity well, gravity influenced, empty space, or an asteroid.

This is my first foray into WPF (C# in general actually, I'm used to Java) so I'm pretty sure there is a lot I could improve on.

My Program.CS

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;

namespace SpaceProbe
{
class Program
{
static void Main(string[] args)
{
SpaceProbeView view = new SpaceProbeView(30);
SpaceProbeModel model = new SpaceProbeModel(30, 20, 1);
model.Start = new SpaceProbeModel.CellPair(5, 5);
model.FindShortestPath(20, 25);
view.SetModel(model);

}
}
}


The SpaceProbeModel.cs class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace SpaceProbe
{
public class SpaceProbeModel
{
public bool[,] passable;
public int[,] distance;
public CellPair[,] backtrack;
public type[,] cellType;
int rowSize;
public enum type { start, finish, asteroid, gravityWell, gravityInfluenced, empty, path }

private CellPair start;
private type oldStartType = type.empty;
public CellPair Start
{
get { return start; }
set
{
if (Start != null)
cellType[Start.Row, Start.Column] = oldStartType;
start = value;
oldStartType = cellType[Start.Row, Start.Column];
cellType[Start.Row, Start.Column] = type.start;
}
}

private CellPair finish;
private type oldFinishType = type.empty;
public CellPair Finish
{
get { return finish; }
set
{
if (Finish != null)
cellType[Finish.Row, Finish.Column] = oldFinishType;
finish = value;
oldFinishType = cellType[Finish.Row, Finish.Column];
cellType[Finish.Row, Finish.Column] = type.finish;
}
}

public class CellPair
{
int row, column;

public int Row
{
get { return row; }
set { }
}

public int Column
{
get { return column; }
set { }
}

public CellPair(int aRow, int aColumn)
{
row = aRow;
column = aColumn;
}

public override bool Equals(object obj)
{
if (obj is CellPair)
return (((CellPair)obj).row == row && ((CellPair)obj).column == column);
else return false;
}

public override string ToString()
{
return "<" + row + ", " + column + ">";
}
}

public SpaceProbeModel(int size, int asteroidPercent, int gravityWellPercent)
{
rowSize = size;
passable = new bool[rowSize, rowSize];
distance = new int[rowSize, rowSize];
backtrack = new CellPair[rowSize, rowSize];
cellType = new type[rowSize, rowSize];

for (int row = 0; row < rowSize; row++)
for (int column = 0; column < rowSize; column++)
{
passable[row, column] = true;
backtrack[row, column] = null;
cellType[row, column] = type.empty;
}

int numberOfAsteroids = (int)Math.Floor((rowSize * rowSize) * (asteroidPercent / 100.0f));
int numberOfGravityWells = (int)Math.Floor((rowSize * rowSize) * (gravityWellPercent / 100.0f));

ArrayList gravityAndAsteroidCells = GenerateUniqueCells(numberOfAsteroids + numberOfGravityWells);
PopulateCells(gravityAndAsteroidCells, numberOfAsteroids, numberOfGravityWells);

distance = new int[rowSize, rowSize];
}

private ArrayList GenerateUniqueCells(int numberOfCells)
{
ArrayList cells = new ArrayList();
Random random = new Random();
for(int i= 0; i < numberOfCells; i++)
{
CellPair cell = new CellPair(random.Next(rowSize), random.Next(rowSize));
while(cells.Contains(cell))
cell = new CellPair(random.Next(rowSize), random.Next(rowSize));
}
return cells;
}

private void PopulateCells(ArrayList cells, int numberOfAsteroids, int numberOfGravityWells)
{
for(int i = 0; i < numberOfAsteroids; i++)

for(int j = numberOfAsteroids; j < numberOfAsteroids + numberOfGravityWells; j++)
}

public void AddAsteroid(int row, int column)
{
MakeCellImpassable(row, column);
cellType[row, column] = type.asteroid;
}

public void AddGravityWell(int inputRow, int inputColumn)
{
for (int row = inputRow - 1; row <= inputRow + 1; row++)
for (int column = inputColumn - 1; column <= inputColumn + 1; column++)
MakeGravityInfluenced(row, column);

cellType[inputRow, inputColumn] = type.gravityWell;
}

private void MakeCellImpassable(int row, int column)
{
if (!CellOutOfBounds(row, column))
passable[row, column] = false;
}

private void MakeGravityInfluenced(int row, int column)
{
if (!CellOutOfBounds(row, column))
{
cellType[row, column] = type.gravityInfluenced;
MakeCellImpassable(row, column);
}
}

public bool CellOutOfBounds(int row, int column)
{
return (row < 0 || column < 0 || row >= rowSize || column >= rowSize);
}

public bool IsPassable(int row, int column) { return passable[row, column]; }

public void FindShortestPath(int finalRow, int finalColumn)
{
Finish = new CellPair(finalRow, finalColumn);
ArrayList unvisited = new ArrayList();
for (int row = 0; row < rowSize; row++)
for (int column = 0; column < rowSize; column++)
{
distance[row, column] = int.MaxValue;
if (passable[row, column] == true)
}
distance[Start.Row, Start.Column] = 0;

FindShortestPathHelper(Start.Row, Start.Column, unvisited);
UpdatePath(finalRow, finalColumn);
}

public void FindShortestPathHelper(int currentRow, int currentColumn, ArrayList unvisited)
{
unvisited.Remove(new CellPair(currentRow, currentColumn));
CellPair nextCell = null;
if (unvisited.Contains(new CellPair(Finish.Row, Finish.Column)))
{
foreach (CellPair pair in unvisited)
{
if (nextCell == null && distance[pair.Row, pair.Column] == int.MaxValue)
continue;
else if (nextCell == null && distance[pair.Row, pair.Column] != int.MaxValue)
nextCell = pair;
else if (nextCell != null && distance[pair.Row, pair.Column] < distance[nextCell.Row, nextCell.Column]
&& distance[pair.Row, pair.Column] != int.MaxValue)
nextCell = pair;
}
}

if (nextCell != null)
FindShortestPathHelper(nextCell.Row, nextCell.Column, unvisited);
}

public void IncrementAdjacentCells(int currentRow, int currentColumn)
{
for (int row = currentRow - 1; row <= currentRow + 1; row++)
for (int column = currentColumn - 1; column <= currentColumn + 1; column++)
IncrementCell(currentRow, currentColumn, row, column);
}

{
if (!CellOutOfBounds(row, column) && IsPassable(row, column))
{
{
}
}
}

public void SetDistancesToMax()
{
for (int row = 0; row < rowSize; row++)
for (int column = 0; column < rowSize; column++)
distance[row, column] = int.MaxValue;
}

public void UpdatePath(int finalRow, int finalColumn)
{
ArrayList backtrackList = new ArrayList();
CellPair backtrackCell = backtrack[finalRow, finalColumn];
while(backtrackCell != null)
{
backtrackCell = backtrack[backtrackCell.Row, backtrackCell.Column];
}

backtrackList.Remove(Start);
backtrackList.Remove(new CellPair(finalRow, finalColumn));

foreach(CellPair cell in backtrackList)
cellType[cell.Row, cell.Column] = type.path;
}
}
}


and, finally, SpaceProbeView.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Shapes;

namespace SpaceProbe
{
public class SpaceProbeView
{
Window window = new Window();
Canvas canvas = new Canvas();
private int cellSize = 25;
SpaceProbeModel model;
int rowAndColumnSize;
SolidColorBrush emptySpaceBrush = System.Windows.Media.Brushes.DarkBlue;
SolidColorBrush asteroidBrush = System.Windows.Media.Brushes.DarkGreen;
SolidColorBrush gravityWellBrush = System.Windows.Media.Brushes.Magenta;
SolidColorBrush gravityInfluencedBrush = System.Windows.Media.Brushes.DarkMagenta;
SolidColorBrush pathBrush = System.Windows.Media.Brushes.DarkTurquoise;
SolidColorBrush startBrush = System.Windows.Media.Brushes.Black;
SolidColorBrush finishBrush = System.Windows.Media.Brushes.DarkOrange;
Brush outlineBrush = System.Windows.Media.Brushes.Black;

public SpaceProbeView(int size)
{
rowAndColumnSize = size;
window.Title = "Space Probe";
canvas.Width = rowAndColumnSize * cellSize;
canvas.Height = rowAndColumnSize * cellSize;
window.Width = rowAndColumnSize * cellSize;
window.Height = rowAndColumnSize * cellSize;
window.Content = canvas;
window.SizeToContent = SizeToContent.WidthAndHeight;

window.Show();
}

public void SetModel(SpaceProbeModel aModel)
{
model = aModel;
for (int row = 0; row < rowAndColumnSize; row++)
{
for (int column = 0; column < rowAndColumnSize; column++)
{
Rectangle rect = new Rectangle();
rect.Width = cellSize;
rect.Height = cellSize;
rect.Stroke = outlineBrush;

switch (model.cellType[row, column])
{
case SpaceProbeModel.type.start:
rect.Fill = startBrush;
break;
case SpaceProbeModel.type.finish:
rect.Fill = finishBrush;
break;
case SpaceProbeModel.type.asteroid:
rect.Fill = asteroidBrush;
break;
case SpaceProbeModel.type.gravityInfluenced:
rect.Fill = gravityInfluencedBrush;
break;
case SpaceProbeModel.type.gravityWell:
rect.Fill = gravityWellBrush;
break;
case SpaceProbeModel.type.empty:
rect.Fill = emptySpaceBrush;
break;
case SpaceProbeModel.type.path:
rect.Fill = pathBrush;
break;
}
Canvas.SetTop(rect, row * cellSize);
Canvas.SetLeft(rect, column * cellSize);
}
}
}
}
}


The Equals() method, can throw an exception if the passed object is null. The pattern for Equals() should look like

public override bool Equals(object obj)
{
if (obj == null)
{
return false;
}

// If parameter cannot be cast to CellPair return false.
CellPair p = obj as CellPair;
if (p == null)
{
return false;
}

// Return true if the fields match:
return (p.row == row) && (p.column == column);
}


this also removes the multiple casts.

Overriding GetHashCode() if overriding Equals() should be always done too.

Enum values should be named using PascalCase casing.

In c# you have for properties different possibilities. You can use them with a backing field like you did but you could e.g skip the setter at all. The same goes the other way skipping the getter. But you can also have autoimplemented properties where getters and setters can have different scope. So instead of using a backing field you could use the autoimplemented properties like

public class CellPair
{

public int Row { get; private set; }

public int Column { get; private set; }

public CellPair(int aRow, int aColumn)
{
Row = aRow;
Column = aColumn;
}

public override bool Equals(object obj)
{
if (obj == null)
{
return false;
}

// If parameter cannot be cast to CellPair return false.
CellPair p = obj as CellPair;
if (p == null)
{
return false;
}

// Return true if the fields match:
return (p.Row == Row) && (p.Column == Column);
}

public override string ToString()
{
return "<" + Row + ", " + Column + ">";
}
}


Instead of ArrayList you should use a List<T>. This removes the need to cast the elements to the desired type.

Using braces {} for single if statements and for/while loops makes your code less errorprone.

Why are all these fields public ?

public bool[,] passable;
public int[,] distance;
public CellPair[,] backtrack;
public type[,] cellType;


thats what properties are for. Also for all these arrays you should use the plural for the names.

What will / what should happen if the CellPair Start will be a on an asteroid ? You should check the edge cases for Start and Finish.

It's good to use the var keyword when "newing up" variables as you declare them. The type is obvious and it will allow the type to be changed more easily should the case arise.

        SpaceProbeView view = new SpaceProbeView(30);
SpaceProbeModel model = new SpaceProbeModel(30, 20, 1);

        var view = new SpaceProbeView(30);
var model = new SpaceProbeModel(30, 20, 1);


Just be sure only to use it when the type is very obvious, as above. It can obfuscate code if used over zealously.

It's good practice to use brackets around all of your if statements. It clarifies the intent at a glance and helps prevent future bugs.

            if (Start != null)
cellType[Start.Row, Start.Column] = oldStartType;
start = value;
oldStartType = cellType[Start.Row, Start.Column];
cellType[Start.Row, Start.Column] = type.start;


I like how you abstracted the colors in your view.

    SolidColorBrush emptySpaceBrush = System.Windows.Media.Brushes.DarkBlue;
SolidColorBrush asteroidBrush = System.Windows.Media.Brushes.DarkGreen;
SolidColorBrush gravityWellBrush = System.Windows.Media.Brushes.Magenta;
SolidColorBrush gravityInfluencedBrush = System.Windows.Media.Brushes.DarkMagenta;
SolidColorBrush pathBrush = System.Windows.Media.Brushes.DarkTurquoise;
SolidColorBrush startBrush = System.Windows.Media.Brushes.Black;
SolidColorBrush finishBrush = System.Windows.Media.Brushes.DarkOrange;
Brush outlineBrush = System.Windows.Media.Brushes.Black;


This is good. It means you can just swap out the color if you want to change the color. You won't need to hunt down each and every usage in your code and make decisions on a one by one basis.

However, I don't understand why you're fully qualifying the path. You already included The System.Windows.Media namespace. So, you could shorten all of those assignments down to just Brushes.Color.

    SolidColorBrush emptySpaceBrush = Brushes.DarkBlue;
SolidColorBrush asteroidBrush = Brushes.DarkGreen;
SolidColorBrush gravityWellBrush = Brushes.Magenta;
SolidColorBrush gravityInfluencedBrush = Brushes.DarkMagenta;
SolidColorBrush pathBrush = Brushes.DarkTurquoise;
SolidColorBrush startBrush = Brushes.Black;
SolidColorBrush finishBrush = Brushes.DarkOrange;
Brush outlineBrush = Brushes.Black;


I don't much with GUIs often, so I'm not sure if it's necessary to specify the type the way you have. As I mentioned earlier, consider using the var keyword here.