d2jsp
Log InRegister
d2jsp Forums > Off-Topic > Computers & IT > Programming & Development > Artifical Intelligence > What Gives?
12Next
Add Reply New Topic New Poll
Views: 570Replies: 17Track Topic
Member
Posts: 31,680
Joined: Nov 10 2007
Gold: 1.00
#1
Oct 7 2009 04:55pm
I've been working on an AI for my game [Snake]. I've created an extremely simple "system-based" AI logic that was poor, but worked.
I've since then been attempting to create an AI where the Snake actually paths his way to the food, rather than finding it real-time by avoiding objects as he goes.

The "objects" he avoids is:
- The wall
- His own body
- Other Snake players ("players" means computers/humans)

This is the newest version (and I'm confused as to why it does this now):
Code
#include <iostream>
#include <vector>
#include <TextControl.h>
using namespace std;

int TotalRuns = 0;
int TotalCrashes = 0;

int FoodX = 0;
int FoodY = 0;

int SnakeX[100] = {'\0'};
int SnakeY[100] = {'\0'};

vector<int> Instructions;

void DrawSnake(const int, int, int);

bool Crash(const int X[], const int Y[]) {

   for (int x = 9; x > 1; x--) {
       if (X[0] == X[x] && Y[0] == Y[x]) {
           PlaceCursor(0, 45);
           SetColor(RED, BLACK);
           printf("X: %d  ", X[0]);

           PlaceCursor(0, 46);
           SetColor(RED, BLACK);
           printf("Y: %d  ", Y[0]);

           //Sleep(250);
           return true;
       }
   }

   return false;
}

void CreatePath() {

   Instructions.clear();

   int TempX[100] = {'\0'};
   int TempY[100] = {'\0'};

   /* Copy Snake location */
   for (int x = 0; x < 100; x++) {
       TempX[x] = SnakeX[x];
       TempY[x] = SnakeY[x];
   }

   int TempNum = 0;

   while (TempX[0] != FoodX || TempY[0] != FoodY) {

       if (FoodX > TempX[0]) {
           TempX[0]++; Instructions.push_back(3);
           while (Crash(TempX, TempY)) {

               switch (TempNum) {
                   case 0: { TempX[0]++; } break;
                   case 1: { TempY[0]--; } break;
                   case 2: { TempX[0]++; } break;
                   case 3: { TempY[0]--; } break;
               }

               Instructions.back() = TempNum;

               PlaceCursor(0, 35); printf("%d", TempNum);
               TempNum++;
               Sleep(250);
               if (TempNum >= 4) { break; }
           }
       }

       if (FoodX < TempX[0]) {
           TempX[0]--; Instructions.push_back(2);
           while (Crash(TempX, TempY)) {

               switch (TempNum) {
                   case 0: { TempX[0]++; } break;
                   case 1: { TempY[0]--; } break;
                   case 2: { TempX[0]++; } break;
                   case 3: { TempY[0]--; } break;
               }

               Instructions.back() = TempNum;

               PlaceCursor(0, 35); printf("%d", TempNum);
               TempNum++;
               Sleep(250);
               if (TempNum >= 4) { break; }
           }
       }

       if (FoodY > TempY[0]) {
           TempY[0]++; Instructions.push_back(1);
           while (Crash(TempX, TempY)) {

               switch (TempNum) {
                   case 0: { TempX[0]++; } break;
                   case 1: { TempY[0]--; } break;
                   case 2: { TempX[0]++; } break;
                   case 3: { TempY[0]--; } break;
               }

               Instructions.back() = TempNum;

               PlaceCursor(0, 35); printf("%d", TempNum);
               TempNum++;
               Sleep(250);
               if (TempNum >= 4) { break; }
           }
       }

       if (FoodY < TempY[0]) {
           TempY[0]--; Instructions.push_back(0);
           while (Crash(TempX, TempY)) {

               switch (TempNum) {
                   case 0: { TempX[0]++; } break;
                   case 1: { TempY[0]--; } break;
                   case 2: { TempX[0]++; } break;
                   case 3: { TempY[0]--; } break;
               }

               Instructions.back() = TempNum;

               PlaceCursor(0, 35); printf("%d", TempNum);
               TempNum++;
               Sleep(250);
               if (TempNum >= 4) { break; }
           }
       }

       TempNum = 0;

       //Sleep(50);
       //DrawSnake(RED, TempX, TempY);
   }

   SetColor(CYAN, BLACK);
   PlaceCursor(25, 0);
   printf("AI PATH COMPLETED");
   Sleep(500);
   PlaceCursor(25, 0);
   printf("                 ");

   return;
}

void DrawSnake(const int color, int Xz[], int Yz[]) {

   SetColor(color, BLACK);
   for (int x = 10; x > 0; x--) { Xz[x] = Xz[x - 1]; Yz[x] = Yz[x - 1]; }
   for (int x = 10; x >= 0; x--) { PlaceCursor(Xz[x], Yz[x]); printf("*"); }

   SetColor(GREEN, BLACK);
   PlaceCursor(Xz[0], Yz[0]); printf("@");
   //PlaceCursor(Xz[10], Yz[10]); SetColor(BLACK, BLACK); printf(" ");
   if (Xz[0] != Xz[10] || Yz[0] != Yz[10]) { PlaceCursor(Xz[10], Yz[10]); SetColor(BLACK, BLACK); printf(" "); }
   return;
}

void RunPath(const int color) {

   /* It'll crash sometimes if it randomly is empty */
   if (!Instructions.empty()) {

       SetColor(color, BLACK);
       for (int x = 0; x < Instructions.size(); x++) {

           switch (Instructions.at(x)) {
               case 0: SnakeY[0]--; break;
               case 1: SnakeY[0]++; break;
               case 2: SnakeX[0]--; break;
               case 3: SnakeX[0]++; break;
           }

           Sleep(50);

           DrawSnake(color, SnakeX, SnakeY);
           if (Crash(SnakeX, SnakeY)) { for (int x = 0; x < 100; x++) { SnakeX[x] = 5; SnakeY[x] = 5; } Instructions.clear(); }
       }
   }

   return;
}

void NewRun() {

   FoodX = rand() % 70 + 5;
   FoodY = rand() % 25 + 5;

   PlaceCursor(FoodX, FoodY);
   SetColor(YELLOW, BLACK);
   printf("x");

   Instructions.clear();

   return;
}

void SpawnFood(const int X, const int Y) {

   if (SnakeX[0] == FoodX && SnakeY[0] == FoodY) {
       FoodX = X;
       FoodY = Y;

       PlaceCursor(FoodX, FoodY);
       SetColor(YELLOW, BLACK);
       printf("x");
   } else {
       SetColor(CYAN, BLACK);
       PlaceCursor(0, 0);
       printf("SnakeX: %d  ", SnakeX[0]);
       PlaceCursor(0, 1);
       printf("SnakeY: %d  ", SnakeY[0]);
   }

   return;
}

int main() {

   HANDLE OutHandle = GetStdHandle(STD_OUTPUT_HANDLE);

   SetConsoleTitle("Snake - AI Module");
   SMALL_RECT windowSize = {0, 0, 79, 49};
   SetConsoleWindowInfo(OutHandle, TRUE, &windowSize);

   ClearConsole(BLACK, BLACK);
   RemoveCursor();

   srand(time(NULL));

   SnakeX[0] = 60;
   SnakeY[0] = 25;

   FoodX = 60;
   FoodY = 25;

   Instructions.clear();

   while (true) {
       SpawnFood(25, 25);
       CreatePath();
       RunPath(BLUE);

       SpawnFood(25, 40);
       CreatePath();
       RunPath(BLUE);

       SpawnFood(30, 20);
       CreatePath();
       RunPath(BLUE);

       SpawnFood(25, 20);
       CreatePath();
       RunPath(BLUE);

       SpawnFood(35, 20);
       CreatePath();
       RunPath(BLUE);
   }

   cin.get();
   return 0;
}


Specifically what's confusing is: The Snake (when "thinking") does not follow the same "rules" as the Snake when it's really running. They follow two different paths, which is fucking whacko. The AI Snake will take an actual SHORTER and ANGLED path, when the real Snake is forced to take UP then RIGHT then UP then RIGHT (no angled movements). This time, I'm dead-positive there isn't a logical error, as you can clearly see the code, it uses the same DrawSnake function, and it uses the same vector for instructions.

Snake AI not shown: http://www.youtube.com/watch?v=ztQU55dIyfs
Snake AI shown: http://www.youtube.com/watch?v=DRCAhBIjZps

I'm pretty sure the error I'm looking for is located in (or has to do with): DrawSnake(const, int, int)!

The logical error has nothing to do with DrawSnake function.
I'm starting to think perhaps it's how I have the instructions set up...
Both the AI and the "real" Snake share the same instruction vector - perhaps that's it?

EDIT: This is a link to the (extremely old and out-dated) "Snake" project (on D2JSP): http://forums.d2jsp.org/index.php?showtopic=32208514&f=120&st=0

This post was edited by Muted on Oct 7 2009 05:04pm
Member
Posts: 9,475
Joined: Mar 14 2005
Gold: 110.00
#2
Oct 7 2009 06:25pm
My C++ is really rusty, but what exactly is Crash doing? It looks like it's testing for a condition and also writing to the screen.. or something. I have a feeling this has something to do with TextControl.h (what is that?)
In CreatePath, there is a ton of copy and pasted code. Try to refactor this so you only have that repeated code block once. Repeating it obfuscates the logic and different between the conditions.
I'd suggest making one object hold the snakes position rather than two parallel arrays. I believe there some kind of data structures in C++ like Point<int, int> or Tuple<int, int> or something like that (as I said, my C++ is very rusty). Doing this will help keep from only adding an X and not adding a Y when you mean to add one point. It will also make it easier to copy a snake by adding a copy method to the snake object instead f doing it in place.

If I can get TextControl, I'll look at it some more.

This post was edited by llamaoo7 on Oct 7 2009 06:25pm
Member
Posts: 31,680
Joined: Nov 10 2007
Gold: 1.00
#3
Oct 7 2009 06:35pm
This has nothing to do with TextControl (that's just a header file I wrote - collection of "ASCII" stuff).
Crash() function returns "true" or "false" if a crash has occured on the given X, Y coordinates - the for loop runs through comparing all body parts to each other.
CreatePath() is the soul of the path creation (obviously), nothing more, nothing less.

This post was edited by Muted on Oct 7 2009 06:52pm
Member
Posts: 9,475
Joined: Mar 14 2005
Gold: 110.00
#4
Oct 7 2009 06:53pm
Quote (Muted @ Wed, 7 Oct 2009, 19:35)
This has nothing to do with TextControl (that's just a header file I wrote - collection of "ASCII" stuff).


I was asking about TextControl.h because I was interesting in actually debugging this.

Member
Posts: 31,680
Joined: Nov 10 2007
Gold: 1.00
#5
Oct 7 2009 06:58pm
Quote (llamaoo7 @ Wed, 7 Oct 2009, 19:53)
I was asking about TextControl.h because I was interesting in actually debugging this.


This has nothing to do with TextControl.
Member
Posts: 6,953
Joined: Sep 27 2003
Gold: 518.50
#6
Oct 7 2009 09:25pm
Quote (Muted @ Wed, Oct 7 2009, 07:58pm)
This has nothing to do with TextControl.

He wants to do test-driven debugging, wherein he tests his assertions about your project in code.
Member
Posts: 31,680
Joined: Nov 10 2007
Gold: 1.00
#7
Oct 7 2009 10:21pm
Quote (ASBands @ Wed, 7 Oct 2009, 22:25)
He wants to do test-driven debugging, wherein he tests his assertions about your project in code.


I'll put it this way, if you want to think about it like that:
SetColor is simply a "wrapper function" I wrote to easily change the colors, rather than calling four+ functions/variables everytime JUST to change it.
PlaceCursor is simply a "wrapper function" I also wrote, for the same reasons. If you want to see them, here they are (PS: I e-mailed him TextControl.h):
Code
void PlaceCursor(const int x, const int y) {

   HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

   COORD PlaceCursorHere;
   PlaceCursorHere.X = x;
   PlaceCursorHere.Y = y;

   SetConsoleCursorPosition(hConsole, PlaceCursorHere);
   return;
}


and

Code
void SetColor(const int foreground, const int background) {

   int Color = foreground + (background * 16);
   HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
   SetConsoleTextAttribute(hConsole, Color);

   return;
}


As you can see, they are not the cause of the logical error (or potential (automatic-"threading?") "glitch" as suggested by another person on another forum).
I've intentionally split the instruction vector (creating a duplicate) already, and it causes a lot of weird, unexpected behavoir, which is why I think the error lies therein.

I'm still working on finding exactly what's causing my problem. I'll more than likely do what I've done over a hundred times (literally) when making Snake.
I will disassemble the entire project (by creating a "new" and "blank" one), and integrate and fully test every little bit, and think about how the 'puzzle piece' fits.

Thank you for the support, help, etc.
I don't mean to be snotty, but I've been at this for over a year, and it's aggrivating.
Member
Posts: 9,475
Joined: Mar 14 2005
Gold: 110.00
#8
Oct 7 2009 10:36pm
The only reason why I asked for the code is so that I could exactly recreate your problem. I couldn't care less how any of those functions were implemented. I just wanted to reproduce the output you were seeing (this cuts debugging time down considerably).


I had a longer reply but I manged to loss it copying/pasting. But it boils down to this:

Can you write out your path finding algorithm is pseudo code (or a sequence of natural language statements)?
I don't really see the intention of it but it appears to be resolving a collision (state A) which puts in another state (B), in which makes it revert back to the original state (A), in turn causes it go back to the second state (B), etc...


To me, the correct solution to this problem is use a path finding algorithm such as A*. Here's a good description of it: http://www.policyalmanac.org/games/aStarTutorial.htm.

This post was edited by llamaoo7 on Oct 7 2009 10:37pm
Member
Posts: 31,680
Joined: Nov 10 2007
Gold: 1.00
#9
Oct 7 2009 10:51pm
Quote (llamaoo7 @ Wed, 7 Oct 2009, 23:36)
To me, the correct solution to this problem is use a path finding algorithm such as A*.  Here's a good description of it: http://www.policyalmanac.org/games/aStarTutorial.htm.


I've read God knows how many "tutorials" on the A* Algorithm, and quite frankly, I don't understand in the slightest how that would apply.
In one respect, I can see how it might fit. In another, I don't. Because it's not what I want, per se.
Member
Posts: 9,475
Joined: Mar 14 2005
Gold: 110.00
#10
Oct 7 2009 11:51pm
Quote (Muted @ Wed, 7 Oct 2009, 23:51)
I've read God knows how many "tutorials" on the A* Algorithm, and quite frankly, I don't understand in the slightest how that would apply.
In one respect, I can see how it might fit. In another, I don't. Because it's not what I want, per se.


It appears to be exactly what you need. You have a starting point, an end point, and you need a path. The different part about your situation is that your obstacle tends to move as you move along the path. (Think about how this could be handled after you understand A*.)
Go Back To Programming & Development Topic List
12Next
Add Reply New Topic New Poll

© 2003-2026 d2jsp  Contact