Hi everyone!

I'm creating this game where I need some pathfinding. Implementing the pathfinder itself is not really a problem, I intend to use some A*-ish approach.

My problem is that I'm not sure how to build the graph on which to run the A* search. My map is made up of a series of rectangles ("rooms") representing the floor. You can move freely across all these rectangles as long as there is no space between them. I could potentially create "portals" between these rooms, but I haven't done so yet.

My ideas so far:

1. Create a grid steching over the entire map and run the search on that. Seems fairly RAM and CPU intensive.

2. Manually place waypoints in editor. I would really like to avoid this if possible.

3. Procedurally finding waypoints by placing waypoints at corners and/or possibly at the center of each portal. The problem I see with this approach is that it would likely create very few waypoints, potentially resulting in ridiculous paths (zig-zag).


Any other ideas? Any ideas on how to improve any of my existing ideas? Any resources I should look up? Please note that I have very limited access to books atm and I would preferr to stay away from the more academic papers if possible.

"Generating NavMesh" are the google keywords you're looking for:

good discussion here:
http://www.gamedev.net/community/forums/topic.asp?topic_id=293929

It's a fairly complicated topic (which is why middle-ware vendors now exist in the games industry for this) but relatively straight forward to implement some of the more naive approaches.

-me