Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm designing a 2d RPG where you navigate on a overhead map. The terrain is mostly open with big parts of inaccessible terrain such as mountains and rivers. The player navigates short distances at a time by clicking/tapping where to go on the map.

I'm looking for a pathfinding algorithm for the navigation. Avoiding obstacles isn't the most important issue. I can see the game stopping the player when hitting an obstacle and leave it to the player to take another path. Although having it would be a bonus, e.g. when crossing bridges etc. it would be easier for the player if he just has to click on the other side and don't have to worry about bumping into walls.

The more important issue is the roads on the map, and I can see it being rather tedious for the player to constantly have to correct the path for staying on the road. As there are incentives to stay on the road such as walking faster and encountering less enemies - I want to make it easy for the player to stay on the roads. So navigation should gravitate to using roads, before going off-road. I also think the game will be more aesthetically pleasing if the navigation gravitates to using roads on the map.

Pathfinding is a new topic for me so I'm unsure where to begin. What is a good way to represent the terrain and roads? Should I use waypoints for the roads and what is a good algorithm for finding a good path that gravitates to using roads?

Thanks

share|improve this question
2  
A* will do all that for you. The algorithm will gravitate to the roads if their movement-cost is lower than other tiles. –  bummzack Feb 16 '13 at 14:14

1 Answer 1

up vote 4 down vote accepted

I would recommend to start reading about A* algorithm. It's one of the most commonly used pathfinding algorithms. For example, Wikipedia has a pretty good article on the topic. Here is an animated gif demonstrating the process:

demonstration of A* algorithm

share|improve this answer
    
Thanks I will read up on A*. –  Pking Feb 16 '13 at 15:47
    
The best A* article, plus illustrations is Amit's A* –  monkey Feb 16 '13 at 22:34
    
Here's the article I relied on when I implemented A* in AS3: policyalmanac.org/games/aStarTutorial.htm –  jhocking Feb 17 '13 at 1:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.