Assignment # 02
Artificial Intelligence, Fall 2012
Department of Computer Science & Software Engineering, IIUI
Submission Deadline: Monday 04:30 PM, November 19, 2012
Apply A* search to find optimal
path between any two cities.
Following map is given. Each block
represents a distance of 10 kilometer.
///////////////////////////////////////////////////////////////
A-STAR
ALGORITHM
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.IO;
using System.Threading;
using System.Diagnostics;
namespace A_Star_Form
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();}
class Program
{
public int n = 0;
public int destination;
public static double[,] Heuristic_sld = new double[27, 27];
char[] Words = { ' ','A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };
public int[,] arr;
public int source;
public string[] path=new string[28];
public static int[,] Graph_plots = new int[27, 2];
public int[] connected;
static Queue<int> toDO=new Queue<int>();
static Queue<int> Seen = new Queue<int>();
/// <summary>
/// Below are some functions used
/// </summary>
//////////////////////////////////////////////////////////////////
public void calculate_sld()
{
for (int i = 1; i < 27; i++)
{
if (i == destination)
Heuristic_sld[destination,
i] = 0;
else
{
double p1 = Graph_plots[i,
0] - Graph_plots[destination, 0];
double p2 = Graph_plots[i,
1] - Graph_plots[destination, 1];
p1 = p1 * p1;
p2 = p2 * p2;
Heuristic_sld[destination,
i] = Math.Sqrt(p1
+ p2);
}}}
//////////////////////////////////////////////////////
public void initGraph_plots()
{
//Y-values X values
Graph_plots[1, 0] = 10; Graph_plots[1, 1] = 10; //a
Graph_plots[2, 0] = 30; Graph_plots[2, 1] = 30; //b
Graph_plots[3, 0] = 10; Graph_plots[3, 1] = 50; //c //Not
connected ahead
Graph_plots[4, 0] = 50; Graph_plots[4, 1] = 10;//d//d
Graph_plots[5, 0] = 120; Graph_plots[5, 1] = 90;//e
Graph_plots[6, 0] = 30; Graph_plots[6, 1] = 60;//f
Graph_plots[7, 0] = 50; Graph_plots[7, 1] = 50;//g
Graph_plots[8, 0] = 70; Graph_plots[8, 1] = 30;//h
Graph_plots[9, 0] = 130; Graph_plots[9, 1] = 60;//i
Graph_plots[10, 0] = 30; Graph_plots[10, 1] = 120;//j
Graph_plots[11, 0] = 40; Graph_plots[11, 1] = 90;//k
Graph_plots[12, 0] = 20; Graph_plots[12, 1] = 100;//l
Graph_plots[13, 0] = 10; Graph_plots[13, 1] = 140;//m
Graph_plots[14, 0] = 90; Graph_plots[14, 1] = 20;//n
Graph_plots[15, 0] = 110; Graph_plots[15, 1] = 50;//o
Graph_plots[16, 0] = 90; Graph_plots[16, 1] = 60;//p
Graph_plots[17, 0] = 80; Graph_plots[17, 1] = 80;//q
Graph_plots[18, 0] = 70; Graph_plots[18, 1] = 100;//r
Graph_plots[19, 0] = 60; Graph_plots[19, 1] = 120;//s
Graph_plots[20, 0] = 50; Graph_plots[20, 1] = 140;//t
Graph_plots[21, 0] = 80; Graph_plots[21, 1] = 150;//u
Graph_plots[22, 0] = 90; Graph_plots[22, 1] = 130;//v
Graph_plots[23, 0] = 100; Graph_plots[23, 1] = 110;//w
Graph_plots[24, 0] = 150; Graph_plots[24, 1] = 120;//x
Graph_plots[25, 0] = 120; Graph_plots[25, 1] = 130;//y
Graph_plots[26, 0] = 120; Graph_plots[26, 1] = 20;//z
}
//////////////////////////////////////////////////////////////////////
public void read_text_File()
{
using (StreamReader reader = new StreamReader("TextFile1.txt"))
{
string size;string line = null;string[] pars;size = reader.ReadLine();
n = int.Parse(size);arr = new int[n + 1, n + 1];
for (int i = 1; i <= n; i++)
{
line = reader.ReadLine();
for (int j = 1; j <= n; j++)
{char[] delimiters = new char[] { ',', '\n' };
pars = line.Split(delimiters, StringSplitOptions.RemoveEmptyEntries);
arr[i, j] = int.Parse(pars[j-1]);}}}}
/////////////////////////////////////////////////////////////////////////////
public string path_trace()
{
string path_trace=null;
while (Seen.Count > 0)
{
int path = Seen.Dequeue();char c = Words[path];
path_trace += c.ToString();
}
path_trace +=
Words[destination].ToString();
return path_trace;
}
////////////////////////////////////////////////////////////////////////////
public void ASTAR()
{
connected = new int[n+1];
double max=999;
int count = 0;
int choosen = 0;
toDO.Clear();
Seen.Clear();
int x = source;
toDO.Enqueue(x);
while (toDO != null)
{
x = toDO.Dequeue();
if (x == destination)
{
return;}
else
{
Seen.Enqueue(x);
for (int loop = 1; loop < 27; loop++)
{
if (arr[x, loop] != 9
&& arr[x, loop] != 0)
{
if (!Seen.Contains(loop))
connected[++count] =
loop;
}
}
int loop_until = connected.Count(i => i!= 0);
for (int loop2=1; loop2 <=loop_until; loop2++)
{
if (max >= Heuristic_sld[destination, connected[loop2]] +
10)
{
max = Heuristic_sld[destination,
connected[loop2]] + 10;
choosen =
connected[loop2];
}}
if (!Seen.Contains(choosen))
{
toDO.Enqueue(choosen);}}
Array.Clear(connected, 0, connected.Length);
count = 0;
max = 999;
}}
}
private void button1_Click(object sender, EventArgs e)
{
button1.Enabled = false;
if (comboBox1.SelectedItem == null || comboBox2.SelectedItem == null)
{
MessageBox.Show("Please enter
source and destination both..!","Warning");
}
else
{
try
{
string source_str, des_str; char source_chr, des_chr;
Program obj = new Program();
source_str = comboBox1.SelectedItem.ToString();
des_str =
comboBox2.SelectedItem.ToString();
source_chr = Char.Parse(source_str);
des_chr = Char.Parse(des_str);
obj.source = Convert.ToInt16(source_chr)
- 64;
obj.destination = Convert.ToInt16(des_chr) -
64;
obj.read_text_File();
obj.initGraph_plots();
obj.calculate_sld();
obj.ASTAR();
string result = obj.path_trace();
for (int i = 0; i < result.Length - 1; i++)
{
textBox1.Text +=
result[i].ToString();
Stopwatch delayWatch = new Stopwatch();
while (delayWatch.ElapsedMilliseconds < 1200)
{
delayWatch.Start();
Application.DoEvents();
delayWatch.Stop();
}
textBox1.Text += "---->";
}
textBox1.Text +=
result[result.Length - 1].ToString();
for (int a = 1; a < 7; a++)
{
textBox1.Text += Environment.NewLine;
}
textBox1.Text +="DONE...!";
pictureBox1.Show();
Image image = Image.FromFile("smile.png");
pictureBox1.Image = image;
pictureBox1.Height = image.Height;
pictureBox1.Width = image.Width;
}
catch (Exception)
{ MessageBox.Show("C node is
not connected ahead..!" + "\n" + "Incomplete Graph");
}
button1.Enabled = true;
}
}
private void button2_Click(object sender, EventArgs e)
{
if (MessageBox.Show("Are you sure
you want to Close ?", "Confirm Close", MessageBoxButtons.YesNo)
== DialogResult.Yes)
{
this.Close();
}
}
private void button3_Click(object sender, EventArgs e)
{
comboBox1.SelectedItem = null;
comboBox2.SelectedItem = null;
textBox1.Text = null;
pictureBox1.Hide();
}
private void Form1_Load(object sender, EventArgs e)
{
pictureBox1.Hide();
}
}
}
