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:

Game procedures

I'm almost at the stage where I've planned out a lot of stuff and studied a lot of techniques used when making 2d tile games. I really want to get stuck into coding, but I thought it would be a good idea to just map out some of the stuff in my head about how things will work. Below is some pseudo code I've come up with:

check if player clicked
if player single clicks in area do nothing
if player single click in interface then act accordingly (ie change action etc)
if player double-clicks:
 first check what action is current (ie talk, attack, pickup, walk)
 case talk:
  if its not an npc then do nothing
  if its an npc and its next to the player:
  initiate talking
 case attack:
  if its not an npc then do nothing
  if its an npc:
   if the npc is too far away (ie not next to the player) then do nothing
   else if the player has enough turn points:
    attack the npc
 case pickup:
  if its not an item then do nothing
  if it is an item:
   if the item is too far away (ie not next to the player) then do nothing
   else if the player has enough turn points:
    pickup the item
 case walk:
  set the point as the destination
  walk towards that area until points run out

if player finishes turn then update other game logic (ie move npcs etc)

update the graphics
draw the map
draw the objects (player, items, npcs, trees, etc)
draw the interface

Obviously, there is heaps missing, but I wanted to get the most important things sorted out. The new thing I've introduced here is that I've decided to make the game turn based. I want the player to remain relaxed and make informed decisions, rather than have an arcade frantic feel.

File formats and scripting - XML

I think I want to use XML to create the quests and bulk of the game. I wrote up a basic idea of what I think an xml file for the game would look like.

<game>

<quest type=" ">
 <id>  </id>
 <title>   </title>
 <description>  </description>
 <incomplete>  </incomplete>
 <complete>  </complete>
 <failure>  </failure>
 <npcid>  </npcid>
 <solution>
  <killnpcid>  </killnpcid>
  <finditemid>  </finditemid>
  <savenpcid>  </savenpcid>
 </solution>
 <reward>
  <giveitemid>  </giveitemid>
 </reward>
</quest>

<npc x=" " y=" ">
 <id>  </id>
 <name>  </name>
 <sprite>  </sprite>
 <avatar>  </avatar>
 <talk>  </talk>
 <alignment>  </alignment>
 <movement>  </movement>
 <health>  </health>
 <inventory>
  <itemid>  </itemid>
  <itemid>  </itemid>
 </inventory>
</npc>

<item x=" " y=" ">
 <id>  </id>
 <type>  </type>
 <name>  </name>
 <sprite>  </sprite>
 <description>  </description>
 <quantity>  </quantity>
 <damage>  </damage>
 <heal>  </heal>
</item>

</game>

After some searching, it seemed that TinyXML was the most popular for games. But alas, I am coding in C, not C++ so I couldnt really use it. I looked around a bit more and found ezXML. Its written in C and its very easy to use. I loaded it up and got it working straight away. I wrote an app that reads in the file and counts how many there are of each type. It then allocates memory to store each in a structure and loads them in.

Tile transitions

After reading http://www.gamedev.net/reference/articles/article934.asp i was utterly confused. I knew what I had to do; just not how to do it.

The answer was in this picture:

From the above article it states that each in order has an equivalent binary value. IE the first one is 0(blank), 1, 2, 3, and so on up to 15. But because we want to store all these in a single byte, the second row starts at 0(blank) and goes up by 16. IE 0,16,32,48,64...etc

Now that we know this, we know that each tile can have a single byte that represents its transition overlays. When we create a new tile type, we add to the 8 surrounding tiles to create their transition value. What do we add? Well, by drawing a 3x3 grid on a piece of paper I started with 0 in the middle - a blank tile. Starting in the upper left I checked each against the list in the picture above. So the corresponding upper left tile in the list above is row 2 tile 4 (starting at 0) . Because its on the second row, and we're storing it all in one byte, we shift the value left 4 bits.

So going through each one starting at the upper left, moving across to middle top, upper right, etc, we get 64,8,128,1,16,2,32 and 4.

Now when we place down our tile, we add those values to the surrounding tiles' existing transition values.

