Currently in order for the bots to walk round my city they go from waypoint to waypoint. These waypoints I've sort of pre calculated in that I moved the camera round my city after creating it and clicked the mouse to create a waypoint the position of which I stored to a way point file. Then on starting the game for real this file is read in and the waypoints connected up using a simply algorithm which can be summarised as:

loop for each waypt x
   loop for each waypt y
       if x, y closer than 30meters and not the same point
            if ray from x doesn't hit a building before reaching y
                connect x to y
            end if
        end if
   end loop
end loop  

So point x maybe connected to several other points. On doing the AI the bots simply run from waypoint to connected waypoint, on reaching a waypoint it calcs angle to required position and then chooses next waypt that has closest angle to this angle. I'm guessing this is a variation on the bump n turn idea for path finding. Is there another or more comon way of finding a waypoint without calculating them firstly? cheers

store them in a spatial tree and do a spherical query.

You might want to think about doing this calculation offline, before you run. Save out the graph and use it at runtime. Another option is to calculate it the first time the game runs, write the results out to a file, then use that file your next run. With a bit of time stamp checking, this could work.

This would allow you to do more fancy precomputation if you want. If your node count gets high, it may also help level load times.

To expand on the annons post, you might want to look at either a quadtree/octtree/kdtree to store your points. This could also be used by your AI at runtime to find the closest point to their location.

If your number of waypoints is low (and will stay that way), most of this may be overkill. :)

Pre-compute (offline) using Dijkstra's algorith, the lowest cost path (which will also be the shortest in a uniform cost space) between each pair of waypoints in the graph formed by deducing connectivity of waypoints. Save this data to a file. Load this data at initialisation of the game/level (rather than computing it on the fly) and whenever a bot needs to get from point A to point B, it's a simple lookup as to the sequence of waypoints required to get to the goal.

The downside of this approach is the storage cost. This is, of course, the eternal tradeoff one must make in pathfinding: computational time for online methods versus storage cost for offline methods.

Cheers,

Timkin

Thanks everyone,
when are the FAQs for this site going up - my question must have been asked many times before.