C++

Forum

 
Pathfinder

ebbo (14)
Hi,

Ive taken a little break from programming but now im back. I thought id be ready
for my first attempt at some very basic "AI". The goal of the program below is
to find the shortest route from the start to the end.
This is what i came up with so far (sorry for the messed up layout, in visual c++ i can move a selection of code a tab to the right by selecting it and pressing tab, is there a way to do that the other way around (move it back a tab?): 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>

using namespace std; 
int Random(int x, int y);

int main()
{
srand ( time(0) );
const int ROW_SIZE = 5;
const int FIELD_SIZE = ROW_SIZE * ROW_SIZE;
const char BORDER = '#';
bool quit = false;
int nCurrent = ROW_SIZE +1;


char cArray[FIELD_SIZE];

for(int i = 0; i < FIELD_SIZE; i++) // fill blanks
			cArray[i] = ' ';
for(int i = 0; i < ROW_SIZE; i++) // fill upperborder
			cArray[i] = BORDER;
for(int i = (FIELD_SIZE - ROW_SIZE); i < FIELD_SIZE; i++) // fill lower border
		cArray[i] = BORDER;

	for(int i = 0; i < FIELD_SIZE; i++)//draw vertical borders
	{
	 if(i % ROW_SIZE == 0)
		{
			cArray[i] = BORDER;
			cArray[i+ (ROW_SIZE - 1)] = BORDER;
		}
	}


	for(int i = 0; i < (FIELD_SIZE/6);i++) //fill field with obstacles
		cArray[Random(0,FIELD_SIZE)] = BORDER;
		cArray[ROW_SIZE+1] = 'S';//start
	cArray[(FIELD_SIZE - (ROW_SIZE + 2))] = 'E';//end
		for(int i = 0; i < FIELD_SIZE; i++) //draw field
		{	
			if((i % ROW_SIZE) == 0)
				cout << endl;
			
			cout << cArray[i];
		}
	cout << endl << endl;
		//semi random pathfinder 
	
	while (cArray[nCurrent] != 'E')//as long as end isnt found, try
	{
		bool legit = false;
		while (legit != true)
		{
				int previous;
				int nRand = Random(1,4);//4 possible directions
				if(nRand == 1)//move right
				{
					if(cArray[nCurrent+1] != BORDER)
					{
						previous = 1;
						nCurrent += 1;
						legit = true;
					}
				}
				if(nRand == 2)//move  left
			{
					if(cArray[nCurrent-1] != BORDER )
					{
						previous = 2;
					nCurrent -= 1;
						legit = true;
					}
				}
				if(nRand == 3)//move up
				{
					if(cArray[nCurrent-ROW_SIZE] != BORDER)
					{
						previous = 3;
						nCurrent -= ROW_SIZE;
						legit = true;
					}	
				}
				if (nRand == 4)//move down
				{
					if(cArray[nCurrent+ROW_SIZE] != BORDER)
					{
						previous = 4;
						nCurrent += ROW_SIZE;
						legit = true;
					}
				}
					
		}
}


What id like to do now to make the AI atleast semi random (add some intelligent behavior) is too make it remember its previous locations/moves and to avoid them as long as there is another valid option (as long as it isnt stuck that is)
Can anyone point me in the right direction. If this would be possible:

1
2
3
 
for(int n = 0; n < tries; n++)
if(cArray[nCurrent-direction(eg. - ROW_SIZE(eg. move up))] != previous[n])
//pseudo: make move; tries++; legit = true;


Thats my first attempt but i know its not going to work. Another problem is i dont know where to put the code for checking wether the pathfinder is stuck (has only 1 direction to go, although it might be possible to code to not go to a location that has only 1 way to reach it)

My last question is what would you use to store the locations where the pathfinder has already been. I could make an array with more than enough room to hold the information (eg nPrevious[1000]) or i could use a vector, any hints?

Thanks again!
ebbo (14)
Ive updated my code with a Stuck check function i mentioned in the previous post:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
bool Stuck(char cArray[], int n)
{
int escapes = 0;
if (cArray[n+1] != BORDER)//check right
	escapes++;
if (cArray[n-1] != BORDER)//check left
	escapes++;
if (cArray[n+ROW_SIZE] != BORDER)//check down
	escapes++;
if (cArray[n-ROW_SIZE] != BORDER)//check up
	escapes++;

if(escapes > 1)
	return false;
else
	return true;
}


This solves part of the problem however the pathfinder sometimes keeps bouncing between two locations before trying another. Any hints on that?
Last edited on
ebbo (14)
Its been allmost a day so i think im allowed to kick this topic back up a bit. TIA
Topic archived. No new replies allowed.