I have an implementation in AS3 that I wrote just last week. I haven't put in on github etc because it's integrated into the rest of the codebase, but it works pretty well. Let me know if you want a copy to pull out pieces from (e.g. priority queue) or whatever.

My version works OK for what I need to do.  If you ported it to C/C++ I would try it, though. 

Orz, just fyi, this doesn't look like A*, more like a flood fill algorithm.
(Fun fact: most of the magic of A* is in using the priority queue for the open set. If you use the same algorithm but use a regular queue, you get breadth-first search. If you implement open set using a stack, you get depth-first search.)

Yeah, it's not actually A*.  There is really nothing out there with a nice clean API, so this will have to do.  I actually tried writing a version with a priority queue earlier, but it was taking too long.

Try reversing your priority queue for fun effects. I once did that by accident, and watched in amazement as my enemies took the longest possible valid path to get to me.

I might actually try this later.  I am using the pathfinder to set up random race routes through a city, so I don't really want the shortest path. 

Should work, I guess.

Yeah, there was one typo but I dropped it right in as a replacement and it does work.  Thanks very much!

I started using C++ for ease of porting & distribution, and more 3rd-party libraries.  So far I'm very satisfied.  I don't think it's the best language for developing all games, but there are some times when nothing else really will do the job.

Maybe we just have similar personalities, but I thought the best guide was "Learn C the hard way" by Zed Shaw (http://c.learncodethehardway.org/book/).  It doesn't cover the features added by C++, but those are not the hardest features to learn anyway.  Since I came from Java & AS3, I also found useful a guide by Cay Horstmann on moving from Java to C++ (http://horstmann.com/ccj2/ccjapp3.html).

Thanks to everyone for the suggestions.  Here's another alternative: I've ported a class I used in AS3 to C++ (which actually has very similar syntax).  It stores map data as an STL map of points to passability values (in this case, 0 or 1 for open or blocked, respectively).  The intended usage is: create the object, load map data, and call "pathfinder->findPath(start, end);".

Code:

#include <set>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>

int map[20][20] = {
// 2nd index
//  0001020304050607080910111213141516171819 //1st index
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},   // 00
{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},   // 01
{0,1,1,0,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,0},   // 02
{0,1,1,0,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,0},   // 03
{0,1,0,0,0,0,1,1,0,1,0,1,0,0,0,0,1,1,0,0},   // 04
{0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0},   // 05
{0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0},   // 06
{0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,0},   // 07
{0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},   // 08
{0,1,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0},   // 09
{0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0},   // 10
{0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,0,0,0},   // 11
{0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,0},   // 12
{0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,0},   // 13
{0,1,0,0,0,0,1,1,0,1,0,1,0,0,0,0,1,1,0,0},   // 14
{0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0},   // 15
{0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0},   // 16
{0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,1,1},   // 17
{0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},   // 18
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}   //  19

};


