Question: Path finding algorithm
BlitzPlus Forums/BlitzPlus Programming/Question: Path finding algorithm
| ||
| Hi All, I'm working on a game, and got to the point where I'm looking for a way for the main sprite to find its own way to a certain point on a map, evading obstacles. (e.g. click on a location, and the main guy automatically walks over there) Now, these won't be extremely complicated mazes, but there will be occasional (odd shaped) objects in in the way between the origin and destination locations. I have a walk-map stored in either an array or a memorybank, which contains a rasterized version of the map with either walkable or non-walkable locations. (Just 1's and 0's) The problem is coming up with a *smart* (or at least half-way decent) algorithm that enables the program to detect the most efficient path, and not take huge detours/dead ends before arriving on the destination point. The optimal path can be returned in another string, array or bank, to be followed by the actual moving/drawing routines Does anyone happen to have any functions that can assist here, or can point me to some resources/tutorials that explain how to implement and write something like this? |
| ||
| Check out A* pathfinding (pronounced A-star). |
| ||
| Thanks! I did some more searching after posting the message above, and ran into some info on the A* algorithm a little bit ago. Best of all, I was just whipped up some blitz code to actually make it work! :-) I'm using two arrays now: one to hold the map info, and another one to store the A* path information. Works like a charm! |
| ||
| Try this: http://www.blitzcoder.com/cgi-bin/articles/show_article.pl?f=turtle177610292002201622.html It's great, and made with Blitz! |
   |