3
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ A* will do all that for you. The algorithm will gravitate to the roads if their movement-cost is lower than other tiles. \$\endgroup\$ – bummzack Feb 16 '13 at 14:14
5
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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