2 Replies Latest reply on Dec 4, 2009 8:27 PM by 843853

A* and Graph suggestions needed

First things first if you are unfamiliar with the A* algorithm here is a link to familiarize yourself.

[http://www.ai-center.com/publications/nareyek-acmqueue04.pdf]

I am looking for suggestions on how to implement a Graph in Java and the quickest or simplest way to initialize the graph for a Game zone given the following information: an image of the Zone map, and and array of information about location of objects in the zone (buildings, spawn points, zone lines, ect..).

In other words, how do I decide where to place vertexes (vertices) on the graph that will allow my NPCs to use the A* path-finding algorithm to navigate around objects on the map while chasing after the player?
• 1. Re: A* and Graph suggestions needed
I am working on an implementation of the a* algorithm in C for my final project in a C programming class. I also need to work the code into java for a game I am creating for fun. The C example is text based and isn't part of a game, so it is much simpler (well sort of. Minus the dynamic memory). Here is how I am doing it in C

``````#ifndef IMPORT

#define IMPORT 0

#include <stdio.h>
#include <stdlib.h>

//Constants
#define WIDTH 25
#define HEIGHT 25

//structs
typedef struct Node{
int x, y;
int count;
struct Node* *connects;
} node;

typedef struct Graph{
int map[WIDTH][HEIGHT];
int count;
node* vertices;
} graph;

//prototypes
graph* graphInit();
graph* graphDestroy(graph* g);
void printG(graph* g);

//definitions
graph* graphInit() {
graph* newGraph;
int i, k, t, x, y, size, count, choice;

newGraph = (graph*) malloc(sizeof(graph));

for (i =0; i < WIDTH; i++)
{
for (k = 0 ; k < HEIGHT; k++)
{
newGraph->map[k] = 0;
}
}

//prompt for number of nodes on map
printf("Enter the number of nodes: ");
do {
scanf("%d", &size);
} while (size < 0);

//initalize the vertex array of nodes
newGraph->count = size;
newGraph->vertices =(node*) malloc(sizeof(node) * size);

//get locations of all nodes on map
for (k = 0; k < size; k++)
{
do {
printf("Enter x for node %d: ", k);
scanf("%d", &x);
printf("Enter y for node %d: ", k);
scanf("%d", &y);
}while ( (x < 0 || x > WIDTH) &&
(y < 0 || y > HEIGHT) );

//put the nodes on the map
newGraph->vertices[k].x = x;
newGraph->vertices[k].y = y;
newGraph->map[x][y] = 1;
}

//get information on edges
for (k = 0; k < size; k++)
{
printf("The node at %d,%d connects to how many other nodes: ",
newGraph->vertices[k].x, newGraph->vertices[k].y);
scanf("%d", &count);

newGraph->vertices[k].count = count;
newGraph->vertices[k].connects = (node*) malloc(sizeof(node*)*count);

for (i = 0; i < count; i++)
{
printf("Select a connecting node: \n");
for (t = 0; t < size; t++)
{
if (t != k)
{
printf("%d. node at (%d,%d)\n", t,
newGraph->vertices[t].x, newGraph->vertices[t].y);
}
}
do{
scanf("%d", &choice);
}while (choice < 0 || choice > size || choice == k);
newGraph->vertices[k].connects[i] = &newGraph->vertices[choice];
}

}

return newGraph;
}

graph* graphDestroy(graph* g)
{
int i;

for (i = 0; i < g->count; i++)
{
free(g->vertices[i].connects);
}

free(g->vertices);
free(g);

return NULL;
}

void printG(graph* g)
{
int i,k;

for (i =0; i < WIDTH; i++)
{
for (k = 0 ; k < HEIGHT; k++)
{
if (k < WIDTH - 1)
{
printf("%d", g->map[k][i]);
}
else
{
printf("%d\n", g->map[k][i]);
}
}
}

for (i = 0; i < g->count; i++)
{
printf("%d: node at (%d,%d)\n", i,
g->vertices[i].x, g->vertices[i].y);
for (k = 0; k < g->vertices[i].count; k++)
{
printf("\tconnected to (%d,%d) \n",
g->vertices[i].connects[k]->x,
g->vertices[i].connects[k]->y);
}
}

}

#endif

int main() {

graph *g;

g = graphInit();

printG(g);

system("pause");
g = graphDestroy(g);
free(command);
return 0;
}
Sorry for the lack of comments but this code should be compilable and runnable.

I haven't gotten the A* algorithm started yet this code just creates the Graph.  Obviously its not a solution for my java game because the player can not be manually entering these way points (vertexes/ vertices whatever you want to call them) and defining the edges,  we all know that is just not how games work.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ``````
• 2. Re: A* and Graph suggestions needed
You may want to take a look at this post, it's a very good thread that talks about mazes, path weights, and A*: [Maze Question|http://forums.sun.com/thread.jspa?threadID=5319334] It includes some really great code.