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

    A* and Graph suggestions needed

    843853
      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
          843853
          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

          Here is my Header
          #ifndef IMPORT
          
          #define IMPORT 0
          
          //headers
          #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
          Main()
          #include "graphHeader.h"

          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
            843853
            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.