class Pathfinder{
public:

class Point{
public:
int x,y,z;
Point(int xValue=0, int yValue=0, int zValue=0){
x=xValue;
y=yValue;
z=zValue;
}

bool operator < ( const Point &other) const {

if(x<other.x) return true;
if(x>other.x) return false;

if(y<other.y) return true;
if(y>other.y) return false;

if(z<other.z) return true;
if(z>other.z) return false;
return false;
}
};

int width, height;
bool
diagonal=false, //Whether to consider diagonal moves.
wraparound=false; //Whether to allow moving off the map and on to the other side (as in Pac-man).

std::map<Point, int>  * nodes; //Map of coordinates to blocked status
std::map<Point, int>  * open; //Un-traversed squares
std::set<Point> * closed; //Traversed squares
std::vector<Point> path; //Stores the latest path

// Returns a list of the given point's surrounding points.
std::vector<Point> neighborhood(Point point){
std::vector<Point> result;
for(int i=-1; i<2; i++){
for(int j=-1; j<2; j++){

if (!diagonal && (abs(i) == abs(j))) continue; //Skip diagonals

if(wraparound){
if (i < 0) i += width;
if (i >= width) i -= width;
if (j < 0) j += height;
if (j >= height) j -= height;
}

result.push_back(Point( point.x+i,point.y+j,0));
}
}
return result;
}

//Check that the given point is inside the pathfinding area
bool inBounds(Point point){
return (
point.x >=0 && point.x < width &&
point.y >=0 && point.y < height
);
}

//Returns the index of the best path of all valid paths.
int bestPath(int iteration=1){
std::vector<Point> neighbors;
std::set<Point>::iterator it;
std::set<Point> * newClosed = new std::set<Point>;

for(it=closed->begin(); it != closed->end(); it++){
neighbors=neighborhood(*it);
for(int i=0; i< neighbors.size(); i++){
Point neighbor = neighbors[i];

if(inBounds(neighbor) && (*open)[neighbor] == -1) return iteration;

if(inBounds(neighbor) &&
(*open)[neighbor] == 0 &&
(*nodes)[neighbor] !=1
){
(*open)[neighbor]=iteration +1;
newClosed->insert(neighbor);
}
}
}

if(iteration > (width * height)) return iteration;

delete closed;
closed = newClosed;

iteration=bestPath(iteration+1);
return iteration;
}

// Returns an array of path points for the given location and iteration.
std::vector<Point> pathArray(Point point, int iteration){
if(iteration==0){
std::reverse(path.begin(), path.end());
return path;
}


std::vector<Point> neighbors = neighborhood(point);
for(int i=0; i<neighbors.size(); i++){

Point neighbor=neighbors[i];

if(inBounds(neighbor) && (*open)[neighbor]==iteration){
path.push_back(neighbor);
return pathArray(neighbor, iteration-1);
}
}
std::vector<Point> result;
return result;
}

// Returns an array of path points for the given start and end points.
std::vector<Point> findPath(Point start, Point end){

//Create empty path. Return empty path if...
std::vector<Point> result;
//Map not loaded
if(nodes==nullptr) return result;

//End point blocked
if((*nodes)[end]==1) return result;

//End is same as start
if (start.x == end.x && start.y == end.y){
result.push_back(start);
return result;
}

//Store start & end coordinates with lowest & highest passability, respectively
open->clear();
(*open)[start]=1;
(*open)[end]=-1;

//Create a set of closed nodes and add start to it
closed->clear();
closed->insert(start);

result=pathArray(end, bestPath());
if (result.size() > 0) result.push_back(end);
return result;
}

Pathfinder(int w, int h){
width=w;
height=h;
nodes = new std::map<Point, int>;
open = new std::map<Point, int>;
closed = new std::set<Point>;
}

~Pathfinder(void){
delete nodes;
delete open;
delete closed;
}
};

int main(int argc, char** argv){
//Create new pathfinder
Pathfinder * pathfinder = new Pathfinder(20,20);

//Loop through the map array and insert all coordinates into pathfinder's STL map
for(int i=0; i < pathfinder->width; i++){
for(int j=0; j < pathfinder->height; j++){
pathfinder->nodes->insert(
std::pair<Pathfinder::Point, int>(
Pathfinder::Point(i,j),
map[j][i]
)
);
}
}

//Find path
std::vector<Pathfinder::Point> path = pathfinder->findPath(Pathfinder::Point(0,0), Pathfinder::Point(5,5));

//Print out coordinates in path
for(int i=0; i< path.size(); i++){
printf("%d, %d, %d\n", path[i].x,path[i].y,path[i].z);
}

return 0;
}

It includes its own point class, which you can replace with your favorite.  Comments are light because I got the algorithm a long time ago and I don't even understand some parts of it.  Map data is stored on the heap, while path data is passed around by value.  There is a recursive function which I don't check for recursion level, so it may cause a stack overflow with big maps.  I'm kind of guessing here because I just started using C++.

