Because I am quite new to programming, especially AI, the best AI I ever did being a pong game where the computer evaluated the position of the ball, then at different levels of skill, randomly made a choice whether to go up or down, of course at the hardest skill level it only made the right choice 37 out of 40 times because if it was perfect, you couldnt win, however, now, I wish to make a little program on a 640x480 size screen, the maze will be 400x400, and the squared will be 20x20 making it easy to see. I wish to then have two different little dots representing characters, they will travel around the maze looking for each other, then when they find each other, take turns attacking each other. I figure I could do this, but the two things that will be hard for me is that the characters need to somewhat remember where theyve been, and make decisions on whether or not to go back there, and i have trouble with making things go through mazes without going where walls are, especially with a 400 square maze, i cant just make coordinated for all 400, then test to see if the move they make is legal or not, unless this is the only way. This project is my way of testing out how to make AI. Or maybe it could be a cat/mouse game, where one is the chaser, one is chased, anyways, ANY input at all will be greatly thanked, and if someone wishes to ASSIST with this project, I will probably pay them a small sum as thanks for teaching me a little. Dustin

Hi

I''d suggest starting by defining motivations for characters - does one hunt the other run; are they both looking for each other?

Then define perceptual ranges for characters [say 5 squares radius or direct line of sight] the mouse would probably have smaller range than the cat. If you wish you can add various forms of perception: sight [exact accuracy along line of sight], sound [radial - I can "hear" cat is in one of 5 grid squares ahead], assigning priority judgements to each.

To aid decisions for characters try creating a tree of last X decisions points, where you store the prioritised danger according to senses, allowing you to calculate likelyhood of this being a safe direction as a function of time stored when backtracking.

This isn''t a logical or perfect solution but will provide simplicity and an organic feel.


Hope this helps in some small way



Lord[BRIT]

The clasical way to go about maze solving is to always turn in the same direction whenever you get to a junction. ie always turn left at every intersection. In this way you can be sure that the whole maze will be covered. Of course this is not very efficient.

If you want to have the two ''characters'' know each other locations, then at each junction, your AI can choose the direction that approximates to the other characters location.

As an amusing thought, how about having them throw things over the walls at each other when they come in a defined range.

quote: Original post by shamen

The clasical way to go about maze solving is to always turn in the same direction whenever you get to a junction. ie always turn left at every intersection. In this way you can be sure that the whole maze will be covered.

Assuming there are no circles

The first thing that comes into my mind is BACKTRACKING.

It's something like shamen said, but you have a matrix of 20*20 representing the maze like this:

        int maze[20][20];maze={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},      {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},      {1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},      {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},      {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},      {1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},      {1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},...}[/source]that should prove my point.you have 2 arrays w/ possible movements, one for x, and the other one for y:[source]int xmov[4]={ 1,-1, 0, 0};int ymov[4]={ 0, 0, 1,-1};    

combining these arrays, let's say you(the computer, comp1) are on maze[1][1]. The backtracking algorithm says try every move, but remember them all. Provinding this theory, we start, and try (y+ymov[1],x+xmov[1]). but here we get an auxiliary matrix and "burn" every move. as the walls are marked w/ 1, the "burned" square will also be 1. we try this move until we reach a point where we can't use the 1st move anymore. Then, we try using the second move. because the 2nd move is the opposite of the first, and we go left, the algorithm realizes that it can't, because we "burned" the square to our left. then we try the third move. We use it. for the next square, we can't use the 1st nor the 2nd moves, but the 3rd applies again. the next square: the 1st move is no good, but the second is usable.we do so, until we get to maze[3][2].there, we find ourselves between "burned" squares. having no other solution, we go back in the line of moves, "unburn" the last used square and try a different move. this continues until the reach of a solution. The backtracking algorithm is meant to give all the possible answers. But in the end/print function, you can put a clause that terminates after it has found one solution. You might want to try finding a solution first and then acting upon it. of course, the comp2 player also moves in the same time, and the same algorithm applies, but w/ different start and end points. oh, i forgot to mention: the backtracking algorithm has a solution if the current location is the same as the desired location. there is only one more thing to say, there might not be a solution! but, this algorithm works even for circles, so Kylotan watch your "funny-stuff"!
the only thing that remains, is to provide you w/ the code for this, or something similar(the simple part of this problem - i use simple part, because this is not a static, not all-solution requiring problem - is a fundamental example for backtracking).
If any of you understood what I meant here, please reply and i will post the code necesarry for this.
For backtracking, you can use either recursive or iterative programs.

