CodeWalrus

General => General Help & Troubleshooting => Topic started by: E37 on January 03, 2017, 07:22:36 PM

Title: Pathfinding
Post by: E37 on January 03, 2017, 07:22:36 PM
Hey!

I am working on a game and in my general worry-about-the-details-later programming style I ignored the fact that I was going to need to make a pathfinding algorithm. I have a couple ideas, but was wondering if there was any better ways of doing it. I am using a grid based world. It is never more than 50x50 tiles.

I could just brute force the best path, but I don't have a good way to check if the found path is the best one. Also storing the path once found could get large.

I may add waypoints so that the object can just move in a line form one to the next. This would be much smaller to store if the path has few turns but gets large if it winds.
I may add global waypoints to the map to help with navigation, especially with tricky areas.

Any thoughts?
Title: Re: Pathfinding
Post by: Yuki on January 04, 2017, 03:00:16 AM
As I heard, A* (https://en.wikipedia.org/wiki/A*_search_algorithm) is a good one and is commonly used in games. You might want to check that out.
Title: Re: Pathfinding
Post by: kotu on January 04, 2017, 03:05:26 AM
Yes A*.......... this explains it....... https://www.raywenderlich.com/4946/introduction-to-a-pathfinding (https://www.raywenderlich.com/4946/introduction-to-a-pathfinding)

I also just uploaded a C++ demo of it for PT_, but you can have the link as well. It's in C++, so obviously you will have to rewrite most of it, but having the code might help a little. If you run the .exe, left click AND right click on the map in the white area, to set start and end points. Then press the button. The important code is in mxPathFinder.cpp and mxPathFinder.h. Have fun

Here is the link... http://www.mediafire.com/file/r4hthvfxoc3i927/pathTest.zip (http://www.mediafire.com/file/r4hthvfxoc3i927/pathTest.zip)