Strongly recommend you don't use that definition (which requires a height and width).

Your method works too, thanks.

You might want std::unordered_map instead if you have C++11 available.

A hashmap would be more appropriate here because order of keys isn't as important as access time.  I just couldn't figure out how to write a hash function for my point class.  You wouldn't happen to know any examples, would you?

Hooray, that did it!  I suspected I had screwed up the comparator, but couldn't think of a better way to do it.  Thanks a million.

I will eventually need to use the third dimension.  In that case, I assume the comparator will be:

Code:

bool operator < ( const ASPoint &other) const {
return ((z*width*height)+(y*width)+x < (other.z*width*height)+(other.y*width)+other.x)
}

...correct me if I'm wrong.

I'm used to storing tile maps as a hashmap of 3D coordinates to tiles.  For example "tile[(3,7,12)]=jukebox".  I'm trying to port some of my code to c++ and am getting stuck with the STL map structure. 

The code sample below declares a 2D array of tile codes, a point class (with its own < comparator), then fills an STL map with what should be 400 tile values.  However, I consistently get 59 back when I iterate over it, even though calling "map.size()" gives me the correct value of 400.  Seems like this should be a common mistake...any suggestions?

Code:

#include <map>
#include <stdio.h>

const int width=20, height=20;
float tilemap[width][height] =
{
// 2nd index
//  0001020304050607080910111213141516171819 //1st index
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},   // 00
{1,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,1},   // 01
{1,9,9,1,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1},   // 02
{1,9,9,1,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1},   // 03
{1,9,1,1,1,1,9,9,1,9,1,9,1,1,1,1,9,9,1,1},   // 04
{1,9,1,1,9,1,1,1,1,9,1,1,1,1,9,1,1,1,1,1},   // 05
{1,9,9,9,9,1,1,1,1,1,1,9,9,9,9,1,1,1,1,1},   // 06
{1,9,9,9,9,9,9,9,9,1,1,1,9,9,9,9,9,9,9,1},   // 07
{1,9,1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1,1},   // 08
{1,9,1,9,9,9,9,9,9,9,1,1,9,9,9,9,9,9,9,1},   // 09
{1,9,1,1,1,1,9,1,1,9,1,1,1,1,1,1,1,1,1,1},   // 10
{1,9,9,9,9,9,1,9,1,9,1,9,9,9,9,9,1,1,1,1},   // 11
{1,9,1,9,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1},   // 12
{1,9,1,9,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1},   // 13
{1,9,1,1,1,1,9,9,1,9,1,9,1,1,1,1,9,9,1,1},   // 14
{1,9,1,1,9,1,1,1,1,9,1,1,1,1,9,1,1,1,1,1},   // 15
{1,9,9,9,9,1,1,1,1,1,1,9,9,9,9,1,1,1,1,1},   // 16
{1,1,9,9,9,9,9,9,9,1,1,1,9,9,9,1,9,9,9,9},   // 17
{1,9,1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1,1},   // 18
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}   // 19

};


class ASPoint{
public:
int x,y,z;
ASPoint(int xValue=0, int yValue=0, int zValue=0){
x=xValue;
y=yValue;
z=zValue;
}

bool operator < ( const ASPoint &other) const {
return ((x < other.x) || (y < other.y) || (z < other.z));
}
};


int main(int argc, char** argv){

//Fill STL map with contents of tile map
std::map<ASPoint, float> m;
for(int i=0; i<20; i++){
for(int j=0; j<20; j++){
m[ASPoint(i,j)]=tilemap[i][j];
}
}

//Iterate through STL map and print each value
std::map<ASPoint, float>::iterator it;
int totalPoints=0;
for(it=m.begin(); it != m.end(); it++){
totalPoints++;
printf("%f\n",it->second);
}

printf("Total points: %d Size: %d\n", totalPoints, m.size());
return 0;
}

