RE : Pathfinding IN PASCAL

[black...@post5.tele.dk]

Hi all.

Need help !

Does anyone have an A* algoritm in Delphi-Pascal.

So far I have only found some in C++ ,Hate C++ !!!!!!!!!!!!!! :)

The big probleme is handling the pointer que in pascal.

Can't rewrite this from C to pascal.

Any help would be highly appreciated.
Kindest regards
Blackstaff.

[Wilminson Ng]

black...@post5.tele.dk writes:

>Hi all.

>Need help !

Here is a path finding algorithm by Dijkstra. It does not really use the
A* algorithm, so f(n) = g(n)+0. You can freely modify this program to A* by
replacing the location of a point with its coordinates. And distance between
the two of them. And then write a function that calculates the straight line
distance between two points. So, the data file should look like:

x1 y1 x2 y2 distance
x1 y1 x2 y2 distance ... etc

My apologize for the bad indentation. I indent this program using the GNU-Emacs
and either I don't know how to use it or it does not behaves as expected.
I also have a version of A* algorithm that is written in Common Lisp
Mail me if you are interested.

/****************************************************************************/
/** this program is to demonstrate the use of Dijkstra's algorithm **/
/** on solving the travelling salesman problem. The user will have to **/
/** run the program with the following arguments: **/
/** dijkstra <source file> <first node> <last node> **/
/** **/
/** Written by : Wilminson NG **/
/** Email : w...@yallara.cs.rmit.edu.au **/
/** **/
/****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_NODES 12
#define MAX_LEN 256
#define EMPTY -1

/* Functions return TRUE to indicate success, FALSE for failure */
#define TRUE 0
#define FALSE 1
#define bool int

/* this procedure is to read a file with a lits of nodes and copies them into
the corresponding matrix nodes.
It returns TRUE if it succeeds, FALSE if it fails.
*/
int read_file(int nodes_matrix[MAX_NODES+1][MAX_NODES+1],
char *file_name, int *maximum)
{
FILE *fp;
char line[MAX_LEN];
int str_length;
int x_axis, y_axis, distance;
int counter=0;
int tmp_value = EMPTY;
int position=0; /* this variable is to record which variable
the computer is trying to get, i.e.
0 -> x_axis,
1 -> y_axis,
2 -> distance,
3 -> completed */


fp = fopen(file_name, "r");
if (fp==0)
{
fprintf(stderr, "Cannot read file '%s'\n", file_name);
return FALSE;
}
else
{
while (fgets(line, MAX_LEN, fp) != NULL)
{
str_length = strlen(line);
position = 0;
for (counter=0; counter<str_length; counter++)
{
if (line[counter] == '/' && line[counter+1]=='/')
{
break;
}
if (isdigit(line[counter]))
{
if (tmp_value==EMPTY)
{
tmp_value = 0;
}
tmp_value = (tmp_value*10)+(line[counter]-'0');
}
else if (line[counter]==' ' || line[counter]=='\n'
|| line[counter]=='\t')
{
if (tmp_value!=EMPTY)
{
if (position==0)
{
x_axis = tmp_value;
if (*maximum < x_axis)
{
*maximum = x_axis;
}
}
else if (position == 1)
{
y_axis = tmp_value;
if (*maximum < y_axis)
{
*maximum = y_axis;
}
}
else if (position == 2)
{
distance = tmp_value;

/* if distance already recorded with
a value higher than current value,
replace the value with the current
value, otherwise ignore the new
value */
if (nodes_matrix[x_axis][y_axis]
== EMPTY ||
nodes_matrix[x_axis][y_axis] >
distance)
{
nodes_matrix[x_axis][y_axis] =
distance;
nodes_matrix[y_axis][x_axis] =
distance;
}
}
tmp_value=EMPTY;
position++;
}
}
else if (line[counter] == '/' && line[counter+1]=='/')
{
if (counter==str_length && position == 2
&& tmp_value!=EMPTY)
{
printf("Updating nodes %d. Cost = %d.");
distance=tmp_value;
if (nodes_matrix[x_axis][y_axis] == EMPTY
|| nodes_matrix[x_axis][y_axis] >
distance)
{
nodes_matrix[x_axis][y_axis] =
distance;
nodes_matrix[y_axis][x_axis] =
distance;
}
}
else
{
break;
}
}
}
}
}
return TRUE;
}

/* Cut below for sample input data

// Dijkstra Least-Cost Test Network

1 2 3 // distance from node 1 to 2 is 3
2 4 1 // distance from node 2 to 4 is 1 ... etc.
1 3 1
3 4 2
4 5 1
5 1 1
6 5 4
*/
--
Wilminson Ng, w...@yallara.cs.rmit.edu.au, http://yallara.cs.rmit.edu.au/~wng

Quote of the day:
"XMODEM - A spot-marking transfer protocol."