How to draw the transitions

We have a transition value for each tile created by going through the base tile type and adding to the transition value as above.

The general algorithm for each tile is as follows: 1. We do the corner layer first. Take the transition value and shift it right 4 bits. This lets us only work with the upper 4 bits. ie T = T>>4

2. From the list of corner tile overlays, look up the corresponding T value and draw the tile.

3. After placing all the corner layer, move on to the transition value for the sides layer. Instead of shifting right 4 bits, we want to AND the value with 15 (binary 00001111) to give us only the lower 4 bits. ie T = T&15

4. From the list of side tile overlays, look up the corresponding T value and draw this layer over the previous. It is important to draw the side layer second because in cases where a tile would use both corner and sides, we dont want corner pieces to be drawn on top of side pieces.

And thats it, really. What if you have more than two tile types (ie something other than just grass and water)? Well, all you need to do is have a T value for each different type of transition. IE a T value for Water to Grass, a T Value for Hill to Grass, etc. You only need a one transition of each direction for each tile type. That is, you dont need a type for Hill to Water, because Grass takes precendence over Water and Hill over Grass. The images in the tutorial that I mentioned earlier explain it pretty well.

The Plan

The key to any successful project I believe is having a good plan.

There are a few key decisions that have to be made early on in the project, or nothing can be done. Here are a few things to think about:

Tile Engine
At first I had this idea of going completely isometric, I even made up a simple engine that displayed an isometric map on the screen, complete with scrolling. But then I remembered - I'm only a beginner. I was bound to run into problems that I couldnt solve easily.


The isometric engine I started. This was actually the editor. The line through the middle was a few road tiles.

So take 2, I restarted my engine and did it in flat tiles, at a resolution of 320x240. It was looking good, and I was getting somewhere. But I started running into problems because my tile size was too big - 40x40 pixels - way too big for such a low resolution.


The second attempt at an engine. By now I had learnt a lot, but it still wasnt quite right. The graphics by the way, were from a talented guy I found with google, at http://lostgarden.com/2006/07/more-free-game-graphics.html

Finally I have decided to settle on 640x480 with a tile size of 32x32. A tile size of 32x32 will come in handy for multiple reasons:

1. 32 is a multiple of both 640 and 480.
2. 32 is a power of 2. This will make bit-wise operations easier, thus making optimisation faster.
3. It is a nice size that allows for a significant amount of graphic detail without having to create a great amount of tiles.

Screen Resolution and Colour Depth

In addition to reasons above, there arent so many good reasons to go 640x480 as there are to not. Most games of today run at 800x600 or higher, with 32-bit colour. These games usually use DirectX or OpenGL and have a splendor of 3d graphics. However our game doesnt use those technologies. Because of our game's simplicity, we will stick to 640x480. Most other games similar to ours from that era were also 640x480.

The next question is - 8,15,16,24 or 32-bit colour?

Whilst most games of the day were 8-bit, I have decided to go for 32-bit. I originally started my earlier engines in 8-bit but found whilst I didnt run into any problems, I kept finding myself having to re-create a new palette for the game every time I added some new graphics. Some might say that I should start with a palette and stick to it, but to put it simply, laziness has won me over. 32-bit will be easier to code and to draw.

Introduction

For many years, I had a dream of creating my own computer adventure games. I followed this for a long while, learning to program, and eventually having a crack at AGI game making.

However, after a couple of years of tinkering with the AGI interpreter, I played a game called 'Solar Winds'. Long before the popularity of MMORPG's I had an idea. I thought wouldnt Solar Winds be awesome if you could play it online against other players? It would be a space trading type game online.

I set out to create my own version. I Called it 'SpaceM' and actually had a working prototype for a short while, around 1998. By 2001 however I had begun an interest in other things, including that which doesnt involve a computer.

So now, in 2009 I have the time again (for the most part) to restart my interests in programming. I have scrapped the idea of a space trading game and have gone back to basics, to hone my skills and create an RPG.

The blog
Keep coming back to this site for the progress on the RPG, and the obstacles I run into.