imported and translated java code

starting to implement algorithms

4 files changed, 239 insertions, 162 deletions

diff --git a/Pathfinding Visualizer/Assets/Scripts/AStar.cs b/Pathfinding Visualizer/Assets/Scripts/AStar.cs
index cb4d13c..a31d2c2 100644
--- a/Pathfinding Visualizer/Assets/Scripts/AStar.cs
+++ b/Pathfinding Visualizer/Assets/Scripts/AStar.cs
@@ -6,10 +6,16 @@ public class AStar : MonoBehaviour
 {
 
     LogicGrid world;
+    List<int[][]> obstacles;
+    List<int[][]> samples;
+    int heuristic; // 0 = h0 | 
 
-    public void setWorld(LogicGrid world)
+    public AStar(LogicGrid world, int heuristic)
     {
         this.world = world;
+        this.obstacles = world.obstacles;
+        this.samples = world.samples;
+        this.heuristic = heuristic;
     }
 
     void Start()
diff --git a/Pathfinding Visualizer/Assets/Scripts/LogicGrid.cs b/Pathfinding Visualizer/Assets/Scripts/LogicGrid.cs
index 212eb91..c87514e 100644
--- a/Pathfinding Visualizer/Assets/Scripts/LogicGrid.cs
+++ b/Pathfinding Visualizer/Assets/Scripts/LogicGrid.cs
@@ -18,6 +18,12 @@ public class LogicGrid
     // Debug Grid Array used for updating the text-objects 
     private TextMesh[,] debugTextArray;
 
+
+    // Coordinates for pathfinding
+    public int[] agent;
+    public List<int[][]> obstacles;
+    public List<int[][]> samples;
+
     public event EventHandler<OnGridValueChangedEventArgs> OnGridValueChanged;
     public class OnGridValueChangedEventArgs : EventArgs
     {
@@ -97,6 +103,46 @@ public class LogicGrid
                     x = x,
                     y = y
                 });
+
+            // If deleting a cell's value, remove coord from set
+            if (value == 0)
+            {
+
+                // make behavior to check for -1 values in coords
+                if (agent[0].Equals(x) && agent[1].Equals(y))
+                {
+                    agent[0] = -1;
+                    agent[1] = -2;
+                }
+
+            }
+
+            // Add coordinate to obstacle array
+            if (value == 1)
+            {
+                int[][] coord = new int[2][];
+
+                coord[0][0] = x;
+                coord[1][0] = y;
+
+                obstacles.Add(coord);
+            }
+            // Add coordinate to sample array
+            if (value == 2)
+            {
+                int[][] coord = new int[2][];
+
+                coord[0][0] = x;
+                coord[1][0] = y;
+
+                samples.Add(coord);
+            }
+            // Add coordinate to obstacle array
+            if (value == 3)
+            {
+                agent[0] = x;
+                agent[1] = y;
+            }
         }
     }
 