Can anyone suggest a good A* pathfinding library/snippet in C++?  I've found surprisingly few examples by googling, and they all seem a bit sketchy.

I am adding tweening to my (C++) 3D engine.  The basic structure is based on Flashpunk, i.e. each entity has an array of tweens which are applied before its update() method.  HOWEVER...since I'm not using AS3 or Java, I can replace whole object hierarchies of tweens with a simple "Tween(float * value, function)".  The provided function updates the value pointed to by the provided pointer, which can be a color value, vector element, or anything.  Awesome!

I have been using Bullet for physics.  It's well maintained and fairly bug-free, but holy shit, what a mess.  I'm stuck with it for now, but in the future I'd really like to use something more well-written.  Recently I discovered JigLib (http://www.rowlhouse.co.uk/jiglib/) , which looks clean but appears to be used mostly through its AS3 interface.  Has anyone had experience with it that they could share?

I am switching jobs right now, and I want to move somewhere that I can hang out with other game developers. 

I'll get a programming job to keep me in practice and bankroll my hobby, but I don't need a job in the game industry, and I don't want to start a business right now.  I'd just like to have a lot of other game developers around for mutual support and inspiration.  What are some good regions for that?  I'm a US citizen, but I've lived overseas before, so I'd consider other countries as well.

Bumping this back from the grave with some new screenshots.  It's been a couple months, and in the interim I've learned C++ and started porting the game over. 

I'm going to build my own engine, because an existing engine is overkill for what I want to do.  Plus, using C++ makes it easier to piece together an engine from someone else's existing code, which I intend to do at every opportunity.

Here's a motorbike pushing around some dynamic box objects:





Here's a simple "city" made of models stuck together.  If you drop an .obj file into the asset folder, the game automatically loads it on startup, makes a mesh and collision shape out of it, and makes it available for building.  You can build the city by sticking geometry onto existing geometry.





Here's a more refined version where you can see multiple meshes, meshes snapped to the grid, and a 3D "cursor" that shows where new blocks will be added.  There's also a skybox added in this shot.

Thanks, the depth test is what was causing the intersection with world geometry.  I had to tweak a couple more things, but here's what I ended up with.

Code:

void render(void){
update();

glMatrixMode( GL_PROJECTION ); ///Go to projection mode to set up camera
glLoadIdentity();
cam->aspect = ((GLfloat)screenWidth / (GLfloat)screenHeight);
gluPerspective( cam->fov, cam->aspect, cam->near, cam->far );

glViewport( 0, 0, screenWidth, screenHeight );

glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT ); //Wipe screen

glMatrixMode( GL_MODELVIEW );
glLoadIdentity();

glMultMatrixf(value_ptr(lookAt(*cam->position, (*cam->position+*cam->direction), UP_VECTOR)));
cam->update();

drawAxes();
world -> render();

///Render HUD
glDisable(GL_DEPTH_TEST);
    glMatrixMode( GL_PROJECTION );
    glPushMatrix();
        glLoadIdentity();
        glOrtho( -1.0f, 1.0f, -1.0f, 1.0f, -1.0f, 1.0f );

        glMatrixMode( GL_MODELVIEW );

        glPushMatrix();
            glLoadIdentity();
hud->render();
        glPopMatrix();

    glMatrixMode( GL_PROJECTION );
    glPopMatrix();

glEnable(GL_DEPTH_TEST);

glutSwapBuffers(); //Flip to next frame
}

I'm starting to work on the score display and HUD for my game.  Here's what my render loop looks like so far.  I render the HUD first, before any transformations are applied to the scene, so anything in the HUD is always directly in front of the camera.  Of course, this means that the HUD graphics are in world space and can intersect with the world's geometry if they get too close. 

Code:

void render(void){
update();

glViewport( 0, 0, screenWidth, screenHeight );

glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT ); //Wipe screen


