Sign in to follow this  
stroma

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
How about the Min Max algorithm...

Search on google for it

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

Share this post


Link to post
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 this post


Link to post
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 i am going to learn more about a*..

and again : Thanks for replies ..

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Trap
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.


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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this