Pathfinding

I want to put pathfinding in my game for the purpose of walking the character around, as well as to give NPC's some intelligence. The players pathfinding will be used for when the player wants to walk somewhere. The NPC pathfinding will be used for 'wandering' npcs. The other type of npc will be stationary. Other times when npc pathfinding will be used is when the npc is chasing or following the player.
There are heaps of online tutorials about pathfinding in games. A really good page on advanced AI and game programming topics is Amit's Page.
The page I mainly followed to learn pathfinding is this one: http://www.policyalmanac.org/games/aStarTutorial.htm. It has a fantastic visually represented tutorial on A* (A Star) Pathfinding. I recommend you read it if you're interested in learning.

However, whlist the above article is really informative, the implementation side of things is quite confusing. He provides an example in C, which is useful, but only if you have a firm grip on pointers and stacks. Now I've never done much work with stacks (not since experimenting with ASM years ago) so I had a bit of a hard time understanding his code. I did manage to integrate his code into my own, but it just didnt feel right. So I set out and made a more simplified (less efficient) version.
Rather than using a stack, or linked list for organising my nodes, I used a static array. The downfall of doing this is that each iteration its scanning the entire array, and not just the nodes in question. But for the purpose of an RPG where the map is small and its not real time, its fine.
I struggled for a bit to understand how to get an actual path from the nodes that are evaluated, but eventually worked it out.
Here is my inefficient code:

