1. RE: pathing.
OthelloVivaldi at hotmail.com wrote:
>
> A question to the list: has anyone of you guys written a faster Bezier
> curve function in Euphoria? The one in my library is very slow and I
> know that Bezier curves CAN be written using only integers, but how?
>
Take a look at Vega.e, which has fairly fast multi-point bezier and
b-spline functions.
Colin Taylor
2. RE: pathing.
- Posted by rforno at tutopia.com
Aug 23, 2002
Mistertrik:
By a lucky coincidence, I posed a labirynth problem to my pupils in a C/C++
course I am giving at an University here in Argentina. Below you will find
two solutions to the problem, not much different from your problem. The
labirynth is a 0 - 1 matrix where a 1 allows passage. Movents are only
right - left - up - down. The programs are written basically in C, with only
I/O in C++. You will find easy translating them to Euphoria. The first and
shortest one is recursive. Sorry for the comments in Spanish.
Regards.
RECURSIVE SOLUTION:
// Programa para resolver un laberinto de F * C. Solucion recursiva.
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#define F 12
#define C 12
#define LAST C - 1
// Variables globales
char lab[F][C]; // Laberinto
char mat[F][C]; // Matriz correspondiente al camino mas corto
int camino[F * C][2]; // Camino(s)
int mascorto[F * C][2]; // El camino mas corto
int donde; // Los pasos dados por Teseo en ese camino
long cuenta; // Cantidad de caminos encontrados
int min; // La menor longitud de camino
// Rutina de ingreso de datos
void ingreso()
{
int i, j;
char c;
ifstream datos;
datos.open("laberint.txt");;
if (! datos)
{
cout << "\nNo se pudo abrir el archivo de entrada laberint.txt\n";
exit(1);
}
for (i = 0; i < F; i++)
for (j = 0; j < C; j++)
{
datos >> c;
if (c != '0' && c != '1')
{
cout << "\nDato incorrecto: " << c << endl;
exit(2);
}
lab[i][j] = c;
}
datos.close();
}
// Rutina para mostrar el camino y guardar el mas corto
void mostrar_camino()
{
int i, j;
cuenta++; // Otro camino
cout << "\nCamino encontrado:\n";
for (i = 0; i <= donde; i++) // Mostrar camino
cout << "[" << camino[i][0] << "," << camino[i][1] << "] ";
cout << endl;
cout << "Longitud: " << (donde + 1) << endl;
cout << "Matriz resultante:\n";;
for (i = 0; i < F; i ++) // Mostrar matriz resultante
{
for (j = 0; j < C; j++)
cout << lab[i][j];
cout << endl;
}
if (donde < min) // Si la longitud es menor
{
min = donde;
for (j = 0; j <= donde; j++) // Copiar camino
{
mascorto[j][0] = camino[j][0];
mascorto[j][1] = camino[j][1];
}
for (i = 0; i < F; i ++) // Copiar laberinto
for (j = 0; j < C; j++)
mat[i][j] = lab[i][j];
}
}
// Rutina recursiva para buscar caminos
void buscar(int i, int j)
{
if (i < F && j < C && i >= 0 && j >= 0 && '1' == lab[i][j]) // Si sigue
{
lab[i][j] = '+'; // Marcar senda usada
camino[donde][0] = i; // Indicar el camino
camino[donde][1] = j;
if (LAST == j) // Fin del camino
mostrar_camino();
donde++; // Paso siguiente
buscar(i + 1, j); // Hacia abajo
buscar(i - 1, j); // Hacia arriba
buscar(i, j + 1); // Hacia la derecha
buscar(i, j - 1); // Hacia la izquierda
donde--; // Retroceder un paso
lab[i][j] = '1'; // Restaurar marca de senda
}
}
void main()
{
int i, j;
ingreso();
cuenta = 0; // Aun no hay caminos
donde = 0; // Empezamos por el principio...
min = F * C; // Valor inicial de la longitud menor
for (i = 0; i < F; i++) // Buscar comienzo(s)
if ('1' == lab[i][0])
buscar(i, 0);
cout << "\nSe encontraron " << cuenta << " caminos\n";
if (cuenta) // Si hubo algun camino
{
donde = min; // Restaurar al camino minimo
for (j = 0; j <= donde; j++)
{
camino[j][0] = mascorto[j][0];
camino[j][1] = mascorto[j][1];
}
for (i = 0; i < F; i++) // Restaurar la matriz
for (j = 0; j < C; j++)
lab[i][j] = mat[i][j];
cout << "\nEl camino mas corto fue:\n";
mostrar_camino();
}
cout << "\nFin del programa\n";
}
NON-RECURSIVE SOLUTION:
// Programa para resolver un laberinto de F * C. Solucion no recursiva.
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#define F 12
#define C 12
#define LAST C - 1
// Variables globales
char lab[F][C]; // Laberinto
char mat[F][C]; // Matriz correspondiente al camino mas corto
int camino[F * C][2]; // Camino(s)
int ruta[F * C]; // Ultima ruta seguida
int mascorto[F * C][2]; // El camino mas corto
int donde; // Los pasos dados por Teseo en ese camino
long cuenta; // Cantidad de caminos encontrados
int min; // La menor longitud de camino
// Rutina de ingreso de datos
void ingreso()
{
int i, j;
char c;
ifstream datos;
datos.open("laberint.txt");;
if (! datos)
{
cout << "\nNo se pudo abrir el archivo de entrada laberint.txt\n";
exit(1);
}
for (i = 0; i < F; i++)
for (j = 0; j < C; j++)
{
datos >> c;
if (c != '0' && c != '1')
{
cout << "\nDato incorrecto: " << c << endl;
exit(2);
}
lab[i][j] = c;
}
datos.close();
}
// Rutina para mostrar el camino y guardar el mas corto
void mostrar_camino()
{
int i, j;
cuenta++; // Otro camino
cout << "\nCamino encontrado:\n";
for (i = 0; i <= donde; i++) // Mostrar camino
cout << "[" << camino[i][0] << "," << camino[i][1] << "] ";
cout << endl;
cout << "Longitud: " << (donde + 1) << endl;
cout << "Matriz resultante:\n";;
for (i = 0; i < F; i ++) // Mostrar matriz resultante
{
for (j = 0; j < C; j++)
cout << lab[i][j];
cout << endl;
}
if (donde < min) // Si la longitud es menor
{
min = donde;
for (j = 0; j <= donde; j++) // Copiar camino
{
mascorto[j][0] = camino[j][0];
mascorto[j][1] = camino[j][1];
}
for (i = 0; i < F; i ++) // Copiar laberinto
for (j = 0; j < C; j++)
mat[i][j] = lab[i][j];
}
}
// Rutina auxiliar para buscar caminos
void buscar1(int i, int j)
{
if (i < F && j < C && i >= 0 && j >= 0 && '1' == lab[i][j]) // Si sigue
{
donde++; // Un paso mas
camino[donde][0] = i; // Indicar camino
camino[donde][1] = j;
ruta[donde] = 0; // Primer caso
lab[i][j] = '+'; // Marcar senda
if (LAST == j) // Si llega a la meta
mostrar_camino();
}
}
// Rutina inicial para buscar caminos
void buscar(int i, int j)
{
int k;
donde = 0; // Empezamos por el principio...
camino[0][0] = i; // Punto inicial
camino[0][1] = j;
lab[i][0] = '+';
ruta[0] = 0;
while (donde >= 0) // Mientras queden sendas por recorrer
{
i = camino[donde][0]; // Ver donde estabamos
j = camino[donde][1];
k = ruta[donde];
ruta[donde]++; // Proximo paso
switch (k)
{
case 0:
buscar1(i + 1, j); // Hacia abajo
break;
case 1:
buscar1(i - 1, j); // Hacia arriba
break;
case 2:
buscar1(i, j + 1); // Hacia la derecha
break;
case 3:
buscar1(i, j - 1); // Hacia la izquierda
break;
default:
lab[i][j] = '1'; // Restaura celda. Si llega aca, debe haber sido '1'
donde--; // No hay mas posibilidades
break;
}
}
}
void main()
{
int i, j;
ingreso();
cuenta = 0; // Aun no hay caminos
min = F * C; // Valor inicial de la longitud menor
for (i = 0; i < F; i++) // Buscar comienzo(s)
if ('1' == lab[i][0])
buscar(i, 0);
cout << "\nSe encontraron " << cuenta << " caminos\n";
if (cuenta) // Si hubo algun camino
{
donde = min; // Restaurar al camino minimo
for (j = 0; j <= donde; j++)
{
camino[j][0] = mascorto[j][0];
camino[j][1] = mascorto[j][1];
}
for (i = 0; i < F; i++) // Restaurar la matriz
for (j = 0; j < C; j++)
lab[i][j] = mat[i][j];
cout << "\nEl camino mas corto fue:\n";
mostrar_camino();
}
cout << "\nFin del programa\n";
}
----- Original Message -----
From: <mistertrik at hotmail.com>
To: EUforum <EUforum at topica.com>
Sent: Thursday, August 22, 2002 10:43 PM
Subject: pathing.
>
> example of problem:
>
> sequence maze = {
> {5,5,5,5,5,5,5,5,5,5,5,5},
> {5,0,0,0,0,0,0,0,0,0,0,5},
> {5,0,0,0,0,5,0,0,0,0,0,5},
> {5,1,0,0,0,5,0,0,0,0,0,5},
> {5,0,0,0,0,5,0,0,0,9,0,5},
> {5,5,5,5,5,5,5,5,5,5,5,5}}
>
> How do I find a path to go from the 1 to the 9, avoiding all non-5
elements?
> (assume that there is only 1 1 and only 1 9, and their locations are known
> in advance)
> =====================================================
> .______<-------------------\__
> / _____<--------------------__|===
> ||_ <-------------------/
> \__| Mr Trick
>
>
>
>
3. RE: pathing.
> Instead of a maze, with narrow passages and many walls, it is a wide open
> area, with a few restrictions. So, instead of there being only one or two
> possible paths, there are many, many different ways.
>
> How would that affect the algorithm?
Now you've got to wall crawl with radar... that's how we did it way back
when.
You follow a wall and use radar... once the objective is in view, you just
dart for it from there.
4. RE: pathing.
This is a multi-part message in MIME format.
------=_NextPart_000_66aa_5ca2_1c1f
>Now you've got to wall crawl with radar... that's how we did it way back
>when.
>
>You follow a wall and use radar... once the objective is in view, you just
>dart for it from there.
>
That may not be desired.
My ascii skilz are a little lacking, so I have to do these as attachments,
sorry.
This pathing algorithm is for my snakers AI, so the snake must not only get
there, it must get back.
In the pictures, the first one goes to the wall (the snake itself) follows
along it until it can 'see' the objective, then it goes straight to it --
and traps itself.
The second one does the same thing, except allows for rudimentary escape.
--It traps itself too.
The third picture does not use the pathing you suggested, and manages to
move into a relatively large area. Now technically it is trapped, however
the area in which it has moved to allows the snake's tail to retract
sufficiently so that it can free itself.
=====================================================
.______<-------------------\__
/ _____<--------------------__|===
||_ <-------------------/
\__| Mr Trick
------=_NextPart_000_66aa_5ca2_1c1f
Content-Type: image/gif; name="Mazes.gif"
5. RE: pathing.
- Posted by rforno at tutopia.com
Aug 26, 2002
Have you tried the C program I posted? It finds the minimum length path.
Regards.
----- Original Message -----
From: <mistertrik at hotmail.com>
Subject: Re: pathing.
>
>
> >From: 10963508 at europeonline.com
> >Reply-To: EUforum at topica.com
> >To: EUforum <EUforum at topica.com>
> >Subject: Re: pathing.
> >Date: Sat, 24 Aug 2002 04:04:28 +0200
> >
> >
> >I wrote this program which solves maze:
>
>
> I changed the first maze around, so that it looked like so (closer to my
> problem), and this is the output from it.
>
> ==================================================
> Maze:
>
> ##########
> #### #####
> 1### #####
> #### ###9#
>
>
> Solution:
>
> ##########
> #### #
> 1### #
> 9#
>
>
> hmmm....
> =====================================================
> .______<-------------------\__
> / _____<--------------------__|===
> ||_ <-------------------/
> \__| Mr Trick
>
>
>
>