@@ -137,6 +183,10 @@ public class LogicGrid
     {
         gridArray = new int[width, height];
 
+        agent = new int[2];
+        obstacles = new List<int[][]>();
+        samples = new List<int[][]>();
+
         if (OnGridValueChanged != null)
             OnGridValueChanged(this, new OnGridValueChangedEventArgs
             {
diff --git a/Pathfinding Visualizer/Assets/Scripts/Main.cs b/Pathfinding Visualizer/Assets/Scripts/Main.cs
index 018ce33..a146859 100644
--- a/Pathfinding Visualizer/Assets/Scripts/Main.cs
+++ b/Pathfinding Visualizer/Assets/Scripts/Main.cs
@@ -16,7 +16,12 @@ public class Main : MonoBehaviour
     void Start()
     {
         // Create world
-        world = new LogicGrid(100, 100, 5f, new Vector3(-110, -110));
+        int width = 100;
+        int height = 100;
+        float cellSize = 5f;
+        Vector3 origin = new Vector3(-110, -110);
+
+        world = new LogicGrid(width, height, cellSize, origin);
         
         // Set default placement to Obstacle
         placementValue = 1;
@@ -28,11 +33,16 @@ public class Main : MonoBehaviour
 
     }
 
-    // Update is called once per frame
-    void Update()
+    public void StartAStar()
     {
-        // Change Placement Modes:
+        AStar astar = new AStar(world, 0);
+    }
 
+    // Update contains keyboard shortcut options
+    void Update()
+    {
+        // Change Placement Mode Keyboard Shortcuts:
+        ////////////////////////////////
         // Place Obstacle in grid
         if (Input.GetKeyDown("o"))
         {
@@ -59,15 +69,16 @@ public class Main : MonoBehaviour
         {
             ResetGrid();
         }
-
+        //////////////////////////
+        
 
         // Update Cell:
-        // Change cell to obstacle
+        // Place value in cell based on selected placementValue with left click
         if (Input.GetMouseButton(0))
         {
             world.SetValue(CodeMonkey.Utils.UtilsClass.GetMouseWorldPosition(), placementValue);
         }
-        // Clear cell
+        // Clear cell with right click
         if (Input.GetMouseButton(1))
         {
             world.SetValue(CodeMonkey.Utils.UtilsClass.GetMouseWorldPosition(), 0);
@@ -79,7 +90,6 @@ public class Main : MonoBehaviour
 
     }
 
-
     public void SetModeObstacle()
     {
         placementValue = 1;
@@ -96,5 +106,5 @@ public class Main : MonoBehaviour
     {
         world.reset();
     }
-
+   
 }
diff --git a/Pathfinding Visualizer/Assets/Scripts/PathNode.cs b/Pathfinding Visualizer/Assets/Scripts/PathNode.cs
index 0f607cd..e65e1b2 100644
--- a/Pathfinding Visualizer/Assets/Scripts/PathNode.cs
+++ b/Pathfinding Visualizer/Assets/Scripts/PathNode.cs
@@ -1,6 +1,7 @@
 using System;
 using System.Collections;
 using System.Collections.Generic;
+using System.Linq;
 using UnityEngine;
 
 	class Node : IComparable<Node>
@@ -15,181 +16,184 @@ using UnityEngine;
 		char lastMove; // for output/animation
 		int distanceTraveled; // for calculating f(n) value
 		double heuristic;
-		double fn; // distance traveled + heuristic value
+		public double fn; // distance traveled + heuristic value
 		bool canSample; // for expansion 
 
 		// construct node :)
 		public Node(Node parent, int[] agent, List<int[]> samples, char lastMove, int distanceTraveled, double heuristic)
 		{
-		this.parent = parent;
-		this.agent = agent;
-		this.samples = new ArrayList<int[]>(samples);
-		this.lastMove = lastMove;
-		this.distanceTraveled = distanceTraveled;
-		this.heuristic = heuristic;
-		this.fn = distanceTraveled + heuristic;
+			this.parent = parent;
+			this.agent = agent;
+			this.samples = new List<int[]>(samples);
+			this.lastMove = lastMove;
+			this.distanceTraveled = distanceTraveled;
+			this.heuristic = heuristic;
+			this.fn = distanceTraveled + heuristic;
 		}
 
-	// determine valid moves and collect children to be sent back to search
-	public List<Node> expand(int depth)
-	{
-		List<Node> children = new ArrayList<Node>();
-		if (this.distanceTraveled >= depth && depth != -1)
-		return children;
+		// determine valid moves and collect children to be sent back to search
+		public List<Node> expand(int depth)
+		{
+			List<Node> children = new List<Node>();
+			if (this.distanceTraveled >= depth && depth != -1)
+				return children;
 
-		// document expansion of node and get ready to collect this node's children
-		SampleWorld.expansions++;
-		int[] onSample = new int[2];
+			// document expansion of node and get ready to collect this node's children
+			// SampleWorld.expansions++;
+			int[] onSample = new int[2];
 
-		// since this state is being currently visited (expanded), put in closed list
-		SampleWorld.closed.add(this.getState());
+			// since this state is being currently visited (expanded), put in closed list
+			// SampleWorld.closed.add(this.getState());
 
-		////////////////////////////////////
-		// BEGIN CHECKING FOR VALID MOVES //
-		////////////////////////////////////
+			////////////////////////////////////
+			// BEGIN CHECKING FOR VALID MOVES //
+			////////////////////////////////////
 
-		// store coordinates for all potential moves to be checked
-		int[] up = { this.agent[row] - 1, this.agent[col] };
-		int[] down = { this.agent[row] + 1, this.agent[col] };
-		int[] left = { this.agent[row], this.agent[col] - 1 };
-		int[] right = { this.agent[row], this.agent[col] + 1 };
+			// store coordinates for all potential moves to be checked
+			int[] up = { this.agent[row] - 1, this.agent[col] };
+			int[] down = { this.agent[row] + 1, this.agent[col] };
+			int[] left = { this.agent[row], this.agent[col] - 1 };
+			int[] right = { this.agent[row], this.agent[col] + 1 };
 
-		// make sure going up doesn't go outside world-bounds or into obstacle
-		if (isOpen(up))
-		{
-			// if move is valid, create that new node/state and document
-			Node child = new Node(this, up, this.samples, 'U', this.distanceTraveled + 1, this.heuristic);
-			SampleWorld.nodesGenerated++;
+			// make sure going up doesn't go outside world-bounds or into obstacle
+			if (isOpen(up))
+			{
+				// if move is valid, create that new node/state and document
+				Node child = new Node(this, up, this.samples, 'U', this.distanceTraveled + 1, this.heuristic);
+				//SampleWorld.nodesGenerated++;
 
-			// make sure that we have not already made that move
-			if (!child.getState().inClosed())
-				children.add(child);
-		}
+				// make sure that we have not already made that move
+				if (!child.getState().inClosed())
+					children.Add(child);
+			}
 
-		// same idea but for the different potential moves
-		if (isOpen(down))
-		{
-			Node child = new Node(this, down, this.samples, 'D', this.distanceTraveled + 1, this.heuristic);
-			SampleWorld.nodesGenerated++;
+			// same idea but for the different potential moves
+			if (isOpen(down))
+			{
+				Node child = new Node(this, down, this.samples, 'D', this.distanceTraveled + 1, this.heuristic);
+				//SampleWorld.nodesGenerated++;
 
-			if (!child.getState().inClosed())
-			children.add(child);
-		}
+				if (!child.getState().inClosed())
+					children.Add(child);
+			}
 
-		if (isOpen(left))
-		{
-			Node child = new Node(this, left, this.samples, 'L', this.distanceTraveled + 1, this.heuristic);
-			SampleWorld.nodesGenerated++;
+			if (isOpen(left))
+			{
+				Node child = new Node(this, left, this.samples, 'L', this.distanceTraveled + 1, this.heuristic);
+				//SampleWorld.nodesGenerated++;
 
-			if (!child.getState().inClosed())
-			children.add(child);
-		}
+				if (!child.getState().inClosed())
+					children.Add(child);
+			}
 
-		if (isOpen(right))
-		{
-			Node child = new Node(this, right, this.samples, 'R', this.distanceTraveled + 1, this.heuristic);
-			SampleWorld.nodesGenerated++;
+			if (isOpen(right))
+			{
+				Node child = new Node(this, right, this.samples, 'R', this.distanceTraveled + 1, this.heuristic);
+				//SampleWorld.nodesGenerated++;
 
-			if (!child.getState().inClosed())
-			children.add(child);
-		}
+				if (!child.getState().inClosed())
+				children.Add(child);
+			}
 
-		// CHECK IF CAN SAMPLE
-		onSample = canSample();
-		if (onSample[0] == 1)
-		{
-			Node child = new Node(this, this.agent, this.samples, 'S', this.distanceTraveled + 1, this.heuristic);
-			child.samples.remove(onSample[1]);
+			// CHECK IF CAN SAMPLE
+			onSample = CanSample();
+			if (onSample[0] == 1)
+			{
+				Node child = new Node(this, this.agent, this.samples, 'S', this.distanceTraveled + 1, this.heuristic);
+			
+				// PROBLEM?
+				child.samples.RemoveAt(onSample[1]);
 
-			SampleWorld.nodesGenerated++;
-			children.add(child);
-		}
+				//SampleWorld.nodesGenerated++;
+				children.Add(child);
+			}
 
-		return children;
-	}
+			return children;
+		}
 
-	// helper for expand, verifies whether potential move is legal
-	public boolean isOpen(int[] position)
-	{
-	// check that agent is not trying to move into an obstacle
-	for (int i = 0; i < SampleWorld.obstacles.size(); i++)
-	{
-	if (Arrays.compare(SampleWorld.obstacles.get(i), position) == 0)
-	return false;
-	}
+		// helper for expand, verifies whether potential move is legal
+		public bool isOpen(int[] position)
+		{
+			// check that agent is not trying to move into an obstacle
+			for (int i = 0; i < SampleWorld.obstacles.size(); i++)
+			{
+				if (Enumerable.SequenceEqual(SampleWorld.obstacles.get(i), position) == 0)
+					return false;
+			}
 
-	// check that agent is not stepping out of the world
-	if (!((position[row] >= 0) && (position[row] <= SampleWorld.worldRows - 1) && (position[col] >= 0) && (position[col] <= SampleWorld.worldCols - 1)))
-	return false;
+			// check that agent is not stepping out of the world
+			if (!((position[row] >= 0) && (position[row] <= SampleWorld.worldRows - 1) && (position[col] >= 0) && (position[col] <= SampleWorld.worldCols - 1)))
+				return false;
 
-	return true;
-	}
+			return true;
+		}
 
-	// returns the coordinates of the sample closest to the agent's current location
-	public int[] nearestSample()
-	{
-		if (samples.size() == 0)
-			return agent;
+		// returns the coordinates of the sample closest to the agent's current location
+		public int[] nearestSample()
+		{
+			if (samples.Count == 0)
+				return agent;
 
-		int[] s = samples.get(0);
-		double lowest = distance(agent, samples.get(0));
-		double distance;
+			// PROBLEM?
+			int[] s = samples[0];
+			double lowest = distance(agent, samples[0]);
+			double dist;
 
-		for (int i = 1; i < samples.size(); i++)
-		{
-			distance = distance(agent, samples.get(i));
-			if (distance < lowest)
+			for (int i = 1; i < samples.Count; i++)
 			{
-				lowest = distance;
-				s = samples.get(i);
+				dist = distance(agent, samples[i]);
+				if (dist < lowest)
+				{
+					lowest = dist;
+					s = samples[i];
+				}
 			}
+			return s;
 		}
-		return s;
-	}
-	// helper function for nearestSample()
-	public static double distance(int[] a, int[] b)
-	{   //								 _________________________
-		// distance between 2D points = √(y2 - y1)^2 + (x2 - x1)^2
-		double total = (((b[row] - a[row]) * (b[row] - a[row])) + ((b[col] - a[col]) * (b[col] - a[col])));
-		total = Math.sqrt(total);
-
-		return total;
-	}
+		// helper function for nearestSample()
+		public static double distance(int[] a, int[] b)
+		{   //								 _________________________
+			// distance between 2D points = √(y2 - y1)^2 + (x2 - x1)^2
+			double total = (((b[row] - a[row]) * (b[row] - a[row])) + ((b[col] - a[col]) * (b[col] - a[col])));
+			total = Math.Sqrt(total);
 
-	// helper function for h2
-	/////////////////////////////
-	// returns two pieces of information if true: 
-	// [0] is 1 to indicate agent can sample
-	// [1] is the index of the valid sample in the list
-	public int[] canSample()
-	{
-		// default to false
-		int[] result = new int[2];
-		result[0] = 0;
-		result[1] = -1;
+			return total;
+		}
 
-		for (int i = 0; i < this.samples.size(); i++)
+		// helper function for h2
+		/////////////////////////////
+		// returns two pieces of information if true: 
+		// [0] is 1 to indicate agent can sample
+		// [1] is the index of the valid sample in the list
+		public int[] CanSample()
 		{
-			if ((this.agent[row] == samples.get(i)[row]) && (this.agent[col] == samples.get(i)[col]))
+			// default to false
+			int[] result = new int[2];
+			result[0] = 0;
+			result[1] = -1;
+
+			for (int i = 0; i < this.samples.Count; i++)
 			{
-				result[0] = 1;
-				result[1] = i;
-				return result;
+				// PROBLEM?
+				if ((this.agent[row] == samples[i][row]) && (this.agent[col] == samples[i][col]))
+				{
+					result[0] = 1;
+					result[1] = i;
+					return result;
+				}
 			}
+			return result;
 		}
-		return result;
-	}
 
-	// returns only the dynamic information directly related to the Node's state.
-	// we need a way to extract just this information for the sake of our closed list
-	public State getState()
-	{
-		return new State(this.agent, this.samples);
-	}
+		// returns only the dynamic information directly related to the Node's state.
+		// we need a way to extract just this information for the sake of our closed list
+		public State getState()
+		{
+			return new State(this.agent, this.samples);
+		}
 
-	// we use to override comparisons for priorityQueues so that our heuristic calculations are actually used
-	@Override
-		public int compareTo(Node other)
+		// we use to override comparisons for priorityQueues so that our heuristic calculations are actually used
+		public int CompareTo(Node other)
 		{
 			if (this.fn > other.fn)
 			return 1;
@@ -200,16 +204,15 @@ using UnityEngine;
 	}
 
 	// helper class for Node
-	class NodeComparator implements Comparator<Node>
+	class NodeComparator : Comparer<Node>
 	{
 		// used to sort nodes based on sum of distance traveled + heuristic estimation of work left
-		@Override
-		public int compare(Node a, Node b)
+		public override int Compare(Node a, Node b)
 		{
-		if (a.fn > b.fn)
-		return 1;
-		else
-		return -1;
+			if (a.fn > b.fn)
+			return 1;
+			else
+			return -1;
 		}
 	}
 	// helper class for Node
@@ -220,17 +223,19 @@ using UnityEngine;
 
 		public State(int[] agent, List<int[]> samples)
 		{
+			// PROBLEM?
 			this.agent = agent;
-			this.samples = new int[samples.size()][];
+			this.samples = new int[samples.Count][];
 
 			// convert List<int[]> into 2D array of ints [][]
-			for (int i = 0; i < samples.size(); i++)
+			for (int i = 0; i < samples.Count; i++)
 			{
-				this.samples[i] = samples.get(i).clone();
+				// PROBLEM??
+				this.samples[i] = samples[i];
 			}
 		}
 
-		public boolean inClosed()
+		public bool inClosed()
 		{
 			for (int i = 0; i < SampleWorld.closed.size(); i++)
 			{
@@ -242,17 +247,23 @@ using UnityEngine;
 			return false;
 		}
 
-		public boolean equals(State other)
+		public bool equals(State other)
 		{
-			if (this.samples.length != other.samples.length)
+			if (this.samples.Length != other.samples.Length)
 				return false;
 
-			if (Arrays.compare(this.agent, other.agent) != 0)
+			// PROBLEM?
+			if (!this.agent[0].Equals(other.agent[0]) && !this.agent[1].Equals(other.agent[1]))
 				return false;
 
-			for (int i = 0; i < this.samples.length; i++)
+			for (int i = 0; i < this.samples.Length; i++)
 			{
-				if (Arrays.compare(this.samples[i], other.samples[i]) != 0)
+				//if (Arrays.compare(this.samples[i], other.samples[i]) != 0)
+				
+				// PROBLEM?
+				if (!(this.samples.Rank == other.samples.Rank) &&
+					!(Enumerable.Range(0, this.samples.Rank).All(dimension => this.samples.GetLength(dimension) == other.samples.GetLength(dimension))) &&
+					!(this.samples.Cast<double>().SequenceEqual(other.samples.Cast<double>())))
 					return false;
 			}