Artificial Intelligence

Understanding the language, error messages, etc.

Artificial Intelligence

Postby Cayon » Thu Jan 08, 2015 5:01 pm

Hello,
I want to make an artificial intelligence for a mob in my futur game :)
But i have some probleme for coding this :?
I would like the monster go from point A to point B with the shortest path.
here's what I coded :
Code: Select all
if(player.x>monster.x){
     monster.x+=1;
}
if(player.x<monster.x){
     monster.x-=1;
}
if(player.y>monster.y){
     monster.y+=1;
}
if(player.y<monster.y){
     monster.y-=1;
}

But here is the result :
Image
And i want this :
Image
How I can make this ? Is it necessary to passed polar coordinated ?
Thanks for your help and sorry for my bad english :?
User avatar
Cayon
 
Posts: 29
Joined: Mon Oct 27, 2014 4:28 pm
Location: France, Le Mans (72)

Re: Artificial Intelligence

Postby Drakker » Thu Jan 08, 2015 5:18 pm

Normally you'd use divisions and floating point coordinates, but on the Gamebuino it might not be such a good idea. What you can do though is when required X or Y movement is significantly higher than the other direction, you can skip movement in the shorter direction every second frame or so. This will not give you a straight line, and it might be a bit jittery, but it will be a huge improvement over your current paths with low CPU usage.

Then again, if your game is small and has relatively few moving enemies, using floating points and divisions might be alright. I would recommend you check your current CPU usage and see if you can afford it.
User avatar
Drakker
 
Posts: 297
Joined: Sun Mar 30, 2014 2:54 am
Location: Québec, Canada

Re: Artificial Intelligence

Postby Cayon » Thu Jan 08, 2015 5:32 pm

My current CPU usage is very hight but how I can make the floating points and divisions ?
User avatar
Cayon
 
Posts: 29
Joined: Mon Oct 27, 2014 4:28 pm
Location: France, Le Mans (72)

Re: Artificial Intelligence

Postby Skyrunner65 » Thu Jan 08, 2015 5:32 pm

This is just my thought on your dilemma, made in code:
Didn't think about backwards, but just reverse the signs in a few places and it would work.
Code: Select all
if(player.y!=monster.y){
     movement == 1;
}
if(player.x!=monster.x){
     movement == 1;
}
if (movement == 1){
  xoff == player.x - monster.x;
  yoff == player.y - monster.y;
  if yoff > xoff {
    monster.y += 1;
  }
  if xoff > yoff {
    monster.x += 1;
  }
User avatar
Skyrunner65
 
Posts: 371
Joined: Thu Mar 20, 2014 5:37 pm
Location: NC,USA

Re: Artificial Intelligence

Postby Cayon » Thu Jan 08, 2015 5:37 pm

Skyrunner65 I have already try this solution but the result make this :
Image
User avatar
Cayon
 
Posts: 29
Joined: Mon Oct 27, 2014 4:28 pm
Location: France, Le Mans (72)

Re: Artificial Intelligence

Postby Drakker » Thu Jan 08, 2015 6:36 pm

Here's a very rough example in pseudoish code for the floating points and divisions:

Code: Select all
float monster.X = somewhere in the play area
float monster.Y = somewhere in the play area

monsterSpeed = speed in pixels per frame (can be a float or an integer)

Ydistance = player.Y - monster.Y
Xdistance = player.X - monster.X

Xdirection = -(Xdistance < 0) + (Xdistance > 0) // store the monster movement direction as -1, 0 or 1 (left, no movement, right)
Ydirection = -(Ydistance < 0) + (Ydistance > 0) // store the monster movement direction as -1, 0 or 1 (up, no movement, down)

Xdistance = abs(Xdistance)
Ydistance = abs(Ydistance) // get rid of direction, not needed anymore

if Xdistance > Ydistance {
  difference = Ydistance / Xdistance
  monster.X += monsterSpeed * Xdirection
  monster.Y += difference * monsterSpeed * Ydirection
}
else {
  difference = Xdistance / Ydistance
  monster.Y += monsterSpeed * Ydirection
  monster.X += difference * monsterSpeed * Xdirection
}


Don't forget to cast back as int/byte or round off the numbers before displaying your bitmaps. I wrote this really fast off the top of my head, it probably needs some tweaking, but the idea is there. Note that with this code monsters will move faster diagonally, but it is more CPU efficient than calculating real euclidean distance for movement. Also, make sure Xdistance AND Ydistance are never both equal to zero (ie. add a check if it is possible for the monsters and the player to occupy the same exact location). ;)
User avatar
Drakker
 
Posts: 297
Joined: Sun Mar 30, 2014 2:54 am
Location: Québec, Canada

Re: Artificial Intelligence

Postby Cayon » Thu Jan 08, 2015 6:56 pm

thanks I test this tomorrow :)
User avatar
Cayon
 
Posts: 29
Joined: Mon Oct 27, 2014 4:28 pm
Location: France, Le Mans (72)

Re: Artificial Intelligence

Postby Cayon » Tue Jan 13, 2015 7:17 pm

I have test your method @Drakker but I have not successful...
But after some research I arrived successful at what I wanted :D
If someone is interested by the code :
Code: Select all
float angle;
float player.X;
float player.Y;
float monster.X;
float monster.Y;

angle = atan(monster.X-player.X)/(monster.Y-player.Y));
monster.X+=cos(angle);
monster.Y+=sin(angle);
gb.display.drawBitmap(int(monster.X),int(monster.Y),Zombie);
User avatar
Cayon
 
Posts: 29
Joined: Mon Oct 27, 2014 4:28 pm
Location: France, Le Mans (72)

Re: Artificial Intelligence

Postby Drakker » Tue Jan 13, 2015 7:27 pm

This will work very well of course, but the tan/atan and sin/cos plus the division mean that the algorithm will be using a lot of CPU power. If you don't get slowdowns and the game runs well, good, but if later on you need to free CPU cycles, you will have to revisit that function...

I had the same problem in my Bricks! game, and I ended up hardcoding a pre-computed angles table just for that.

Code: Select all
// Angles
angleStruct angles[NB_ANGLES] = {
  { 0.996194698092, 0.0871557427477 }, // 5 deg
  { 0.984807753012, 0.173648177667 }, // 10 deg
  { 0.965925826289, 0.258819045103 }, // 15 deg
  { 0.939692620786, 0.342020143326 },
  { 0.906307787037, 0.422618261741 },
  { 0.866025403784, 0.5 },            //30 deg
  { 0.819152044289, 0.573576436351 },
  { 0.766044443119, 0.642787609687 },
  { 0.707106781187, 0.707106781187 }, // 45deg
  { 0.642787609687, 0.766044443119 },
  { 0.573576436351, 0.819152044289 },
  { 0.5, 0.866025403784 },            // 60deg
  { 0.422618261741, 0.906307787037 },
  { 0.342020143326, 0.939692620786 },
  { 0.258819045103, 0.965925826289 }, // 75 deg
  { 0.173648177667, 0.984807753012 },  // 80deg
  { 0.0871557427477, 0.996194698092 }, // 85deg
};


If you round the result from atan to the nearest 5 degrees, you can use the pre-computed values in this table instead of actually running sin and cos. That simple change would likely make your function about twice as fast.
User avatar
Drakker
 
Posts: 297
Joined: Sun Mar 30, 2014 2:54 am
Location: Québec, Canada


Return to Programming Questions

Who is online

Users browsing this forum: No registered users and 14 guests

cron