More on Pathfinding

After re-reading my previous code, I have realised that there are a few things that can be done to optimise the code, whilst still keeping the same method of static arrays.

1. The Struct list_s could be made to a typedef, and *path declared only inside the findpath function, eliminating the need for the initnodes() function.
2. node.onopen and node.onclosed could become one variable of either TRUE, FALSE, or NULL.
3. There's no need to keep the f value on the list.
4. The instances of 40 need to be replaced with a constant tilesize or even tilew and tileh.
5. The map and its associated dimensions could all be passed to the findpath function.
6. Some error checking needs to be included, such as what if there is no possible path? At the same time, some checks already included might be able to be removed.

Also sorry if the code is a bit hard to read, it looks great in code::blocks, but the width of the blog restricts it. If you're having trouble, copy and paste it into your editor and it'll be a lot easier. When I get the chance I'll go and edit it to be easier to read.

Oh yeah, and on a side note, I've noticed that the code syntax highlighter I'm using (http://www.dreamprojections.com/syntaxhighlighter) doesnt seem to work properly in Firefox for Ubuntu. I'm not sure if its working in other firefoxes (such as windows) but it does work in Internet Explorer, which is what I'm using most of the time (I know - dont ask!).

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: