So I've implemented a decent version of the A* algorithm, it's working an all. But I have two concerns/questions, looking at the little "grid" below in the code box, where each O is a node, S is the start, T is the target and 1-7 are the nodes found for the path.


OOOOOOOOOOOOO
OSOOOOOOOOOOO
OO1OOOOOOOOOO
OOO2OOOOOOOOO
OOOO3OOOOOOOO
OOOOO4567TOOO
OOOOOOOOOOOOO


1. Currently my A* implementation spits out one waypoint for each node, which is far from ideal as in the example above there is one waypoint at S and 1, 2 and 3, etc. all the way down to 7 and T, when all I really need is a waypoint at S, 4 and T. How do I go about to reduce the amount of waypoints?
2. Smoothing, this has probably been asked a million times but can someone point me in the direction of a nice introduction to smoothing the path?
3. Also, assuming a path like the one in the code above, since my units don't really move on a grid the straightest path is really from S to T in a line, how is this achieved?

Place "waypoint" nodes; search the map for entries to passages, and as such place nodes near corners. You can on your map approximate a voronoi diagram with passable-levels, where each cell center is a node. There was an article here on gamedev about pathfinding not too long ago, that explained it.

Note: key points of interest such as a chat/melee combat range away from another character, or the target/clicked position are also nodes. Unpassable materials are not a must.

To your second opinion, loose the nodes/tile thing, and place nodes relative to the geometry in your map. If the blocking geometry follows the tiles, the result would represent that, but the lines between the nodes would still be straight. Move actors on the scene along a vector being node2-node1 normalized.

Hope this helps, ask again if I'm not being clear enough. ;-)

Sounds like you might be best served by using a navigation mesh, if you have comparatively large swaths of open ground where agents should be able to move freely.

Sounds like you might be best served by using a navigation mesh, if you have comparatively large swaths of open ground where agents should be able to move freely.

I believe you might be correct, is there any good reference material and/or reference implementations available for navigation meshes? I'm looking for something like what this: http://www.policyalmanac.org/games/aStarTutorial.htm is for grid based A*