"Everything is relative." -- Even in the world of computers.

Edited by - Ionut Costica on July 16, 2000 9:12:41 PM

It''s done. Everyone, here is the code...
(notice that i use up to 25 moves from the backtracking algorithm before trying to do it again. backtracking TAKES time... very much time!)
so, let''s start:
3 files:
player.h
player.cpp
maze.cpp

"Everything is relative." -- Even in the world of computers.

player.h

    #ifndef __PLAYER_1_0__#define __PLAYER_1_0__struct p2d{	int x,y;};class player{public:	p2d pos;	player();	player(int x, int y);	~player();	void move(int x,int y);};#endif    

"Everything is relative." -- Even in the world of computers.

player.cpp

    #include "stdafx.h"#include "player.h"player::player(){	pos.x=0;	pos.y=0;}player::player(int x,int y){	pos.x=x;	pos.y=y;}player::~player(){}void player::move(int x,int y){	pos.x+=x;	pos.y+=y;}    

"Everything is relative." -- Even in the world of computers.

maze.cpp:

    #include "stdafx.h"#include "player.h"#include <stdio.h>#include <conio.h>#include <process.h>#define maxw 20#define maxl 20struct result{	int pw[400];	int size;};int xvect[4]={-1, 1, 0, 0};int yvect[4]={ 0, 0,-1, 1};player *comp1=new player(1,1);player *comp2=new player(18,2);bool killedeachother=false;result res;bool found=false;bool auxm[maxw][maxl];bool maz1[maxw][maxl];bool maz2[maxw][maxl];bool maze[maxw][maxl]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1},{1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,0,1},{1,1,0,1,0,1,1,0,1,1,0,1,1,1,1,0,1,1,0,1},{1,0,0,1,0,0,1,0,0,1,1,1,0,1,1,0,1,0,0,1},{1,0,1,1,1,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1},{1,0,1,0,0,0,1,0,1,0,0,1,1,1,0,1,1,1,1,1},{1,0,0,0,1,0,1,0,1,1,0,0,1,0,0,1,0,1,0,1},{1,1,1,1,1,0,1,0,0,1,1,0,1,0,1,1,0,1,0,1},{1,0,0,0,1,1,1,0,1,1,0,0,1,0,1,0,0,0,0,1},{1,0,1,0,1,0,1,0,1,1,0,1,1,0,1,1,1,1,0,1},{1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},{1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1},{1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,1},{1,0,1,0,1,1,0,0,0,0,0,1,0,1,1,1,0,1,0,1},{1,0,1,0,0,1,1,0,1,1,1,1,0,1,0,1,0,1,0,1},{1,0,1,0,1,1,1,0,1,0,0,1,0,1,0,0,0,1,0,1},{1,0,1,0,0,0,1,0,1,0,1,1,0,1,1,1,1,1,0,1},{1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};void initmaze(bool m[maxw][maxl]){	int im,jm;	for(im=0;im<maxw;im++)	{		for(jm=0;jm<maxl;jm++)		{			m[im][jm]=maze[im][jm];		}	}}void initpath(int p[400]){	int ip;	for(ip=0;ip<400;ip++)	{		p[ip]=4;	}}void copypath(int a[400],int b[400]){	int icp;	initpath(a);	for(icp=0;icp<400;icp++)	{		a[icp]=b[icp];	}}void printm(void){	int ipm,jpm;	printf("\n\n\n\n");	for(ipm=0;ipm<maxw;ipm++)	{		for(jpm=0;jpm<maxl;jpm++)		{			if(comp1->pos.x==ipm&&comp1->pos.y==jpm)			{				printf("1");			}			else			{				if(comp2->pos.x==ipm&&comp2->pos.y==jpm)				{					printf("2");				}				else				{					if(maze[ipm][jpm])					{						printf("#");					}					else					{						printf(" ");					}				}			}		}		printf("\n");	}	printf("P1: (%2d,%2d) P2: (%2d,%2d)\n",comp1->pos.x,comp1->pos.y,comp2->pos.x,comp2->pos.y);	getch();}bool findpath(p2d from,p2d to,int currmove,int pw[400]){	int ifp;	if((!found)&&(from.x==to.x)&&(from.y==to.y))	{		found=true;		copypath(res.pw,pw);		res.size=currmove;		return 1;	}	for(ifp=0;ifp<4;ifp++)	{		if((from.x+xvect[ifp])>=0&&(from.x+xvect[ifp])<maxw&&(from.y+yvect[ifp])>=0&&(from.y+yvect[ifp])<maxl)		{			if((!found)&&((from.x+xvect[ifp])==to.x)&&((from.y+yvect[ifp])==to.y)&&(!auxm[from.x+xvect[ifp]][from.y+yvect[ifp]]))			{				pw[currmove]=ifp;				copypath(res.pw,pw);				res.size=currmove+1;				found=true;				return 1;			}		}	}	p2d auxf;	for(ifp=0;ifp<4;ifp++)	{		if((from.x+xvect[ifp])>=0&&(from.x+xvect[ifp])<maxw&&(from.y+yvect[ifp])>=0&&(from.y+yvect[ifp])<maxl)		{			if((!found)&&((from.x+xvect[ifp])==to.x)&&((from.y+yvect[ifp])==to.y)&&(!auxm[from.x+xvect[ifp]][from.y+yvect[ifp]]))			{				pw[currmove]=ifp;				copypath(res.pw,pw);				res.size=currmove+1;				found=true;				return 1;			}			else			{				if((!found)&&(!auxm[from.x+xvect[ifp]][from.y+yvect[ifp]]))				{					auxf.x=from.x+xvect[ifp];					auxf.y=from.y+yvect[ifp];					pw[currmove]=ifp;					auxm[auxf.x][auxf.y]=1;					if(findpath(auxf,to,currmove+1,pw))					{						return 1;					}					else					{						auxm[auxf.x][auxf.y]=0;						pw[currmove]=4;					}				}			}		}	}	return 0;}bool checkkill(void){	int im;	if(comp1->pos.x==comp2->pos.x&&comp1->pos.y==comp2->pos.y)	{		killedeachother=true;		printf("They are killed");		getch();		exit(0);		return true;	}	for(im=0;im<4;im++)	{		if((comp1->pos.x+xvect[im])==comp2->pos.x&&(comp1->pos.y+yvect[im])==comp2->pos.y)		{			killedeachother=true;			printf("They are killed");			getch();			exit(0);			return true;		}	}	return false;}void main(void){	int auxp1[400];	int auxp2[400];	bool fpsucces[2]={false,false};	initmaze(maz1);	initmaze(maz2);	initmaze(auxm);	printm();		while(!killedeachother)	{		killedeachother=checkkill();		initmaze(auxm);		initpath(auxp1);		initpath(auxp2);		found=false;		fpsucces[0]=findpath(comp1->pos,comp2->pos,0,auxp1);				initmaze(auxm);				found=false;		fpsucces[1]=findpath(comp2->pos,comp1->pos,0,auxp2);				if(fpsucces[0]&&fpsucces[1])		{			for(int i=0;i<25;i++)			{				comp1->move(xvect[auxp1<i>],yvect[auxp1[i]]);				killedeachother=checkkill();				comp2->move(xvect[auxp2[i]],yvect[auxp2[i]]);				printm();				killedeachother=checkkill();			}		}		else		{ 			printf("Road blocked: 1->%s 2->%s\n",fpsucces[0]?"yes":"no",fpsucces[1]?"yes":"no");			getch();			exit(0);		}	}	printf("They are killed");}    

"Everything is relative." -- Even in the world of computers.

This is THE BASIC answer to your question. the other stuff, mentioned by the Lord, can easily be added in the player class and in the checkkill() procedure.
The maze i used:

"Everything is relative." -- Even in the world of computers.