glMatrixMode( GL_PROJECTION ); ///Go to projection mode to set up camera
glLoadIdentity();

cam->aspect = ((GLfloat)screenWidth / (GLfloat)screenHeight);

gluPerspective( cam->fov, cam->aspect, cam->near, cam->far );
       
        hud->render();

glMultMatrixf(value_ptr(lookAt(*cam->position, (*cam->position+*cam->direction), UP_VECTOR)));


glMatrixMode( GL_MODELVIEW );
glLoadIdentity();
drawAxes();
world -> render();

glutSwapBuffers(); //Flip to next frame
}

What I really need to do is render the HUD after the world, in such a way that it overwrites anything rendered so far.  I've looked at tutorials for a while, but I think I am missing some basic OpenGL concepts.  Any suggestions?

Ben_Hurr, one thing I found helpful was to look at frameworks and libraries I enjoyed using before, and copy the way they did things.  I am basing the API of my 3D engine on the Flashpunk API because I found it very intuitive.

[EDIT]

Memset clear the arrays at the end of the frame?

Perfect - I am new to C++ so I knew there was something I was missing.

Have you checked out glfw? I think it does almost the same as glut, but it handles in much more pleasant way.

Yeah, I was actually using GLFW previously and noticed that, but there are a lot more tutorials and libraries for GLUT.

EDIT: Upon further inspection, it looks like I just forgot to register one of the callbacks. 

I'm using GLUT to detect keyboard input in my game.  To do this, I have to write 2 separate callbacks, one for ASCII keys (which can be represented by a char) and one for "special" keys which must be represented by an int.  I don't handle input directly in these callbacks, but use them to update several arrays that store key state. "keyDown" is true as long as the key is held down; "keyPressed" is true only if the key was up during the last frame.

Code:

void onKeypress(unsigned char key, int x, int y) {
if(!keyDown[key]){
keyPressed[key]=true;
keyDown[key]=true;
}
}

void onSpecialKeypress(int key, int x, int y){
if(!specialKeyDown[key]){
specialKeyPressed[key]=true;
specialKeyDown[key]=true;
}
}

At the end of every frame, I set all the "keyPressed" values to false.  This is working for the ASCII keys, but not for the special keys.  I think this is because I am not hitting all of the possible key values when I set them false (even though the two variables in my loop are the lowest and highest defined values). 

Code:

for(char i=CHAR_MIN; i<CHAR_MAX; i++){
keyPressed[i] = false;
keyReleased[i] = false;
}

for(int i=GLUT_KEY_F1; i<GLUT_KEY_INSERT; i++){
specialKeyPressed[i] = false;
specialKeyReleased[i]=false;
}

I can't iterate over every possible value of an int, so what are my options?  Using a map<int, boolean>, maybe?  Would appreciate any suggestions.

Sorry to spam the board, but that last post reminded me of something.  How are people storing the transform data for their game entities?  I'm using GLM, so I started out with something like this:

Code:

class Entity{
    public: mat4x4 transform;
}

But I soon found out that rounding errors accumulate over time and spill over into other attributes: for example, a spinning tire wobbles and expands to the size of a house within seconds.  So I did something like this:

Code:

class Entity{
    public: float x,y,z,  h,p,r;
    
}

I store the attributes separately and update the matrix every frame.  Now the values are rock solid, but it's kind of a hassle to add arbitrary transformations, like if I want to strafe left and right by adding a sideways vector.

I'm still coming to grips with matrices (as you can probably tell), so I may stumble onto the solution, but it seems like someone must have solved this before.

First learn OGL 3.0/2.1, then make abstract layer for 1.0. This way you don't have to 'unlearn' things.

That sounds like a great idea - any examples?  Basically, I want the game to run if someone starts it on a old/cheap computer.  If it checks for programmable shaders, finds none, and falls back to an older rendering pipeline, that's fine too.  There are still lots of laptops out there with Intel integrated video that doesn't support shaders.