# simple ai in a 2d array

## Recommended Posts

hi, i have a random matrix (2D) array with 1 and 0 like this: 0110001001 0011000101 0011000101 ... ... .. and i want to go to position(last,last) from position(0,0) the one s are not passable. i mean player will go on the zero s and i can go 4 way: right, left, up, down. i use c++ and here is my algrithm: i am using a function FindWays(x,y,) to find the ways for x,y positions. like this: left = matrix[x-1][y]; //finds the left and using a function to move: ChangePositionFrom(x,y) my question is about this function. i use it like this: if(left == 0 && prev_pos != right) x -= 1; ... ... my control order is: right, down, left and up in ChangePositionFrom(x,y) function. but this technic does not solve lots of matrix. i mean it is not a good algorithm(i found it myself). can i improve it easily or do i have to change all system? (i do not need expert ai) Thank you very much..

##### Share on other sites
Look up for A*(A-star) in the Articles here in Gamedev in the AI section, or if you preffer use a search engine. It's a better algorithm.

##### Share on other sites
i know A* is better but it have to be simple. :D
i use this for right:
if(right== 0 && (prev_pos != RIGHT|| (left!= 0 && down!= 0 && up!= 0))) //can go right
{
//go right
}
...//else if s for down, left, up..
//else printf("cannot find the way");
/bla bla

this works for this:
00110
10011
01011
00000
11100
but not for this:
00011
11011
00011
01101
00000

because it says : up up down down up up down down... the turning back funtions does not works fine..

any suggestions ?

##### Share on other sites
How about the Min Max algorithm...

Hmmmm. on second thoughts its maybe not quite what you want.. But its worth a look anyway

##### Share on other sites
how can i go straight forward ? i dont want up up down down.

asiest method to solve this making a prev_pos_x,y variable and check it. but if i use that model wont solve this

000001
101111
000000
000000
000000

because it will go straight forward right and cant turn back. i controlled left&&up&&down but it still does not make any sense... are there any other suggsetions?

thank you...

##### Share on other sites
A* is the way to go, and it is not a complex algorithm.... it is very simple

##### Share on other sites
thank you, i will chek it out.

##### Share on other sites
anyway, i improved my own algorithm and now it works very well.
i added some parameters to change position function and some checks to know is the player on the edge. and added some functions for previous position vector. i am very happy with this. [smile]
if anyone wants to look up my code, i may send it.

and again : Thanks for replies ..

##### Share on other sites
Simplest algorithm (pseudocode):
while(not at goal)
{
direction = randint(0,3);
if(walkable(direction))walk();
}

Doesn't find optimal paths though. Isn't fast either.

##### Share on other sites
Quote:
 Original post by TrapSimplest algorithm (pseudocode):while(not at goal){direction = randint(0,3);if(walkable(direction))walk();}Doesn't find optimal paths though. Isn't fast either.

hey thanks but, that is soo much easy :D
here is my code:
if(done)
//done
else
if((right == 0) && ((prev!= RIGHT) || (left!= 0 && down != 0 && up!= 0)))
//go right

... //and the other ways

and i make a variable to find how many movements done. if it reachs 40 it means that player cannot find way, so no solve for the random matrix.

edit: : this algorith is not perfect but can solve this:
0000001
1101111
0001111
0111111
0100011
0101000
0001100

Thank you..

##### Share on other sites
Dude! I'm trying to contact you !! :) where can I reach you ? I want you to test my 2-Dimensional Path Finding Algorithm !!! :)
Anyways here are some ways to contact me:
via ICQ: 242219573
via MSN: ariyes@bezeqint.net
via Yahoo: arie_segal
Talk to ya there ;).

##### Share on other sites
Funny this came up. I was disucssing a similar problem with a friend of mine not long ago.

My friend claims that the only way to solve 'any' maze is to randomly move about until the exit is found. I'm not sure if I agree with this but:

When I was 13 I wrote a program that would use random maze walking to try to find a good path to the exit.

The program contained three entities: A maze, a maze-walker, and a memory of the maze.

The memory of the maze is an array of the same dimensions of the actual maze. Initially the array is set to 0.

A maze-walker would start at the entrance to maze and randomly move about for 1000 turns or so. If it found the exit, each square that it used would be 'remembered'. By remember, a counter would be increased in the maze memory at each corresponding cell. So the first successful walk through, the memory of the maze would contain a bunch of '1's in cells corresponding to the actual maze.

After doing this 100 or so times I would display at the squares in maze memory with the highest number. Oddly this typically was the optimal / shortest route from start to end of the maze.

I can't fully remember (It was a long time ago), but I may have increased the odds of the maze walker to move to squares it's already visited that have resulted in an exit.

Will

##### Share on other sites
Going back to the posters original question... I have a few of my own.

1) Are you talking about an AI agent to find a path through the maze (this is what other posters seem to have assumed); or,
2) are you talking about finding valid moves for a player that is controlling a character in a maze-like environment?

3) If we're discussing an AI agent to move in the environment, do they have access to the entire map, or only a limited horizon around themself?
4) If it's the latter, does the agent have the ability to remember/model the maze? That is, does it have an internal representation or only its sensors and no memory?

If you simply want to find a shortest path from any point in your 2d array to any other point, then I would recommend you not use A* but rather the Distance Transform Algorithm. For practical array sizes, it's trivial to compute and then gives you the shortest path to your goal from any point in the environment. If you want details of this algorithm, search the archives of this forum.

Cheers,

Timkin