Quote (ASBands @ Thu, 8 Oct 2009, 02:35)
A* is a graph-search algorithm that can be easily adapted for 2D graph traversal. It is one of the most helpful and applicable algorithms in all of computer science (not just 2D pathfinding as some believe)
I'm not saying A* algorithm is not proper for this "job." I'm well aware of its capabilities. There's plenty proof that it'd be extremely applicable in the case of Snake (this console-based game I've written).
Speaking of which, there's a rather interesting video of somebody who apparently won some tournie using Java, Mario Brothers, and the A* algorithm:
http://www.youtube.com/watch?v=qYluZRwrw9w&feature=relatedHowever! I've actually managed to find one of the major bugs that's been driving me crazy this entire time (past few months and extremely tonight). I haven't sat down eight hours straight like this since January.
Here's the final elimination of all logical bugs I've had in my AI program:
http://www.youtube.com/watch?v=R891r2NwENY - as you can see, he is
no longer moving angular or doing "arbitrary" behavoir.
The real Snake is finally following the AI Snake as it should! I'll be hopefully finding a way to tell him to avoid his body by either tonight, or tomorrow.
Here's the source code (current):
Code
#include <iostream>
#include <vector>
#include <TextControl.h>
using namespace std;
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
int FoodX = 0;
int FoodY = 0;
void CreatePath(int*, int*); // THE LOGIC ERROR LIES HERE
void RunPath(const int, int*, int*);
void SpawnFood(const int, const int);
void DrawSnake(const int, int*, int*, int);
bool Crash(const int*, const int*, const int);
vector<int>Instructions;
void CreatePath(int *SnakeX, int *SnakeY) {
Instructions.clear();
int TempX[100] = {'\0'};
int TempY[100] = {'\0'};
/* Copy Snake location */
for (int x = 0; x < 10; x++) {
TempX[x] = SnakeX[x];
TempY[x] = SnakeY[x];
}
while (TempX[0] != FoodX || TempY[0] != FoodY) {
if (FoodX > TempX[0]) {
Instructions.push_back(RIGHT);
TempX[0]++;
Sleep(50);
DrawSnake(RED, TempX, TempY, 10);
}
if (FoodX < TempX[0]) {
Instructions.push_back(LEFT);
TempX[0]--;
Sleep(50);
DrawSnake(RED, TempX, TempY, 10);
}
if (FoodY > TempY[0]) {
Instructions.push_back(DOWN);
TempY[0]++;
Sleep(50);
DrawSnake(RED, TempX, TempY, 10);
}
if (FoodY < TempY[0]) {
Instructions.push_back(UP);
TempY[0]--;
Sleep(50);
DrawSnake(RED, TempX, TempY, 10);
}
}
SetColor(CYAN, BLACK);
PlaceCursor(25, 0);
printf("AI PATH COMPLETED");
Sleep(500);
PlaceCursor(25, 0);
printf(" ");
return;
}
bool Crash(const int *SnakeX, const int *SnakeY, const int SnakeSize) {
for (int x = SnakeSize; x > 1; x--) {
if (SnakeX[0] == SnakeX[x] && SnakeY[0] == SnakeY[x]) {
PlaceCursor(SnakeX[x], SnakeY[x]);
SetColor(RED, BLACK);
printf("X");
PlaceCursor(0, 45);
SetColor(RED, BLACK);
printf("X: %d ", SnakeX[0]);
PlaceCursor(0, 46);
SetColor(RED, BLACK);
printf("Y: %d ", SnakeY[0]);
Sleep(50);
return true;
}
}
return false;
}
void RunPath(const int color, int *SnakeX, int *SnakeY, vector<int> Instructions) {
/* 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; // UP
case 1: SnakeY[0]++; break; // DOWN
case 2: SnakeX[0]--; break; // LEFT
case 3: SnakeX[0]++; break; // RIGHT
}
Sleep(50);
DrawSnake(color, SnakeX, SnakeY, 10);
if (Crash(SnakeX, SnakeY, 10)) { Sleep(250); }
}
}
return;
}
void DrawSnake(const int color, int *SnakeX, int *SnakeY, int SnakeSize) {
SetColor(color, BLACK);
for (int x = SnakeSize; x > 0; x--) { SnakeX[x] = SnakeX[x - 1]; SnakeY[x] = SnakeY[x - 1]; }
for (int x = SnakeSize; x > 0; x--) { PlaceCursor(SnakeX[x], SnakeY[x]); printf("*"); }
SetColor(GREEN, BLACK);
PlaceCursor(SnakeX[0], SnakeY[0]); printf("@");
// If his head, is NOT on his tail (specifically his "tail") - draw a black square
if (SnakeX[0] != SnakeX[SnakeSize] || SnakeY[0] != SnakeY[SnakeSize]) {
PlaceCursor(SnakeX[SnakeSize], SnakeY[SnakeSize]);
SetColor(BLACK, BLACK);
printf(" ");
}
PlaceCursor(0, 47);
SetColor(RED, BLACK);
printf("Snake's current size: ");
SetColor(WHITE, BLACK);
printf("%d", SnakeSize);
PlaceCursor(0, 48);
SetColor(WHITE, BLACK);
for (int x = SnakeSize; x > 0; x--) {
printf("[");
SetColor(CYAN, BLACK);
printf("%d", SnakeX[x]);
SetColor(WHITE, BLACK);
printf(",");
SetColor(GREEN, BLACK);
printf("%d", SnakeY[x]);
SetColor(WHITE, BLACK);
printf("] ");
}
return;
}
void SpawnFood(const int X, const int Y) {
FoodX = X;
FoodY = Y;
PlaceCursor(FoodX, FoodY);
SetColor(YELLOW, BLACK);
printf("x");
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));
int SnakeX[100] = {'\0'};
int SnakeY[100] = {'\0'};
/* Spawn point for the Snake */
SnakeX[0] = 35;
SnakeY[0] = 25;
SpawnFood(15, 15);
CreatePath(SnakeX, SnakeY);
RunPath(BLUE, SnakeX, SnakeY, Instructions);
SpawnFood(45, 15);
CreatePath(SnakeX, SnakeY);
RunPath(BLUE, SnakeX, SnakeY, Instructions);
cin.get();
return 0;
}
Thank you for the encouragement,
llamaoo7.
You have no idea how much you did just by taking a few minutes to actually look at my Pong game and change something...
Including showing an interest in the Snake game/AI. It's given me a tiny bit of hope that somebody actually cares other than me; Which gives me reason to actually work on it again.
I usually don't get so down and distraught but, I hate it when things I write suddenly go berserk and improper and just, shit hits the fan basically. Makes me really sad and nobody helps.
Everybody just says something general like "Go learn A*" or "A* will do this" and posts the same link I've read years ago, and aside from that, I've read many documentaries/posts/tutorials on A*.
I don't think I quite understand or at least remember the A* algorithm or any algorithm for that matter. The entire 'vector of instructions' idea, came from my AI book, and it works extremely well.
llamaoo7 Quote (llamaoo7 @ Thu, 8 Oct 2009, 00:51)
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*.)
Oh, and here's something for you to think about: Everybody learns differently.
Some people learn from stubbornness (trial & error). Some people learn from observing other people (seeing their errors, or perhaps mimicking their successes).
Me personally? I learn from trial & error mostly. But sometimes, I do need to learn from example (which is basically "observing" other peoples successes and mimicking them).
I can't solve this puzzle of Snake using the A* algorithm, because I don't understand the A* algorithm.
I do however, know what I've written. I also know what I've written in the past is successful.
I've slowly been building an AI that's more and more advanced everytime I compile it (insignificantly "improved," but improved non-the-less).
When he avoids his own body, and I get him to avoid other players bodies, I'll be happy and try this from an entirely different structure (the A* algorithm if possible).
There's one faint thing I can remember, and that's something about Djinn's A* algorithim, or something on the lines of that. It calculates every possible move and saves them all.
Anyways, thanks again!
This post was edited by Muted on Oct 8 2009 01:51am