#include <stdio.h> #include <stdlib.h> #include "allegro.h" BITMAP *map; #define MAPW 16 #define MAPH 12 struct list_s { int x; int y; int f; } path[10000]; struct NODE { int walkable; int onopen; int onclosed; int g; int h; int f; int parentx; int parenty; } node[MAPW][MAPH]; int count; void initnodes() { int x,y; for (x=0;x<MAPW;x++) { for (y=0;y<MAPH;y++) { node[x][y].walkable = getpixel(map,x,y); node[x][y].onopen = FALSE; node[x][y].onclosed = FALSE; node[x][y].g = 0; node[x][y].h = 0; node[x][y].f = 0; node[x][y].parentx = 0; node[x][y].parenty = 0; } } } struct list_s *findpath(int startx, int starty, int endx, int endy) { int x=0,y=0; // for running through the nodes int dx,dy; // for the 8 squares adjacent to each node int cx=startx, cy=starty; int lowestf=10000; // start with the lowest being the highest // add starting node to open list node[startx][starty].onopen = TRUE; node[startx][starty].onclosed = FALSE; //////////////////////LOOP BEGINS HERE///////////////////////// while (cx!=endx || cy!=endy) { //look for lowest F cost node on open list - this becomes the current node lowestf=10000; for (x=0;x<MAPW;x++) { for (y=0;y<MAPH;y++) { node[x][y].f = node[x][y].g + node[x][y].h; if (node[x][y].onopen) { rect(screen,(x*40)+1,(y*40)+1,(x*40)+39,(y*40)+39,makecol(0,0,255)); if (node[x][y].f<lowestf) { cx = x; cy = y; lowestf = node[x][y].f; } } else if (node[x][y].onclosed) rect(screen,(x*40)+1,(y*40)+1,(x*40)+39,(y*40)+39,makecol(0,255,0)); } } // we found it, so now put that node on the closed list node[cx][cy].onopen = FALSE; node[cx][cy].onclosed = TRUE; // for each of the 8 adjacent node for (dx=-1;dx<=1;dx++) { for (dy=-1;dy<=1;dy++) { if ((dx!=0) || (dy!=0)) { if ((cx+dx)<MAPW && (cx+dx>-1) && (cy+dy)<MAPH && (cy+dy)>-1) { // if its walkable and not on the closed list if (node[cx+dx][cy+dy].walkable==0 && node[cx+dx][cy+dy].onclosed==FALSE) { //if its not on open list if (node[cx+dx][cy+dy].onopen==FALSE) { //add it to open list node[cx+dx][cy+dy].onopen = TRUE; node[cx+dx][cy+dy].onclosed = FALSE; //make the current node its parent node[cx+dx][cy+dy].parentx = cx; node[cx+dx][cy+dy].parenty = cy; //work out G if (dx!=0 && dy!=0) node[cx+dx][cy+dy].g = 14; // diagonals cost 14 else node[cx+dx][cy+dy].g = 10; // straights cost 10 //work out H //MANHATTAN METHOD node[cx+dx][cy+dy].h = (abs(endx-(cx+dx))+abs(endy-(cy+dy)))*10; node[cx+dx][cy+dy].f = node[cx+dx][cy+dy].g + node[cx+dx][cy+dy].h; textprintf_ex(screen,font,((cx+dx)*40)+2,((cy+dy)*40)+2, makecol(255,255,255),0,"%d",node[cx+dx][cy+dy].g); textprintf_ex(screen,font,((cx+dx)*40)+2,((cy+dy)*40)+12, makecol(255,255,255),0,"%d",node[cx+dx][cy+dy].h); textprintf_ex(screen,font,((cx+dx)*40)+2,((cy+dy)*40)+22, makecol(255,255,255),0,"%d",node[cx+dx][cy+dy].f); } //otherwise it is on the open list else if (node[cx+dx][cy+dy].onclosed==FALSE && node[cx+dx][cy+dy].onopen==TRUE) { if (dx==0 || dy==0) // if its not a diagonal { if (node[cx+dx][cy+dy].g==14) //and it was previously { node[cx+dx][cy+dy].g = 10; // straight score 10 //change its parent because its a shorter distance node[cx+dx][cy+dy].parentx = cx; node[cx+dx][cy+dy].parenty = cy; //recalc H node[cx+dx][cy+dy].h = (abs(endx-(cx+dx))+abs(endy-(cy+dy)))*10; //recalc F node[cx+dx][cy+dy].f = node[cx+dx][cy+dy].g + node[cx+dx][cy+dy].h; } } }//end else }// end if walkable and not on closed list } } } }//end for each 8 adjacent node }//end while //follow all the parents back to the start count=0; cx = endx; cy = endy; while (cx!=startx || cy!=starty) { path[count].x = node[cx][cy].parentx; path[count].y = node[cx][cy].parenty; path[count].f = node[cx][cy].f; cx = path[count].x; cy = path[count].y; count++; if (count>100) break; } return path; //we're done, return a pointer to the final path; }//end function int init() { //INITIALISE ALLEGRO printf("Starting Engine\nallegro_init()... "); if (allegro_init()) { allegro_message("Cannot initalize Allegro.\n"); return 1; } else printf("Success!\n"); //INITIALISE KEYBOARD printf("install_keyboard()... "); if (install_keyboard()) { allegro_message("Keyboard error.\n"); return 1; } else printf("Success!\n"); //INSTALL TIMER printf("install_timer()... "); if (install_timer()) { allegro_message("Cannot start timers.\n"); return 1; } else printf("Success!\n"); //START MOUSE printf("install_mouse()... "); if (install_mouse()==-1) { allegro_message("Cannot start mouse.\n"); return 1; } else printf("Success!\n"); //CHANGE GRAPHICS MODE set_color_depth(8); if (set_gfx_mode(GFX_AUTODETECT_WINDOWED, 640, 480, 0, 0)!=0) { printf("Cannot start graphics mode\n%s\n", allegro_error); return 1; } //START SOUND DRIVERS if (install_sound(DIGI_AUTODETECT, MIDI_NONE, NULL) != 0) { printf("Error initialising sound system\n%s\n", allegro_error); return 1; //CHANGE BACK TO 1 after DEBUG } //everything is okay, so return! return 0; } int main(int argc, char* argv[]) { srandom(time(0)); int i,x,y; //run the initialisation if (init()) { allegro_exit(); return 1; } map = load_bitmap("map.pcx",NULL); initnodes(); for (x=0;x<640;x+=40) { for (y=0;y<480;y+=40) { rect(screen,x,y,x+40,y+40,makecol(255,255,255)); if (node[x/40][y/40].walkable) rectfill(screen,x,y,x+40,y+40,makecol(255,255,255)); } } struct list_s *thepath = findpath(0,0,15,11); for (i=0;i<count-1;i++) { rect(screen,(thepath[i].x*40)+1,(thepath[i].y*40)+1, (thepath[i].x*40)+39,(thepath[i].y*40)+39,makecol(255,0,0)); line(screen,(thepath[i].x*40)+20,(thepath[i].y*40)+20, (thepath[i+1].x*40)+20,(thepath[i+1].y*40)+20,makecol(255,0,0)); } readkey(); if (set_gfx_mode(GFX_TEXT, 0, 0, 0, 0)!=0) { printf("Cannot start graphics mode\n%s\n", allegro_error); return 1; } allegro_exit(); return 0; } END_OF_MAIN()

I know I used MAPW and MAPH, but it only works at the ones I specified because I got lazy when testing it. It does work, and like I said its not the most efficient, but definitely easy to understand. I hope someone might get some use out of it, and let me know if you implement my method in your code!
Here is what the output looks like: